Page 245 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes After fi rst iteration

X=1 6 2 5 8 10 12 15 31 23
When the increment reduces to 3, you will get the following lists
(1, 5, 12, 23)
(6, 8, 15)
(2, 10, 31)
Now if we analyse the first sub lists where increment was 6 and then second sub lists where

increment was 3, we can see that in the second set of lists, we are comparing and sorting 1, 12
again which we had already sorted before in the previous sub list. So, we should choose the
value of K in such a way that in every iterations we get almost different elements in the sub lists
to compare and sort.

There are proven and recommended ways for generating the increment sequences.
Some of them have been discussed below.
Donald Shell has suggested
H = N/2
t
H = h /2
k k+1
Which give the increment series as: N/2, N/4, …….1
K
Hibbard suggested the sequence of increment as 1, 3, 7, …….2 -1.
Another way for calculating increment K suggested by Knuth and we have used this method for
generating the increments in this tutorial.
hi = 1
hi = hi* 3 +1 and stops at h , When h +2 >= N.
t t
Which gives the increment series as 1, 4, 13….. h .
t

Task Discuss insertion sorting techniques.

Other than these, there are many series which have been empirically found and perform well.

Example: We will take an example to illustrate Shell sort. Let the list be 8 2 84 6 12 5
76 9 13 67 54 0 43 20 -4 78 32 62 75 106 16 4 77 45 23 31 92 7 18 and the increment values using
Knuth formula we get are 13, 4, 1.
When increment is 13, we get the following 13 sub lists and the elements are divided among the
th
sub lists in the following ways i.e. every K element of the list starting with the index i will be in
the sub list i.

240 LOVELY PROFESSIONAL UNIVERSITY