In this assignment, you are given two functions quicksort and partition . You ar
ID: 3692171 • Letter: I
Question
In this assignment, you are given two functions quicksort and partition. You are required to do the following:
Modify as necessary all functions (partition and quicksort) such that quicksort returns the number of comparisons that it, and partition function together (in total) have performed in sorting the given array a. In these comparisons, only the comparisons that involve array elements are counted. You are not allowed to use any global variable in counting these comparisons. You may want to add new parameters to functions and/or make them return integer values.
Write a C++ program that receives as input an array of integers and calls quicksort to sort this array. Output must include the final sorted array and number of comparisons performed as described in Item 1 above.
One input to your program is the following:
21 3 5 7 26 18 20 11 25 17 27 9 30 24 16 28 14 5 19 23 6 29 4 13 18 22 10 8
Quicksort:
void quicksort(int a[], int l, int r)
{
if (r <= l) return;
/* call for partition function that you modify */
quicksort(a, l, i-1);
quicksort(a, i+1, r);
}
Partition:
int partition(int a[], int l, int r)
{ inti = l-1, j = r; int v = a[r];
for (;;)
{
while (a[++i] < v) ;
while (v < a[--j]) if (j == l) break;
if (i>= j) break;
exch(a[i], a[j]);
}
exch(a[i], a[r]);
returni;
}
Explanation / Answer
/*
* C++ program for shorting array value with total Number of comparisions performed
* Define two function with main first QuickSort and second partion
*
*/
#include <iostream>
using namespace std;
//partion function define here with counter varible
int* partion(int *a,int l, int r,int counter){
//define dome varible Initialization of parameters
int* p = new int[2];
int p_index=l;
int v = a[r];
//Loop through the array and check if a[i] is less than pivot
for(int i=l;i<r;i++){
if(a[i]<=v){
swap(a[i],a[p_index]);
p_index++;
}
counter++;
}
swap(a[p_index],a[r]);
p[0] = p_index;
p[1] = counter;
return p;
}
/*
* define quick shoet funcation here
* this is recurse function
* return number of total count
*/
int QuickSort(int *a,int l,int r,int counter){
int count = counter;
if(l<r){
// call partion function here
int *p = partion(a,l,r,count);
int p_index = p[0];
QuickSort(a,l,p_index-1,count);
QuickSort(a,p_index+1,r,count);
count = p[1];
}
// return final value
return count;
}
int main(){
//define array and add some value
// check with another array value program run correct and not
//int a[] = {5, 3, 7, 2, 1, 6};
// current array value
//int a[] = {7,2,1,6,8,5,3,4};
int a[] = {21, 3, 5, 7, 26, 18, 20, 11, 25, 17, 27, 9, 30, 24, 16, 28, 14, 5, 19, 23, 6, 29, 4, 13, 18, 22, 10, 8};
// coutn size of array
int n = sizeof(a)/sizeof(a[0]);
// call QuickSort function here
int counter = QuickSort(a, 0, n-1,0);
//print Comparisions count
cout << "Number of comparisions performed = "<<counter<<endl;
//Print final the array
for(int i=0;i<n;i++)
cout << a[i]<< " ";
return 0;
}