Understanding QuickSort: A Deep Dive into One of the Fastest Sorting Algorithms

QuickSort is a divide-and-conquer sorting algorithm. Its basic idea is to divide the array into smaller partitions based on a "pivot" element and recursively sort those subarrays. This approach allows QuickSort to handle large datasets efficiently.

How QuickSort Works

• Choose a Pivot: The first step is to choose an element in the array as the "pivot." The pivot can be any element, but typically, it is determined to be the middle, first, or last element of the array. The choice of pivot can affect the algorithm’s performance, especially when dealing with sorted or nearly sorted data.
• Partition the Array: All elements less than the pivot come before the pivot, and all elements greater than the pivot come after the pivot. This results in the pivot being placed in its final sorted position.
• Recursively Sort Subarrays: After partitioning, the pivot is in its final sorted position, but the left and right subarrays still need to be sorted. QuickSort is then recursively applied to these subarrays until the base case is reached.

Suppose we have the following list of integers: [10, 7, 8, 9, 1, 5]

Choose a Pivot: Let's choose 8 as the pivot.

Partition the Array: Elements less than 8 = [7, 1, 5], Elements greater than 8 = [10, 9]

Recursively Sort Subarrays: Recursively apply QuickSort to both subarrays.

For [7, 1, 5], choose 1 as the pivot: Partitioning: [1] | 7, 5 | Recurse into [7, 5]: Choose 5 as pivot: [5] | 7 | For [10, 9], choose 9 as pivot: Partitioning: [9] | 10 |

Final Sorted List: [1, 5, 7, 8, 9, 10]

Best & Average Case: O(nlogn), Worst Case: O(n2)

def quicksort(lst):
    # Base case: if the list has 1 or fewer elements, it's already sorted
    if len(lst) <= 1:
        return lst

    # Choose the pivot element (in this case, the middle element)
    pivot = lst[len(lst) // 2]

    # Partition the list into three parts:
    # 1. 'left' contains elements smaller than the pivot
    # 2. 'middle' contains elements equal to the pivot
    # 3. 'right' contains elements greater than the pivot

    left = [x for x in lst if x < pivot]
    middle = [x for x in lst if x == pivot]
    right = [x for x in lst if x > pivot]

    # Recursively sort the 'left' and 'right' lists, then combine them with 'middle'
    return quicksort(left) + middle + quicksort(right)