Este repositório contém uma série de implementações de algoritmos de busca e ordenação que fazem parte de um estudo para o curso de Estruturas de Dados de minha faculdade. Abaixo estão as descrições de alguns algoritmos implementados, comparações de desempenho e exemplos de uso.
- Binary Search
- Interpolation Search
- Jump Search
- Exponential Search
- Ternary Search
- Shell Sort
- Shell
- Knuth
- Hibbard
- Merge Sort
- Selection Sort
- Bucket Sort
- Radix Sort
- Base 10
- Base 2
- Quick Sort
- First Pivot
- Middle Pivot
- Last Pivot
| Comparação de Tempo | Complexidade de Tempo | ||||||
| Algorithm | Tempo de Execução - Lista Pequena | Tempo de Execução - Lista Média | Tempo de Execução - Lista Grande | Melhor Caso | Médio Caso | Pior Caso | Complexidade de Espaço |
| Binary Search | 0,012787 | 0,000107 | 0,000048 | O(1) | O(log n) | O(log n) | O(1) |
| Interpolation Search | 0,000244 | 0,000199 | 0,000197 | O(1) | O(n) | O(log(log n)) | O(1) |
| Jump Search | 0,000422 | 0,000100 | 0,000073 | O(√n) | O(√n) | O(√n) | O(1) |
| Exponential Search | 0,000265 | 0,000068 | 0,000174 | O(1) | O(log n) | O(log n) | O(1) |
| Ternary Search | 0,000243 | 0,000178 | 0,000096 | O(1) | O(log₃ n) | O(log₃ n) | O(1) |
| Comparação de Tempo | Complexidade de Tempo | ||||||
| Algoritmo | Tempo de Execução | Numero de Comparação | Melhor Caso | Médio Caso | Pior Caso | Complexidade de Tempo | |
| Shell Sort (Knuth) | 0.000007 | 40 | O(n log n) | - | O(n^(3/2) | O(1) | |
| Shell Sort (Shell) | 0.000008 | 36 | O(n log n) | O(n^(3/2)) | O(n²) | O(1) | |
| Quick Sort (Middle Pivot) | 0.000020 | 61 | O(log n) | O(n log n) | O(n²) | O(log n) | |
| Radix Sort (Base 10) | 0.000020 | 88 | O(n * k) | O(n * k) | O(n * k) | O(n + k) | |
| Quick Sort (First Pivot) | 0.000039 | 210 | O(log n) | O(n log n) | O(n²) | O(log n) | |
| Quick Sort (Last Pivot) | 0.000043 | 210 | O(log n) | O(n log n) | O(n²) | O(log n) | |
| Selection Sort | 0.000019 | 231 | O(n²) | O(n²) | O(n²) | O(1) | |
| Bucket Sort | 0.000067 | 22 | O(n + k) | O(n + k) | O(n²) | O(n + k) | |
| Merge Sort | 0.000095 | 76 | O(n log n) | O(n log n) | O(n log n) | O(n) | |
| Radix Sort (Base 2) | 0.000070 | 308 | O(n * k) | O(n * k) | O(n * k) | O(n + k) | |
| Shell Sort (Hibbard) | 0.002483 | 48 | O(n log n) | O(n^(3/2)) | O(n²) | O(1) | |
- Estabilidade: Não estável
- Por quê? Durante o processo de comparação de elementos em grandes intervalos, elementos iguais podem ser deslocados, alterando sua ordem relativa.
- Exemplo:
- Original: [(3, A), (3, B), (2, C)]
- Shell Sort: [(2, C), (3, B), (3, A)]
- Estabilidade: Estável
- Por quê? Durante a intercalação de sub-arrays ordenados, os elementos iguais são copiados na ordem em que aparecem nos sub-arrays.
- Exemplo:
- Original: [(3, A), (2, B), (3, C)]
- Merge Sort: [(2, B), (3, A), (3, C)]
- Estabilidade: Não estável
- Por quê? Durante o processo de troca do menor elemento com o elemento atual, a ordem relativa de elementos iguais pode mudar.
- Exemplo:
- Original: [(3, A), (3, B), (2, C)]
- Selection Sort: [(2, C), (3, B), (3, A)]
- Estabilidade: Estável (se o método usado dentro de cada balde for estável)
- Por quê? Elementos iguais caem no mesmo balde, e sua ordem relativa é preservada se o método de ordenação usado nos baldes for estável (por exemplo, Merge Sort).
- Exemplo:
- Original: [(3, A), (3, B), (2, C)]
- Bucket Sort: [(2, C), (3, A), (3, B)]
- Estabilidade: Estável
- Por quê? Ele ordena os dígitos do menos significativo para o mais significativo, usando um algoritmo de ordenação estável (geralmente Counting Sort) em cada etapa.
- Exemplo:
- Original: [(32, A), (32, B), (21, C)]
- Radix Sort: [(21, C), (32, A), (32, B)]
- Estabilidade: Não estável
- Por quê? Durante o particionamento, elementos iguais podem ser colocados em lados diferentes do pivô, alterando sua ordem relativa.
- Exemplo:
- Original: [(3, A), (3, B), (2, C)]
- Quick Sort: [(2, C), (3, B), (3, A)]
Aqui está um gráfico de colunas representando os algoritmos de ordenação:
