Please Complete in C++ with a output screenshot! Here is the code I have so far:
ID: 3833329 • Letter: P
Question
Please Complete in C++ with a output screenshot!
Here is the code I have so far:
//************************************************
// quickSort uses the QuickSort algorithm to *
// sort arr from arr[start] through arr[end]. *
//************************************************
void quickSort(int arr[], int start, int end);
{
int pivotPoint; //index
if (start < end)
{
pivotPoint = partition(arr, start, end);
//sort the left sublist
quickSort(arr, start, pivotPoint - 1);
//sort the right sublist
quickSort(arr, pivotPoint + 1 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)
{
int pivotValue, pivotIndex;
//find the middle of the list as the pivot
//swap
swap(arr[start], arr[mid])
pivotValue = arr[start];
pivotIndex = start;
for (int index = start + 1; index <= end; index++)
{
if (arr[index] < pivotValue)
{
//..
}
return pivotIndex;
}
}
//***********************************************************
// swap simply exchanges the contens of *
// values1 and value2 *
//***********************************************************
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 // values 1 and value2 // void swap (int & value 1, int & value2); Create a template version of the QuickSort algorithm that will work with any data type. Demonstrate the template with a driver function.Explanation / Answer
#include<iostream>
using namespace std;
//***********************************************************
// swap simply exchanges the contens of *
// values1 and value2 *
//***********************************************************
void swap(int & value1, int & value2) {
int temp = value1;
value1 = value2;
value2 = temp;
}
//***********************************************************
// 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)
{
int pivot = arr[end]; // pivot
int i = (start - 1); // Index of smaller element
for (int j = start; j < end; j++)
{
// If current element is smaller or equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[end]);
return (i + 1);
}
//************************************************
// quickSort uses the QuickSort algorithm to *
// sort arr from arr[start] through arr[end]. *
//************************************************
void quickSort(int arr[], int start, int end)
{
int pivotPoint; //index
if (start < end)
{
pivotPoint = partition(arr, start, end);
//sort the left sublist
quickSort(arr, start, pivotPoint - 1);
//sort the right sublist
quickSort(arr, pivotPoint + 1, end);
}
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
cout<<"Sorted array: ";
for(int i = 0; i< 6; i++)
cout<< arr[i] <<endl;
return 0;
}
So you have the code for quick sort here. Hope this code will help you. If you have any query, please feel free to comment below.