Adaptive sorting

Adaptive sorting algorithms are sorting algorithms whose control flow depends on the input data. In particular, adaptive sorting algorithms are of interest that achieve shorter runtimes on inputs that already have a certain order than on inputs without a structure. Many of the known adaptive sorting algorithms have arisen by modifying known algorithms.

Since it often happens in practice that entries are almost sorted, one is interested in algorithms that work particularly quickly in these cases. The aim is to undercut the lower limit for the average case in comparison-based sorting algorithms. ${\ displaystyle O (n \ log n)}$

In the run-time analysis of the adaptive method, in addition to the input variable, a measure of the order that already exists in the input is included - in contrast to classic comparison-based sorting methods , in which a distinction is only made between best-case, average-case and worst-case, the behavior the algorithms between these cases will not be investigated further.

Dimensions of order

This order must be measured so that the existing order in the input can flow into the analysis of the algorithm. Several different measures have been established for this.

A frequently used measure is the number of faults , i.e. the number of pairs in the wrong order, in the input : ${\ displaystyle X = (x_ {1}, ..., x_ {n})}$

{\ displaystyle \ operatorname {Inv} (X) = | \ left \ {(i, j) \ mid 1 \ leq i <j \ leq n ~ {\ text {and}} ~ x_ {i}> x_ {j } \ right \} |}

.

Other often used dimensions are:

the number of series of successive, ascending elements, so-called "runs":

{\ displaystyle \ operatorname {Runs} (X) = | \ {\, i \, \ mid 1 \ leq i <n ~ {\ text {and}} ~ x_ {i}> x _ {(} i + 1) \} | +1}

the minimum number of elements that must be removed to get a sorted sequence:

{\ displaystyle \ operatorname {Rem} (X) = n- \ max \ {\, k \, \ mid X ~ {\ text {has a sorted substring of length}} ~ k \}}

the minimum number of interchanges of any two elements to sort the input: ${\ displaystyle \ operatorname {Exc} (X)}$

Examples

input ${\ displaystyle X}$	${\ displaystyle \ operatorname {Inv} (X)}$	${\ displaystyle \ operatorname {Runs} (X)}$	${\ displaystyle \ operatorname {Rem} (X)}$	${\ displaystyle \ operatorname {Exc} (X)}$
${\ displaystyle (1,2,3,4,5)}$	0	1	0	0
${\ displaystyle (2,3,4,5,1)}$	4th	2	1	4th
${\ displaystyle (4,3,2,1,5)}$	6th	4th	3	2
${\ displaystyle (5,4,3,2,1)}$	10	5	4th	2

Different measures not only lead to different values, but also to different assessments of which inputs are more ordered than others.

Further dimensions can be found in, for example.

Overview

The running time is not specified as a function of the measure of order for all of the algorithms listed here. However, one has the hope that in cases of great order in the input the running time of these algorithms is still close to the best case.

Sorting process	running time
A-Sort	${\ displaystyle O \ left (n \ log \ left ({\ frac {\ operatorname {Inv} (X)} {n}} \ right) + n \ right)}$ (optimal)
Adaptive heap sort	${\ displaystyle O \ left (n \ log \ left ({\ frac {\ operatorname {Inv} (X)} {n}} \ right) + n \ right)}$
AVL Sort	${\ displaystyle O \ left (n \ log \ left ({\ frac {\ operatorname {Inv} (X)} {n}} \ right) + n \ right)}$
Natural merge sort	${\ displaystyle \ Theta (n \ log (\ operatorname {Runs} (X)))}$
Solitaire sorting	Best case:, with sorted input. Average case ${\ displaystyle O (n)}$ ${\ displaystyle O (n \ log n)}$
Randomized quicksort	${\ displaystyle O \ left (n \ log \ left ({\ frac {\ operatorname {Inv} (X)} {n}} \ right) + n \ right)}$
Shellsort	Best case:, with sorted input. Average case not in . ${\ displaystyle O (n \ log n)}$ ${\ displaystyle O (n \ log n)}$
Smoothsort	${\ displaystyle O (n)}$ for sorted entries. Not achieved . Worst case: ${\ displaystyle O \ left (n \ log \ left ({\ frac {\ operatorname {Inv} (X)} {n}} \ right) + n \ right)}$ ${\ displaystyle O (n \ log n)}$
Splaysort	In experiments from a certain order in the input is faster than Randomized Quicksort and AVL Sort.
Straight insertion sort	${\ displaystyle \ Theta (n + \ operatorname {Inv} (X))}$
Timsort	${\ displaystyle O (n + n \ log \ operatorname {Runs} (X))}$ . Worst case: ${\ displaystyle O (n \ log n)}$

