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

1)

Sorry i couldn't get the perfect solution for problem 2 .

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

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