Page 243 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes Shell Sort improves the efficiency and decreases the run time complexity to O(N 1.25 ). Donald Shell

discovered the Shell sort and thence it is known as Shell Sort.

Algorithm

The algorithms for shell sort can be defined in two steps:

Step 1: Divide the original list into smaller lists.
Step 2: Sort individual sub lists using any known sorting algorithm (like bubble sort, insertion
sort, selection sort, etc).

void shellsort (int[] a, int n)
{
int 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<n; i++)
{
v=a[i];
j=i;
while (j>=h && a[j-h]>v)
{
a[j]=a[j-h];
j=j-h;
}
a[j]=v;
}
}
}
Many questions arise

1. How should I divide the list?
2. Which sorting algorithm to use?
3. How many times I will have to execute steps 1 and 2?
4. And the most puzzling question if I am anyway using bubble, insertion or selection sort
then how I can achieve improvement in efficiency? I shall discuss each of these questions

one by one.
For dividing the original list into smaller lists, we choose a value K, which is known as increment.
Based on the value of K, we split the list into K sub lists. For example, if our original list is
x[0], x[1], x[2], x[3], x[4]….x[99] and we choose 5 as the value for increment, K then we get the
following sub lists.
first_list = x[0], x[5], x[10], x[15]…….x[95]

238 LOVELY PROFESSIONAL UNIVERSITY