Quick Sort Simplified: The Ultimate Beginner's Guide to Fast Sorting

In our previous articles, we've explored sorting algorithms like Bubble Sort, Selection Sort, Insertion Sort, and Merge Sort. Now, let's dive into Quick Sort, another popular and efficient sorting algorithm widely used in practice.

What is Quick Sort?

Quick Sort is a divide-and-conquer algorithm that sorts an array by partitioning it into smaller sub-arrays. It selects a 'pivot' element and reorders the array such that all elements less than the pivot come before it, and all elements greater than the pivot come after it. The process is recursively applied to the sub-arrays.

Key Concepts of Quick Sort

1. Pivot Selection: The algorithm selects a pivot element (can be the first, last, or a random element).

2. Partitioning: Rearranging the array so that elements smaller than the pivot move to the left, and elements larger move to the right.

3. Recursion: Quick Sort then recursively applies the same steps to the sub-arrays on both sides of the pivot.\

Ways to Choose the Pivot in Quick Sort

Choosing the right pivot is key to the efficiency of Quick Sort. There are several common strategies to select the pivot:

1. First Element: Select the first element in the array as the pivot.

   • Advantage: Simple and quick.

   • Disadvantage: Can lead to poor performance on already sorted or nearly sorted arrays.

2. Last Element: Select the last element as the pivot.

   • Advantage: Easy to implement, often used in introductory explanations.

   • Disadvantage: Like the first element, it can cause inefficient sorting in certain cases.

3. Random Element: Select a random element from the array.

   • Advantage: More likely to avoid worst-case performance.

   • Disadvantage: Requires random number generation, slightly more complex.

4. Median of Three: Select the median of the first, middle, and last elements as the pivot.

   • Advantage: A good balance, reduces the chances of hitting worst-case performance.

   • Disadvantage: Slightly more computation needed to determine the median.

For simplicity, we'll use the last element as the pivot in the following explanation.

Quick Sort Algorithm in Action

Let’s sort the array [10, 80, 30, 90, 40] using Quick Sort, with the last element as the pivot. Here is step-by-step explanation of Quick Sort Using the First Element as Pivot.

Step 1: Choose the Pivot

• Pivot: The last element, 40.

  

Step 2: Partition the Array

• We need to rearrange the array so that all elements smaller than 40 are to the left, and all elements larger than 40 are to the right of 40.

  • Comparisons:

    10 < 40: Keep 10 on the left.

    80 > 40: Ignore it for now.

    30 < 40: Swap 30 with 80.

  • Array after swapping: [10, 30, 80, 90, 40]

• Now, swap the pivot 40 with 80 to place the pivot in its correct position.

• Array after partition: [10, 30, 40, 90, 80]

• The pivot 40 is now correctly placed, and we have two sub-arrays: [10, 30] on the left and [90, 80] on the right.

Step 3: Recursively Sort the Left Sub-array [10, 30]

• Pivot: The last element, 30.

• Comparisons:

  10 < 30: Keep 10 on the left.

• Since 30 is already in its correct position, the array is already sorted.

• Array after partition: [10, 30]

No further sorting is needed for this sub-array.

Step 4: Recursively Sort the Right Sub-array [90, 80]

• Pivot: The last element, 80.

• Comparisons:

  90 > 80: Swap 90 with 80.

• Array after partition: [80, 90]

The sub-array [80, 90] is now sorted.

step 4: Final Sorted Array

After sorting all the sub-arrays, the fully sorted array becomes:

• Sorted array: [10, 30, 40, 80, 90]

Comparision of Insertion and Quick sorts

Oh, wait... did you notice the similarity? At first glance, Quick Sort and Insertion Sort might seem alike because both involve comparing elements and rearranging them in the correct order. However, their underlying methods and strategies are quite different. Here's why they may appear similar but are actually distinct:

Pseudocode for Quick Sort

Here’s a simple pseudocode for Quick Sort:

function quickSort(arr, low, high):
    if low < high:
        pivotIndex = partition(arr, low, high)
        quickSort(arr, low, pivotIndex - 1)  // Sort left part
        quickSort(arr, pivotIndex + 1, high) // Sort right part

function partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j = low to high - 1:
        if arr[j] < pivot:
            i = i + 1
            swap arr[i] with arr[j]
    swap arr[i + 1] with arr[high]
    return (i + 1)

Python Code for Quick Sort

Let’s translate the pseudocode into Python:

# Quick Sort in Python

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)  # Recursively sort the left part
        quick_sort(arr, pi + 1, high)  # Recursively sort the right part

def partition(arr, low, high):
    pivot = arr[high]  # Choosing the last element as the pivot
    i = low - 1  # Index of smaller element
    for j in range(low, high):
        if arr[j] < pivot:
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]  # Swap if current element is smaller
    arr[i + 1], arr[high] = arr[high], arr[i + 1]  # Move pivot to correct position
    return i + 1

# Example usage
arr = [8, 3, 1, 7, 0, 10, 2]
n = len(arr)
quick_sort(arr, 0, n - 1)
print("Sorted array is:", arr)

Explanation:

• quick_sort: The main function that recursively sorts the array by calling the partition function.

• partition: Divides the array around a pivot and rearranges elements.

When you run the above code, the output will be:

Sorted array is: [0, 1, 2, 3, 7, 8, 10]

Advantages of Quick Sort

• Efficiency: Quick Sort is much faster than simpler algorithms like Bubble Sort, Insertion Sort, and even Selection Sort in most cases.

• In-place Sorting: It doesn’t require extra space for another array, making it more space-efficient than Merge Sort.

• Divide and Conquer: This approach simplifies the problem by breaking it into smaller sub-problems.

Disadvantages of Quick Sort

• Worst-case Time Complexity: If the pivot is poorly chosen (e.g., always the smallest or largest element), the performance degrades to O(n²).

• Unstable: Quick Sort is not a stable sorting algorithm, meaning it doesn’t maintain the relative order of equal elements.

• Recursion: For large datasets, excessive recursion could lead to stack overflow issues.

Time Complexity of Quick Sort

• Best Case: O(n log n) – This happens when the pivot divides the array into two nearly equal parts.

• Average Case: O(n log n) – Even for randomly distributed inputs, Quick Sort performs efficiently.

• Worst Case: O(n²) – This occurs when the pivot is poorly chosen, leading to unbalanced partitions (e.g., when the array is already sorted).

Conclusion

Quick Sort is one of the most widely used sorting algorithms due to its efficiency and in-place sorting. It performs best when the pivot is chosen well, balancing the array division. Understanding Quick Sort’s behavior, from how it partitions arrays to how it performs in different scenarios, gives you a powerful tool for tackling sorting problems.

Quick Sort might seem a bit tricky at first, but once you visualize how it works, it becomes an intuitive and valuable algorithm to use in your programming toolkit.