Shell sort in C\C++ (Algorithm, Pseudocode and output)

Shell Sort

 Hy guys welcome to another tutorial of Sorting Algorithms. In this tutorial you will learn about shell sort and it's programs both in C and c++

Shell sort is a highly efficient sorting algorithm and is based on insertion sort algorithm. This algorithm avoids large shifts as in case of insertion sort, if the smaller value is to the far right and has to be moved to the far left. Shell short is an improved and efficient version of Insertion Sort rather while compared with other Sorting Techniques like Merge Sort , Bubble Sort and Selection Sort which we have already discussed earlier. In this algorithm we sort the pair of elements that are far apart by gap h. The process is repeated by reducing h until it becomes 1.

This algorithm uses insertion sort on a widely spread elements, first to sort them and then sorts the less widely spaced elements. This spacing is termed as an interval. This interval is calculated based on Knuth's formula given bellow:

Knuth's Formula

h = h * 3 + 1
where −
   h is interval with initial value 1

This algorithm is quite efficient for medium-sized data sets as its average and worst-case complexity of this algorithm depends on the gap sequence the best known is Ο(n), where n is the number of items. And the worst case space complexity is O(n).

How Shell Sort Works?

Let us consider the following example to have the idea of how shell sort works. We will take the same array we have used in our previous examples. For our example and ease of understanding, we take the interval of 4. Now make a virtual sub-list of all values located at the interval of 4 positions. Here these values are {35, 14}, {33, 19}, {42, 27} and {10, 44}

Now we will compare values in each sub-list and swap them (if necessary) in the original array. After this step, the new array should look like this -

Then, we take interval of 1 and this gap generates two sub-lists - {14, 27, 35, 42}, {19, 10, 33, 44}

We compare and swap the values, if required, in the original array. After this step, the array should look like this −

Finally, we sort the rest of the array using interval of value 1. Shell sort uses insertion sort to sort the array.

Following is the step-by-step depiction −

We see that it required only four swaps to sort the rest of the array.

Algorithm

Following is the algorithm 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

Pseudocode

 

Following is the pseudocode 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

 

Program for Shell Sort in C

 

  

#include <stdio.h>

void sort(int a[],int n)


{


    int gap,i,j,temp;


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


    {


        for(i=gap;i=gap&&a[j-gap]>temp;j-=gap)


                a[j]=a[j-gap];            


            a[j]=temp;


        }


    }


}


int main()


{


    int a[20],i,n;

    printf("Enter number of elements:");


    scanf("%d",&n);

    printf("Enter array elements:\n");


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

     
    printf("%d ",a[i]);
 
    return 0;
}

 

Output

Enter number of elements: 5                                                                                                     
Enter array elements:                                                                                                           
22                                                                                                                              
33                                                                                                                              
46                                                                                                                              
72                                                                                                                              
66                                                                                                                              
                                                                                                                                
Array after shell sort:                                                                                                         
22 33 46 66 72

 

Program for Shell Sort in C++ 

 

  
#include <iostream> 
using namespace std;


void sort(int a[],int n)

{
    int gap,i,j,temp;

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

    {
        for(i=gap;i=gap&&a[j-gap]>temp;j-=gap)

                a[j]=a[j-gap];

            a[j]=temp;

        }

    }

}


int main()

{

    int a[20],i,n;   

    cout<<"Enter number of elements:";

    cin>>n;

    cout<<"Enter array elements:\n";

    for(i=0;i>a[i];

    sort(a,n);

    cout<<"\nArray after shell sort:\n";

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

     
    cout<<a[i]<<" ";


    return 0;

}

Output

 

Enter number of elements: 5                                                                                                     
Enter array elements:                                                                                                           
56                                                                                                                              
7                                                                                                                              
2                                                                                                                              
9                                                                                                                              
12                                                                                                                              
                                                                                                                                
Array after shell sort:                                                                                                         
2 7 9 12 56 

So this is it guys if you want us to write more on this topic or have any particular Query regarding this post you can always comment or feel free to mail us at our official mail also follow us on Instagram and Facebook to receive Latest Updates first.

Peace!!!