Quicksort problem

[MachDelta]

Hi everyone. I've been struggling with a quicksort implementation here. I think - scratch that - I know i'm overrunning an array (erm, vector) based on how it explodes, but I honestly can't see it and I have no debugger. I slept on it but fresh eyes didn't get me anywhere. I've been digging around online for a while but there are a thousand different ways to do quicksort and it just ends up being confusing to keep it all straight.
Oh and two things to note:
-Yes, I have to use vectors. I've no idea why.
-There are global variables (don't shoot me) being incremented for performance tracking and comparing sorts.
Here's the mess:

//Quick Sort
vector<int> quickSort(vector<int> &data, int left, int right){
    if(left>=right){ return data; }
    else{
         int split = partition(data, left, right);
         recurses+=2;
         quickSort(data, left, split-1);
         quickSort(data, split+1, right);
    }
}

//Quick sort partitioning
int partition(vector<int> &data, int left, int right){
    int pivot=left;
    int i=left+1;
    int j=right;

    while (i<j){
        for(;i<right && (data[i]<=data[pivot]);i++) { compares++; }
        for(;(data[j]>data[pivot]);j--) { compares++; }
        if(i<j){
            swap(data[i],data[j]);
            swaps++;
        }
    }
    swap(data[pivot], data[j]);
    swaps++;
    return j;
}

I feel like i'm somehow passing bad indeces to the partition function and the for loops are running away. Every once in a while the function will finish (it's fed 1-10 in random order) but the first and second elements of the vector are always garbage when it does. Mind you, it's certainly possible that I have more than one error going on.

Thoughts?

[phorce]

First question:

Where do you define:

for(;i<right && (data[i]<=data[pivot]);i++) { compares++; }

compares?

Second of all, you have function declartion:

vector<int> quickSort(vector<int> &data, int left, int right) {

This assumes that it has a return type, so therefore is expecting a vector of ints to be returned. BUT you send the pointer (memeory location) of the data so whatever values get's passed to this function, it will perform on THAT dataset therefore, this function can have a return type of "void".

You have a lot of variables, in your code which are not defined (If you had compiled this code, you would have seen them). I have no idea what they do, or, what they are for so I just set these to 0 so that the code compiles. FIX THIS!

Ok, I have a compilable version of your code (Please look through it, don't just copy it)! I have questions though, do you understand the logic behind Quick Sorting? If not, you should research this, also, are you implementing multiple sorting algorithms?

#include <iostream>
#include <string>
#include <vector>
using namespace std;
//Quick Sort

void printSorted(vector<int> &values)
{

    for(unsigned i=0; (i < values.size()); i++)
    {
        cout << values[i] << " ";

    }

    cout << endl << endl;
}

int partition(vector<int> &data, int left, int right){
    int pivot=left;
    int i=left+1;
    int j=right;

    int compares = 0;
    int swaps = 0;
    while (i<j){
        for(;i<right && (data[i]<=data[pivot]);i++) { compares++; }
        for(;(data[j]>data[pivot]);j--) { compares++; }
        if(i<j){
            swap(data[i],data[j]);
            swaps++;
        }
    }
    swap(data[pivot], data[j]);
    swaps++;
    return j;
}


void quickSort(vector<int> &data, int left, int right){
    int recurses = 0;
    if(left>=right){ return; }
    else{
         int split = partition(data, left, right);
         recurses+=2;
         quickSort(data, left, split-1);
         quickSort(data, split+1, right);
    }
}

//Quick sort partitioning

int main()
{
    int tempArr[] = {5,3,8,9,1,7,0,2,6,4};
    int size = sizeof tempArr / sizeof tempArr[0];
    vector<int> values(tempArr, tempArr+size);

    quickSort(values, 0, 9);

    printSorted(values);
}

// output 0 1 2 3 4 5 6 7 8 9 

-Yes, I have to use vectors. I've no idea why.

Vectors are amazing. Don't diss the vectors, vectors are your friend in time of need.

-There are global variables (don't shoot me) being incremented for performance tracking and comparing sorts.

You wouldn't get shot for global variables ;)! BUT you should have (pointers) variables inside your main that is passed through to your function and then can are changed. Like something (or something):

void changedMe(int &pnt)
{
    pnt = 200;
}
int main(int argc, char *argv[]) {


    int pnt = 1;
    cout << pnt << endl;
    changedMe(pnt);
    cout << pnt << endl;
}

// output:
// 1 (before)
// 200 (after)

[ken_taiken]

I have fixed your code.

You don't have to return anything as phorce said already ,and why didn't you check for boundaries for the iterator 'j' like you did for 'i' in the partition function's for loops.
And there is a trivial case where the partition function would go wrong, for e.g if you were to partition [1,2], the split would return 1 after partitioning the array into [2,1]. If that was the whole array you know it's not what you wanted.

Here is the fixed code :

#include<iostream>
#include<vector>

using namespace std;

int compares;
int recurses;
int swaps;
int partition(vector<int>&,int,int);

void quickSort(vector<int> &data, int left, int right){
    if(left<right){

         int split = partition(data, left, right);
         recurses+=2;
         quickSort(data, left, split-1);
         quickSort(data, split+1, right);
   }
}
//Quick sort partitioning
int partition(vector<int> &data, int left, int right)
{
      int pivot=left;   
      int i=left+1;
      int j=right;
      while (i<j)
      {
           for(;i<right && (data[i]<=data[pivot]);i++) { compares++; }
           for(;j>left && (data[j]>data[pivot]);j--) { compares++; }
           if(i<j)
           {
                 swap(data[i],data[j]);
                 swaps++;
           }
      }
      if(data[pivot]>=data[j])
       {
            swap(data[pivot], data[j]);
            swaps++;
            return j;
       }
       compares++;
       return pivot;
 }

int main()
{
     vector <int> toSort;
     int n;
     int i;
     cin>>n;
     toSort.resize(n);
     for(i=0;i<n;++i) cin>>toSort[i];
     //cout<<partition(toSort,0,n-1)<<endl;
     quickSort(toSort,0,toSort.size()-1);
     cout<<"Sorted : "<<endl;
     for(i=0;i<n;++i) cout<<toSort[i]<<" ";
     cout<<endl<<"No of comparisons : "<<compares<<endl;
     cout<<"No of swaps        : "<<swaps<<endl;
     return 0;
}

Also try to be good at debugging without a debugger. Have fun. :)

[phorce]

@ken_taiken Any reason to why the for loop goes from (0 - {first input})? E.g. 5 (0-5)?

[ken_taiken]

@phorce : Sorry, in which for loop or line ?