In order to understand the flexible quicksort function, you should start by full

Question

In order to understand the flexible quicksort function, you should start by fully understanding how a program can use this function to sort any kind of array. For example, the function can sort an array of integers, or sort an array of strings, or sort an array of doubles... The steps required in the program are as follows: The program must declare a comparison function that compares two elements from the array. For example, suppose that the program wants to sort an array of integers. Then that program must declare a comparison function that can compare two integers, as shown here: int compare_ints (const void* ptr1, const void* ptr2)//NOTE: *ptr1 is the first integer but since ptr1 is a void//pointer, we must use the notation *((int ptr1) to refer to//this first integer Similarly, *((int *) ptr2) refers to the//second integer. This comparison function works by subtracting//the second integer from the first, and returning the result.//This result meets the requirements listed above (for example, //it is negative when the second argument is larger than the//first. return * ((int *) ptr1) - * (int *) ptr2);} Notice that compare_ints has two parameters that are declared as void pointers. This means that in the prototype, we are not going to tell the compiler exactly what ptr1 and ptr2 are pointing to. But, as the implementor of this function, we know that ptr1 and ptr2 are actually pointing to integers. In particular: * ((int *) ptr1) is the integer that ptr1 points to, and * (((int *) ptr2) is the integer that ptr2 points to. The return value of compare_ints tells us whether the two integers are equal (return value of zero), or the first integer is bigger (return value is positive), or the second integer is bigger (return value is negative) Once you have your compare_ints function in place, the program you can declare an array of integers, and use quicksort to sort the array, as shown here: int my_numbers (4000); ...code to put 4000 numbers into the array my_numbers.....//Now use quicksort Note that the array my numbers is the first//argument (but we need to cast it to void* to match the quicksort//prototype). The second argument is the number of elements in the//array. The third argument is the number of bytes in each array//component (obtained by using the predefined size of operator)//The fourth arguement is the comparison function listed above quicksort (void *) my numbers, 4000, sizeof(int), compare_ints); 

Explanation / Answer

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int compare_ints(const void* ptr1, const void* ptr2)
{
    return *((int *) ptr1) - *((int *) ptr2);
}

int part(int arr[], int low, int high)
{
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j <= high- 1; j++)
        if ( compare_ints(&arr[j], &pivot) < 1 )
        {
            ++i;
            swap(arr[i], arr[j]);
        }

    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int pi = part(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// DRIVER
int main()
{
    int arr[4000] = {10, 7, 8, 9, 1, 5};  

    quickSort(arr, 0, 4000);  

    for (int i = 0; i < 4000; ++i)
        if (arr[i] > 0)
            cout << arr[i] << " ";
    cout << endl;
  
    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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