Introdução
A ordenação de dados é uma das operações mais fundamentais na computação. Algoritmos de ordenação são essenciais para organizar informações, otimizar buscas e servir de base para outros algoritmos. Nesta aula, estudamos os principais algoritmos de ordenação, analisamos suas complexidades de tempo e espaço e discutimos quando cada um é mais adequado.
Bubble Sort
O Bubble Sort é um algoritmo simples que percorre repetidamente a lista, compara elementos adjacentes e os troca se estiverem na ordem errada. A cada passagem, o maior elemento "flutua" para o final da lista, reduzindo o número de elementos a verificar. Sua complexidade é O(n²) no pior e no caso médio, e O(n) no melhor caso (quando a lista já está ordenada e utilizamos uma otimização com flag). É um algoritmo estável (a ordem relativa de elementos iguais é preservada) e in-place.
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped:
break
return arrSelection Sort
O Selection Sort divide a lista em duas partes: uma sublista ordenada no início e outra não ordenada. A cada iteração, seleciona o menor elemento da parte não ordenada e o troca com o primeiro elemento não ordenado. Sua complexidade é O(n²) em todos os casos, pois sempre percorre a lista em busca do menor elemento. É um algoritmo não estável (a troca pode alterar a ordem relativa de elementos iguais) e in-place.
def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr>Insertion Sort
O Insertion Sort constrói a lista ordenada um elemento de cada vez, inserindo cada novo elemento na posição correta entre os já ordenados. É eficiente para listas pequenas ou parcialmente ordenadas, com complexidade O(n) no melhor caso (lista ordenada) e O(n²) no pior caso. É um algoritmo estável e in-place.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >= 0 and key < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
return arr>Merge Sort
O Merge Sort é um algoritmo de divisão e conquista. Ele divide recursivamente a lista ao meio até que cada sublista tenha um único elemento, depois mescla as sublistas de forma ordenada. Sua complexidade é O(n log n) nos três casos (melhor, médio e pior). É um algoritmo estável e requer memória extra O(n) para as operações de mesclagem. É ideal para cenários onde a estabilidade e a previsibilidade são importantes.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr)//2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return resultQuick Sort
O Quick Sort também utiliza divisão e conquista, mas de forma diferente: escolhe um pivô e particiona a lista em duas sublistas (elementos menores e maiores que o pivô), depois ordena recursivamente as sublistas. Sua complexidade média é O(n log n), mas no pior caso (geralmente quando o pivô é o menor ou maior elemento) chega a O(n²). É um algoritmo in-place, porém não estável. Estratégias como escolha aleatória do pivô ou mediana de três ajudam a evitar o pior caso.
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr)//2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)Comparação dos Algoritmos
A tabela a seguir resume as principais características dos algoritmos estudados:
| Algoritmo | Melhor Caso | Caso Médio | Pior Caso | Estável | In-Place |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | Sim | Sim |
| Selection Sort | O(n²) | O(n²) | O(n²) | Não | Sim |
| Insertion Sort | O(n) | O(n²) | O(n²) | Sim | Sim |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | Sim | Não (memória extra O(n)) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | Não | Sim |
Quando usar cada algoritmo?
- Bubble Sort: raramente usado na prática, exceto para fins didáticos. Sua ineficiência o torna inadequado para listas grandes.
- Selection Sort: útil quando o custo de troca é muito alto, pois minimiza o número de trocas (O(n)), mas ainda O(n²) comparações.
- Insertion Sort: excelente para listas pequenas ou quase ordenadas. Muito usado como base em algoritmos híbridos (ex.: TimSort).
- Merge Sort: indicado quando a estabilidade é essencial e a memória extra é aceitável. É previsível e eficiente para grandes conjuntos.
- Quick Sort: geralmente o mais rápido na prática, especialmente para listas grandes. Escolha do pivô é crucial para evitar o pior caso.
Perguntas Frequentes
Qual algoritmo de ordenação é o mais rápido?
Não há uma resposta absoluta. O Quick Sort costuma ser o mais rápido em média para a maioria dos cenários, mas pode degenerar para O(n²). Merge Sort e Heap Sort (não abordado aqui) oferecem O(n log n) garantido. A escolha depende do contexto: tamanho dos dados, necessidade de estabilidade, uso de memória e distribuição dos valores.
O Quick Sort sempre é a melhor escolha?
Não. Em listas ordenadas ou inversamente ordenadas, sem um bom pivô, o Quick Sort pode ter desempenho O(n²). A implementação com mediana de três ou pivô aleatório reduz essa probabilidade. Além disso, o Merge Sort é mais adequado quando a estabilidade é obrigatória ou a memória não é problema.
Por que o Insertion Sort é eficiente para listas pequenas?
Porque tem baixo overhead (não usa recursão nem alocação extra) e seu deslocamento de elementos é eficiente para listas pequenas. Muitos algoritmos de ordenação híbridos usam Insertion Sort para sublistas de tamanho reduzido (tipicamente até 16-64 elementos).
Conclusão
Nesta aula, vimos os principais algoritmos de ordenação, suas complexidades e características. A escolha do algoritmo adequado depende do problema: tipo e volume dos dados, requisitos de estabilidade, memória disponível e desempenho esperado. O conhecimento desses algoritmos é fundamental para qualquer profissional de computação. Para mais conteúdos, explore outros artigos na seção Posts ou navegue pelas Tags do blog.