home | alphabetical index | |||||

## Shell sort
Shell sort is really just an extension of insertion sort, with two observations in mind: - Insertion sort is efficient if the input is almost sorted.
- Insertion sort is inefficient, on average, because it moves values just one position at a time.
Consider a small value that is initially stored in the wrong end of the array. Using insertion sort, it will take roughly The idea of Shell sort can be illustrated in the following way: - arrange the data sequence in a two-dimensional array
- sort the columns of the array
3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2be the data sequence to be sorted. First, it is arranged in an array with 7 columns (left), then the columns are sorted (right): 3 7 9 0 5 1 6 3 3 2 0 5 1 5 8 4 2 0 6 1 5 -> 7 4 4 0 6 1 6 7 3 4 9 8 2 8 7 9 9 8 2Data elements 8 and 9 have now already come to the end of the sequence, but a small element (2) is also still there. In the next step, the sequence is arranged in 3 columns, which are again sorted: 3 3 2 0 0 1 0 5 1 1 2 2 5 7 4 3 3 4 4 0 6 -> 4 5 6 1 6 8 5 6 8 7 9 9 7 7 9 8 2 8 9Now the sequence is almost completely sorted. When arranging it in one column in the last step, it is only a 6, an 8 and a 9 that have to move a little bit to their correct position. Actually, the data sequence is not arranged in a two-dimensional array, but held in a one-dimensional array that is indexed appropriately. For instance, data elements at positions 0, 5, 10, 15 etc. would form the first column of an array with 5 columns. The "columns" obtained by indexing in this way are sorted with Insertion sort, since this method has a good performance with presorted sequences.
The following program sorts an array a from index position 0 through The following Java program implements Shell sort.
void shellsort (int[] a, int n) {The correctness of the algorithm follows from the fact that in the last step (withint i, j, k, h, v; int[] cols= {1391376, 463792, 198768, 86961, 33936, 13776, 4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1}; for (k=0; k<16; k++) { h=cols[k]; for (i=h; i} h = 1) an ordinary Insertionsort is performed on the whole array. But since data are presorted by the preceding steps (h = 3, 7, 21, ...) only few Insertionsort steps are sufficient. How many exactly depends on the sequence of h's (denoted as h-sequence). The h-sequence above is just one of several possible.
With the
With the
Thus it requires fewer than O( ## References[Se] R. Sedgewick: Algorithms. Addison-Wesley (1988)[Sh] D.L. Shell: A high-speed sorting procedure. Communications of the ACM 2 (7), 30-32 (1959) ## External link | |||||

copyright © 2004 FactsAbout.com |