Nesta aula, abordamos os principais algoritmos de ordenação utilizados em ciência da computação. Vimos desde os mais simples, como Bubble Sort, até os mais eficientes, como Merge Sort e Quick Sort. Cada algoritmo foi analisado em termos de funcionamento, implementação e complexidade assintótica.
1. O que são algoritmos de ordenação?
Algoritmos de ordenação são métodos para rearranjar os elementos de uma lista em uma ordem específica (geralmente crescente ou decrescente). Eles são fundamentais para otimizar outros algoritmos que dependem de dados ordenados, como busca binária. A escolha do algoritmo adequado pode impactar significativamente o desempenho de uma aplicação.
2. Bubble Sort
Bubble Sort é um algoritmo simples que percorre a lista repetidamente, comparando elementos adjacentes e trocando-os se estiverem na ordem errada. O processo é repetido até que nenhuma troca seja necessária. Embora ineficiente para listas grandes, é fácil de entender e implementar.
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
Complexidade: O(n²) no pior caso e O(n) no melhor caso (lista já ordenada). Memória extra: O(1).
3. Selection Sort
Selection Sort encontra o menor elemento da lista e o coloca na primeira posição. Em seguida, encontra o segundo menor e coloca na segunda posição, e assim sucessivamente. É simples, mas também possui complexidade quadrática.
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
Complexidade: O(n²) em todos os casos (melhor, pior e médio). Memória extra: O(1).
4. Insertion Sort
Insertion Sort constrói a lista ordenada um elemento de cada vez, inserindo cada novo elemento na posição correta em relação aos já ordenados. É eficiente para listas pequenas ou quase ordenadas e é amplamente utilizado na prática como parte de algoritmos híbridos.
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
Complexidade: O(n²) no pior caso, O(n) no melhor caso. Memória extra: O(1).
5. Merge Sort
Merge Sort é um algoritmo de divisão e conquista. Ele divide a lista ao meio recursivamente até ter sublistas de um elemento, depois mescla as sublistas ordenadamente. É estável e garante complexidade O(n log n), mas requer memória extra proporcional ao tamanho da lista.
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 result
Complexidade: O(n log n) no pior, melhor e médio caso. Memória extra: O(n).
6. Quick Sort
Quick Sort também usa divisão e conquista. Escolhe um pivô e particiona a lista em elementos menores e maiores que o pivô, depois ordena recursivamente as partições. Na prática, é muitas vezes mais rápido que Merge Sort, embora possa ter desempenho O(n²) em cenários desfavoráveis.
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
left = [x for x in arr[1:] if x <= pivot]
right = [x for x in arr[1:] if x > pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
Complexidade: O(n log n) no caso médio, O(n²) no pior caso (pivô mal escolhido). Memória extra: O(log n) (pilha de chamada).
7. Comparação de Complexidades
| Algoritmo | Melhor Caso | Caso Médio | Pior Caso | Memória Extra |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
8. Perguntas Frequentes
Qual o melhor algoritmo de ordenação?
Não há um único "melhor". A escolha depende do contexto: para listas pequenas, Insertion Sort pode ser eficiente; para listas grandes e aleatórias, Quick Sort ou Merge Sort são preferíveis. Se o espaço de memória é limitado, Quick Sort é uma boa opção. Algoritmos como Timsort (uma mistura de Merge Sort e Insertion Sort) são usados em linguagens como Python por serem adaptáveis.
Quando o Bubble Sort é útil?
Bubble Sort raramente é usado na prática devido à sua baixa eficiência, mas é útil para fins educacionais e para ordenar listas muito pequenas. Sua simplicidade facilita o entendimento dos conceitos básicos de ordenação.
O que é um algoritmo de ordenação estável?
Um algoritmo de ordenação é estável se mantém a ordem relativa de elementos com chaves iguais. Merge Sort é estável, Quick Sort geralmente não é (dependendo da implementação). A estabilidade é importante quando os elementos têm múltiplos campos de ordenação.