Sort Realize direct insertion sort, half insertion sort, bubble sort, quick sort, select sort, heap sort and merge sort. Raw data is generated randomly.  For different problem size, output the number of comparisons and moves required by various sorting algorithms When the program is running, input the problemsize from the keyboard, the source data is randomly generated by the system, and then output the comparison times and movement times required by various sorting algorithms under this problem scale..   Do this in C++ language..do it according to the above requirement

The code for the given problem is written below in c++ language-

#include <iostream> //header files

using namespace std;

void swap(int *xp, int *yp) // swap function
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
  
// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
int i, j,cmp=0,mov=0;
for (i = 0; i < n-1; i++)
  
// Last i elements are already in place
for (j = 0; j < n-i-1; j++){
cmp++;//counting comparision
if (arr[j] > arr[j+1]){
swap(&arr[j], &arr[j+1]);
mov++;//counting movements
  
}
}
cout<<"Bubble sort needs "<<cmp<<" times of comparision ,"<<mov<<" times of moves.\n";
}

void selectionSort(int arr[], int n)
{
int i, j, min_idx,cmp=0,mov=0;
  
// 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++) {
cmp++;
if (arr[j] < arr[min_idx])
min_idx = j;
}
// Swap the found minimum element with the first element
swap(&arr[min_idx], &arr[i]);
mov++;
}
  
cout<<"Selection sort needs "<<cmp<<" times of comparision ,"<<mov<<" times of moves.\n";
}

void insertionSort(int arr[], int n)
{
int i, key, j,cmp=0,mov=0;
for (i = 1; i < n; i++)
{
key = arr[i];
mov++;
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];
mov++;
j = j - 1;
cmp++;
}
cmp++;
arr[j + 1] = key;
mov++;
}
  
cout<<"Insertion sort needs "<<cmp<<" times of comparision ,"<<mov<<" times of moves.\n";
}

int partition (int arr[], int low, int high,int &cmp,int &mov)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
  
for (int j = low; j <= high - 1; j++)
{
// If current element is smaller than the pivot
cmp++;
if (arr[j] < pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
mov++;
}
}
swap(&arr[i + 1], &arr[high]);
mov++;
return (i + 1);
}
  
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void doQuickSort(int arr[], int low, int high,int &cmp,int &mov)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high,cmp,mov);
// Separately sort elements before
// partition and after partition
doQuickSort(arr, low, pi - 1,cmp,mov);
doQuickSort(arr, pi + 1, high,cmp,mov);
}
}

void quickSort(int arr[],int sz){
int cmp=0,mov=0;
doQuickSort(arr,0,sz,cmp,mov);
  
cout<<"Quick sort needs "<<cmp<<" times of comparision ,"<<mov<<" times of moves.\n";
}

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r,int &cmp,int &mov)
{
int n1 = m - l + 1;
int n2 = r - m;

// Create temp arrays
int L[n1], R[n2];

// Copy data to temp arrays L[] and R[]
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];

// Merge the temp arrays back into arr[l..r]

// Initial index of first subarray
int i = 0;

// Initial index of second subarray
int j = 0;

// Initial index of merged subarray
int k = l;

while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
mov++;
i++;
}
else {
arr[k] = R[j];
mov++;
j++;
}
k++;
cmp++;
}

// Copy the remaining elements of
// L[], if there are any
while (i < n1) {
arr[k] = L[i];
mov++;
i++;
k++;
}

// Copy the remaining elements of
// R[], if there are any
while (j < n2) {
arr[k] = R[j];
mov++;
j++;
k++;
}
}

// l is for left index and r is
// right index of the sub-array
// of arr to be sorted */
void doMergeSort(int arr[],int l,int r,int &cmp,int &mov){
if(l>=r){
return;//returns recursively
}
int m = (l+r-1)/2;
doMergeSort(arr,l,m,cmp,mov);
doMergeSort(arr,m+1,r,cmp,mov);
merge(arr,l,m,r,cmp,mov);
}

void mergeSort(int arr[],int sz){
int cmp=0,mov=0;
doMergeSort(arr,0,sz,cmp,mov);
  
cout<<"Merge sort needs "<<cmp<<" times of comparision ,"<<mov<<" times of moves.\n";
}
void heapify(int arr[], int n, int i,int &cmp,int &mov)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2

// If left child is larger than root
if (l < n && arr[l] > arr[largest])
{cmp++;largest = l;}

// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
{cmp++;largest = r;}

// If largest is not root
if (largest != i) {
mov++;
swap(arr[i], arr[largest]);

// Recursively heapify the affected sub-tree
heapify(arr, n, largest,cmp,mov);
}
}

// main function to do heap sort
void heapSort(int arr[], int n)
{
int cmp=0,mov=0;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i,cmp,mov);

// One by one extract an element from heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
swap(arr[0], arr[i]);

// call max heapify on the reduced heap
heapify(arr, i, 0,cmp,mov);
}
  
cout<<"Heap sort needs "<<cmp<<" times of comparision ,"<<mov<<" times of moves.\n";
}

/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
void cpy(int a[],int b[],int size){
for (int i = 0; i < size; i++)
a[i]=b[i];
}

int main()
{
  
int sz;
cout<<"Enter the size of array::";
cin>>sz;
int arr[sz],cpa[sz];
for(int i=0;i<sz;i++){
arr[i]=rand()%sz; //Generate number between 0 to sz
cpa[i]=arr[i];

}
printArray(arr,sz);

bubbleSort(arr,sz);

cpy(arr,cpa,sz);
selectionSort(arr,sz);

cpy(arr,cpa,sz);
insertionSort(arr,sz);

cpy(arr,cpa,sz);
quickSort(arr,sz);

cpy(arr,cpa,sz);
mergeSort(arr,sz);
  
cpy(arr,cpa,sz);
heapSort(arr,sz);
return 0;
}