C# - Algoritmos de ordenação - III

 Hoje vamos continuar apresentando os algoritmos de ordenação usando a linguagem C#.

Continuando o artigo anterior vamos tratar agora do algoritmo de ordenação Selection Sort.

Ordenação com Selection Sort

O algoritmo de ordenação Selection Sort usa o método de ordenação por seleção percorrendo o array em busca do menor valor e movendo para a posição correta precedido pelo elemento de menor valor, ou seja, ele passa sempre o menor valor do array para a primeira posição, depois o segundo menor valor para a segunda posição e assim por diante.

O número de operações necessárias usadas no Selecion Sort pode ser obtido pela fórmula:  n * ( n-1) / 2

Para análise assintótica, podemos ignorar os valores constantes, e o que importa é o valor n² / 2 , pois conforme a lista cresce, este valor vai aumentar quadraticamente.

Obs: Análise Assintótica é uma forma de julgarmos se o nosso algoritmo é eficiente, independente dos “recursos que o cercam” (como velocidade de processamento, quantidade de memória, latência de rede, etc). (wikibooks)

Assim o algoritmo Selection sort possui tempo de execução O(n²).

A seguir temos uma implementação da ordenação com Selecion Sort no C#:

using System;
namespace Selection_Sort
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] numeros = { 230, 45, 345, 14, 324, 90, 76, 34, 67 , 3 };
            Console.WriteLine("######## Ordenação com Selecion Sort ########\n");
            Console.WriteLine("Array original\n");

            foreach (int numero in numeros)
                Console.Write($"{numero} ");
            Console.WriteLine("\n\nOrdenando o array usando Selection Short\n");
            int[] arrayOrdenado = IntArraySelectionSort(numeros);
            Console.WriteLine("Array Ordenado\n");
            foreach (int numero in arrayOrdenado)
                Console.Write($"{numero} ");
            Console.ReadLine();
        }
        public static int[] IntArraySelectionSort(int[] data)
        {
            int i;
            int N = data.Length;
            for (i = 0; i < N - 1; i++)
            {
                int k = IntArrayMin(data, i);
                if (i != k)
                    TrocarValores(data, i, k);
            }
            return data;
        }
        public static int IntArrayMin(int[] data, int start)
        {
            int minPos = start;
            for (int pos = start + 1; pos < data.Length; pos++)
            {
                if (data[pos] < data[minPos])
                    minPos = pos;
            }
            return minPos;
        }        
        public static int[] TrocarValores(int[] arrayDados, int m, int n)
        {
            int temp;
            temp = arrayDados[m];
            arrayDados[m] = arrayDados[n];
            arrayDados[n] = temp;
            return arrayDados;
        }
    }
}

Vamos entender o código:

A ordenação é feita pelo método IntArraySelectionSort() que recebe um array de inteiros como parâmetro.

- Um laço externo visita cada item no array para descobrir se este valor é o mínimo de todos os elementos depois dele. Se não for o mínimo ele será trocado por qualquer item do resto do array que seja o mínimo.

- Foi usado o método IntArrayMin() para encontrar a posição do valor mínimo no array. Este método possui o parâmetro start que indica onde desejamos iniciar a pesquisa.

Lembrando que no C# o índice do primeiro elemento é 0. Assim em um array de 10 elementos o laço inicia com zero e vai até 9.

A ordenação por seleção faz a maior parte de seu trabalho por meio de comparações, que são sempre as mesmas, independentemente de como os dados são ordenados.

No selection sort, não temos pior e melhor caso, pois ele sempre executará a mesma quantidade de vezes dado o tamanho da lista, não importa que itens venham na entrada.

Uma implementação alternativa sem usar métodos auxiliares pode ser vista a seguir:

public static int[] SelectionSort(int[] array)
{
   int min, aux;	 
   for (int i = 0; i< array.Length - 1; i++)
   {
          min = i;	 
         for (int j = i + 1; j< array.Length; j++)
         {
	if (array[j] < array[min])
	     min = j;	 
         }
          if (min != i)
          {
                aux = array[min];
                array[min] = array[i];
                array[i] = aux;
           }
    }
    return array;
 }

Executando o projeto teremos o resultado abaixo :

Pegue o projeto completo aqui:  Algoritmos_Ordenacao_2.zip

Na próxima parte do artigo veremos o algoritmo de ordenação insertion sort.

"17 Quando o vi (Jesus), caí aos seus pés como morto. Então ele colocou sua mão direita sobre mim e disse: "Não tenha medo. Eu sou o primeiro e o último. 18 Sou aquele que vive. Estive morto mas agora estou vivo para todo o sempre! E tenho as chaves da morte e do Hades."
 Apocalipse 1:17,18

Referências:

José Carlos Macoratti