Burstsort Ligações externas | Menu de navegaçãoCache-Conscious Sorting of Large Sets of Strings with Dynamic TriesCache-Efficient String Sorting Using CopyingBurst Tries: A Fast, Efficient Data Structure for String KeysEfficient Trie-Based Sorting of Large Sets of StringsEngineering Burstsort: Towards Fast In-Place String SortingFree C++ Copy-Burstsort Libraryburstsort4j
Algoritmos de ordenação
stringsquicksortradix sorttentativasarrays crescentes
Burstsort | |
|---|---|
| classe | Algoritmo de ordenação |
estrutura de dados | Array, Listas ligadas |
complexidade pior caso | O(nlog(n))displaystyle O(nlog(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 |
- O artigo original sobre o burstsort: Cache-Conscious Sorting of Large Sets of Strings with Dynamic Tries
- Um programa derivado do burstsort (C-burstsort), mais rápido do que o burstsort: Cache-Efficient String Sorting Using Copying
- O tipo de dados utilizado no burstsort: Burst Tries: A Fast, Efficient Data Structure for String Keys
- Efficient Trie-Based Sorting of Large Sets of Strings
- Engineering Burstsort: Towards Fast In-Place String Sorting
- Uma implementação do burstsort em C++: Free C++ Copy-Burstsort Library
- Uma implementação do burstsort em Java: burstsort4j
