### Quicksort pivot & quicksort complexity

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?

 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162`` `````` 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)).
Last edited on
closed account (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:
 ``12`` `````` 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
Last edited on
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
Last edited on
closed account (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
Last edited on
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
closed account (2AoiNwbp)
I think you are excluding the pivot with your code,
 ``12`` ``````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.
Last edited on
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.
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.
Thanks Duoas,

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.
Last edited on
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.
closed account (2AoiNwbp)
You are welcome Void life, I wish I was more useful to you.

regards,
Alejandro
Topic archived. No new replies allowed.