Burstsort

Burstsort

Burstsort and its variants are cache-efficient algorithms for sorting strings and are faster than quicksort and radix sort for large data sets.

Burstsort algorithms use tries to store prefixes of strings, with binary search trees as end nodes containing sorted, unique, suffixes.

References

* The original burstsort article: [http://www.cs.rmit.edu.au/~jz/fulltext/alenex03.pdf Cache-Conscious Sorting of Large Sets of Strings with Dynamic Tries]
* A burstsort derivative (C-burstsort), faster than burstsort: [http://www.cs.mu.oz.au/~rsinha/papers/SinhaRingZobel-2006.pdf Cache-Efficient String Sorting Using Copying]
* The data type used in burstsort: [http://goanna.cs.rmit.edu.au/~jz/fulltext/acmtois02.pdf Burst Tries: A Fast, Efficient Data Structure for String Keys]
* [http://goanna.cs.rmit.edu.au/~jz/fulltext/acsc03sz.pdf Efficient Trie-Based Sorting of Large Sets of Strings]
* A burstsort implementation in C++: [http://sourceforge.net/projects/burstsort/ Free C++ Copy-Burstsort Library]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Sorting algorithm — In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other… …   Wikipedia

  • Trie — A trie for keys A , to , tea , ted , ten , i , in , and inn . In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Unlike a binary search… …   Wikipedia

  • Merge sort — Example of merge sort sorting a list of random dots. Class Sorting algorithm Data structure Array Worst case performance O(n log n) …   Wikipedia

  • Pigeonhole sort — Class Sorting algorithm Data structure Array Worst case performance O(N + n), where N is the range of key values and n is the input size Worst case space complexity O(N * n) …   Wikipedia

  • Radix sort — In computer science, radix sort is a sorting algorithm that sorts integers by processing individual digits. Because integers can represent strings of characters (e.g., names or dates) and specially formatted floating point numbers, radix sort is… …   Wikipedia

  • Counting sort — In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct… …   Wikipedia

  • Bogosort — Class Sorting algorithm Data structure Array Worst case performance [1] Best case performance Ω …   Wikipedia

  • Comb sort — Class Sorting algorithm Data structure Array Worst case performance O(n log n)[1] …   Wikipedia

  • Cocktail sort — Class Sorting algorithm Data structure Array Worst case performance О(n²) Best case performance O(n) …   Wikipedia

  • Topological sorting — Dependency resolution redirects here. For other uses, see Dependency (disambiguation). In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that, for every edge uv, u comes… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”