**Algoritmos de Ordenação: Um Estudo Comparativo**
**Introdução**
A ordenação de dados é uma tarefa fundamental em Ciência da Computação, presente em diversas aplicações, desde a ordenação de registros em um banco de dados até a organização de elementos em uma lista. Neste artigo, vamos explorar os principais algoritmos de ordenação, analisando suas complexidades de tempo e espaço, com exemplos de código em Python e diagramas que ilustram seu funcionamento.
**Bubble Sort**
O algoritmo Bubble Sort é um dos mais simples e fáceis de entender. Ele funciona iterando sobre a lista, comparando pares de adjacentes e trocando-os se estiverem na ordem errada. Este processo é repetido até que a lista esteja ordenada.
Complexidade de tempo: O(n²)
Complexidade de espaço: O(1)
Exemplo de código em Python:
```python
def bubble_sort(lista):
n = len(lista)
for i in range(n-1):
for j in range(n-i-1):
if lista[j] > lista[j+1]:
lista[j], lista[j+1] = lista[j+1], lista[j]
return lista
```
Diagrama:
```
lista = [5, 2, 8, 3, 1, 4, 6]
Passo 1:
[5, 2, 8, 3, 1, 4, 6] -> [2, 5, 8, 3, 1, 4, 6]
Passo 2:
[2, 5, 8, 3, 1, 4, 6] -> [2, 3, 5, 8, 1, 4, 6]
...
```
**Insertion Sort**
O algoritmo Insertion Sort é semelhante ao Bubble Sort, mas com uma abordagem mais eficiente. Ele parte da lista vazia e vai inserindo elementos na ordem correta.
Complexidade de tempo: O(n²)
Complexidade de espaço: O(1)
Exemplo de código em Python:
```python
def insertion_sort(lista):
for i in range(1, len(lista)):
chave = lista[i]
j = i-1
while j >=0 and key < lista[j] :
lista[j+1] = lista[j]
j -= 1
lista[j+1] = chave
return lista
```
Diagrama:
```
lista = [5, 2, 8, 3, 1, 4, 6]
Passo 1:
[] -> [5]
Passo 2:
[5] -> [2, 5]
Passo 3:
[2, 5] -> [2, 3, 5]
...
```
**Merge Sort**
O algoritmo Merge Sort é um exemplo de algoritmo divisão e conquista, onde a lista é dividida em sublistas menores, ordenadas individualmente e, posteriormente, mescladas.
Complexidade de tempo: O(n log n)
Complexidade de espaço: O(n)
Exemplo de código em Python:
```python
def merge_sort(lista):
if len(lista) <= 1:
return lista
meio = len(lista) // 2
esquerda = merge_sort(lista[:meio])
direita = merge_sort(lista[meio:])
return merge(esquerda, direita)
def merge(esquerda, direita):
resultado = []
while len(esquerda) > 0 and len(direita) > 0:
if esquerda[0] <= direita[0]:
resultado.append(esquerda.pop(0))
else:
resultado.append(direita.pop(0))
resultado.extend(esquerda)
resultado.extend(direita)
return resultado
```
Diagrama:
```
lista = [5, 2, 8, 3, 1, 4, 6]
Divisão:
[5, 2, 8, 3, 1, 4, 6] -> [5, 2, 3] [8, 1, 4, 6]
Ordenação individual:
[2, 3, 5] [1, 4, 6, 8]
Mesclagem:
[1, 2, 3, 4, 5, 6, 8]
```
**Quick Sort**
O algoritmo Quick Sort é outro exemplo de algoritmo divisão e conquista, onde a lista é dividida em sublistas menores, ordenadas individualmente e, posteriormente, mescladas.
Complexidade de tempo: O(n log n) em média, O(n²) no pior caso
Complexidade de espaço: O(log n) em média, O(n) no pior caso
Exemplo de código em Python:
```python
def quick_sort(lista):
if len(lista) <= 1:
return lista
pivô = lista[0]
menores = [x for x in lista[1:] if x <= pivô]
maiores = [x for x in lista[1:] if x > pivô]
return quick_sort(menores) + [pivô] + quick_sort(maiores)
```
Diagrama:
```
lista = [5, 2, 8, 3, 1, 4, 6]
Seleção do pivô:
pivô = 5
Divisão:
[2, 3, 1, 4] [8, 6]
Ordenação individual:
[1, 2, 3, 4] [6, 8]
Mesclagem:
[1, 2, 3, 4, 5, 6, 8]
```
**Conclusão**
Este artigo apresentou os principais algoritmos de ordenação, Bubble Sort, Insertion Sort, Merge Sort e Quick Sort, destacando suas complexidades de tempo e espaço, com exemplos de código em Python e diagramas que ilustram seu funcionamento. Cada algoritmo tem suas características e aplicações específicas, e a escolha do algoritmo mais adequado depende do conjunto de dados e do contexto em que será utilizado.
**Referências**
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, e Clifford Stein. Introduction to Algorithms, 3ª edição. MIT Press, 2009.
* Robert Sedgewick e Kevin Wayne. Algorithms, 4ª edição. Addison-Wesley, 2011.
Rocket
Mini tools
