Implementation of Quick Sort Algorithm in Python

Quick Sort is a popular and efficient algorithm used for sorting lists or arrays. It follows a “divide and conquer” strategy, breaking down the problem into smaller pieces, sorting them, and putting them back together. In this article, we’ll guide you through implementing the Quick Sort algorithm in Python, step by step. We’ll start with a basic implementation and then look at variations like sorting in reverse order or sorting lists of custom objects.

Prerequisites:

Core Idea Recap

Before we jump into the code, let’s quickly remember the main steps of Quick Sort:

  1. Choose a Pivot: Select an element from the array (the pivot).
  2. Partition: Rearrange the array so that all elements smaller than the pivot are on its left, and all elements larger are on its right. The pivot ends up in its final sorted position.
  3. Recurse: Apply the Quick Sort algorithm recursively to the sub-arrays on the left and right of the pivot.
  4. Base Case: The recursion stops when a sub-array has zero or one element (as it’s already sorted).

Basic Quick Sort Implementation (Recursive)

Let’s implement Quick Sort using recursion. We’ll need two functions: one for the main recursive logic (quick_sort) and one for the partitioning step (partition). For simplicity, we’ll use the last element as the pivot in our partition function.

The partition Function

This function takes the array (or sub-array) and the low and high indices as input. It rearranges the elements around the pivot and returns the final index of the pivot.

def partition(arr, low, high):
  # Choose the last element as the pivot
  pivot = arr[high]
  
  # i is the index for the boundary between smaller elements and larger elements
  # Initialize i to be just before the start of the sub-array
  i = low - 1 

  # Iterate through the sub-array from low to high-1 (excluding the pivot)
  for j in range(low, high):
    # If the current element is less than or equal to the pivot
    if arr[j] <= pivot:
      # Increment the boundary index i
      i = i + 1
      # Swap the element at index i with the current element at index j
      # This moves the smaller element arr[j] to the left side
      arr[i], arr[j] = arr[j], arr[i]

  # After the loop, all elements smaller than the pivot are to the left of index i+1
  # Place the pivot in its correct final position (at index i+1)
  # Swap the pivot (arr[high]) with the element at the boundary (arr[i+1])
  arr[i + 1], arr[high] = arr[high], arr[i + 1]
  
  # Return the index where the pivot ended up
  return i + 1

The quick_sort Function

This function implements the recursive logic. It calls partition and then recursively calls itself on the two resulting sub-arrays.

def quick_sort(arr, low, high):
  # Check if there are elements to sort (low < high means at least 2 elements)
  if low < high:
    # Partition the array and get the pivot's final index (pi)
    pi = partition(arr, low, high)

    # Recursively call quick_sort on the sub-array before the pivot
    # Elements from low to pi-1
    quick_sort(arr, low, pi - 1)

    # Recursively call quick_sort on the sub-array after the pivot
    # Elements from pi+1 to high
    quick_sort(arr, pi + 1, high)

Putting It Together

Now, let’s see how to use these functions to sort an array:

# Example array to sort
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)

print("Original array:", arr)

# Call quick_sort on the entire array
# low = 0 (start index), high = n-1 (end index)
quick_sort(arr, 0, n - 1)

print("Sorted array:", arr)
# Output:
# Original array: [10, 7, 8, 9, 1, 5]
# Sorted array: [1, 5, 7, 8, 9, 10]

Explanation:

  1. We define the partition and quick_sort functions as shown above.
  2. We create an example list arr.
  3. We call quick_sort with the initial low index as 0 and the initial high index as n-1 (the last index of the array).
  4. The quick_sort function handles the recursive calls and partitioning until the entire array is sorted.

Sorting in Descending Order

Want to sort from largest to smallest? It’s a simple change! Just modify the comparison in the partition function. Instead of checking if arr[j] <= pivot, check if arr[j] >= pivot.

def partition_desc(arr, low, high):
  pivot = arr[high]
  i = low - 1
  for j in range(low, high):
    # Change comparison to >= for descending order
    if arr[j] >= pivot: 
      i = i + 1
      arr[i], arr[j] = arr[j], arr[i]
  arr[i + 1], arr[high] = arr[high], arr[i + 1]
  return i + 1

def quick_sort_desc(arr, low, high):
  if low < high:
    pi = partition_desc(arr, low, high) # Use the descending partition
    quick_sort_desc(arr, low, pi - 1)
    quick_sort_desc(arr, pi + 1, high)

# Example
arr_desc = [10, 7, 8, 9, 1, 5]
n = len(arr_desc)
print("\nOriginal array for descending sort:", arr_desc)
quick_sort_desc(arr_desc, 0, n - 1)
print("Sorted array (descending):", arr_desc)
# Output:
# Original array for descending sort: [10, 7, 8, 9, 1, 5]
# Sorted array (descending): [10, 9, 8, 7, 5, 1]

Sorting Custom Objects

What if you have a list of objects, like students with names and ages, and you want to sort them by age? You can make your Quick Sort more flexible by using a key function (similar to Python’s built-in sorted()) to specify how to compare elements.

class Student:
  def __init__(self, name, age):
    self.name = name
    self.age = age

  # This helps in printing the object nicely
  def __repr__(self):
    return f"({self.name}, {self.age})"

def partition(arr, low, high, key=lambda x: x):
  # Use the key function to get the comparison value
  pivot_value = key(arr[high])
  i = low - 1
  for j in range(low, high):
    # Compare using the key function
    if key(arr[j]) <= pivot_value:
      i = i + 1
      arr[i], arr[j] = arr[j], arr[i]
  arr[i + 1], arr[high] = arr[high], arr[i + 1]
  return i + 1

def quick_sort(arr, low, high, key=lambda x: x):
  if low < high:
    # Use the student partition function
    pi = partition(arr, low, high, key)
    quick_sort(arr, low, pi - 1, key)
    quick_sort(arr, pi + 1, high, key)

# Example with Student objects
students = [
  Student("Alice", 22),
  Student("Bob", 20),
  Student("Charlie", 25),
  Student("David", 22) 
]
n = len(students)

print("\nOriginal student list:", students)
# Sort by age using a lambda function
quick_sort(students, 0, n - 1, key=lambda student: student.age)
print("Sorted student list by age:", students)
# Output:
# Original student list: [(Alice, 22), (Bob, 20), (Charlie, 25), (David, 22)]
# Sorted student list by age: [(Bob, 20), (Alice, 22), (David, 22), (Charlie, 25)] 
# Note: Quick sort is not stable, so the order of Alice and David (both age 22) might vary.

# You can also sort by name if needed
quick_sort(students, 0, n - 1, key=lambda student: student.name)
print("Sorted student list by name:", students)
# Output would show students sorted alphabetically by name

This approach is more flexible because you can sort by any attribute without creating separate partition functions.

What’s Next?

Now that you’ve seen how to implement Quick Sort in Python, you can explore further: