Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos de Ordenação e Busca - Coggle Diagram
Algoritmos de Ordenação e Busca
Librarysort
Complexidades:
Tempo: $O(n)$ (Melhor), $O(n \log n)$ (Médio e Pior esperado).
Memória: $O(n)$ (Desperdiça espaço intencionalmente para ganhar velocidade).
Casos de Uso:
Índices de bancos de dados em tempo real.
Árvores B e memória externa.
Sistemas que recebem inserções contínuas e não podem travar.
Conceito Principal: * Gapped Insertion Sort (Cria espaços vazios estrategicamente).
Usa uma Busca Binária modificada.
Exige rotinas de Rebalanceamento para recriar lacunas.
Ligações:
Diferença de Memória: Ao contrário do BogoSort que usa $O(1)$, o Library Sort paga o preço de $O(n)$ para garantir um processamento rápido e contínuo, assim como o Timsort.
Timsort
Conceito Principal: * Algoritmo híbrido (Merge Sort + Insertion Sort).
Identifica runs (subsequências já ordenadas).
Altamente adaptativo e totalmente estável.
Complexidades:
Tempo: $O(n)$ (Melhor), $O(n \log n)$ (Médio e Pior).
Memória: $O(n)$ (Requer memória auxiliar para fundir blocos).
Casos de Uso:
Padrão oficial do Python e Java.
Big Data e sistemas de informação.
Ordenação cronológica (logs, notas fiscais, extratos bancários).
Ligações:
Semelhança: Ambos utilizam o Insertion Sort como ferramenta base para lidar com pequenos blocos, mas com estratégias de memória diferentes.
Bogosort
Casos de Uso:
Estritamente didático e acadêmico.
Ensino do limite do pior caso e crescimento fatorial.
Estabelecimento de uma linha de base de ineficiência.
Complexidades:
Tempo: $O(n)$ (Melhor), $O(n \times n!)$ (Médio), $O(\infty)$ (Pior - pode rodar para sempre).
Memória: $O(1)$ (Excelente, faz tudo no próprio local).
Ligações :
Contraponto absoluto: Mostra exatamente o que os algoritmos de mercado (Timsort/Library) tentam evitar usando lógicas inteligentes.
Conceito Principal: * Algoritmo probabilístico (tentativa e erro puro).
Embaralha a lista aleatoriamente até acertar.
Sem heurística e sem memória de estado.
Links Úteis e Referências
Artigos e Documentações:
Timsort - Documentação Oficial do Python:
https://docs.python.org/3/library/functions.html#sorted
Artigo: Análise Experimental Detalhada do Library Sort (Bender et al. / Faujdar).
Artigo: Análise Comparativa do Consumo Energético de Algoritmos (UFRJ).
Vídeos:
Análise do Algoritmo TimSort:
https://www.youtube.com/watch?v=UJI4anKf6F8
Repositórios (GitHub):
Código Fonte Original do Timsort em C (CPython):