Please Complete in C++ with a output screenshot! Here is the code I have so far:

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.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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