quick sort python recursion

Mastering Quick Sort in Python with Recursion

Explore the Quick Sort algorithm, a highly efficient, comparison-based sorting technique, implemented using recursion in Python. Understand its principles, implementation, and performance characteristics.

Quick Sort is one of the most popular and efficient sorting algorithms. It's a comparison sort, meaning it can sort items of any type for which a 'less-than' relationship is defined. The algorithm employs a divide-and-conquer strategy, recursively breaking down a list into smaller sub-lists until they are sorted. Its average-case time complexity is O(n log n), making it a strong choice for many applications.

Understanding the Quick Sort Algorithm

Quick Sort operates by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. This process is repeated until the entire array is sorted. The choice of pivot significantly impacts the algorithm's performance. Common pivot selection strategies include picking the first element, the last element, a random element, or the median of three elements.

flowchart TD
    A[Start Quick Sort] --> B{Choose Pivot}
    B --> C[Partition Array]
    C --> D{Elements < Pivot}
    C --> E{Elements > Pivot}
    D --> F[Recursively Sort Left Sub-array]
    E --> G[Recursively Sort Right Sub-array]
    F --> H[Combine Sorted Sub-arrays and Pivot]
    G --> H
    H --> I[End Quick Sort]

Flowchart illustrating the Quick Sort algorithm's recursive process.

Implementing Quick Sort in Python

Python's dynamic typing and list manipulation features make implementing Quick Sort straightforward. The recursive nature of the algorithm fits well with Python's function call stack. We'll demonstrate a common implementation that uses the last element as the pivot and partitions the array in-place.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[-1]  # Choose the last element as the pivot
        less = [x for x in arr[:-1] if x <= pivot]
        greater = [x for x in arr[:-1] if x > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)

# Example usage:
my_list = [10, 7, 8, 9, 1, 5]
sorted_list = quick_sort(my_list)
print(f"Original list: {my_list}")
print(f"Sorted list: {sorted_list}")

my_list_2 = [3, 0, 2, 5, -1, 4, 1]
sorted_list_2 = quick_sort(my_list_2)
print(f"Original list 2: {my_list_2}")
print(f"Sorted list 2: {sorted_list_2}")

A simple, readable implementation of Quick Sort using list comprehensions and recursion.

In-Place Quick Sort Implementation

An in-place Quick Sort modifies the original array directly, reducing memory overhead. This typically involves a helper function that takes the array and the start/end indices of the current sub-array to be sorted. The partitioning step rearranges elements such that all elements less than the pivot come before it, and all greater elements come after it.

def partition(arr, low, high):
    pivot = arr[high]  # Choose the last element as the pivot
    i = low - 1  # Index of smaller element

    for j in range(low, high):
        # If current element is smaller than or equal to pivot
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i] # Swap

    arr[i + 1], arr[high] = arr[high], arr[i + 1] # Swap pivot into correct position
    return i + 1

def quick_sort_in_place(arr, low, high):
    if low < high:
        # pi is partitioning index, arr[pi] is now at right place
        pi = partition(arr, low, high)

        # Separately sort elements before partition and after partition
        quick_sort_in_place(arr, low, pi - 1)
        quick_sort_in_place(arr, pi + 1, high)

# Example usage:
my_list_in_place = [10, 7, 8, 9, 1, 5]
quick_sort_in_place(my_list_in_place, 0, len(my_list_in_place) - 1)
print(f"Sorted list (in-place): {my_list_in_place}")

my_list_in_place_2 = [3, 0, 2, 5, -1, 4, 1]
quick_sort_in_place(my_list_in_place_2, 0, len(my_list_in_place_2) - 1)
print(f"Sorted list 2 (in-place): {my_list_in_place_2}")

An in-place Quick Sort implementation for better memory efficiency.