Flashsort

From Wikipedia, the free encyclopedia

Flashsort is a sorting algorithm with extremely good $O (n)$ efficiency for balanced data sets published in 1998 by Karl-Dietrich Neubert.

1 Algorithm
2 Efficiency
3 See also
4 References
5 External links

[edit] Algorithm

Flashsort works based on the principle that in either a randomized or partially-ordered data set in which data are in a balanced distribution, one can immediately estimate where an item should be placed when one knows the range of the set. This approximate location is called the class of an item $A i$ , and is computed as

$K(A_i) = 1+\textrm{INT}\left((m-1)\frac{A_i-A_\textrm{min}}{A_\textrm{max}-A_\textrm{min}}\right)$

which gives a total of $m$ possible classes. After calculating the class of an element, it is inserted into the position in the array given by the order of the class (arranged from 1 through $m$ ). The final step is an insertion sort to arrange items in each class and fix any remaining errors ^[1]. For implementations of the algorithm, see ^[2].

[edit] Efficiency

In the ideal case of a balanced data set, the efficiency scales as $O (n)$ because each class is similarly sized, creating well-sorted data for the final insertion sort. As an in-place algorithm, it uses minimal memory and it also makes efficient use of the machine cache. In the worst case of unbalanced data, flashsort is as slow as insertion sort, scaling as $O (n 2)$ precisely due to the need to use insertion sort on data that was poorly sorted during classification. Using a faster algorithm such as quicksort in the final step alleviates this problem somewhat, giving an efficiency of $O (n log n)$ for any randomized data, although the worst case is still $O (n 2)$ ^[3].

[edit] See also

[edit] References

^ Neubert, Karl-Dietrich (February 1998). "The Flashsort Algorithm". Dr. Dobb's Journal: 123.
^ Karl-Dietrich Neubert (1998). The FlashSort Algorithm. Retrieved on 2007-11-06.
^ Li Xiao, Xiaodong Zhang, Stefan A. Kubricht. Cache-Effective Quicksort. Improving Memory Performance of Sorting Algorithms. Department of Computer Science, College of William and Mary, Williamsburg, VA 23187-8795. Retrieved on 2007-11-06.