Burstsort

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Burstsort
classe Algoritmo de ordenação
estrutura de dados Array, Listas ligadas
complexidade pior caso O(n\log(n))
otimo  ?
Algoritmos

Burstsort e suas variantes são algoritmos cache-eficientes para a ordenação de strings, e são mais rápidos que o quicksort e o radix sort para grandes conjuntos de dados.

Os algoritmos Burstsort usam tentativas para armazenar prefixos de strings, com arrays crescentes de ponteiros como nodos final contendo sufixos ordenados, unicos (referidos como buckets (baldes)). Algumas variantes copiar as caudas das strings nos buckets. A medida em que os buckets crescem além de um limite pré-determinado, os buckets são "estourados" (burst), dando ao algoritmo o seu nome. Uma variante mais recente, usa um bucket com menor índice de sub-buckets para reduzir o uso de memória.

Ligações externas[editar | editar código-fonte]