Complete in C++! Write a recursive version of the quicksort function. Demonstrat

Question

Complete in C++!

Write a recursive version of the quicksort function. Demonstrate the functions in a driver program. The function prototypes are as followings

//************************************************

// quickSort uses the QuickSort algorithm to *

// sort arr from arr[start] through arr[end]. *

//************************************************

void quickSort(int arr[], int start, int end);

//***********************************************************

// partition rearranges the entries in the array arr from *

// start to end so all values greater than or equal to the *

// pivot are on the right of the pivot and all values less *

// than are on the left of the pivot. *

//***********************************************************

int partition(int arr[], int start, int end);

//***********************************************************

// swap simply exchanges the contens of *

// values1 and value2 *

//***********************************************************

void swap (int & value1, int & value2);

Step 2: Create a template version of the QuickSort algorithm that will work with any data type. Demonstrate the template with a driver function.

Please include output screenshot!

Explanation / Answer

Hi, Please find my implementation of all methods of Step 1.

#include <iostream>
using namespace std;

void swap(int &a, int &b);
int partition (int arr[], int low, int high);
void quickSort(int arr[], int low, int high);
void printArray(int arr[], int size);

// A utility function to swap two elements
void swap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}

/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element

for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}

/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);

// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
cout<<arr[i]<<" ";
cout<<endl;
}

// Driver program to test above functions
int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = 6;
quickSort(arr, 0, n-1);
cout<<"Sorted array: ";
printArray(arr, n);
return 0;
}

Please repost Step 2 problem

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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