# Ordenação (Sorting Algorithms)

### 📌 Visão Geral

**Ordenação** é o processo de reorganizar elementos de uma lista em uma ordem específica (crescente, decrescente, etc.). É um dos problemas mais fundamentais da ciência da computação, com aplicações em busca de dados, otimização de algoritmos e organização de informação.

```
Entrada: [5, 2, 8, 1, 9, 3]
           ↓
Algoritmo de Ordenação
           ↓
Saída:   [1, 2, 3, 5, 8, 9]
```

#### Analogia

> *"Ordenar é como organizar uma pilha de papéis: você pode colocar cada folha no lugar certo (inserção), trocar pares adjacentes repetidamente (bolha), ou dividir em pilhas menores e depois juntar (merge). Cada método tem seu momento certo."*

***

### 📋 Classificação dos Algoritmos

#### Por Complexidade

| Complexidade   | Algoritmos                   | Viabilidade                              |
| -------------- | ---------------------------- | ---------------------------------------- |
| **O(n²)**      | Bubble, Selection, Insertion | ❌ Inviável para n > 10.000               |
| **O(n log n)** | Merge, Quick, Heap           | ✅ Ideal para n grande                    |
| **O(n + k)**   | Counting, Radix, Bucket      | ✅ Melhor, mas requer condições especiais |

#### Por Estabilidade

| Estável        | Instável       |
| -------------- | -------------- |
| Bubble Sort    | Selection Sort |
| Insertion Sort | Quick Sort     |
| Merge Sort     | Heap Sort      |

> **Estável:** Elementos iguais mantêm a ordem relativa original.

#### Por Abordagem

| Abordagem          | Algoritmos                                       |
| ------------------ | ------------------------------------------------ |
| **Comparação**     | Bubble, Selection, Insertion, Merge, Quick, Heap |
| **Não comparação** | Counting, Radix, Bucket                          |

***

### 🔢 Algoritmos em Detalhe

#### 1. Bubble Sort (Bolha)

**Como funciona:** Percorre repetidamente a lista, trocando elementos adjacentes fora de ordem.

```python
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # Otimização: flag para parar se já ordenado
        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 arr

# Exemplo
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr)  # [11, 12, 22, 25, 34, 64, 90]
```

| Característica | Valor |
| -------------- | ----- |
| Melhor caso    | O(n)  |
| Médio caso     | O(n²) |
| Pior caso      | O(n²) |
| Memória        | O(1)  |
| Estável        | ✅ Sim |

**Quando usar:** Apenas para fins educacionais ou listas muito pequenas (n < 100).

***

#### 2. Selection Sort (Seleção)

**Como funciona:** Encontra o menor elemento e o coloca no início, repete.

```python
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

# Exemplo
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print(arr)  # [11, 12, 22, 25, 64]
```

| Característica | Valor |
| -------------- | ----- |
| Melhor caso    | O(n²) |
| Médio caso     | O(n²) |
| Pior caso      | O(n²) |
| Memória        | O(1)  |
| Estável        | ❌ Não |

**Quando usar:** Quando a memória é extremamente limitada (poucas trocas).

***

#### 3. Insertion Sort (Inserção)

**Como funciona:** Constrói a lista ordenada um elemento por vez, inserindo cada novo elemento na posição correta.

```python
def insertion_sort(arr):
    for i in range(1, len(arr)):
        chave = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > chave:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = chave
    return arr

# Exemplo
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print(arr)  # [5, 6, 11, 12, 13]
```

| Característica | Valor |
| -------------- | ----- |
| Melhor caso    | O(n)  |
| Médio caso     | O(n²) |
| Pior caso      | O(n²) |
| Memória        | O(1)  |
| Estável        | ✅ Sim |

**Quando usar:** Listas pequenas (n < 1000) ou quase ordenadas.

***

#### 4. Merge Sort (Intercalação)

**Como funciona:** Divide a lista ao meio, ordena recursivamente, e intercala as metades.

