Flashsort

Flashsort is a sorting process , which on distribution ( english distribution sorting based). It has a linear complexity ${\ displaystyle {\ mathcal {O}} (n)}$ for uniformly distributed input data.

concept

The idea behind Flashsort is that a data set with a known probability distribution is given, which makes it easier to estimate immediately where an element should be positioned within the scope of the sorting, if the lower and upper bounds of the value range are known. For example, given a uniformly distributed set of numbers with a minimum of 1 and a maximum of 100, then it is a good assumption that an element with the value 50 will be roughly in the middle of the sorted set. This approximate position is called class in this sorting process. If the elements are numbered from to , the class of the element is calculated as follows: ${\ displaystyle 1}$ ${\ displaystyle m}$ ${\ displaystyle A_ {i}}$

{\ displaystyle K (A_ {i}) = 1+ \ operatorname {int} \ left ((m-1) {\ frac {A_ {i} -A _ {\ text {min}}} {A _ {\ text { max}} - A _ {\ text {min}}}} \ right)}

,

where is the unsorted input quantity. The area covered by each class is (roughly) the same, except for the last class, which only contains the maximum or the maxima. This classification ensures that every element in a given class is larger than every element in a lower class. This ensures a partial order of the data and reduces the number of inversions. Insertion sort (sort by insert) is applied to the classified set. As long as the input data uniformly ( English Uniformly ) are distributed, these classes are approximately equal, that contain only a few elements, so that the sorting can be conducted efficiently within the classes. ${\ displaystyle A}$

Memory efficient implementations

In order to run Flashsort with low main memory requirements, you can do without using your own data structures for the classes. Instead, the upper limit of each class of the input data list is stored in an auxiliary vector . These upper bounds can be determined by running through all of the data and calculating the number of elements in each class. The upper limit of a class is then the upper limit of the previous class plus the number of elements in the class itself. The elements of this vector can be used as pointers to the classes. ${\ displaystyle A}$ ${\ displaystyle L}$

The distribution to the classes is implemented by a series of cycles, where element is taken on the input vector and its class is calculated. The pointers in the vector are used to insert this element in a free position within the appropriate class. After the insertion, this pointer is decremented. The insertion takes place in the vector itself and displaces another element, which is then inserted next in the appropriate position. This cycle ends when an element is inserted in the position from which the first element of the cycle came. ${\ displaystyle A}$ ${\ displaystyle L}$ ${\ displaystyle A}$

An element is a valid starting element for a cycle if it has not yet been classified. As the algorithm iterates over the input vector , the elements that have already been classified are omitted and unclassified elements are used to start a new cycle. You can decide without further auxiliary structures for the individual elements whether a certain element has already been classified: An element has been classified precisely when its index is greater than the pointer in the auxiliary vector . To prove this, consider the current index of the vector that the algorithm is processing. Be that index. The elements to have already been classified and placed in the correct class. Assume is greater than the pointer to the element's class . It is now assumed that it is unclassified and thus can legitimately be inserted at the index specified by its class pointer where it would replace a classified element in another class. This is impossible, however, since the initial pointers of each class point to their upper limits, which ensures that the exact space required for each class of the input vector is provided. Therefore, every element from the element's class , including the element itself, has already been classified. So if an element has already been classified, then the pointer of this class has been reduced by and thus below the new index of the element. ${\ displaystyle A}$ ${\ displaystyle L}$ ${\ displaystyle A}$ ${\ displaystyle i}$ ${\ displaystyle A_ {0}}$ ${\ displaystyle A_ {i-1}}$ ${\ displaystyle i}$ ${\ displaystyle A_ {i}}$ ${\ displaystyle A_ {i}}$ ${\ displaystyle A}$ ${\ displaystyle A_ {i}}$ ${\ displaystyle A_ {i}}$ ${\ displaystyle 1}$

Performance / complexity

Considerations Performance ( English Performance ) comprise the main memory and the time required for sorting. The only additional memory required is for the auxiliary vector to store the boundaries of the classes, as well as a constant number of scalar variables that are required during the calculation. ${\ displaystyle L}$

In the ideal case of a balanced input dataset, each class is roughly the same size and sorting the individual classes is the complexity . If the number of classes is proportional to the size of the input data set , the runtime results from the sorting within the classes, which is. In the worst case, if all elements end up in one or very few classes, the complexity of the algorithm as a whole is dominated by the performance of the insertion location within the classes. In this case you get . Variants of the algorithm improve the performance in this case by using better algorithms for sorting within the classes, e.g. B. Quicksort or recursive Flashsort on the classes that exceed a certain size. ${\ displaystyle {\ mathcal {O}} (1)}$ ${\ displaystyle m}$ ${\ displaystyle n}$ ${\ displaystyle m * {\ mathcal {O}} (1) = {\ mathcal {O}} (m) = {\ mathcal {O}} (n)}$ ${\ displaystyle {\ mathcal {O}} (n ^ {2})}$

