- Flashsort
Flashsort is a
sorting algorithm with extremely good O(n) efficiency for balanced data sets published in 1998 by Karl-Dietrich Neubert.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+ extrm{INT}left((m-1)frac{A_i-A_ extrm{min{A_ extrm{max}-A_ extrm{min ight)
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 [cite journal |last=Neubert |first=Karl-Dietrich |year=1998 |month=February |title=The Flashsort Algorithm |journal=Dr. Dobb's Journal |pages=123 |url=http://www.ddj.com/ |accessdate=2007-11-06] . For implementations of the algorithm, see [cite web |url=http://www.neubert.net/FSOIntro.html |title=The FlashSort Algorithm |accessdate=2007-11-06 |author=Karl-Dietrich Neubert |date=1998] .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 machinecache . 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 asquicksort in the final step alleviates this problem somewhat, giving an efficiency of O(nlog n) for any randomized data, although the worst case is still O(n^2) [cite web |url=http://jea.acm.org/ARTICLES/Vol5Nbr3/node4.html |title=Cache-Effective Quicksort |accessdate=2007-11-06 |author=Li Xiao, Xiaodong Zhang, Stefan A. Kubricht |work=Improving Memory Performance of Sorting Algorithms |publisher=Department of Computer Science, College of William and Mary, Williamsburg, VA 23187-8795] .See also
*
Big O notation
*Comparison sort
*Computational complexity theory
*List of algorithms References
External links
* [http://elliottback.com/wp/archives/2006/01/07/sorting-in-linear-time/ Sorting in Linear time]
* [http://citeseer.ist.psu.edu/91922.html Implementations of Randomized Sorting on Large Parallel Machines (1992)]
* [http://stinet.dtic.mil/oai/oai?verb=getRecord&metadataPrefix=html&identifier=ADA253638 Implementation of Parallel Algorithms (1992)]
Wikimedia Foundation. 2010.