Que algoritmos de ordenação você conhece?

Algoritmos principais de ordenação:

• Ordenação de bolha (Bubble Sort): Algoritmo simples, mas ineficiente, que passa repetidamente pela lista, trocando elementos adjacentes se estiverem na ordem errada.
• Ordenação por seleção (Selection Sort): Encontra o menor (ou maior) elemento da parte não ordenada da lista e coloca-o no início.
• Ordenação por inserção (Insertion Sort): Constrói gradualmente uma lista ordenada inserindo cada novo elemento na posição correta já ordenada.
• Ordenação por fusão (Merge Sort): Algoritmo recursivo que divide a lista em sublistas, as ordena e depois as combina.
• Ordenação rápida (Quick Sort): Algoritmo de "dividir e conquistar" que escolhe um elemento pivô e redistribui os elementos para que os menores fiquem à esquerda e os maiores à direita, aplicando recursivamente às sublistas.
• Ordenação Shell (Shell Sort): Melhoria do ordenamento por inserção que usa comparações a distâncias maiores.
• Ordenação por heap (Heap Sort): Usa a estrutura de dados "heap" para ordenar eficientemente.

Existem também algoritmos menos comuns, mas eficazes em certos casos, como ordenação por contagem (Counting Sort), ordenação radix (Radix Sort) e ordenação por baldes (Bucket Sort).

Tempo de execução médio dos principais algoritmos:

Algoritmo de ordenação	Tempo médio de execução
Ordenação de bolha	O(n²)
Ordenação por seleção	O(n²)
Ordenação por inserção	O(n²)
Ordenação por fusão	O(n log n)
Ordenação rápida	O(n log n)
Ordenação Shell	Depende do passo
Ordenação por heap	O(n log n)

Exemplo de implementação de ordenação rápida em Python:

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]  # Escolhemos o elemento pivô
    left = [x for x in arr if x < pivot]  # Elementos menores que o pivô
    middle = [x for x in arr if x == pivot] # Elementos iguais ao pivô
    right = [x for x in arr if x > pivot] # Elementos maiores que o pivô
    return quicksort(left) + middle + quicksort(right) # Ordenamento recursivo e união