Execute the following using C++ language: you are given two functions quicksort

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

Answer:

1)

void quicksort(int a[], int l, int r){
  
if(l < r){
int m = (l+r)/2;
quicksort(a,l, m);
quicksort(a,m+1,r);
partition(a, l,m, m+1, r);
}
}

void partition(int a[], int lf, int ll, int rf, int rl)
{
int count=0;
static int aux[maxN];
int i = lf;
int saveFirst = lf;

while((lf <= ll) && ( rf <= rl))
{

if(a[lf] < a[rf])
{
aux[i] = a[lf];
lf++;
}
else
{
aux[i] = a[rf];
rf++;
}
i++;
count++;
}
  
while(lf <= ll)
{

aux[i] = a[lf];
lf++;
i++;
  
}
while(rf <= rl)
{
aux[i] = a[rf];
rf++;
i++;
  
}

}

2)

#include < iostream >
#include < stdio.h >
using namespace std;

int count = 0;
int n = 0;
const int MaxN= 100;
void partition(int a[], int lf, int ll, int rf, int rl);
void displayarray(int a[], int n);
void partition(int a[], int lf, int ll, int rf, int rl)
{
  
static int aux[maxN];
int i = lf;
int holdfirstelement = lf;

while((lf <= ll) && ( rf <= rl))
{

if(a[lf] < a[rf])
{
aux[i] = a[lf];
lf++;
}
else
{
aux[i] = a[rf];
rf++;
}
i++;
count++;
}
  
while(lf <= ll)
{

aux[i] = a[lf];
lf++;
i++;
  
}
while(rf <= rl)
{
aux[i] = a[rf];
rf++;
i++;
  
}
for(i= holdfirstelement; i<= rightLast; i++)
a[i] = aux[i];
displayarray(a,n);
cout << endl;
}
void displayarray( int a[], int n){
cout<<"The array which is sorted is :"<<endl;
for (int i=0; i < n; i++)
cout << a[i] << " ";
}

int main(){
  
cout << "Enter number of elements : ";
cin >>n;

int a[MaxN];
for (int i=0; i < n; i++){
if(i==0)
cout << "Enter the first element: ";
else
cout << "Enter the next element: ";
cin >> a[i];
}
  
int l = 0;
int r = n-1;
quicksort(a, l, r);
displayarray(a, n);
cout << endl;
cout << "Number of comparisons are : "<< count << endl;
}

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.