Hoje vamos estudar três algoritmos de ordenação clássicos: Bubble Sort, Selection Sort e Insertion Sort. Esses algoritmos são considerados elementares e formam a base para entender métodos mais avançados como Merge Sort e Quick Sort. Vamos ver como cada um funciona, sua implementação em Python e analisar sua complexidade de tempo e espaço.
1. Bubble Sort
O Bubble Sort é o algoritmo mais simples. Ele percorre a lista repetidamente, compara elementos adjacentes e os troca se estiverem fora de ordem. O processo se repete até que nenhuma troca seja necessária.
Exemplo: para ordenar [5, 3, 8, 1], o algoritmo faz:
- Primeira passagem: compara 5 e 3 → troca → [3,5,8,1]; 5 e 8 não troca; 8 e 1 → troca → [3,5,1,8]
- Segunda passagem: 3 e 5 não troca; 5 e 1 → troca → [3,1,5,8]; 5 e 8 não troca
- Terceira passagem: 3 e 1 → troca → [1,3,5,8]; 3 e 5 não troca
- Quarta passagem: nenhuma troca → fim
Implementação em Python:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
trocou = 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]
trocou = True
if not trocou:
break
return arrComplexidade: O(n²) no pior e médio caso, O(n) no melhor (lista já ordenada). Espaço O(1).
2. Selection Sort
O Selection Sort divide a lista em duas partes: a parte ordenada (à esquerda) e a parte não ordenada (à direita). Em cada iteração, seleciona o menor elemento da parte não ordenada e o coloca ao final da parte ordenada.
Implementação:
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
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, espaço O(1).
3. 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.
Implementação:
def insertion_sort(arr):
for i in range(1, len(arr)):
chave = arr[i]
j = i-1
while j >= 0 and chave < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = chave
return arr>Complexidade: O(n²) no pior caso, O(n) no melhor (lista ordenada). Muito eficiente para listas pequenas ou quase ordenadas. Espaço O(1).
Comparação entre os Algoritmos
| Algoritmo | Melhor Caso | Pior Caso | Médio | Espaço | Estável |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Sim |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | Não |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Sim |
Principais Pontos
- Bubble Sort é fácil de entender mas ineficiente para listas grandes.
- Selection Sort sempre faz O(n²) comparações, independente da entrada.
- Insertion Sort é o melhor entre os três para listas pequenas ou parcialmente ordenadas.
- Nenhum destes algoritmos é usado em produção para grandes volumes; prefira Quick Sort, Merge Sort ou Timsort.
Perguntas Frequentes
Qual algoritmo de ordenação é mais rápido?
Em média, nenhum dos três é eficiente para listas grandes. Para listas pequenas (até ~50 elementos), Insertion Sort é o mais rápido devido à baixa constante.
O Selection Sort é estável?
A implementação padrão não é estável, pois pode trocar elementos iguais de posição.
Quando usar Bubble Sort?
Praticamente nunca, exceto para fins didáticos ou quando se sabe que a lista está quase ordenada (com otimização).
Esta aula cobriu os fundamentos da ordenação elementar. Nos próximos dias veremos algoritmos mais eficientes como Merge Sort e Quick Sort. Continue acompanhando!