Page 246 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 12: Sorting

Notes

After sorting the sub lists, the resulting list we get is as follows.
8 -4 18 6 12 5 76 9 4 67 45 0 31 20 2 78 32 62 75 106 16 13 77 54 23 43 92 7 84
You now, reduce the increment value to 4 and get the following 4 sub lists.

After sorting these sub lists, the resulting list is as follows:
4 -4 2 0 8 5 18 6 12 13 45 7 16 20 75 9 23 43 76 54 31 62 77 78 32 67 92 106 84
You further reduce increment value to 1, which is our last increment value. Now there is only one
list, which after sorting, we get:

–4 0 2 4 5 6 7 8 9 12 13 16 18 20 23 31 32 43 45 54 62 67 75 76 77 78 84 92 106
Now try to understand and analyse what is happening? How the elements are moved? We can
see, after the first iteration when the increment was 13, the element –4 of the list, which was

nd
at 15th position in the original list has reached to the 2 position. The element 18 was at 29th
position and has reached the 3rd position. Using insertion sort on the whole list, we know that
if –4 has to reach from the 15th position to the 2nd position, the required number of movements
of the elements in the list will be very high. Shell Sort performs better than insertion sort by
reducing the number of movements of elements in the lists. This is achieved by large strides the
element take in the beginning cycle.

Upper Bound

Theorem: With the h-sequence 1, 3, 7, 15, 31, 63, 127, ..., 2 – 1, ... Shellsort needs O(n• n) steps for
k
sorting a sequence of length n (Papernov/Stasevic [PS 65]).
Proof: Let h be the h closest to n. We analyze the behavior of Shellsort separately for the elements
t
h with k ≤ t and with k > t.
k
k
Let k ≤ t. Since h = 2 – 1 we have the conditions mentioned above that h and h are relatively
k k+1 k+2
prime and in O(h ). Therefore, O(n⋅h ) sorting steps suffice for h -sorting the data sequence. Since

k k k
LOVELY PROFESSIONAL UNIVERSITY 241