Shellsort
Shellsort is a sorting method developed by Donald L. Shell in 1959 , which is based on the sorting method of direct insertion ( insertion sort ).
principle
In principle, Shellsort uses the insertion point. It tries to compensate for the disadvantage that here elements in the sequence often have to be moved over long distances. This makes insertion sorting inefficient. Shellsort follows the approach that the sequence is first broken down into individual sub-sequences and these are sorted. The division takes place in a different number in each step. The elements are not copied over for the division, but the elements have a certain constant distance from one another. For example, factor 4 means division into 4 sub-sequences, the elements of which are formed from the original sequence by spacing 4, i.e. indices 0, 4, 8 ... forms one sub-sequence, indices 1, 5, 9 ... another. Once the sorting step has been completed, the sequence is then called 4-sorted. The entire shell sort then leads, for example, to a sequence that is first 4-sorted, then 2-sorted, and finally 1-sorted, so to speak, with the normal insertion sort.
This could be illustrated clearly using auxiliary matrices (see example):
- The data are written line by line in a k-column matrix
- The columns of the matrix are sorted individually
This results in a rough sorting. This step is repeated several times, the width of the matrix being reduced in each case until the matrix only consists of a single, completely sorted column.
Important: An a * b-sorted sequence is not automatically a-sorted or b-sorted! To prove this, we consider a sequence of the numbers 1 to 12. This is 6-sorted if we follow any permutation of the numbers 1 ... 6 with any permutation of the numbers 7 ... 12. The permutation 6, 5, 4, 3, 2, 1 is by no means 2- or 3-sorted.
6, 5, 4, 3, 2, 1, 7, 8, 9, 10, 11, 12 ist 6-sortiert, aber nicht 2- und auch nicht 3-sortiert.
Shellsort works in-place , but is not one of the stable sorting algorithms. Because of the sorting over distance, the sorting method loses its “stable” property. Two adjacent and sorted elements end up in different sub-sequences and may be rearranged so that their order is reversed.
example
The numbers 2, 5, 3, 4, 3, 9, 3, 2, 5, 4, 1, 3 are to be sorted using the sequence
First the data is entered line by line in a matrix with four columns and sorted column by column. The sequence of numbers is thus 4-sorted.
2 5 3 4 2 4 1 2 3 9 3 2 → 3 5 3 3 5 4 1 3 5 9 3 4
The sorted four-column matrix is now divided into two columns, reading from left to right. These columns are now 2-sorted.
2 4 1 2 1 2 2 3 3 5 → 3 4 3 3 3 4 5 9 3 5 3 4 5 9
The sorted two-column matrix is now written in one line and sorted again using the normal insertion sort. The advantage here is that no element of the sequence has to be moved as far as with the insertion location, which is applied to a sequence that has not been pre-sorted.
1 2 2 3 3 4 3 4 3 5 5 9 → 1 2 2 3 3 3 3 4 4 5 5 9
The sequence of steps used here (as originally proposed by Shell in 1959) does not prove to be useful in practice, since only even positions are sorted and odd positions in the sequence are only touched in the last step. 1,4,13,40 ... has proven to be more useful (value n = 3 × value n-1 +1).
implementation
Java 5
Shellsort is an improvement on the straight insertion algorithm. There the elements move into their place in single steps: After finding the smallest element, the ones in between are pushed up one by one and only the smallest "jumps". Most (i.e., n) elements are pushed from their original place to their final place in an average of n / 3 steps.
With the shell sort one introduces decreasing step sizes k [1], k [2]… k [t], whereby the last step size is always k [t] = 1. T steps are carried out one after the other; in the m-th step, the elements jump in the direction of their future place by k [m] places. In the first step, those elements are sorted among themselves which are k [1] places apart; then those that are a distance k [2] from one another, etc. The effect of this procedure is that the elements “jump” to their place in the first pass, not one, but k [1] places.
The last step size k [t] is 1, i.e. H. Finally, a normal straight insertion sorting process is carried out. This guarantees that the sequence is sorted at the end. However, the algorithm hardly needs to do anything, as the previous steps have almost completely sorted the order.
The sorting effort can be significantly reduced by a suitable choice of the step sizes k [1], k [2] ... k [t]. For the step sizes (1, 3, 7, 15, 31 ...) it was proven (see Donald E. Knuth : The Art of Computer Programming ) that the time complexity of the algorithm n is 1.5 , which is clearly better than that quadratic complexity of bubble sort, insertion sort or selection sort , but (at least for very large amounts of data) worse than the complexity n log n of mergesort or heapsort .
static <E extends Comparable<? super E>> void shellSort(E[] sammlung, int[] schrittweiten) {
for (int schrittweite : schrittweiten) { // straight insertion mit schrittweite
for (int index = schrittweite; index < sammlung.length; index++){
E elementZumEinfuegen = sammlung[index];
int einfuegestelle = index;
while (einfuegestelle - schrittweite >= 0 &&
elementZumEinfuegen.compareTo(sammlung[einfuegestelle-schrittweite]) < 0) {
sammlung[einfuegestelle] = sammlung[einfuegestelle - schrittweite];
einfuegestelle -= schrittweite; // Sprung um schrittweite
}
sammlung[einfuegestelle] = elementZumEinfuegen;
}
}
}
Java
In fact, the data is not arranged in the form of a matrix, but in the form of a one-dimensional field. The columns are formed by clever indexing. So all elements at a distance h form a column. The columns are sorted by insertion location, as this algorithm can benefit from pre-sorting the data.
In the following program, the data is first arranged in h = 2147483647 columns, if that much data is available. If not, the for-i loop is skipped and continued with h = 1131376761 etc.
void shellsort (int[] a, int n)
{
int i, j, k, h, t;
int[] spalten = {2147483647, 1131376761, 410151271, 157840433,
58548857, 21521774, 8810089, 3501671, 1355339, 543749, 213331,
84801, 27901, 11969, 4711, 1968, 815, 271, 111, 41, 13, 4, 1};
for (k = 0; k < spalten.length; k++)
{
h = spalten[k];
// Sortiere die "Spalten" mit Insertionsort
for (i = h; i < n; i++)
{
t = a[i];
j = i;
while (j >= h && a[j-h] > t)
{
a[j] = a[j-h];
j = j - h;
}
a[j] = t;
}
}
}
Complexity and distance consequences
The complexity of Shellsort depends on the choice of the distance sequence for the number of columns h. For various consequences, upper limits of complexity have been proven, which thus provide an indication of the duration. Most of the theoretical work on the consequences regards only the number of comparisons as a major cost factor. However, real implementations show that the loops and copying actions also play a decisive role in non-huge arrays.
Originally Donald Shell proposed the series 1, 2, 4, 8, 16, 32…, 2 k . The performance is very bad, however, because the elements are only sorted into odd positions in the very last step. The complexity is very high.
With the sequence 1, 3, 7, 15, 31, 63…, 2 k - 1 by Hibbard, a complexity of is achieved.
With the sequence 1, 2, 3, 4, 6, 8, 9, 12, 16…, 2 p 3 q from Pratt, the complexity is .
Donald E. Knuth also did some episodes for Shellsort. A commonly used one in the literature is the following: 1, 4, 13, 40, 121, 364, 1093…, (3 k -1) / 2. The calculation rule for the same sequence is better known: 3h k-1 + 1. The complexity is .
Some good episodes are from Robert Sedgewick . The sequence 1, 8, 23, 77, 281, 1073, 4193, 16577…, 4 k + 1 + 3 * 2 k + 1 has reached complexity of . A much better sequence is the following: 1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929, 16001 ..., 9 * 2 k - 9 * 2 k / 2 + 1 (k even) or . 8 * 2 k - 6 * 2 (k + 1) / 2 + 1 (k odd)
If one considers purely geometric sequences, there is a minimum in the larger area of factor 2.3, i.e. H. the following members have the ratio of about 2.3. One of the theoretically best sequences (i.e. number of comparisons) determined experimentally by Marcin Ciura is 1, 4, 10, 23, 57, 132, 301, 701, 1750 and is based on this factor. Based on the factor 1750/701, the series is continued as follows: Let g be the last term, then the next one is given by 1 + floor (2.5 * g), i.e. 701, 1753, 4383, 10958, 27396, 68491 , 171228… A series by Gonnet and Baeza-Yates is based on a factor of 2.2, which gives very good results.
Amazingly, in practice better sequences than those of Marcin Ciura are known, which are calculated recursively. The runtime of the shell sort is shorter, although the number of comparisons is higher (elements to be sorted are integers in register width). Recursive sequences are calculated from integers, and the ratio of the following members converges to a certain value, for Fibonacci numbers it is the golden ratio .
Such a sequence is based on the Fibonacci numbers . One of the two 1's at the beginning is omitted and each number in the sequence is raised to the power of twice the golden ratio (approx. 3.236), which then leads to this distance sequence: 1, 9, 34, 182, 836, 4025, 19001, 90358, 428481 , 2034035 ...
Another recursive sequence was found by Matthias Fuchs. The sequence 1, 4, 13, 40, 124, 385, 1195, 3709, 11512, 35731 ... has a convergence value of approximately 3.103803402. The calculation rule is f k + 1 = 3 * f k + f k-2 , whereby the sequence starts initially with 1, 1, 1 and the first two 1's are omitted for the shell sort.
Other sequences are not constant, but are calculated from the current number of elements in the array. They are initialized with this number and decrease until they finally reach 1.
Robert Kruse: h k-1 = h k / 3 + 1
Gonnet and Baeza-Yates: h k-1 = (5 * h k - 1) / 11
Both episodes have a slightly worse performance than the two recursive episodes and the very good episodes of Sedgewick and that of Marcin Ciura. But they can be integrated directly into the shell sort algorithm.
The existence of a sequence with the complexity has already been ruled out in a work by Bjorn Poonen , Plaxton, and Suel. But it could be proven that in principle for sufficiently large n a sequence with a complexity of can always be found.
The search for an optimal sequence turns out to be extremely difficult. Gaps between the following elements that are too large result in shifts that are too large; gaps that are too narrow result in too many passes before the final sorting. When choosing a sequence, it is important to avoid that two successive terms of the sequence have common factors, since an a * b-sorted sequence and a subsequent a * c-sorting exclude certain sub-sequences from the sorting (see note on the original sequence 1, 2, 4, 8, 16 ..., which omits the odd ones and only takes them into account when sorting 1). This is definitely an advantage across several links.
A major advantage of the shell sort algorithm compared to others is that it can take advantage of already existing sorting. It is only of minor importance whether the array is sorted or inversely sorted. Both cases are times faster than a purely randomly sorted array. With only 65536 elements the speed advantage is approx. Factor 4, with 128 it is still more than factor 2.
Variations
Combsort works in a similar way to Shellsort. The column sorting is only sorted with one pass of Bubble Sort before the number of columns is reduced.
literature
- Donald L. Shell : A High-Speed Sorting Procedure. In: Timon N. Commun. ACM , 2 (7), 1959, pp. 30-32.
- Robert Sedgewick : Algorithms in Java , Part 1–4. Addison-Wesley, ISBN 0-201-36120-5