Comparação de Algoritmos de Ordenação: Bubble Sort, Shellsort e Merge Sort

Bubble Sort: Este algoritmo realiza comparações entre os elementos de um vetor. Quando dois elementos estão fora de ordem, ocorre uma inversão e eles são trocados de posição. O processo se repete até que o elemento de maior valor esteja na última posição.

Shellsort: Uma versão otimizada do algoritmo de inserção. Ele divide o vetor em segmentos e realiza comparações e trocas entre elementos distantes, diminuindo a distância a cada iteração até que se torne uma simples ordenação por inserção.

O processo de inserção simples consiste em dividir o vetor a ser ordenado em dois segmentos: um ordenado e outro desordenado. O primeiro elemento do segmento desordenado é comparado com os elementos do segmento ordenado e inserido na posição correta. Este processo se repete até que todos os elementos estejam ordenados.

Se o vetor inicial estiver ordenado, a ordenação se comporta como O(n). Se estiver na ordem inversa, a complexidade será O(n²).

Observe que o próprio vetor é utilizado na ordenação, consumindo pouca memória adicional. No Shellsort, elementos distantes são comparados, com o valor de h diminuindo a cada ciclo até atingir 1, tornando-se uma inserção simples. O ideal é que os valores de h sejam primos entre si para evitar sobreposição de subdivisões.

Merge Sort: Um algoritmo de ordenação do tipo dividir-para-conquistar. Ele divide o vetor em subconjuntos menores, ordena esses subconjuntos e, em seguida, os combina (fusão) para produzir um vetor ordenado final.