c++ QuickSort not clear

Question

I am trying to understand the quicksort mechanism but so far I can't figure it out. According to wikipedia, the steps are :

1. Pick an element, called a pivot, from the list.

2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.

3. Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values.

And this is the code:

 int partition(int arr[], int left, int right)
    {
          int i = left, j = right;
          int tmp;
          int pivot = arr[(left + right) / 2];

          while (i <= j) {

                while (arr[i] < pivot)
                      i++;
                while (arr[j] > pivot)
                      j--;
                if (i <= j) {
                      tmp = arr[i];
                      arr[i] = arr[j];
                      arr[j] = tmp;
                      i++;
                      j--;
                }
          }
          return i;
    }
     void quickSort(int arr[], int left, int right) {
          int index = partition(arr, left, right);
          if (left < index - 1)
                quickSort(arr, left, index - 1);
          if (index < right)
                quickSort(arr, index, right);
    }

All is somehow clear to me except one thing. Why is the partition function returning i and not j?

It could return either one depending on which group you put the pivot in. — user529758
if I put return j; instead of return i;, for the array {3,2,4,1} the program crashes — Teo
@Theo.: That's because the quickSort function you have there expects partition to return the index of the first element of the second partition. Changing it to expect the index of the last element would be a pretty trivial change. — Mooing Duck
yes, that's what I figured but why can't I find any other example of quickSort that is not returning the index of the first element in the second partition? — Teo
@Theo. "I've seen it on TV so it must be true." - Not every possible correct implementation of every possible program has been written (yet). — user529758

Shiva Shiva · Accepted Answer · 2013-04-11T05:02:15

I found this program (and the output) here. Have a look,

#include <iostream>
using namespace std;

const int INPUT_SIZE = 10;

// A simple print function
void print(int *input)
{
    for ( int i = 0; i < INPUT_SIZE; i++ )
        cout << input[i] << " ";
    cout << endl;
}

// The partition function
int partition(int* input, int p, int r)
{
    int pivot = input[r];

    while ( p < r )
    {
        while ( input[p] < pivot )
            p++;

        while ( input[r] > pivot )
            r--;

        if ( input[p] == input[r] )
            p++;
        else if ( p < r )
        {
            int tmp = input[p];
            input[p] = input[r];
            input[r] = tmp;
        }
    }

    return r;
}

// The quicksort recursive function
void quicksort(int* input, int p, int r)
{
    if ( p < r )
    {
        int j = partition(input, p, r);        
        quicksort(input, p, j-1);
        quicksort(input, j+1, r);
    }
}

int main()
{
    int input[INPUT_SIZE] = {500, 700, 800, 100, 300, 200, 900, 400, 1000, 600};
    cout << "Input: ";
    print(input);
    quicksort(input, 0, 9);
    cout << "Output: ";
    print(input);
    return 0;
}

OUTPUT:-
Input: 500 700 800 100 300 200 900 400 1000 600
Output: 100 200 300 400 500 600 700 800 900 1000

c++ QuickSort not clear

1 Answers