Algoritmos de ordenação simples

Temos 4 algoritmos básicos de ordenação simples: Bubble Sort, Insertion Sort, Selection Sort e Enumeration Sort.

Bubble Sort: o bubble é um algoritmo baseado em trocas. Ele percorre o vetor do início ao final comparando pares de elementos e trocando-os caso seja necessário. Ele faz isso quantas vezes forem necessárias até que a ordenação esteja completa. A cada passada, o maior elemento analisado já fica no lugar.
O bubble sempre será O(n²) comparações. Para trocas, seu melhor caso é O(1), pois não faz trocas caso os elementos já estejam ordenados, e caso médio e pior caso são O(n²).
É um algoritmo amplamente utilizado didaticamente, porém é ineficiente.

Insertion Sort: o insertion analisa cada elemento e o insere na posição correta em relação aos elementos já ordenados. Ou seja, é um algoritmo que não realiza trocas, mas sim movimentações (cada troca é composta de 3 movimentações). Um bom exemplo: imagine que você está jogando cartas. Para organizá-las na sua mão, você pega a carta à direita e, a partir da esquerda, encontra seu lugar e a insere ali, não é mesmo? Isso é o insertion sort.
O algoritmo é sensível à ordenação inicial do arquivo: para o pior caso, é O(n²) comparações, mas para o melhor (arquivo ordenado) é O(n). Idem para o número de movimentações.
Caso se tenha um arquivo quase ordenado ou poucos registros para inserir num arquivo ordenado, o insertion sort é mais recomendado do que métodos sofisticados.

Selection Sort: o selection seleciona no conjunto de n elementos o maior (ou menor, dependendo da ordem desejada) e o troca com a primeira posição. A seguir, repete o processo para n-1 elementos. Assim, a cada passada um elemento estará na posição correta.
O número de comparações também é O(n²), porém para cada elemento é feita uma troca (a troca é realizada mesmo se ele já estiver na posição correta). Assim, é O(n) para trocas.

Enumeration Sort: ele percorre o vetor e armazena em outro vetor do mesmo tamanho a posição relativa daquele índice na ordenação. Por exemplo, se tem-se
|9|3|7|4|2|8|, o enumeration cria um outro vetor com os seguintes valores:
|5|1|3|2|0|4|, que correspondem à posição que o elemento de mesmo índice no vetor original ocuparia num vetor ordenado.
Além de não ordenar de fato, o algoritmo ainda ocupa um espaço adicional do tamanho do vetor original, tornando-se extremamente ineficiente.