```python
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    meio = len(arr) // 2
    esquerda = merge_sort(arr[:meio])
    direita = merge_sort(arr[meio:])
    
    return merge(esquerda, direita)

def merge(esq, dir):
    resultado = []
    i = j = 0
    
    while i < len(esq) and j < len(dir):
        if esq[i] <= dir[j]:
            resultado.append(esq[i])
            i += 1
        else:
            resultado.append(dir[j])
            j += 1
    
    resultado.extend(esq[i:])
    resultado.extend(dir[j:])
    return resultado

# Exemplo
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(sorted_arr)  # [3, 9, 10, 27, 38, 43, 82]
```

| Característica | Valor      |
| -------------- | ---------- |
| Melhor caso    | O(n log n) |
| Médio caso     | O(n log n) |
| Pior caso      | O(n log n) |
| Memória        | O(n)       |
| Estável        | ✅ Sim      |

**Quando usar:** Listas grandes (n > 10.000), quando a estabilidade é importante.

***

#### 5. Quick Sort (Ordenação Rápida)

**Como funciona:** Escolhe um pivô, particiona a lista (menores à esquerda, maiores à direita), e ordena recursivamente.

```python
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivô = arr[len(arr) // 2]
    esquerda = [x for x in arr if x < pivô]
    meio = [x for x in arr if x == pivô]
    direita = [x for x in arr if x > pivô]
    
    return quick_sort(esquerda) + meio + quick_sort(direita)

# Versão in-place (economiza memória)
def quick_sort_inplace(arr, baixo=0, alto=None):
    if alto is None:
        alto = len(arr) - 1
    
    if baixo < alto:
        p = particao(arr, baixo, alto)
        quick_sort_inplace(arr, baixo, p - 1)
        quick_sort_inplace(arr, p + 1, alto)

def particao(arr, baixo, alto):
    pivô = arr[alto]
    i = baixo - 1
    
    for j in range(baixo, alto):
        if arr[j] <= pivô:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[alto] = arr[alto], arr[i + 1]
    return i + 1

# Exemplo
arr = [10, 7, 8, 9, 1, 5]
quick_sort_inplace(arr)
print(arr)  # [1, 5, 7, 8, 9, 10]
```

| Característica | Valor      |
| -------------- | ---------- |
| Melhor caso    | O(n log n) |
| Médio caso     | O(n log n) |
| Pior caso      | O(n²)      |
| Memória        | O(log n)   |
| Estável        | ❌ Não      |

**Quando usar:** Listas grandes, quando a estabilidade não é necessária (mais rápido que Merge em média).

***

#### 6. Heap Sort (Ordenação por Montículo)

**Como funciona:** Constrói um heap máximo e extrai repetidamente o maior elemento.

```python
def heapify(arr, n, i):
    maior = i
    esq = 2 * i + 1
    dir = 2 * i + 2
    
    if esq < n and arr[esq] > arr[maior]:
        maior = esq
    if dir < n and arr[dir] > arr[maior]:
        maior = dir
    
    if maior != i:
        arr[i], arr[maior] = arr[maior], arr[i]
        heapify(arr, n, maior)

def heap_sort(arr):
    n = len(arr)
    
    # Construir heap máximo
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # Extrair elementos um por um
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    
    return arr

# Exemplo
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print(arr)  # [5, 6, 7, 11, 12, 13]
```

| Característica | Valor      |
| -------------- | ---------- |
| Melhor caso    | O(n log n) |
| Médio caso     | O(n log n) |
| Pior caso      | O(n log n) |
| Memória        | O(1)       |
| Estável        | ❌ Não      |

**Quando usar:** Quando a memória é limitada (in-place) e O(n log n) é necessário.

***

#### 7. Counting Sort (Ordenação por Contagem)

**Como funciona:** Conta a frequência de cada valor e depois reconstrói a lista.

```python
def counting_sort(arr):
    if not arr:
        return arr
    
    # Encontrar o valor máximo
    max_val = max(arr)
    min_val = min(arr)
    range_val = max_val - min_val + 1
    
    # Array de contagem
    count = [0] * range_val
    
    # Contar ocorrências
    for num in arr:
        count[num - min_val] += 1
    
    # Reconstruir array ordenado
    resultado = []
    for i, freq in enumerate(count):
        resultado.extend([i + min_val] * freq)
    
    return resultado

# Exemplo
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print(sorted_arr)  # [1, 2, 2, 3, 3, 4, 8]
```

