Quick Sort Algorithm: Pseudocode and Implementation

In earlier articles, we explored the quick sort algorithm, its partitioning routine, and different pivot selection methods. Now, let’s put it all together and look at the pseudocode and implementation details for quick sort. By the end of this article, you’ll have a strong understanding of how to implement quick sort in practice.

Prerequisites:

Key Concepts

Before we dive into the code, let’s review the main ideas behind quick sort in simple terms:

  1. Divide and Conquer: Quick sort solves the big problem by breaking it into smaller, more manageable pieces.
  2. Pivot Selection: We choose one element (called the “pivot”) from the array as a reference point.
  3. Partitioning: We rearrange the array around the pivot so that:
    • Smaller elements than pivot go to the left of the pivot
    • Larger elements than pivot go to the right of the pivot
    • After this step, the pivot is exactly where it would be in the final sorted array
  4. Recursion: We repeat the same process on the left and right portions of the array (the smaller pieces).
  5. Stopping Point: We stop dividing when we reach portions with zero or one element, as these are already sorted by definition.

Think of it like organizing books on a shelf - you pick one book as a reference, put shorter books to the left, taller books to the right, and then repeat the process for each group until everything is in order.

Partitioning: Pseudocode

Partitioning is the heart of the quick sort algorithm - it’s the process that rearranges elements in the array so that all elements smaller than the pivot are moved to the left side, and all elements greater than the pivot are moved to the right side. After partitioning, the pivot element is placed in its final sorted position. For a more detailed explanation of how partitioning works, check out our article on Understanding the Partitioning Routine in Quick Sort.

Here’s the pseudocode for the partitioning, using the center element as the pivot:

function partition(array, low, high):
  # Choose the center element as the pivot
  pivotIndex = (low + high) // 2
  pivot = array[pivotIndex]

  # Swap pivot with the last element
  swap array[pivotIndex] with array[high]
  
  # i is the index of the "last element smaller than the pivot"
  i = low

  # Iterate through the sub-array (excluding the pivot which is now at the end)
  for j = low to high - 1:
    # If the current element is less than or equal to the pivot
    if array[j] <= pivot:
      # Swap array[i] and array[j]
      swap array[i] with array[j]
      # Increment i
      i = i + 1

  # Place the pivot in its correct position (between the smaller and larger elements)
  swap array[i] with array[high]

  # Return the index of the pivot (its final sorted position)
  return i

Explanation:

  • array: The array (or sub-array) to be partitioned.
  • low: The starting index of the sub-array.
  • high: The ending index of the sub-array.
  • pivotIndex: The index of center element.
  • pivot: The element chosen as the pivot (here, the center element).
  • i: A pointer keeping track of the boundary between elements smaller than the pivot, and elements greater than the pivot.
  • j: A pointer scanning through the sub-array.
  • The for loop goes from low to high - 1 (excluding the last element, where we temporarily put the pivot).
  • Inside, if array[j] is less than/equal to pivot, we swap array[i] with array[j]. This moves smaller elements to the left.
  • After the loop, we swap array[i] with array[high] (the pivot). This puts the pivot in the correct sorted spot.
  • The function returns the index of the pivot.

Quick Sort: Pseudocode

Now, let’s see the pseudocode for the complete quick sort algorithm:

function quickSort(array, low, high):
  # Base case: if the sub-array has 0 or 1 element, it's already sorted
  if low < high:
    # Partition the array and get the pivot index
    pivotIndex = partition(array, low, high)

    # Recursively sort the sub-array before the pivot
    quickSort(array, low, pivotIndex - 1)

    # Recursively sort the sub-array after the pivot
    quickSort(array, pivotIndex + 1, high)

Explanation:

  • array: The array (or sub-array) to be sorted.
  • low: The starting index.
  • high: The ending index.
  • Base Case: if low < high checks for more than one element. If low is greater than or equal to high, the sub-array has 0 or 1 element and it’s sorted.
  • Partitioning: The partition function rearranges the sub-array and places the pivot. It returns the index of the pivot.
  • Recursive Calls: quickSort calls itself twice:
    • For the sub-array before the pivot (low to pivotIndex - 1).
    • For the sub-array after the pivot (pivotIndex + 1 to high).

Example Walkthrough

Let’s trace a simple example: [7, 2, 1, 6, 8, 5, 3, 4]

  1. quickSort([7, 2, 1, 6, 8, 5, 3, 4], 0, 7):

    • pivotIndex = (0+7)//2 = 3, pivot = 6
    • partition rearranges the array, for example, to [2, 1, 4, 3, 5, 6, 8, 7] , and returns pivotIndex = 5.
    • quickSort([2, 1, 4, 3, 5], 0, 4) // Left sub-array
    • quickSort([8, 7], 6, 7) // Right sub-array

  2. quickSort([2, 1, 4, 3, 5], 0, 4):

    • pivotIndex = (0+4)//2 = 2, pivot = 4
    • partition rearranges, for example, to [2, 1, 3, 4, 5] and returns pivotIndex = 3.
    • quickSort([2, 1, 3], 0, 2) // Left
    • quickSort([5], 4, 4) // Right (single element - base case!)

  3. quickSort([2, 1, 3], 0, 2):

    • pivotIndex = (0+2)//2 = 1, pivot = 1
    • partition rearranges to [1, 2, 3] and returns pivotIndex = 0.
    • quickSort([], -1, -1) // Left (empty - base case!)
    • quickSort([2,3], 1, 2) // Right

  4. quickSort([8, 7], 6, 7): (This continues similarly)

    • pivotIndex = (6+7)//2 = 6, pivot = 7
    • partition rearranges the array to [7, 8] and returns pivotIndex = 6.
    • quickSort([7], 6, 6) // Left sub-array
    • quickSort([8], 7, 7) // Right sub-array

The process continues, recursively partitioning and sorting.

What’s Next?