Selection sort

Selection Sort
Um algoritmo de ordenação coloca os elementos de uma dada sequência em uma certa ordem
(crescente ou decrescente) .
Selection Sort – Esse algoritmo divide o vetor de entrada em partes ordenadas e não-ordenadas e a cada varredura pela parte não-ordenada ele encontra o menor elemento e o transfere para o fim da região ordenada. São feitas muitas comparações, todavia é muito eficiente se contarmos o número de troca de posições, pois são apenas n-1, no pior dos casos.
Selection Sort
Classificação
Complexidade Algoritmo Casos:
Melhor: O(n²).
Médio: O(n²).
Pior: O(n²).
Memória: 1.
Algoritmo do tipo: Seleção.
Definição
Consiste em encontrar a menor chave por pesquisa sequencial. Encontrando a menor chave, essa é permutada com a que ocupa a posição inicial do vetor, que fica então reduzido a um elemento.
O processo é repetido para o restante do vetor, sucessivamente, até que todas as chaves tenham sido selecionadas e colocadas em suas posições definitivas.
Exemplo:
Sequência:
5-3-1-4-2
Verifica quem é o menor e troca com a primeira posição.
1-3-5-4-2
Verifica o mesmo só que a partir da segunda posição:
1-2-5-4-3
e assim sucessivamente até que não exista mais menores após determinada posição:
1-2-3-4-5
Uma outra variação deste método consiste em posicionar-se no primeiro elemento e aí ir testando-o com todos os outros (segundo)... (último), trocando cada vez que for encontrado um elemento menor do que o que está na primeira posição. Em seguida passa-se para a segunda posição do vetor repetindo novamente todo o processo.

Codificação void selection_sort(int num[], int tam)
{
int i, j, min, aux; for (i = 0; i < (tam-1); i++)
{
min = i; for (j = (i+1); j < tam; j++) { if(num[j] < num[min]) { min = j;
}
} if (i != min) { aux = num[i]; num[i] = num[min]; num[min] = aux;
}
}
}
main(){ int array[5], i; for (i = 0; i<5; i++ ) scanf("%d",& array[i]); selection_sort(array, 5); printf("Ordenação: "); for (i = 0; i<5; i++ ) printf("%d", array[i]);

}

Referencias