Quick sort

Imagine you have a deck of cards, each with a different face value. Your task is to sort these cards in ascending order based on their values. However, you don't have much time to spare.

1. You decide to divide the deck into smaller sub-decks. You just take the top card as the "pivot" and create two new sub-decks: one with cards having face values lower than the pivot and another with cards having face values higher than the pivot. This way, you've divided the large task into smaller, more manageable sub-tasks – sub-decks.
2. Now, you apply the same process recursively until the sub-decks become small enough to be easily sorted (until it's a 1-card sub-deck).
3. Since each sub-deck is already sorted, this implies that the entire deck is sorted in ascending order.

   

Just like quick sort's efficiency in sorting arrays, this approach helps you quickly sort the cards with minimal effort, making it a practical and effective method for sorting tasks in real life.

Description

Quick sort, like merge sort, is based on the divide-and-conquer paradigm. Here are the steps of divide-and-conquer in quick sort:

1. Divide: Partition (rearrange) the array into two parts. $A[l : p - 1]$ (the lower side) and $A[p + 1 : r]$ (the upper side). Such that all elements in the lower side are less than the pivot, and all elements in the upper side are greater or equal to the pivot. The pivot is excluded. For demonstration, here we always choose the rightmost element as the pivot.
2. Conquer: Recursively call quick sort on the two sub-arrays $A[l : p - 1]$ and $A[p + 1 : r]$.
3. Combine: All the sub-arrays are sorted in-place so there's no need to combine them.

Example

Suppose we have an array $\langle 4,2,5,7,9,3,8,6 \rangle$. Let's see the first partition process. In this example, we always choose the rightmost element, $A[r]$, as the pivot.

(a): In the initial array, nothing has yet been processed.

(b-d): The values 4, 2, and 5 are less than the pivot, so are put into the lower side.

(e-f): The values 7 and 9 are put on the upper side. Here we remember where the last element less than the pivot was. If we meet another one while going right, it should be removed to the left part, right?

(g): The value 3 is less than the pivot, so it is swapped with 7, and the lower side extends.

(h): The value 8 is put into the upper side, and the loop terminates.

(i): Finally, the pivot is swapped, such that it lies between the two partitions. And the pivot index is returned.

Now let's see the big picture. We recursively apply the partition process to the two partitions, excluding the pivot index. Resulting in the whole array being sorted in non-descending order.

In every partition process, we have only swapped the elements. So there's no new array created, and we are able to perform the sort within the array.

Pseudocode

QuickSort(A[], l, r):
  if l < r:
    // partition the array around the pivot
    pivot = Partition(A, l, r)
    QuickSort(A, l, pivot - 1)  // recursively sort the lower side
    QuickSort(A, pivot + 1, r)  // recursively sort the upper side

Partition(A[], l, r):
  x = A[r]                  // the pivot
  i = l - 1
  for j = l to r - 1:       // process each element except the pivot
    if A[j] < x:            // does it belong to the lower side?
      i = i + 1
      Exchange(A[i], A[j])  // put the element to the lower side
  Exchange(A[i + 1], A[r])  // put the pivot to the right of the lower side 
  return i + 1              // return the new index of the pivot

In every step, the partition process has only reduced the problem size by 1. This issue can be addressed by opting for a different pivot-picking strategy.

The quick sort algorithm has a worst-case running time of $O(n^2)$ on an input array of $n$ elements. Despite its slow worst-case running time, it's often the best choice for sorting in practice. This is because it has a remarkably more efficient average running time of $O(n\log n)$ when all the elements are distinct.

Variations and improvements

What is the best way to break an array? How to divide the problem so that sub-problems are of the smallest possible size? Of course, we should make two equal parts! However, this means that the pivot should be the median of the elements.

In order to find the median, we would need to use an already sorted array (what we are trying to get). But we might be able to approximate the median in the fastest way possible. Here are some possible methods of choosing the pivot:

• Pick the leftmost, the rightmost, or the middle element.
• Pick a random element.
• Take three elements and choose the median of these.

The median-of-three works as follows:

1. Select three elements from the array, typically the first element (A), the middle element (B), and the last element (C).
2. Determine the median value among A, B, and C.
3. Use the median value as the pivot element for the current partition.

Using the median of three helps avoid some of the potential pitfalls of using just the first, last, or a random element as the pivot. For example:

1. Using the first or last element as the pivot may result in poor performance for already sorted or nearly sorted arrays, leading to a time complexity of $O(n^2)$.
2. Picking a random element as the pivot may lead to inconsistent performance, although it typically performs well on average.

When all the input elements are equal, one subarray is always empty while another has only decreased by one element (the pivot is removed). This causes the worst-case behavior.

Three-way partitioning addresses this issue by dividing the array into three partitions:

1. Values less than the pivot.
2. Values equal to the pivot.
3. Values greater than the pivot.

The benefits of using three-way partitioning include:

1. Better handling of duplicate elements: When the array has many duplicate elements, three-way partitioning avoids unnecessary comparisons and swaps by gathering all the equal elements together in a single partition.
2. Stability: Three-way partitioning maintains the relative order of equal elements in the final sorted array, preserving their original order. It can be essential in certain applications or when sorting objects with multiple key attributes.

Conclusion

In this topic, we've covered the quick sort algorithm. To summarize:

• Quick Sort uses a divide-and-conquer approach, selecting a pivot element and partitioning the array into two sub-arrays: elements less than the pivot and elements greater than the pivot. This process is recursively applied to the sub-arrays until the entire array is sorted.
• While it may have a slow worst-case running time, Quick Sort's average-case performance of $O(n\log n)$ makes it a preferred choice for practical sorting tasks, especially when the elements are distinct.

Now we are ready to move on to the practical part to solidify our knowledge of Quick Sort.