Quick Sort Algorithm in Python

Note: this page has been created with the use of AI. Please take caution, and note that the content of this page does not necessarily reflect the opinion of Cratecode.

Sorting algorithms are like the unsung heroes of the programming world. They silently work behind the scenes, ensuring that your data is in the right order, ready to be processed. One such efficient and widely used sorting algorithm is the Quick Sort algorithm. It's quick, intuitive, and a bit of a daredevil. Let's get acquainted with this fascinating algorithm and see how we can implement it in Python.

What is Quick Sort?

Quick Sort is a comparison-based sorting algorithm that employs a divide-and-conquer strategy to sort elements. Imagine you’re in a library with a bunch of unsorted books and you want to sort them by their titles. Instead of painstakingly going through each book, you decide to take a more strategic approach. You pick a random book (we'll call it the pivot) and start placing all books with titles that come before it on the left and those that come after it on the right. You repeat this process for the smaller piles of books until every book is in its correct spot. That’s essentially how Quick Sort works!

The Algorithm

Quick Sort works 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.

Here is a step-by-step breakdown of the process:

1. Choose a Pivot: Select an element from the array as the pivot.
2. Partitioning: Rearrange the array so that all elements less than the pivot come before it, and all elements greater than the pivot come after it.
3. Recursively Apply: Apply the above steps to the sub-arrays of elements with smaller and larger values.

Implementation in Python

Let’s get our hands dirty and implement Quick Sort in Python. Here's a simple and clean implementation:

def quick_sort(arr):
    """Sorts an array using the quick sort algorithm."""
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        less_than_pivot = [x for x in arr[1:] if x <= pivot]
        greater_than_pivot = [x for x in arr[1:] if x > pivot]
        
        # Recursively sort the sub-arrays
        return quick_sort(less_than_pivot) + [pivot] + quick_sort(greater_than_pivot)

# Example usage
unsorted_array = [33, 10, 55, 71, 29, 2]
sorted_array = quick_sort(unsorted_array)
print(sorted_array)  # Output: [2, 10, 29, 33, 55, 71]

In this implementation, we pick the first element as the pivot, then create two sub-arrays: one with elements less than the pivot and the other with elements greater than the pivot. We then recursively sort these sub-arrays and concatenate the results.

Choosing the Pivot

The efficiency of Quick Sort heavily depends on the choice of the pivot. For example, choosing the first element as the pivot in a sorted array results in the worst-case time complexity of O(n²). To avoid this, there are different strategies for choosing a pivot:

1. First Element: Always choose the first element.
2. Last Element: Always choose the last element.
3. Random Element: Choose a random element.
4. Median-of-Three: Choose the median of the first, middle, and last elements.

Here’s a modified version of the Quick Sort implementation using the Median-of-Three pivot strategy:

import random

def median_of_three(arr):
    """Finds the median of the first, middle, and last elements."""
    first = arr[0]
    middle = arr[len(arr) // 2]
    last = arr[-1]
    return sorted([first, middle, last])[1]

def quick_sort(arr):
    """Sorts an array using the quick sort algorithm with the Median-of-Three pivot."""
    if len(arr) <= 1:
        return arr
    else:
        pivot = median_of_three(arr)
        arr.remove(pivot)
        less_than_pivot = [x for x in arr if x <= pivot]
        greater_than_pivot = [x for x in arr if x > pivot]

        return quick_sort(less_than_pivot) + [pivot] + quick_sort(greater_than_pivot)

# Example usage
unsorted_array = [33, 10, 55, 71, 29, 2]
sorted_array = quick_sort(unsorted_array)
print(sorted_array)  # Output: [2, 10, 29, 33, 55, 71]

Performance

Quick Sort is generally faster compared to other O(n²) algorithms like Bubble Sort and Insertion Sort. However, its performance can degrade to O(n²) in the worst case, especially if the pivot selection is poor. On average, Quick Sort operates in O(n log n) time, making it a preferred choice for many applications.

Space Complexity

Quick Sort's space complexity depends on the implementation. The above recursive implementation has a space complexity of O(log n) due to the recursive function calls. An iterative implementation can reduce the space complexity but is slightly more complex to implement.

Stability

Quick Sort is not a stable sort, meaning it does not preserve the relative order of equal elements. Stability is crucial in certain applications, so if you need a stable sorting algorithm, you might want to look at Merge Sort.

Applications

Quick Sort is used in various applications due to its efficiency and simplicity. It's often used in:

• Database Query Processing: To sort records quickly.
• Search Algorithms: As a preprocessing step to sort data.
• Genetic Algorithms: For sorting populations based on fitness values.
• Embedded Systems: Where memory usage is limited.

FAQ