C++ quicksort in one function with 2 parameters (___ _____, int length)

Question

My task is to implement a Quicksort in one function with 2 parameters(___ ____, int length). I have a Code snippet in which I have to implement quicksort.

#include <cstdlib>
#include <iostream>

void qsort(___ ____, int length);

int main(int argc,char** argv){
    int array[127];
    for(int i = 0; i < 127; ++i)
    {
        array[i] = rand();
    }

    qsort(____, 127);

    for(int i = 0; i < 127; ++i)
    {
        std::cout << array[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}


void qsort(___ ____, int right){
....
}

My approach for qsort is:

    void qsort( int *array, int right){
        std::vector<int> less;
        std::vector<int> equal;
        std::vector<int> greater;

        if (right <= 1){
            return;
        }
        else
        {
            int mid = right/2;
            int pivot = arr[mid];
            for (int i = 0; i < 127; i++)
            {
                if (array[i] < pivot){
                    less.push_back(arr[i]);
                }
                if (array[i] == pivot){
                    equal.push_back(arr[i]);
                }
                if (array[i] > pivot){
                    greater.push_back(arr[i]);
                }
            }
            int *less_a = less.data();
            int *equal_a = equal.data();
            int *greater_a = greater.data();

            qsort(less_a, sizeof(less_a));
            qsort(greater_a, sizeof(greater_a));
            array = less_a + equal_a + greater_a;

    }
}

I know there are multiple syntax errors in it but the "general logic should be fine".

My first problem is that qsort gets an array as parameter, because if I'm looking which element is greater or less than the pivot, I can't use arrays, because I don't know the size of them. So I thought I can make a workaround with vectors and at the end I'm converting them to arrays back...

My second Problem is that qsort has to be void so I don't know how exactly to manipulate the array at the end...

And in my opinion, the first paramter of qsort() has to be the array. The concatenation at the end is wrong too, it's just a "placeholder" for the actual concatenation.

I'm happy about any kind of help. I implemented this solution in Python and it works fine, I can upload it too, if someone wants to see it, but I'm unable to implement it in C++.

Answer 1

Quick sort is in-place manipulation. Means you will be modifying original array only. No need to create extra arrays. This is answer of your both questions.

Try this code

void qsort(int* xArray, int xSize)
{
        int lPivot = xArray[xSize-1];
        int lIndexOfLargestElement = 0;
        for (int i = 0; i < xSize-1; i++)
        {
                if (xArray[i] < lPivot)
                {
                        // Swap largest element with this
                        int lTmp = xArray[i];
                        xArray[i] = xArray[lIndexOfLargestElement];
                        xArray[lIndexOfLargestElement]  = lTmp;
                        lIndexOfLargestElement++;
                }
        }
        // swap pivot with xArray[lIndexOfLargestElement]
        int lTmp = xArray[lIndexOfLargestElement];
        xArray[lIndexOfLargestElement] = xArray[xSize-1];
        xArray[xSize-1] = lTmp;
        if (lIndexOfLargestElement > 1)
                qsort(xArray, lIndexOfLargestElement);
        if (xSize-lIndexOfLargestElement-1 > 1)
                qsort(xArray+lIndexOfLargestElement+1, xSize-lIndexOfLargestElement-1);
}