findPivot function

fingPivot.cpp

/*Remember Quick Sort?  The pivot element selection has a significant impact on the efficiency of quick sort. The optimal pivot is the median element. The median element is an element that (almost) half of the elements in the list are smaller than the pivot element and (almost) half of elements are greater than the pivot element. For example, if a list is {3, 2, 9, 4, 5}, the median element is 4 (index 3) since 2 elements are smaller than 4 and 2 elements are greater than 4. Another example, if a list is {3, 2, 9, 5}, the median element is 3 (index 0) since 1 element is smaller than 3 and 2 elements are greater than 3. 

Write a function findPivot that accepts an array of integers, its size as parameters, and it returns the index of median element in the array. Here is the function prototype:

unsigned int findPivot( int* p_array, unsigned int size);

If we use this function in quick sort to select the pivot element, do you think it will help with efficiency of quick sort? Explain your reasoning. */

//a very complete answer

#include <iostream>


unsigned int findPivot(int* p_array, unsigned int size)
{
    if (p_array != NULL && size > 0)
    {
        //looping though array and incrementing pivot each time
        for (int j = 0; j < size; j++)
        {
            int pivot = j;
            int smaller = 0;
            int bigger = 0;
            //looping though array and checking how many values there are that are greater and smaller than the pivot Value
            for (int i = 0; i < size; i++)
            {
                //checking if current value is larger than pivot, if yes incrementing numMoreThan
                if (p_array[i] > p_array[pivot])
                {
                    bigger++;
                }
                if (p_array[i] < p_array[pivot])
                {
                    smaller++;
                }
            }
            //checking if the amount of larger and smaller values
            if (abs(bigger -smaller) <= 1)
            {
                return pivot;
            }
        }
    }
    //not ideal
    return -1;
}

int array1[5] = {3, 2, 9, 4, 5};
int array2[4] = {2, 3, 9, 5};
int main() {
    // Write C++ code here
    std::cout << "The index of median for array 1 is: " << findPivot(array1, 5) << std::endl;
    std::cout << "The index of median for array 2 is: " << findPivot(array2, 4) << std::endl;
    return 0;
}