| Característica | Valor                           |
| -------------- | ------------------------------- |
| Melhor caso    | O(n + k)                        |
| Médio caso     | O(n + k)                        |
| Pior caso      | O(n + k)                        |
| Memória        | O(k)                            |
| Estável        | ✅ Sim (implementação cuidadosa) |

**k = faixa de valores (max - min)**

**Quando usar:** Quando a faixa de valores (k) é pequena em relação a n.

***

#### 8. Radix Sort (Ordenação por Dígitos)

**Como funciona:** Ordena dígito por dígito, do menos significativo ao mais significativo.

```python
def counting_sort_radix(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    
    # Contar ocorrências do dígito atual
    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1
    
    # Transformar em posições cumulativas
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    # Construir array ordenado por este dígito
    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
    
    # Copiar de volta
    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    if not arr:
        return arr
    
    max_val = max(arr)
    exp = 1
    
    while max_val // exp > 0:
        counting_sort_radix(arr, exp)
        exp *= 10
    
    return arr

# Exemplo
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print(arr)  # [2, 24, 45, 66, 75, 90, 170, 802]
```

| Característica | Valor    |
| -------------- | -------- |
| Melhor caso    | O(n × k) |
| Médio caso     | O(n × k) |
| Pior caso      | O(n × k) |
| Memória        | O(n + k) |
| Estável        | ✅ Sim    |

**k = número de dígitos**

**Quando usar:** Números inteiros com muitos elementos e faixa grande (Counting Sort inviável).

***

#### 9. Bucket Sort (Ordenação por Baldes)

**Como funciona:** Distribui elementos em baldes e ordena cada balde individualmente.

```python
def bucket_sort(arr, num_buckets=10):
    if not arr:
        return arr
    
    # Encontrar mínimo e máximo
    min_val, max_val = min(arr), max(arr)
    
    # Criar baldes
    buckets = [[] for _ in range(num_buckets)]
    
    # Distribuir elementos nos baldes
    for num in arr:
        index = int((num - min_val) / (max_val - min_val + 1) * num_buckets)
        if index == num_buckets:  # Ajuste para o último elemento
            index -= 1
        buckets[index].append(num)
    
    # Ordenar cada balde (Insertion Sort é eficiente para baldes pequenos)
    for i in range(num_buckets):
        insertion_sort(buckets[i])
    
    # Concatenar baldes
    resultado = []
    for bucket in buckets:
        resultado.extend(bucket)
    
    return resultado

# Exemplo (dados uniformemente distribuídos)
arr = [0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51]
sorted_arr = bucket_sort(arr, 5)
print(sorted_arr)  # [0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52]
```

| Característica | Valor    |
| -------------- | -------- |
| Melhor caso    | O(n + k) |
| Médio caso     | O(n + k) |
| Pior caso      | O(n²)    |
| Memória        | O(n × k) |
| Estável        | ✅ Sim    |

**Quando usar:** Dados uniformemente distribuídos (ex: números entre 0 e 1).

***

### 📊 Comparação de Performance

#### Tempo de Execução (n = 100.000 elementos)

| Algoritmo                  | Tempo (aprox.) | Complexidade |
| -------------------------- | -------------- | ------------ |
| **Quick Sort**             | 0.03 segundos  | O(n log n)   |
| **Merge Sort**             | 0.04 segundos  | O(n log n)   |
| **Heap Sort**              | 0.05 segundos  | O(n log n)   |
| **Insertion Sort**         | 45 segundos    | O(n²)        |
| **Bubble Sort**            | 90 segundos    | O(n²)        |
| **Selection Sort**         | 45 segundos    | O(n²)        |
| **Counting Sort** (k=1000) | 0.01 segundos  | O(n + k)     |

#### Visualização de Complexidades

```
n=1.000     n=10.000    n=100.000   n=1.000.000
O(n²):     1M ops     100M ops    10B ops    1T ops
O(n log n): 10K ops    140K ops    1.7M ops   20M ops
O(n):      1K ops     10K ops     100K ops   1M ops
```

***

### 🎯 Guia de Seleção

#### "Preciso ordenar uma lista..."

