Question

(50’) Implement Quick-Sort algorithm in quickSort.cpp, where you are expected to implement three functions, swap(), partition() and quickSort(). You are expected to call swap() within partition(), to call partition() within quickSort(), and you are not expected to declare/ implement other additional functions nor change the main() function. OPTIONAL: If you don’t need/ want to use swap() in your implementation, that is fine. Just delete/ comment it.

quickSort.cpp

#include <iostream>

using namespace std;

  

// A helper function to facilitate swapping two int elements

// You might want to use this function in the function partition().

void swap(int& a, int& b)

{

}

  

// This function partitions sub-array A[p..r]. It takes last element in the sub-array, i.e., A[r], as pivot,

// places the pivot element at its correct position in sorted array,

// places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot,

// and returns the index of the pivot element (i.e. it's correct position in sorted array)

// You might want to use this function in the function quickSort().

int partition (int A[], int p, int r)

{

}

  

// using quickSort to sort sub-array A[p..r]  

// p is for left index and r is right index of the

// sub-array of A[] to be sorted

void quickSort(int A[], int p, int r)

{

}

  

int main()

{

cout << "Please enter the length (number of elements) of the input array: ";

int n;

cin >> n;

if(n <= 0) {

cout << "Illegal input array length!" << endl;

return 0;

}

int* A = new int [n];

cout << "Please enter each element in the array" << endl;

cout << "(each element must be an integer within the range of int type)." << endl;

for(int i=0; i<n; i++) {

cout << "A[" << i << "] = ";

cin >> A[i];

}

  

cout << "Given array A[] is: ";

for(int i=0; i<n-1; i++)

cout << A[i] << ",";

cout << A[n-1] << endl;

  

quickSort(A, 0, n-1);

  

cout << "After quickSort, sorted array A[] is: ";

for(int i=0; i<n-1; i++)

cout << A[i] << ",";

cout << A[n-1] << endl;

delete [] A;

return 0;

}

Answer 1

//quickSort.cpp

#include <iostream>

using namespace std;

// A helper function to facilitate swapping two int elements

// You might want to use this function in the function partition().

void swap(int& a, int& b)

{

int temp =a;

a=b;

b=temp;

}

int partition(int A[],int p,int r){

int pivot=A[r];

int i=0,j=-1;

while(i<r){

if(A[i]<pivot){

j++;

swap(A[i],A[j]);

}

i++;

}

A[i]=A[++j];

A[j]=pivot;

return j;

}

void quickSort(int A[],int p,int r){

int pivot;

if(p<r){

pivot=partition(A,p,r);

quickSort(A,p,pivot-1);

quickSort(A,pivot+1,r);

}

}

  

int main()

{

cout << "Please enter the length (number of elements) of the input array: ";

int n;

cin >> n;

if(n <= 0) {

cout << "Illegal input array length!" << endl;

return 0;

}

int* A = new int [n];

cout << "Please enter each element in the array" << endl;

cout << "(each element must be an integer within the range of int type)." << endl;

for(int i=0; i<n; i++) {

cout << "A[" << i << "] = ";

cin >> A[i];

}

  

cout << "Given array A[] is: ";

for(int i=0; i<n-1; i++)

cout << A[i] << ",";

cout << A[n-1] << endl;

  

quickSort(A, 0, n-1);

  

cout << "After quickSort, sorted array A[] is: ";

for(int i=0; i<n-1; i++)

cout << A[i] << ",";

cout << A[n-1] << endl;

delete [] A;

return 0;

}

//sample output