Python Quick Sort

Python Quick Sort

Quick Sort is another highly efficient, comparison-based sorting algorithm that also uses the Divide and Conquer strategy. It is often faster in practice than other O(n log n) algorithms like Merge Sort.

The key process in quick sort is partitioning. The goal of partitioning is to take an element from the list, called the pivot, and place it in its correct sorted position. All elements smaller than the pivot are moved to its left, and all elements greater than the pivot are moved to its right.

How Quick Sort Works

1. Select a Pivot: Choose an element from the list to be the pivot. Common choices include the first element, the last element (used in our example), the middle element, or a random element.
2. Partition: Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it. After this partitioning, the pivot is in its final sorted position.
3. Recurse: Recursively apply the above steps to the sub-list of elements with smaller values and the sub-list of elements with greater values.

The recursion stops when the sub-lists have zero or one element, as they are already sorted.

Implementing Quick Sort in Python

Here is a common implementation of the quick sort algorithm.

// This function takes last element as pivot, places
// the pivot element at its correct position in sorted
// array, and places all smaller (smaller than pivot)
// to left of pivot and all greater elements to right
def partition(data, low, high):
    i = (low - 1)         // index of smaller element
    pivot = data[high]    // pivot
    for j in range(low, high):
        // If current element is smaller than or equal to pivot
        if data[j] <= pivot:
            // increment index of smaller element
            i = i + 1
            data[i], data[j] = data[j], data[i]
    data[i + 1], data[high] = data[high], data[i + 1]
    return (i + 1)

// The main function to implement QuickSort
def quick_sort(data, low, high):
    if len(data) == 1:
        return data
    if low < high:
        // pi is partitioning index, data[p] is now at right place
        pi = partition(data, low, high)
        // Separately sort elements before and after partition
        quick_sort(data, low, pi-1)
        quick_sort(data, pi+1, high)
// --- Usage ---
my_list = [10, 7, 8, 9, 1, 5]
n = len(my_list)
quick_sort(my_list, 0, n-1)
print("Sorted list is:", my_list)

Time Complexity

• Best Case: O(n log n) - Occurs when the pivot element is always the middle element or near the middle.
• Worst Case: O(n²) - Occurs when the pivot element is always the smallest or largest element. This happens with sorted or reverse-sorted lists if the pivot is chosen as the first or last element.
• Average Case: O(n log n)

Unlike Merge Sort, Quick Sort is an in-place algorithm, meaning it has a space complexity of O(log n) due to recursion, which is better than Merge Sort's O(n).