Optimizing Quick Sort Algorithm for Efficiency and Best Practices

[WalidKhan]

I am currently working on implementing the Quick Sort algorithm in Python, and while my code seems to work correctly, I am eager to optimize it for better performance and adhere to best practices.

I would appreciate insights from the community on how to fine-tune my Quick Sort implementation to make it more efficient, especially when dealing with large datasets. Are there specific techniques, pivot selection strategies, or partitioning schemes that are recommended for faster sorting?

Additionally, I would like to know how to handle edge cases and prevent potential issues like stack overflow during recursion, especially when dealing with arrays that are nearly sorted or already sorted.

Here's my current implementation:

import random

def quick_sort(arr):
    _quick_sort(arr, 0, len(arr) - 1)

def _quick_sort(arr, low, high):
    if low < high:
        # Randomly select the pivot to avoid worst-case scenarios
        pivot_index = random.randint(low, high)
        arr[high], arr[pivot_index] = arr[pivot_index], arr[high]

        # Perform the partition and get the pivot index
        pivot_index = partition(arr, low, high)

        # Recursively sort the two partitions
        _quick_sort(arr, low, pivot_index - 1)
        _quick_sort(arr, pivot_index + 1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# Sample usage:
unsorted_array = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
quick_sort(unsorted_array)
print(unsorted_array)

In this implementation, the _quick_sort function handles the recursive sorting, while the partition function rearranges the elements around the pivot using the Lomuto partition scheme. We use the random pivot selection strategy to avoid worst-case scenarios and improve average performance.

It is worth mentioning that even with these optimizations, Quick Sort's worst-case time complexity is O(n^2) for an already sorted or nearly sorted array. However, the random pivot selection helps to mitigate this issue in practice, making Quick Sort generally efficient and widely used in many sorting applications.

For my initial understanding of the subject, I have been using articles on Scaler's Quick Sort Algorithm, but I'm open to suggestions and code samples that show how to optimize the Quick Sort algorithm in Python while maintaining its correctness and making sure it operates robustly in a variety of scenarios. Thank you for your valuable expertise and time!

Edited November 16, 2023 by Phi for All
commercial link removed by moderator

[Sensei]

4 hours ago, WalidKhan said:

Additionally, I would like to know how to handle edge cases and prevent potential issues like stack overflow during recursion, especially when dealing with arrays that are nearly sorted or already sorted.

https://www.google.com/search?q=python+recursion+limit

"Python has a default maximum recursion depth of 1000"

As you can see, this is much worse than, for example, in C/C++ on Windows, where you have a default of 1 MB per thread.

You should create a special debugging version that prints the current level of recursion and/or calculates the maximum depth it has reached so you can calculate at what number of elements in the array problems will occur.

 

[Sensei]

1) make function that will dynamically generate arrays with random values and random size

2) create a function that will check if the array is correctly sorted

3) create a loop that will generate arrays, sort them and check if they are correctly sorted and warn you if they don't match (dump unsorted array to know in what circumstances it failed!)

4) run it millions of times e.g. overnight

Programmers call it "unit testing":

https://en.wikipedia.org/wiki/Unit_testing

 

Edited July 19, 2023 by Sensei