Array - XII [ Shell Sort ]

Shell Sort Shellsorts largely a deviation of Insertion Sort, it is also one of the oldest sorting algorithms. Shellsort is named after its inventor Donald Shell. It is fast, easy to understand and easy to implement. In Insertion sort an elements only move by one position in front. When an element has to be moved far-off, it requires to move many times. ShellSort allows swapping of far items. Its complexity is a little more complicated. The running time of Shellsort is greatly dependent on the gap sequence it uses.

Complexity :

---

Worst case performance              O(n^2)

Best case performance                O(N)

Average case performance           depends on gap sequence

---

Algorithm.

---

function shellsort(int arr[],int n)

           int last,tmp,limit,temp,k

           int mid=n/2

           while mid>0

              do

                   last=0;

                   limit=n-mid;

                   while last==0

                        do

                            tmp=0;

                            for k=0 to limit-1 step 1

                                do

                                      if arr[k]>arr[k+mid]

                                                then

                                                          temp=arr[k]

                                                          arr[k]=arr[k+mid]

                                                          arr[k+mid]=temp

                                                          tmp=k

                                                endif

                                endfor

                            limit=tmp-mid

                            if tmp==0 then

                                then

                                      last=1

                                endif

                        enddo

                   mid=mid/2

              enddo

      end

---

Source Code

---

import java.io.*;

class Shell_Sort

{

  void shellsort(int Arr[],int n)

      {

         int i, k, j,mid, temp ;

         for (mid = n / 2; mid > 0; mid /= 2)

            {

                for (i = mid; i < n; i++)

                    {

                         temp = Arr[i];

                         for (j = i; j >= mid; j -= mid)

                             {

                                 if (temp < Arr[j - mid])

                                     {

                                          Arr[j] = Arr[j - mid];

                                     }

                                 else

                                     {

                                          break;

                                     }

                               }

                         Arr[j] = temp;

                    }

             }

      }

  void Display(int Arr[],int n)

     {

          int i;

          for(i=0;i<n ;i++)

              {

                   System.out.print(Arr[i]+"  ");

              }

     }

  public static void main(String args[])throws IOException

      {

           BufferedReader Br = new BufferedReader(new InputStreamReader(System.in));

           int i;

           Shell_Sort S=new Shell_Sort();

           int Arr[],n;

           System.out.print("\n\tEnter Size of Array below 20 : ");

           n=Integer.parseInt(Br.readLine());

           Arr=new int[n];

           for(i=0;i<n; i++)

              {

                   System.out.print("\n\tEnter Array Element at  : "+i+" -> ");

                   Arr[i]=Integer.parseInt(Br.readLine());;

              }

           System.out.print("\n\tOriginal Array :  ");

           S.Display(Arr,n);

           S.shellsort(Arr,n);

           System.out.print("\n\tAfter Sort     :  ");

           S.Display(Arr,n);

      }

    }