Quicksort pivot & quicksort complexity

[Void life]

So I have an assignment to validate the complexity of quicksort. Here is my quicksort code below. It works fine when I set the pivot as the left most element in the array but it doesn't sort the elements correctly when the pivot is any other element. What am i doing wrong?
Or must you move the pivot to the start of the array always like say your using the median of 3 method must move the median so that it is the left most element?

  void quicksort(int a[], int left, int right)
{
    int SplitPoint;

    if(compare(right, left) <= 0)  //checking if there is only 1 element in array so no need to do anything
    {
        return;
    }
    else if(compare(left+1,right) == 0) //checking if there is 2 elements in array, can just swap with if statement.
    {
        if(compare(a[left],a[right]) > 0)
        {
            swap(a[left],a[right]);
        }
        return;
    }

    SplitPoint = partition(a,left,right);  //splitpoint is the index of the pivot's correct positions

    quicksort(a,left,SplitPoint-1);        //recursively calling quick-sort on the 2 smaller sub-arrays
    quicksort(a, SplitPoint+1, right);     //as split by the pivot
}

int partition(int a[], int left, int right)
{
    int i, j, pivot;
    j = right + 1;
    i = left - 1; 
    pivot = a[left+2]; //just testing using a different pivot 

    while(true)
    {
        while(compare(pivot, a[++i]) > 0) // keep scanning from left until an element greater than the pivot is found
        {
            if(i == right)     //if the right-most index is reached then break out of this while loop
            {                  //i.e there is nothing greater than the pivot
                break;
            }
        }
        while(compare(pivot, a[--j]) < 0) // keep scanning from right until an element less than the pivot is found
        {
            if(j == left)    //if the left-most index is reached then break out of this while loop
            {                //i.e theres nothing less than the pivot
                break;
            }
        }



        if(compare(i, j) >= 0)  //if i and j meet or crossover then break out the infinite while(true) loop
        {                       //as everything to the left is less than the pivot and everything to the right is greater
            break;
        }
        swap(a[i],a[j]); //swap elements in wrong side
        print_array(a, 10);
    }

    swap(a[left], a[j]); //put the pivot in the right place
    print_array(a, 10);

    return j; //returns the correct position of the pivot
}

*note the compare function just returns the difference between the 2 values called.

I used this array as input 38,7719,21238,2437,8855,11797,8365,32285,10450,30612
(random array generated using rand() function with seed 0
..actually as an aside is there a way to increase RAND_MAX ? its like =~ 32000 something in my computer and if im sorting arrays for size 1,000,000+ numbers are going to be repeating an awful lot)

My second question is that im to show that the complexity of the average case in quicksort is O(nlog(n)). I have the number of operations for a few different values for n, but how would i show that they follow O(nlog(n)).

[2AoiNwbp]

It seems you are in trouble with indices and an extra bit of code.
I think that if you substract one in the recursive calls of quicksort (lines 20 and 21), you are excluding previous pivots from newer sorts. This will end with a list unsorted in the middle, so I would chang it to:

    quicksort(a,left,SplitPoint);        //recursively calling quick-sort on the 2 smaller sub-arrays
    quicksort(a, SplitPoint, right);     //as split by the pivot 

On the other hand, I would use a pivot right in the middle, like:

pivot = a[(left+right)/2];

Besides, if you use break in line 52, the rest of the code will be executed. Why to do so, if everything to the left and right is ordered already? I would chang it to:

return j;

if you still have some problems, try putting a couple of print statements in the right places to check the values of the indices.

regards,
Alejandro

[Void life]

Thanks alejandro
I have some questions...
Why would i need to compare the pivot include them in sorting again.....quicksort will put the pivot in its right full place.
And in line 52 everything to the left and right isisnt ordered ...its just that everything to one side is less than the pivot and everything to the right is greater. (actually im only putting the pivot in its right place in line 58 so what i said in my comment isisnt really true) say this is the array : 4 8 1 9 2 3 and pivot = 4
at 1st pass it will be 4 3 1 9 2 8
at 2nd it will be..... 4 3 1 2 9 8.
now it will break out of the while(true) loop as everything to one side is less than the pivot (3,1,2) and greater on the other (9,8). I still need to put the pivot in its right place so thats why the rest of the code has to be executed

[2AoiNwbp]

.....quicksort will put the pivot in its right full place.

Why do you assume this? have you tested it? cause I did, and it is not working that way..

regards,
Alejandro

[Void life]

read the wikipedia article on quicksort https://en.wikipedia.org/wiki/Quicksort
quoting a bit from it

. It partitions the portion of the array between indexes left and right, inclusively, by moving all elements less than array[pivotIndex] before the pivot, and the equal or greater elements after it. In the process it also finds the final position for the pivot element, which it returns.

. The it being referred to here is the partition function. And if you do test it it does work that way.....its kindof the bases for quicksort. Whatever position the pivot is put in at the end of 1 run through quicksort is its final position...i.e thats the position the pivot will be at when the array is sorted

[2AoiNwbp]

I think you are excluding the pivot with your code,

quicksort(a,left,SplitPoint-1);
quicksort(a, SplitPoint+1, right);

After calling quicksort in the code above, it will probably call partition again, but excluding the previous pivot (which is not included at left, nor at right of quicksort succesive calls)

On the other hand, once the list is ordered, if i > j in line 50, would break and jump to line 58, producing an extra swap, leaving the list unordered because of this.

[Void life]

no... the point is to exclude the pivot in that code... once the pivot is in its right place you don't need to touch it. The list only becomes ordered at line 58 it is not an extra swap. Before this the pivot will at the leftmost index. Try the code the pivot set to a[left] it works fine. The only problem is when i set it to something else. And if you were to do something like

quicksort(a,left,SplitPoint);
quicksort(a, SplitPoint, right);

including the pivot as you say . You will get an infinite loop.

[Duthomhas]

You can include the pivot in the partitioning, but that is not normal -- it is usually excluded.

One thing that is not obvious is that the median of three method requires you to sort the three potential pivots relative to each other.

There is more about it on the FAQ.
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/quicksort/

I don't actually have time right now to look at your code, but I can when I get home later....

Hope this helps.

[Void life]

Thanks Duoas,

I did read the FAQ about quicksort.

While I can easily sort the 3 potential pivots relative to each other. Im not able to declare the pivot as pivot = a[What_ever_is_median] and just run quicksort. It doesn't sort correctly
I have to make the median the left-most element for my code to work. So my first question is just is there something wrong with my code that makes it not possible to declare the pivot as any element in an array or must whatever element you choose as the pivot be set to the left-most element.

*note im not trying to implement median of 3 method in my code i just changed the pivot from the left most index to pivot = a[left+2] to see if it would work.

[Void life]

Nevermind i think i have it almost figured out. I'm really sorry aabuezo i completely misunderstood what you were saying, you were right about line 58 . But the program needed a bit more modifying.
Thanks for the help.

[2AoiNwbp]

You are welcome Void life, I wish I was more useful to you.

regards,
Alejandro