CODEWITHSUNDEEP
quicksort
Roy Shani
Roy Shani

Reputation: 21

K&R quicksort code

I examined the quick sort code in K&R book and after 2 hours I still fail to understand what the first swap (swap(a, left, (left+right)/2);) achieves. I tried removing it and the sorting still works. can someone explain? is it a performance issue? and if so, why? this action seems random to me (that is that on some group of numbers it will improve performance and on some not).

thank you. 

void qsort(int a[], int left, int right)
{
    int i, last;

    if (left >= right)
        return;

    swap(a, left, (left+right)/2);

    last = left;
    for (i = left + 1; i <= right; i++)
        if(a[i] < a[left])
             swap(a, ++last, i);

   swap(a, left, last);
   qsort(a, left, last-1);
   qsort(a, last+1, right);
}

Upvotes: 2

Views: 959

Answers (2)

ioreskovic
ioreskovic

Reputation: 5699

It puts the pivot element onto the very first position of the sub-array.

Then it continues to partition the sub-array around the pivot, so that after the partitioning is done, the sub-array looks like this: [pivot, [elements < pivot], [elements >= pivot]].

After that, the pivot is simply put into proper space, so the sub-array looks like this: [[elements < pivot], pivot, [elements >= pivot]].

And after that, the recursive call is made on two sub-sub-arrays.

Quick sort will always work, regardless of which element is chosen as a pivot. The catch is, if you choose the median element, then the time complexity will be linearithmic (O(nlogn)). However, if you choose, for example, the biggest element as a pivot, then the performance will degrade to quadratic (O(n^2)).

So, in essence, pivot selection is the key to performance of Quick-Sort, but it will work (and when I say work, I mean you'll get a sorted array, eventually).

Upvotes: 4

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726509

K&R implementation chooses the middle index (i.e. (left+right)/2) for the pivot. Removing this line uses the leftmost element for the pivot instead. The implementation still works, but the performance degrades when the array is already sorted.

Wikipedia article explains this:

In the very early versions of quicksort, the leftmost element of the partition would often be chosen as the pivot element. Unfortunately, this causes worst-case behavior on already sorted arrays, which is a rather common use-case. The problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot (as recommended by Sedgewick).

Upvotes: 3

Related Questions