How does the recursive part of quick_sort work?

Question

Here is an implementation of quick_sort found in many places including wikipedia.

Here is my simple synopsis.

• Select a pivot element – ½ of left and right.
• Start index at right and iterate left.
• If Elements[right] < P pick as flip.
• Start index at left and Iterate right.
• If Elements[left] > P pick as a flip.
• Flip the two elements.
• Repeat abou the pivot point
• Repeat recursively for each half

Can someone explain the reasoning behind the two recursive lines:

if (left < j)quick_sort(arr, left, j);
if (i < right)quick_sort(arr, i, right);

Snippet:

  void quick_sort(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--;
        }
      }
    if (left < j)quick_sort(arr, left, j);
    if (i < right)quick_sort(arr, i, right);
  }

Answer 1

Before the recursive calls the algorithm breaks the elements into two partitions: all the elements lesser than the pivot on the left, and all the elements greater than the pivot on the right. The pivot is left right in the middle of these two partitions. Now what does this tells us about the state of things?

To have the array sorted, the elements that are less than the pivot cannot be moved to right of it: they would be out-of-place there. So these elements will never be swapped out of the "lesser" partition. The same applies to the elements on the "greater" partition. From this we can also conclude that the pivot is already in its final resting place: no element on the left will swap with it, and no element on the right will swap with it.

So, having the pivot sorted, all that is left is sorting the two remaining partitions. Since we know we don't need to swap any element out of its partition, we can sort each partition alone. And how do we do that? We use the sorting algorithm we have at hand: quicksort!

But how would it work if we haven't completed the algorithm yet?

We invoke quicksort on each partition. This will break each one into two more partitions, and put one more pivot into its final resting place. Then another level of quicksort starts on each of the new partitions. And on and on, each time with successively smaller partitions, until eventually the partitions are small enough that no sorting is required: a partition of a single element is already sorted. This is where the if tests come in: they test if the partition is big enough to need sorting. If it is, run quicksort on it; if it isn't, the work is done there.

Answer 2

If you start with an array:

[74, 32, 39, 15, 25, 82, 23, 2, 97, 62, 95, 34, 92, 84, 28]

it selects the element in the middle (23), and partitions:

[15 2 ] 23 [ 32 74 32 39 25 82 97 62 95 34 92 84 28]

Note the list is not sorted. Since there's more than one on the left, it calls itself to sort the left partition.

[15 2 ] ...

It picks the middle (15) and partitions:

[2] 15 ...

Then since both the left (1 element) and right (0 elements) are less than two elements each, it returns.

2 15 23 [74 32 39 25 82 97 62 95 34 92 84 28]

Now the right still has more than one element, so it calls itself to sort the right partition.

... [74 32 39 25 82 97 62 95 34 92 84 28]

It picks the middle (97) and partitions:

... [74 32 39 25 82 62 95 34 92 84 28] 97

Now the left has more than one element, so it calls itself to sort the left parition...

...etc.

Eventually it reaches a point where all the subsets are ordered, and returns to the first one:

2 15 23 25 28 32 34 39 62 74 82 84 92 95 97

And it's done!

(I didn't deliberately pick bad pivots, excel chose the numbers for me. Good example that sometimes the pivots aren't stellar though.)

Answer 3

The idea behind quicksort is to swap values around a pivot point. The issue though is that just because you've swapped around one pivot point that happened to be in the middle of the array does not mean that you've swapped around the optimal median value for the values in the array. Therefore once the indexes of i and j have reached the pivot point, and all the values are sorted with respect to that pivot point, you must now recurse over the left and right sides of the array from the pivot, and make sure that each of these "branches" of the array are also optimally sorted around each respective pivot point. Eventually you will reach a point where the array is only a single value, and no more swapping can take place since those singular-values are optimally "swapped" (i.e., they are the pivots).

You mentioned in the comments that you were perplexed by all the "jumping around", but in reality what's happening is that the quicksort mirrors the process that takes place when filling in a binary search tree. The root of the binary search tree acts like the first pivot. Every value inserted into the tree is then sorted with respect to that pivot value. Each recursive call's pivot value then becomes like the subtree-roots of a binary search tree. For instance, from the root you have two subtrees. Every value in the array will be sorted against the root's "pivot value", but only the values that fall to the left-hand-side (i.e., are less than the root-value) will be compared against the left-child subtree root "pivot". The same is true for all the values that are greater than the root pivot-value ... they will be compared against the right-child subtree root value. This process then continues until all the values are inserted into the binary search tree. In the end the complexity on average for both quicksort and inserting into a binary search tree is O(N log N), and the worst-case complexity is O(N).

Answer 4

Each time you use recursion in this example, you use a smaller portion of data, executing a quick_sort over it: both, left and right of pivot element data are used to sort again and again until each 'half' is sorted.