Question

Question7 Use Quicksort to sort the array A <H.U.RRI CAN E in alphabetical order. Draw the tree of the recursive calls made Upload Choose a File Question 8

Answer 1

qsort.cpp

#include<iostream>
using namespace std;

void quickSort(char arr[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[((left + right) / 2)];
  

/* partition */
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
cout<<"i and j are"<<i<<" "<<j<<"and corresponding array value is"<<arr[i]<<" " <<arr[j]<<endl;
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
cout<<"entering while loop"<<endl;
for(int i=0;i<7;i++)
cout<<arr[i]<<" "<<endl ;
}
}
cout<<"recursion"<<endl;

/* recursion */
if (left < j)
quickSort(arr, left, j);

if (i< right)
quickSort(arr, i, right);
}
int main(){
char arr[9]= {'h','u','r','r','i','c','a','n','e'};
for(int i=0;i<9;i++)
cout<<arr[i]<<" " ;
quickSort(arr,0,8);
cout<<endl;
for(int i=0;i<9;i++)
cout<<arr[i]<<" " ;
int wait;
cin>>wait;
return 0;
}

output showing recursive calls:

Select CAProgram Files (x86)\Dev-CpplConsolePauser.exe h u rri c an e i and j are1 8and corresponding array value isu e entering while loop i and j are2 6and corresponding array value isr a ntering while loop i and j are3 5and corresponding array value isr c ntering while loop i and j are4 4and corresponding array value isi i entering while loop recursion i and j aree 3and corresponding array value ish c ntering while loop

Select CProgram Files (x86)\Dev-CpplConsolePauser.exe recursion i and j are0 3and corresponding array value ish c ntering while loop i and j are1 2and corresponding array value ise a entering while loop recursion i and j aree 1and corresponding array value isc a entering while loop recursion i and j are2 2and corresponding array value ise e entering while loop recursion i and j are5 7and corresponding array value isr n entering while loop

Select CProgram Files (x86)\Dev-CpplConsolePauser.exe entering while loop recursion i and j are5 7and corresponding array value isr n entering while loop i and j are6 6and corresponding array value isr r entering while loop recursion i and j are7 7and corresponding array value isr r entering while loop recursion acehinrru

you can change input in the program to check for different values also.