A-Sort

Uses AVL trees in which the elements are stored and removed in sorted order.

Adaptive heap sort

Uses a Cartesian tree into which the elements are inserted and then removed again in sorted order.

AVL Sort

Uses AVL trees .

Natural merge sort

Natural Mergesort does not use single-element subsequences as the starting point for the merge operations, but the runs already present in the input (see above). If the largest element of one partial sequence is smaller than the smallest of the second partial sequence, the merge operation can be replaced by a corresponding concatenation of the two partial sequences.

Solitaire sorting

Solitaire sorting has two phases. In the first phase, runs are created (see above): each element is either added to the end of a run that has already been created, or, if there is no run that allows this, creates a new run. In the second phase, k-way shuffling is applied to the runs to get a sorted sequence.

Example:

step	input ${\ displaystyle X}$	Runs
0	${\ displaystyle (3,5,4,2,1,7,6,8,9,10)}$	${\ displaystyle \ emptyset}$
1	${\ displaystyle (5,4,2,1,7,6,8,9,10)}$	${\ displaystyle (3)}$
2	${\ displaystyle (4,2,1,7,6,8,9,10)}$	${\ displaystyle (3.5)}$
3	${\ displaystyle (2,1,7,6,8,9,10)}$	${\ displaystyle (3.5), (4)}$
4th	${\ displaystyle (1,7,6,8,9,10)}$	${\ displaystyle (3.5), (4), (2)}$
5	${\ displaystyle (7,6,8,9,10)}$	${\ displaystyle (3.5), (4), (2), (1)}$
6th	${\ displaystyle (6,8,9,10)}$	${\ displaystyle (3,5,7), (4), (2), (1)}$
7th	${\ displaystyle (8,9,10)}$	${\ displaystyle (3,5,7), (4,6), (2), (1)}$
8th	${\ displaystyle (9.10)}$	${\ displaystyle (3,5,7,8), (4,6), (2), (1)}$
9	${\ displaystyle (10)}$	${\ displaystyle (3,5,7,8,9), (4,6), (2), (1)}$
10	${\ displaystyle \ emptyset}$	${\ displaystyle (3,5,7,8,9,10), (4,6), (2), (1)}$

Randomized quicksort

In the randomized quicksort algorithm, the pivot element is chosen randomly evenly distributed .

Shellsort

Shell sort repeatedly divides the input into disjoint subsequences, the elements of which are regularly spaced in the input, and sorts these subsequences. With each repetition, the distance between the elements is reduced, the partial sequences become longer, until in the last step the entire data is sorted with distance 1. Based on insertion location .

Smoothsort

Uses binary trees .

Splaysort

Uses splay trees .

Straight Insertion Sort

Straight Insertion Sort is a variation of the insertion site , see below.

Timsort

Timsort is based on Natural Mergesort and Insertionsort .

Other algorithms with adaptive properties

Bubblesort , comb sort , insertion sort .

example

Straight Insertion Sort

