jeudi 14 juin 2018

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

My task is to implement a Quicksort in one function with 2 parameters(___ ____, int length). I have a Code snippet in wich 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, right);
        qsort(greater_a, right);
        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 lookin which element is greater or less than the pivot, i can't use arrays, because i dont know the size of them. So i thought i can make a workaround with vectors and at the end im converting them to arrays back...

My second Problem is that qsort has to be void so i dont 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 concetation at the end is wrong too, it's just a "placeholder" for the actual concetation.

Im 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 im unable to implement it in c++

Aucun commentaire:

Enregistrer un commentaire