DAA - Classificação por Seleção

Este tipo de classificação é chamado Selection Sortcomo funciona, classificando elementos repetidamente. Funciona da seguinte forma: primeiro encontre o menor na matriz e troque-o pelo elemento na primeira posição, depois encontre o segundo menor elemento e troque-o pelo elemento na segunda posição e continue assim até que toda a matriz seja classificado.

Algorithm: Selection-Sort (A) 
fori ← 1 to n-1 do 
   min j ← i; 
   min x ← A[i] 
   for j ←i + 1 to n do 
      if A[j] < min x then 
         min j ← j 
         min x ← A[j] 
   A[min j] ← A [i] 
   A[i] ← min x

A classificação por seleção está entre as técnicas de classificação mais simples e funciona muito bem para arquivos pequenos. Tem uma aplicação muito importante, pois cada item é movido no máximo uma vez.

A classificação por seção é um método de escolha para classificar arquivos com objetos muito grandes (registros) e chaves pequenas. O pior caso ocorre se a matriz já estiver classificada em ordem decrescente e quisermos classificá-la em ordem crescente.

No entanto, o tempo exigido pelo algoritmo de classificação de seleção não é muito sensível à ordem original da matriz a ser classificada: o teste se A[j] < min x é executado exatamente o mesmo número de vezes em todos os casos.

A classificação por seleção passa a maior parte do tempo tentando encontrar o elemento mínimo na parte não classificada da matriz. Mostra claramente a semelhança entre a classificação por seleção e a classificação por bolha.

  • A classificação por bolha seleciona o máximo de elementos restantes em cada estágio, mas desperdiça algum esforço ao transmitir alguma ordem a uma parte não classificada da matriz.

  • A classificação por seleção é quadrática no pior caso e no caso médio e não requer memória extra.

Para cada i de 1 para n - 1, há uma troca e n - i comparações, então há um total de n - 1 trocas e

(n − 1) + (n − 2) + ...+ 2 + 1 = n(n − 1)/2 comparações.

Essas observações são válidas, não importa quais sejam os dados de entrada.

No pior caso, isso poderia ser quadrático, mas no caso médio, essa quantidade é O(n log n). Isso implica que orunning time of Selection sort is quite insensitive to the input.

Implementação

Void Selection-Sort(int numbers[], int array_size) { 
   int i, j; 
   int min, temp;  
   for (i = 0; I < array_size-1; i++) { 
      min = i; 
      for (j = i+1; j < array_size; j++) 
         if (numbers[j] < numbers[min]) 
            min = j; 
      temp = numbers[i]; 
      numbers[i] = numbers[min]; 
      numbers[min] = temp; 
   } 
}

Exemplo

Unsorted list:
5 2 1 4 3

1 r iteração:

Menor = 5

2 <5, menor = 2

1 <2, menor = 1

4> 1, menor = 1

3> 1, menor = 1

Troca 5 e 1
1 2 5 4 3

2 nd iteração:

Menor = 2

2 <5, menor = 2

2 <4, menor = 2

2 <3, menor = 2

Sem troca
1 2 5 4 3

3 rd iteração:

Menor = 5

4 <5, menor = 4

3 <4, menor = 3

Troca 5 e 3
1 2 3 4 5

4 th iteração:

Menor = 4

4 <5, menor = 4

Sem troca
1 2 3 4 5

Finalmente,

the sorted list is
1 2 3 4 5