After experiencing the interview, I came back on 10th oct. But during my journey I kept thinking about data structures. I saw there lot of people discussing about data structures, although I had studied them but it didn’t remember the algorithms and work process they talked about. So I thought to have a look at them too.
After coming home I took 8-9 hours sound sleep. After that data structures and the interviewee’s most famous question that I heard i.e shell short and bubble sort were playing something in my mind till now.
Didn’t wait much googled out and started learning the concepts. I read about shell sort.
The idea of Shell-sort is the following:
arrange the data sequence in a two-dimensional array
sort the columns of the array
The effect is that the data sequence is partially sorted. The process above is repeated, but each time with a narrower array, i.e. with a smaller number of columns. In the last step, the array consists of only one column. In each step, the sortedness of the sequence is increased, until in the last step it is completely sorted. However, the number of sorting operations necessary in each step is limited, due to the pre-sortedness of the sequence obtained in the preceding steps.
We can find lot of examples for this sort.
Anyhow, the following algorithm explains the procedure for it.

void shell-sort (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;
         }
     }
 }
Advertisements