C program function Double Insertion Sort is a variation on I

C++ program/ function

Double Insertion Sort is a variation on Insertion Sort that works from the middle of the array out. At each iteration, some middle portion of the array is sorted. On the next iteration, take the two adjacent elements to the sorted portion of the array. If they are out of order with respect to each other, then swap them. Now, push the left element toward the right in the array so long as it is greater than the element to its right. And push the right element toward the left in the array so long as it is less than the element to its left. The algorithm begins by processing the middle two elements of the array if the array is even. If the array is odd, then skip processing the middle item and begin with processing the elements to its immediate left and right. First, explain what the cost of Double Insertion Sort will be in comparison to standard Insertion sort, and why. (Note that the two elements being processed in the current iteration, once initially swapped to be sorted with respect to each other, cannot cross as they are pushed into sorted position.) Then, implement Double Insertion Sort, being careful to properly handle both when the array is odd and when it is even. Compare its running time in practice against standard Insertion Sort.

Solution

a ) there is a procedure to find the time complexity of the program .

first find the number of \"for loops\" are in the program and find how mant times those are executing.

secondly write all as the sum .

finally the largest one is the time complexity of the given program.

b) I have executed it under dev c++ and did for even only and later i will repost with odd one aslo.

#include <iostream>
using namespace std;
/* run this program using the console pauser or add your own getch, system(\"pause\") or input loop */

int main(int argc, char** argv) {
   int arr[20],i,j,n,k,temp;
   static int mid;
   cout << \"\\t\\tWelcome to Double Insertion Sort\ \";
   cout << \"Enter size of array:\\t\";
   cin >> n;
   cout << \"Enter array elements:\ \";
   for(i=0;i<n;i++){
       cin >> arr[i];
   }
   mid = n/2;
   cout << \"mid =\" << mid << \"\ \";
   int middle = mid;
   if(n % 2 == 0){
       cout << \"EVEN array :\ \";      
               static int m = middle-1;
       for(k=0;k<n/2;k++){
         
               for(i=m;i>=0;i--){ // one element left to the middle
                   for(j=mid;j<n;j++){ // one element which is middle.
                       if(arr[i] >= arr[j]){ // to sort in increasing order
                       //swap two elements
                           temp=arr[i];
                           arr[i] = arr[j];
                           arr[j] = temp;
                       }
                       else
                           break;
                      
                       for(j=middle;j<n;j++){ //right side
                           if(arr[j] >= arr[j+1]){
                             
                              temp = arr[j];
                               arr[j] = arr[j+1];
                               arr[j+1] = temp;
                           }
                       }
                      
                   break;
                   }
                  
                  
                   for(i=middle-1;i>=0;i--){//left side
                           if(arr[i] <= arr[i-1]){
                              temp = arr[i];
                               arr[i] = arr[i-1];
                               arr[i-1] = temp;
                           }
                  
                   }
                  
                   break;
               }
               cout << \"\ \";
          
       }
   }

   cout << \"Array after sort:\ \";
   for(i=0;i<n;i++){
       cout << arr[i] << \"\\t\" ;
   }
   return 0;
}