Quicksort

[heatedcrows]

Hi everybody, i just need some help with the quicksort program. I have to write a quicksort program in a function with the prototype void qsort (int data[], int length

my question is weather it is possible to write the code with just those two, or if i would have to use this function to call another function, one that had a left and right bound as well.

My other question is on how i would write this, i have tried other implementations, but they do not seem to work.

Thanks in advance for any help, thanks

[EricDu]

Yes, the prototype is good enough to complete your job if you have learned recursive function call.

You can get an idea from wiki below about how to make a quicksort program.

http://en.wikipedia.org/wiki/Quicksort

[heatedcrows]

I understand how i would do the first one, but my question is about putting everything back together inside of the first array. If you could provide any help with that, it would be greatly appreciated.

Thanks.

[heatedcrows]

also, this is what my code looks like right now (it compiles, but the console window crashes in about 2 seconds)

#include <cstdlib>
#include <iostream>
#include <fstream>

using namespace std;

void qsort (int data[], int length);

int main()
{
    char filename [256];
    ifstream myInFile;
    bool openedFile = false;
    int data [100];
    int length = 0;

    cout << "Welcome to bubble sort " << endl;

    do
    {
        cout << "Enter the name of the file (with .txt at the end): ";
        cin >> filename;
        myInFile.open (filename);

        if (!myInFile.fail ())
        {
            openedFile = true;
        }

        else
        {
            myInFile.clear();
            openedFile = false;
            cout << "Error Loading " << filename << "!!!!!!";
        }
    }
    while (!openedFile);

    while (!myInFile.eof())
    {
        myInFile >> data[length];
        length = length + 1;
    }


    cout << "The original set of numbers: ";

    for (int i = 0; i < length; i = i + 1)
    {
        cout << data[i] << ",";
    }

    srand (time (NULL));
    qsort (data, length);

    cout << endl << endl << "After quick sorting: ";

    for (int i = 0; i < length; i = i + 1)
    {
        cout << data [i] << ", ";
    }

    cout << endl << endl;

    return EXIT_SUCCESS;
}

void qsort (int data [], int length)
{
    int less_than[100];
    int less_length = 0;
    int greater_than[100];
    int greater_length = 0;

    if (length <= 1)
    {
        return;
    }

    srand (time (NULL));
    int pivot = data [rand () % length + 1];
    for (int i =0; i < length; i = i + 1)
    {
        if (data [i] <= pivot)
        {
            less_than[less_length] = data [i];
            less_length = less_length + 1;
        }

        else
        {
            greater_than[greater_length] = data[i];
            greater_length = greater_length + 1;
        }
    }
    qsort(less_than, less_length);
    qsort (greater_than, greater_length);

}

[EricDu]

my question is about putting everything back together inside of the first array.

If you have carefully read the wiki, you should notice this sentence

Quicksort can be implemented as an in-place sort, requiring only O(log n) additional space.

That means if you do it in this way, the first array is sorted in-place already, obviously your code above is not going this way.

If you really like your implementation as pasted, yes, you have to put sorted less_than[] and greater_than[] back to data[], you just need to do one more step below right after the 2 qsort():

memcpy(data, less_than, less_length * sizeof(int));
memcpy(data + less_length, greater_than, greater_length * sizeof(int));

Line below is the cause of crash, hopefully you can fix it by yourself.

int pivot = data [rand () % length + 1];

[heatedcrows]

okay, i now have different code, it pivots properly, but i dont get i how i would do recursion with it.
PS. the various seemingly useless functions are to satisfy project reaquirements.

#include <cstdlib>
#include <iostream>
#include <fstream>

using namespace std;

void qsort(int data[], int length);
void quicksort(int data[], int start, int end);
void pivot(int data[], int start, int end);

int main()
{
    char filename [256];
    ifstream myInFile;
    bool openedFile = false;
    int data [100] = {5,1,2,8,3};
    int length = 5;

    cout << "Welcome to bubble sort " << endl;

    do
    {
        cout << "Enter the name of the file (with .txt at the end): ";
        cin >> filename;
        myInFile.open(filename);

        if (!myInFile.fail())
        {
            openedFile = true;
        } else
        {
            myInFile.clear();
            openedFile = false;
            cout << "Error Loading " << filename << "!!!!!!";
        }
    } while (!openedFile);

    while (!myInFile.eof())
    {
        myInFile >> data[length];
        length = length + 1;
    }

    cout << "The original set of numbers: ";

    for (int i = 0; i < length; i = i + 1)
    {
        cout << data[i] << ",";
    }
    qsort(data, length);

    cout << endl << endl << "After pivoting: ";

    for (int i = 0; i < length; i = i + 1)
    {
        cout << data [i] << ", ";
    }

    cout << endl << endl;

    return EXIT_SUCCESS;
}

void qsort(int data [], int length)
{
    quicksort(data, 0, length - 1);
}

void quicksort(int data[], int start, int end)
{
    if (start - end < 2)
    {
        return;
    }

    else if (start - end == 2)
    {
        if (data[start] > data [end])
        {
            int temp = data[start];
            data[start] = data[end];
            data[end] = temp;
        }
    }

        pivot(data, start, end);
}

void pivot(int data[], int start, int end)
{
    srand(time(NULL));
    int pivot_index = end;
    int quick_index = start;
    int temp;

    while (pivot_index != quick_index)
    {
        if (data[pivot_index] < data[quick_index])
        {
            temp = data [quick_index];
            data [quick_index] = data[pivot_index - 1];
            data[pivot_index - 1] = data[pivot_index];
            data[pivot_index] = temp;
            pivot_index = pivot_index - 1;

        }
        else
        {
            quick_index = quick_index + 1;
        }
    }
}

[EricDu]

Seems your new design is worse than your old design because 2 more overhead functions are introduced, you can actually use only one qsort() function to do sorting in-place, below is a brief demo:

int main()
{
    // read data from file, you've done already
    qsort(data, length);
    return 0;
}

void qsort(int data [], int length)
{
    int pivotIndex; // use this variable to store pivot value's index in data[], range is [1, length]
    // choose a pivot value from data[]
    // move around the values in data[] and finally get a left part and right part seperated by pivotIndex, the left part is <= pivot value, the right part > pivot

    // pass left part and right part to qsort() to sort
    qsort(data, pivotIndex); // sort left part
    qsort(data+pivotIndex, length-pivotIndex); // sort right part
    return;
}