For the correct choice of the number of classes, the time for the classification of the elements (small favorable) and the time required for the sorting within the classes (large favorable) must be balanced against each other. Based on his research, Neubert found that was optimal. ${\ displaystyle m}$ ${\ displaystyle m}$ ${\ displaystyle m}$ ${\ displaystyle m = 0 {,} 42 \, n}$

In terms of main memory, Flashsort avoids the effort required to store the classes in the very similar bucket sort . For evenly distributed data, Flashsort is faster than Heapsort for everyone and faster than Quicksort for everyone . At around it becomes twice as fast as Quicksort. ${\ displaystyle m = 0 {,} 1 \, n}$ ${\ displaystyle n}$ ${\ displaystyle n> 80}$ ${\ displaystyle n = 10000}$

Because of the classification process, Flashsort is not stable .

Demarcation

The algorithm presented by Neubert as Flashsort has the same name as an older randomized sorting algorithm for parallel computer architectures.

Individual evidence

^ ^A ^b ^c Karl-Dietrich Neubert: The Flashsort Algorithm . In: Dr. Dobb's Journal . February 1998, p. 123. Retrieved November 6, 2007.
^ ^A ^b Karl-Dietrich Neubert: The FlashSort Algorithm . 1998. Retrieved November 6, 2007.
↑ Li Xiao, Xiaodong Zhang, Stefan A. Kubricht: Cache-Effective Quicksort . In: Improving Memory Performance of Sorting Algorithms . Department of Computer Science, College of William and Mary, Williamsburg, VA 23187-8795. Archived from the original on November 2, 2007. Retrieved November 6, 2007.
↑ http://nist.gov/dads/HTML/flashsort.html
↑ John H. Reif and Leslie G. Valiant: A logarithmic time sort for linear size networks . In: Proceedings of the fifteenth annual ACM symposium on Theory of computing . 1983, p. 10-16 , doi : 10.1145 / 800061.808727 .
↑ John H. Reif and Leslie G. Valiant: A logarithmic time sort for linear size networks . In: Journal of the ACM . tape 34 , no. 1 , 1987, pp. 60-76 , doi : 10.1145 / 7531.7532 .

literature

Karl-Dietrich Neubert: The Flashsort Algorithm . In: Dr. Dobb's Journal . February 1998, p. 123 ( HTTP ).
Karl-Dietrich Neubert: The FlashSort Algorithm . In: Proceedings of the euroFORTH '97 . September 1997 ( Word Document - without peer review ).
Apostolos Burnetas and Daniel Solow and Rishi Agarwal: An analysis and implementation of an efficient in-place bucket sort . In: Acta Informatica . tape 34 , no. 9 , 1997, pp. 687-700 , doi : 10.1007 / s002360050103 (filed 1995).
EJ Isaac and RC Singleton: Sorting by Address Calculation . In: Journal of the ACM . tape 3 , no. 3 , July 1956, p. 169-174 , doi : 10.1145 / 320831.320834 .

Web links

Flashsort site from Neubert
Visualization of Flashsort (English)

[neubert_journal-1] A ^b ^c Karl-Dietrich Neubert: The Flashsort Algorithm . In: Dr. Dobb's Journal . February 1998, p. 123. Retrieved November 6, 2007.

[neubert_code-2] A ^b Karl-Dietrich Neubert: The FlashSort Algorithm . 1998. Retrieved November 6, 2007.

[3] Li Xiao, Xiaodong Zhang, Stefan A. Kubricht: Cache-Effective Quicksort . In: Improving Memory Performance of Sorting Algorithms . Department of Computer Science, College of William and Mary, Williamsburg, VA 23187-8795. Archived from the original on November 2, 2007. Retrieved November 6, 2007.

[4] ttp://nist.gov/dads/HTML/flashsort.html

[5] John H. Reif and Leslie G. Valiant: A logarithmic time sort for linear size networks . In: Proceedings of the fifteenth annual ACM symposium on Theory of computing . 1983, p. 10-16 , doi : 10.1145 / 800061.808727 .

[6] John H. Reif and Leslie G. Valiant: A logarithmic time sort for linear size networks . In: Journal of the ACM . tape 34 , no. 1 , 1987, pp. 60-76 , doi : 10.1145 / 7531.7532 .