Straight Insertion Sort is a modification of Insertion Sort . The difference between Insertion Sort and Straight Insertion Sort is that with Insertion Sort, the order in which the already sorted array is run through can be selected as desired, while with Straight Insertion Sort you have to search from the largest index to the smallest. In the case of almost sorted input, the while loop is seldom executed.

Straight Insertion Sort (Array X der Länge n)
for j:= 2 to n do
   t := X[j]
   i := j
   while i > 1 & X[i - 1] > t do
      X[i] := X[i - 1]
      i := i - 1
   end
   X[i] := t
end

Straight Insertion Sort maturity is in . Straight Insertion Sort thus has the minimum runtime on an input that has already been sorted ; To check a list for sorting, each element must be examined at least once. ${\ displaystyle \ Theta (n + \ operatorname {Inv} (X))}$ ${\ displaystyle \ Theta (n)}$

Outlook: AdaSort

None of the known adaptive sorting algorithms is faster than all others in all cases. The runtime of the algorithms depends heavily on the input due to their adaptivity, and so in some cases one algorithm is faster, in others the other. Which algorithm is the fastest for an input is only known after it has been executed.

However, it is possible to estimate the runtimes in advance and to select the algorithm with the lowest estimated runtime, in the hope that this is actually the fastest algorithm for the input. In this way, an algorithm can be constructed from the known algorithms which sorts all inputs that lead to a good estimate of the transit times as quickly as the fastest algorithm in each case, but with the additional effort for the transit time estimates. This estimation can be carried out using machine learning methods.

In, the machine learning process was trained in such a way that it selects a sorting algorithm depending on two parameters, RUNS and n . It is

{\ displaystyle \ operatorname {RUNS} (X) = {\ frac {\ operatorname {Runs} (X)} {| X |}}}

.

Once the decision limits have been learned, there is no need to execute the machine learning method for the estimation; a decision tree is sufficient. This complex tree has been reduced even further. The result of S. Majumdar, I. Jain and K. Kukreja looks like this:

AdaSort(Array X der Länge n)
if n <= 100
   runs := computeRUNS(X)

   if runs > 0.68799
      ShellSort(X)
   else if n <= 50 & runs > 0.44
      parallelMergeSort(X, p)
   else if n <= 50 & runs > 0.25388
       MergeSort(X)
   else
       InsertionSort(X)
   end
else if n <= 1000
    QuickSort(X)
else if n <= 500000
    ParallelMergeSort(X, p)
else
    ParallelQuickSort(X, p)
end

Final experiments show that AdaSort reliably selects the fastest algorithm and is on average only a few microseconds slower than the fastest sorting algorithm. These experiments were, however, adapted to the decision limits for n in the algorithm , and restricted to inputs with almost no order . Since the machine learning method has also only learned for these n decision limits, it is not clear how good AdaSort is compared to other algorithms for, for example , runs with an average length of . It can be assumed that for general and greater order in the inputs, other decision limits can be found for other algorithms with which AdaSort also achieves a better average runtime in these cases. ${\ displaystyle n \ in \ {50,100,1000,10000,100000,500000,1000000 \}}$ ${\ displaystyle \ operatorname {RUNS} (X) \ approx 0.8}$ ${\ displaystyle n = 357211, RUNS = 0.001}$ ${\ displaystyle \ approx 357}$ ${\ displaystyle \ approx 1000}$ ${\ displaystyle n}$

Individual evidence

