Question

c++ program that finds the total number of comparisons and total number of moves in insertion sort, bubble sort, selection sort, shell sort, quick sort and merge sort using the same array of numbers.

Answer 1

#include<iostream>
using namespace std;

int c_in=0,m_in=0;

//insertion sort
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)
{ c_in++;//counting comparisions
m_in++;//counting moves
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
//bubblesort
int c_b=0,m_b=0;
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n-1; i++)   
  
// Last i elements are already in place
for (j = 0; j < n-i-1; j++)
{ if (arr[j] > arr[j+1])
{ swap(&arr[j], &arr[j+1]);
           m_b++;//counting moves
       }
       c_b++;//counting comparisions
   }
}
//selection sort
int c_se=0,m_se=0;
void selectionSort(int arr[], int n)
{
int i, j, min_idx;
  
// One by one move boundary of unsorted subarray
for (i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
min_idx = i;
for (j = i+1; j < n; j++)
{if (arr[j] < arr[min_idx])
min_idx = j;
c_se++;//counting comparisions
       }
// Swap the found minimum element with the first element
swap(&arr[min_idx], &arr[i]);
m_se++;//counting moves
}
}
//shell sort
int c_sh=0,m_sh=0;
int shellSort(int arr[], int n)
{
for (int gap = n/2; gap > 0; gap /= 2)
{

for (int i = gap; i < n; i += 1)
{
int temp = arr[i];
  

int j;   
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
{ arr[j] = arr[j - gap];
               c_sh++;//counting comparisions
               m_sh++;//counting moves
           }
arr[j] = temp;
}
}
return 0;
}
//quick sort
int c_q=0,m_q=0;
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
  
for (int j = low; j <= high- 1; j++)
{
c_q++;//counting comparisions
if (arr[j] <= pivot)
{
i++;   
m_q++;//counting moves
           swap(&arr[i], &arr[j]);
}
}
m_q++;//counting moves
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
  

void quickSort(int arr[], int low, int high)
{
if (low < high)
{
  
int pi = partition(arr, low, high);
  

quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
//merge sort
int c_m=0,m_m=0;
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
  
  
int L[n1], R[n2];
  
  
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
  
  
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
       c_m++;//counting comparisions
if (L[i] <= R[j])
{
           m_m++;
arr[k] = L[i];
i++;
}
else
{
           m_m++;
arr[k] = R[j];
j++;
}
k++;
}
  
  
while (i < n1)
{
      
arr[k] = L[i];
i++;
k++;
}
  

while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}

void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
  
int m = l+(r-l)/2;
  
  
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
  
merge(arr, l, m, r);
}
}

int main()
{
   int A[] = {12, 11, 13, 5, 6, 7};
   int B[] = {12, 11, 13, 5, 6, 7};
   int C[] = {12, 11, 13, 5, 6, 7};
   int D[] = {12, 11, 13, 5, 6, 7};
   int E[] = {12, 11, 13, 5, 6, 7};
   int F[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(A)/sizeof(A[0]);
insertionSort(A,n);
bubbleSort(B,n);
selectionSort(C,n);
shellSort(D,n);
   quickSort(E,0,n-1);
mergeSort(F, 0, n - 1);
  
   //displaying output
   cout<<"insertion sort: comparisions :"<<c_in<<", moves :"<<m_in<<endl;
   cout<<"bubble sort: comparisions :"<<c_b<<", moves :"<<m_b<<endl;
   cout<<"selection sort: comparisions :"<<c_se<<", moves :"<<m_se<<endl;
   cout<<"shell sort: comparisions :"<<c_sh<<", moves :"<<m_sh<<endl;
   cout<<"quick sort: comparisions :"<<c_q<<", moves :"<<m_q<<endl;
   cout<<"merge sort: comparisions :"<<c_m<<", moves :"<<m_m<<endl;
   return 0;
}

output:

insertion sort: comparisions :10, moves :10
bubble sort: comparisions :15, moves :10
selection sort: comparisions :15, moves :5
shell sort: comparisions :4, moves :4
quick sort: comparisions :9, moves :9
merge sort: comparisions :9, moves :9

Process exited normally.
Press any key to continue . . .