| Seu cenário                           | Algoritmo recomendado |
| ------------------------------------- | --------------------- |
| Lista pequena (n < 1000)              | Insertion Sort        |
| Lista grande, estabilidade importante | Merge Sort            |
| Lista grande, memória limitada        | Heap Sort             |
| Lista grande, geral                   | Quick Sort            |
| Dados inteiros com faixa pequena      | Counting Sort         |
| Números com muitos dígitos            | Radix Sort            |
| Dados uniformemente distribuídos      | Bucket Sort           |
| Lista quase ordenada                  | Insertion Sort (O(n)) |

#### "Quero aprender ordenação..."

| Objetivo                     | Algoritmo                 |
| ---------------------------- | ------------------------- |
| Entender conceitos básicos   | Bubble Sort               |
| Entender recursão            | Merge Sort, Quick Sort    |
| Entender estruturas de dados | Heap Sort                 |
| Entender casos especiais     | Counting Sort, Radix Sort |

***

### 📈 Propriedades Importantes

#### Estabilidade (quando a ordem de elementos iguais importa)

```python
# Exemplo: ordenar por nome, depois por idade
dados = [("Alice", 25), ("Bob", 20), ("Alice", 30)]

# Estável: mantém "Alice 25" antes de "Alice 30"
estavel = [("Alice", 25), ("Alice", 30), ("Bob", 20)]

# Instável: pode inverter "Alice 25" e "Alice 30"
instavel = [("Alice", 30), ("Alice", 25), ("Bob", 20)]
```

#### Adaptabilidade (melhor caso em dados quase ordenados)

| Algoritmo      | Melhor caso | Comportamento         |
| -------------- | ----------- | --------------------- |
| Insertion Sort | O(n)        | ✅ Altamente adaptável |
| Bubble Sort    | O(n)        | ✅ Adaptável           |
| Quick Sort     | O(n log n)  | ❌ Não adaptável       |
| Merge Sort     | O(n log n)  | ❌ Não adaptável       |

***

### 💻 Exemplo de Benchmark

```python
import time
import random

def benchmark_sort(nome, func, arr):
    start = time.time()
    func(arr.copy())
    return time.time() - start

# Gerar dados
tamanhos = [1000, 10000, 100000]
resultados = {}

for n in tamanhos:
    arr = [random.randint(1, 1000000) for _ in range(n)]
    
    print(f"\n--- n = {n} ---")
    
    # Bubble (apenas para n pequeno)
    if n <= 10000:
        t = benchmark_sort("Bubble", bubble_sort, arr)
        print(f"Bubble Sort: {t:.4f}s")
    
    t = benchmark_sort("Quick", quick_sort_inplace, arr)
    print(f"Quick Sort: {t:.4f}s")
    
    t = benchmark_sort("Merge", merge_sort, arr)
    print(f"Merge Sort: {t:.4f}s")
```

***

### 🔗 Links Úteis

* [Sorting Algorithm Animations](https://www.toptal.com/developers/sorting-algorithms)
* [Visualgo - Sorting](https://visualgo.net/en/sorting)
* [Big-O Cheat Sheet](https://www.bigocheatsheet.com/)

***

### 📚 Resumo Rápido

| Algoritmo     | Estável | In-place | Melhor     | Médio      | Pior       | Uso típico                |
| ------------- | ------- | -------- | ---------- | ---------- | ---------- | ------------------------- |
| **Bubble**    | ✅       | ✅        | O(n)       | O(n²)      | O(n²)      | Educacional               |
| **Selection** | ❌       | ✅        | O(n²)      | O(n²)      | O(n²)      | Memória limitada          |
| **Insertion** | ✅       | ✅        | O(n)       | O(n²)      | O(n²)      | Pequenos, quase ordenados |
| **Merge**     | ✅       | ❌        | O(n log n) | O(n log n) | O(n log n) | Estabilidade, grandes     |
| **Quick**     | ❌       | ✅        | O(n log n) | O(n log n) | O(n²)      | Geral (rápido)            |
| **Heap**      | ❌       | ✅        | O(n log n) | O(n log n) | O(n log n) | Memória limitada          |
| **Counting**  | ✅       | ❌        | O(n+k)     | O(n+k)     | O(n+k)     | Faixa pequena             |
| **Radix**     | ✅       | ❌        | O(n×k)     | O(n×k)     | O(n×k)     | Números inteiros          |


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://0xmorte.gitbook.io/bibliadopentestbr/conceitos/algoritmos/ordenacao-sorting-algorithms.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.