Sort

[Problem Description]

Realize direct insertion sort, half insertion sort, bubble sort, quick sort, select sort, heap sort and merge sort.

[Basic Requirements]

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 problem size 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.

The code works perfectly can you please design an algorithm and make a summary for this code?

#include

#include

using namespace std;

void swap(int *xp, int *yp)

{

int temp = *xp;

*xp = *yp;

*yp = temp;

}

// A function to implement bubble sort

void Bubble_Sort(int arr[], int n)

{

int i, j,compares=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++)

{

compares++;//counting comparision

if (arr[j] > arr[j+1])

{

swap(&arr[j], &arr[j+1]);

mov++;//counting movements

}

}

cout<<"Bubble sort needs "<

}

void Selection_Sort(int arr[], int n)

{

int i, j, min_idx,compares=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++)

{

compares++;

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 "<

}

void Insertion_Sort(int arr[], int n)

{

int i, key, j,compares=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;

compares++;

}

compares++;

arr[j + 1] = key;

mov++;

}

cout<<"Insertion sort needs "<

}

int partition (int arr[], int low, int high,int &compares,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

compares++;

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 Quick_Sort

arr[] --> Array to be sorted,

low --> Starting index,

high --> Ending index */

void doQuick_Sort(int arr[], int low, int high,int &compares,int &mov)

{

if (low < high)

{

/* pi is partitioning index, arr[p] is now

at right place */

int pi = partition(arr, low, high,compares,mov);

// Separately sort elements before

// partition and after partition

doQuick_Sort(arr, low, pi - 1,compares,mov);

doQuick_Sort(arr, pi + 1, high,compares,mov);

}

}

void Quick_Sort(int arr[],int Size)

{

int compares=0,mov=0;

doQuick_Sort(arr,0,Size,compares,mov);

cout<<"Quick sort needs "<

}

// 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 &compares,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++;

compares++;

}

// 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 doMerge_Sort(int arr[],int l,int r,int &compares,int &mov)

{

if(l>=r)

{

return;//returns recursively

}

int m = (l+r-1)/2;

doMerge_Sort(arr,l,m,compares,mov);

doMerge_Sort(arr,m+1,r,compares,mov);

merge(arr,l,m,r,compares,mov);

}

void Merge_Sort(int arr[],int Size)

{

int compares=0,mov=0;

doMerge_Sort(arr,0,Size,compares,mov);

cout<<"Merge sort needs "<

}

void heapify(int arr[], int n, int i,int &compares,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])

{compares++;largest = l;}

// If right child is larger than largest so far

if (r < n && arr[r] > arr[largest])

{compares++;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,compares,mov);

}

}

// main function to do heap sort

void Heap_Sort(int arr[], int n)

{

int compares=0,mov=0;

// Build heap (rearrange array)

for (int i = n / 2 - 1; i >= 0; i--)

heapify(arr, n, i,compares,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,compares,mov);

}

cout<<"Heap sort needs "<

}

/* 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 copy(int a[],int b[],int size)

{

for (int i = 0; i < size; i++)

a[i]=b[i];

}

int main()

{

int Size;

cout<<"Enter the size of array:: ";

cin>>Size;

int arr[Size],cpa[Size];

for(int i=0;i

{

arr[i]=rand()%Size; //Generate number between 0 to Size

cpa[i]=arr[i];

}

printArray(arr,Size);

Bubble_Sort(arr,Size);

copy(arr,cpa,Size);

Selection_Sort(arr,Size);

copy(arr,cpa,Size);

Insertion_Sort(arr,Size);

copy(arr,cpa,Size);

Quick_Sort(arr,Size);

copy(arr,cpa,Size);

Merge_Sort(arr,Size);

copy(arr,cpa,Size);

Heap_Sort(arr,Size);

return 0;

}