Mumbai University > Information Technology > Sem 3 > Data structure and algorithm analysis

Marks: 10M

Year: Dec 2015

Following are steps to be used for shell sort:

Step 1 − Initialize the value of h

Step 2 − Divide the list into smaller sub-list of equal interval h

Step 3 − Sort these sub-lists using insertion sort

Step 3 − Repeat until complete list is sorted

// algorithm for shell sort

procedure shellSort()
    A : array of items  
   /* calculate interval*/
   while interval  <  A.length /3  
do:
      interval = interval * 3 + 1       
   end while
   while interval  > 0 do:

      for outer = interval; outer < A.length; outer ++ do:

      /* select value to be inserted */
      valueToInsert = A[outer]
      inner = outer;

         /*shift element towards right*/
         while inner > interval -1 && A[inner - interval] >= valueToInsert do:
            A[inner] = A[inner - interval]
            inner = inner - interval
         end while

      /* insert the number at hole position */
      A[inner] = valueToInsert

      end for
   /* calculate interval*/
   interval = (interval -1) /3;   
   end while

end procedure