Program to compare shell and insertion sort methods.

   

#include < iostream >
#include < iomanip >
 
using namespace std;
int insertcount=0;
int shellcount=0;
int shellSort(int arr[], int n) 
{ 
    // Start with a big gap, then reduce the gap 
    for (int gap = n/2; gap > 0; gap /= 2) 
    { 
        // Do a gapped insertion sort for this gap size. 
        // The first gap elements a[0..gap-1] are already in gapped order 
        // keep adding one more element until the entire array is 
        // gap sorted  
        for (int i = gap; i < n; i += 1) 
        { 
            // add a[i] to the elements that have been gap sorted 
            // save a[i] in temp and make a hole at position i 
            int temp = arr[i]; 
  
            // shift earlier gap-sorted elements up until the correct  
            // location for a[i] is found 
            int j;             
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) 
                arr[j] = arr[j - gap]; 
              
            //  put temp (the original a[i]) in its correct location 
            arr[j] = temp; 
        } 
shellcount++;
    } 
    return 0; 
} 
 

void insertionSort(int arr[], int n) 
{ 
    int i, key, j; 
    for (i = 1; i < n; i++)
    { 
        key = arr[i]; 
        j = i - 1; 
 
        /* Move elements of arr[0..i-1], that are 
        greater than key, to one position ahead 
        of their current position */
        while (j >= 0 && arr[j] > key)
        { 
            arr[j + 1] = arr[j]; 
            j = j - 1; 
        } 
        arr[j + 1] = key; 
insertcount++;
    } 
} 


int main()
{
  

   int arr[] = { 12, 11, 13, 5, 6 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 



 
cout<< "Shell sort "<< endl;
    shellSort(arr, n); 
    


 

cout<< endl<<"Time :" << shellcount<< endl;


cout<< endl<< endl;

cout<< "Insertion Sort"<< endl;
     insertionSort(arr, n);
   

    cout<< endl<<"Time :" << insertcount<< endl;
 cout<< endl;

return 0;
}