^ ^A ^b O. Petersson, A. Moffat: A framework for adaptive sorting. 1992, pp. 155 + 156.
^ V. Estivill-Castro, D. Wood: A Survey of Adaptive Sorting Algorithms. 1992, I.2.
↑ K. Mehlhorn: Sorting Presorted files. 1978, p. 11.
^ ^A ^b ^c O. Petersson, A. Moffat: A framework for adaptive sorting. 1992, p. 165.
^ G. Stolting, Chapman & Hall / CRC Computer and Information Science Series. Handbook of Data Structures and Applications , 2005, pp. 11-8.
↑ ^a ^b S. Edelkamp, A. Elmasry, J. Katajainen. Two Constant-Factor-Optimal Realizations of Adaptive Heapsort , 2011, p. 3.
↑ ^a ^b A. Elmasry. Adaptive sorting with AVL trees. , 2004, p. 309.
↑ ^a ^b Natural Mergesort. In: FH Flensburg. Retrieved July 20, 2019 .
↑ ^a ^b Patience is a Virtue: Revisiting Merge and Sorton Modern Processors. Retrieved July 30, 2019 .
↑ G. Brodal, R. Fagerberg and G. Moruz. On the adaptiveness of quicksort. , 2005, p. 3.
^ ^A ^b C. Plaxton, B. Poonen, T. Suel, Improved Lower Bounds for Shellsort. 1992, p. 9.
↑ ^a ^b Smoothsort's behavior on presorted sequences. Retrieved July 30, 2019 .
↑ ^a ^b A. Elmasry, A. Hammad. An Empirical Study for Inversions-Sensitive Sorting Algorithms. , 2005, p. 597.
↑ N. Auger, V. Jugé, C. Nicaud, C. Pivoteau. On the Worst-Case Complexity of TimSort. , 2012, p. 4: 8.
↑ ^a ^b N. Auger, V. Jugé, C. Nicaud, C. Pivoteau. On the Worst-Case Complexity of TimSort. , 2012, p. 4: 4.
↑ K. Mehlhorn: Sorting Presorted files. 1978, p. 14.
^ S. Majumdar, I. Jain, K. Kukreja AdaSort: Adaptive Sorting using Machine Learning. 2016.

[Petersson155-1] A ^b O. Petersson, A. Moffat: A framework for adaptive sorting. 1992, pp. 155 + 156.

[2] V. Estivill-Castro, D. Wood: A Survey of Adaptive Sorting Algorithms. 1992, I.2.

[3] K. Mehlhorn: Sorting Presorted files. 1978, p. 11.

[Peterson165-4] A ^b ^c O. Petersson, A. Moffat: A framework for adaptive sorting. 1992, p. 165.

[5] G. Stolting, Chapman & Hall / CRC Computer and Information Science Series. Handbook of Data Structures and Applications , 2005, pp. 11-8.

[ConstantFactor-6] S. Edelkamp, A. Elmasry, J. Katajainen. Two Constant-Factor-Optimal Realizations of Adaptive Heapsort , 2011, p. 3.

[AVL-7] A. Elmasry. Adaptive sorting with AVL trees. , 2004, p. 309.

[Flensburg-8] Natural Mergesort. In: FH Flensburg. Retrieved July 20, 2019 .

[Patience-9] Patience is a Virtue: Revisiting Merge and Sorton Modern Processors. Retrieved July 30, 2019 .

[10] G. Brodal, R. Fagerberg and G. Moruz. On the adaptiveness of quicksort. , 2005, p. 3.

[shellsort-11] A ^b C. Plaxton, B. Poonen, T. Suel, Improved Lower Bounds for Shellsort. 1992, p. 9.

[hertel-12] Smoothsort's behavior on presorted sequences. Retrieved July 30, 2019 .

[inversionsensitive-13] A. Elmasry, A. Hammad. An Empirical Study for Inversions-Sensitive Sorting Algorithms. , 2005, p. 597.

[14] N. Auger, V. Jugé, C. Nicaud, C. Pivoteau. On the Worst-Case Complexity of TimSort. , 2012, p. 4: 8.

[Tim-15] N. Auger, V. Jugé, C. Nicaud, C. Pivoteau. On the Worst-Case Complexity of TimSort. , 2012, p. 4: 4.

[16] K. Mehlhorn: Sorting Presorted files. 1978, p. 14.

[17] S. Majumdar, I. Jain, K. Kukreja AdaSort: Adaptive Sorting using Machine Learning. 2016.