Question

C++ Question- Write function templates for 5 sort algorithms: - Quick Sort

Apply these algorithms to 10 different arrays of integers. Each array has 100 integer elements. The arrays are filled with random integer numbers.

Answer 1

// STAY HOME STAY SAFE

#include <iostream>
#include <stdlib.h>
using namespace std;
// function to partition the array
int partition (int arr[], int l, int h)
{
int p = arr[h];
int i = (l - 1);
// iterate from low to higt
for (int j = l; j <= h - 1; j++)
{
if (arr[j] < p)
{
// increment i
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
// swap arr[i+1] and arr[h]
int temp = arr[i+1];
arr[i+1]=arr[h];
arr[h]=temp;
return (i + 1);
}
// the quick sort function
void QSort(int arr[], int l, int h)
{
if (l < h)
{
// find the pivot element
int pivot = partition(arr, l, h);
// sort before partition
QSort(arr, l, pivot - 1);
// sort after partition
QSort(arr, pivot + 1, h);
}
}
// main function
int main()
{
// run a loop 10 times for 10 arrays
for(int a=1;a<=10;a++)
{
// declare array os size 100
int arr[100];
// fill with random values
for(int i=0;i<100;i++)
{
arr[i]=rand()%100 + 1;
}
// display array before sorting
cout<<"Array "<<a<<" before quick sort...\n";
for(int i=0;i<100;i++)
{
cout<<arr[i]<<" ";
}
// call merge sort function
QSort(arr,0,99);
// display array after sorting
cout<<"\nArray "<<a<<" after quick sort...\n";
for(int i=0;i<100;i++)
{
cout<<arr[i]<<" ";
}
cout<<"\n\n";
}

return 0;
}