Execute the following using C++ language: you are given two functions quicksort
ID: 3691705 • Letter: E
Question
Execute the following using C++ language:
you are given two functions quicksort and partition.
You are required to do the following:
1. 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.
2. 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)
{ int i = 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]);
return i; }
Explanation / Answer
ANS;
Required Code:
int quicksort(int a[], int l, int r)
{
int i,cmp=0;
if (r <= l) return 0;
i=partition(a,l,r,&cmp);
return cmp+quicksort(a, l, i-1)+quicksort(a, i+1, r);
}
int partition(int a[], int l, int r,int *cmp)
{
int i = l-1, j = r; int v = a[r];
for (;;)
{
while (a[++i] < v)
(*cmp)++;// increment number of comparisions by one for each iteration of while loop
(*cmp)++; // for last iteration at which while breaks
while (v < a[--j])
{
(*cmp)++;// increment number of comparisions by one for each iteration of while loop
if (j == l) break;
}
(*cmp)++; // for last iteration at which while breaks
if (i>= j) break;
exch(a,i,j);
}
exch(a,i,r);
return i;
}
void exch(int a[], int i, int j)
{
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
Total Code:
#include <iostream>
using namespace std;
void exch(int a[], int i, int j);
int partition(int a[], int l, int r,int *cmp);
int quicksort(int a[], int l, int r);
int main()
{
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};
cout<<"Array befor Sort : ";
for(int i=0;i<28;i++)
cout<<a[i]<<" ";
cout<<endl;
cout << "Number of comparisions for sorting = "<<quicksort(a,0,27) << endl;
cout<<"Array after soting : ";
for(int i=0;i<28;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
int quicksort(int a[], int l, int r)
{
int i,cmp=0;
if (r <= l) return 0;
i=partition(a,l,r,&cmp);
return cmp+quicksort(a, l, i-1)+quicksort(a, i+1, r);
}
int partition(int a[], int l, int r,int *cmp)
{
int i = l-1, j = r; int v = a[r];
for (;;)
{
while (a[++i] < v)
(*cmp)++;// increment number of comparisions by one for each iteration of while loop
(*cmp)++; // for last iteration at which while breaks
while (v < a[--j])
{
(*cmp)++;// increment number of comparisions by one for each iteration of while loop
if (j == l) break;
}
(*cmp)++; // for last iteration at which while breaks
if (i>= j) break;
exch(a,i,j);
}
exch(a,i,r);
return i;
}
void exch(int a[], int i, int j)
{
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
Output:
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.