Adaptive sort
Encyclopedia
A sorting algorithm
falls into the adaptive sort family if it takes advantage of existing order in its input. It benefits from the presortedness in the input sequence – or a limited amount of disorder
for various definitions of measures of disorder – and sorts faster. Adaptive sorting is usually performed by modifying existing sorting algorithms.
have traditionally dealt with achieving an optimal bound of O
(n logn) when dealing with time complexity
. Adaptive sort takes advantage of the existing order of the input to try to achieve better times, so that the time taken by the algorithm to sort is a smoothly growing function of the size of the sequence and the disorder in the sequence. In other words, the more presorted the input is, the faster it should be sorted.
This is an attractive algorithm because nearly sorted sequences are common in practice. Thus, the performance of existing sort algorithms can be improved by taking into account the existing order in the input.
Note that the most worst-case sorting algorithms that do optimally well in the worst-case, notably heap sort and merge sort
, do not take existing order within their input into account, although this deficiency is easily rectified in the case of merge sort
by checking if left.last_item ≤ right.first_item, in which case a merge operation may be replaced by simple concatenation – a modification that is well within the scope of making an algorithm adaptive.
In pseudo-code form, the Straight Insertion Sort algorithm could look something like this:
procedure Straight Insertion Sort (X, n):
X[0] := − ∞;
for j := 2 to n do
begin i := j − 1;
t := X[j];
while t < X[i] do
begin X[i + 1] := X[i];
i := i - 1
end;
X[i + 1] := t;
end;
The performance of this algorithm can be described in terms of the number of inversions in the input, and then T(n) will be roughly equal to I(A) + (n - 1), where I(A) is the number of Inversions. Using this measure of presortedness – being relative to the number of inversions – Straight Insertion Sort takes less time to sort the closer it is to being sorted.
Other examples of adaptive sorting algorithms are Adaptive Heap-Sort
and Adaptive Merge-Sort. Dijkstra’s Smoothsort
algorithm is a variation on heap-sort that is also considered an adaptive sorting algorithm.
Timsort
, used as the generic sorting algorithm for several programming languages including Python, is adaptive.
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...
falls into the adaptive sort family if it takes advantage of existing order in its input. It benefits from the presortedness in the input sequence – or a limited amount of disorder
Randomness
Randomness has somewhat differing meanings as used in various fields. It also has common meanings which are connected to the notion of predictability of events....
for various definitions of measures of disorder – and sorts faster. Adaptive sorting is usually performed by modifying existing sorting algorithms.
Motivation
Comparison-based sorting algorithmsComparison sort
A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation that determines which of two elements should occur first in the final sorted list...
have traditionally dealt with achieving an optimal bound of O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(n logn) when dealing with time complexity
Time complexity
In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and...
. Adaptive sort takes advantage of the existing order of the input to try to achieve better times, so that the time taken by the algorithm to sort is a smoothly growing function of the size of the sequence and the disorder in the sequence. In other words, the more presorted the input is, the faster it should be sorted.
This is an attractive algorithm because nearly sorted sequences are common in practice. Thus, the performance of existing sort algorithms can be improved by taking into account the existing order in the input.
Note that the most worst-case sorting algorithms that do optimally well in the worst-case, notably heap sort and merge sort
Merge sort
Merge sort is an O comparison-based sorting algorithm. Most implementations produce a stable sort, meaning that the implementation preserves the input order of equal elements in the sorted output. It is a divide and conquer algorithm...
, do not take existing order within their input into account, although this deficiency is easily rectified in the case of merge sort
Merge sort
Merge sort is an O comparison-based sorting algorithm. Most implementations produce a stable sort, meaning that the implementation preserves the input order of equal elements in the sorted output. It is a divide and conquer algorithm...
by checking if left.last_item ≤ right.first_item, in which case a merge operation may be replaced by simple concatenation – a modification that is well within the scope of making an algorithm adaptive.
Examples
A classic example of an adaptive sorting algorithm is Straight Insertion Sort. In this sorting algorithm, we scan the input from left to right, repeatedly finding the position of the current item, and insert it into an array of previously sorted items.In pseudo-code form, the Straight Insertion Sort algorithm could look something like this:
procedure Straight Insertion Sort (X, n):
X[0] := − ∞;
for j := 2 to n do
begin i := j − 1;
t := X[j];
while t < X[i] do
begin X[i + 1] := X[i];
i := i - 1
end;
X[i + 1] := t;
end;
The performance of this algorithm can be described in terms of the number of inversions in the input, and then T(n) will be roughly equal to I(A) + (n - 1), where I(A) is the number of Inversions. Using this measure of presortedness – being relative to the number of inversions – Straight Insertion Sort takes less time to sort the closer it is to being sorted.
Other examples of adaptive sorting algorithms are Adaptive Heap-Sort
Adaptive heap sort
The adaptive heap sort is a sorting algorithm that is similar to heap sort, but uses a randomized binary search tree to structure the input according to any preexisting order. The randomized binary search tree is used to select candidates that are put into the heap, so the heap doesn't need to...
and Adaptive Merge-Sort. Dijkstra’s Smoothsort
Smoothsort
Smoothsort is a comparison-based sorting algorithm. It is a variation of heapsort developed by Edsger Dijkstra in 1981. Like heapsort, smoothsort's upper bound is O...
algorithm is a variation on heap-sort that is also considered an adaptive sorting algorithm.
Timsort
Timsort
Timsort is a hybrid sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was invented by Tim Peters in 2002 for use in the Python programming language. The algorithm is designed to find subsets of the data which are already...
, used as the generic sorting algorithm for several programming languages including Python, is adaptive.