Python Program to Implement Quick Sort

Quick Sort is a highly efficient sorting algorithm that follows the divide-and-conquer paradigm to sort an array or list of elements. It’s widely used in practice due to its average-case time complexity of O(n log n), making it one of the fastest sorting algorithms available.

Problem Statement

You are given an unsorted array of integers. Your task is to implement the Quick Sort algorithm in Python to sort the array in ascending order.

Python Program to Implement Quick Sort

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]  # Choose pivot as the middle element
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    return quick_sort(left) + middle + quick_sort(right)

# Example usage
if __name__ == "__main__":
    input_list = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
    sorted_list = quick_sort(input_list)
    print("Original list:", input_list)
    print("Sorted list:", sorted_list)

How it Works

1. Picking a Pivot: The first step is to choose a pivot element from the array. The pivot is used to partition the array into two parts – elements less than the pivot and elements greater than the pivot. The choice of pivot is crucial for the efficiency of the algorithm. A common approach is to choose the middle element, but other strategies like choosing the first, last, or a random element can also be used.
2. Partitioning: Once the pivot is chosen, the array is partitioned into two segments: elements less than the pivot and elements greater than the pivot. This is done by rearranging the elements in a way that elements less than the pivot come before it, and elements greater than the pivot come after it.
   • Start with two pointers, left and right, at the beginning and end of the array.
   • Move the left pointer towards the right until an element greater than or equal to the pivot is found.
   • Move the right pointer towards the left until an element less than or equal to the pivot is found.
   • Swap the elements at the left and right pointers.
   • Repeat these steps until the left pointer crosses the right pointer.
   After partitioning, the pivot is in its correct sorted position, and elements less than it are on the left, and elements greater than it are on the right.
3. Recursive Sorting: After partitioning, the sub-arrays to the left and right of the pivot need to be sorted recursively. Apply the Quick Sort algorithm to both sub-arrays.
4. Combining: As the recursion unwinds, the sub-arrays are combined to produce the final sorted array. Since the pivot is already in its correct position and the left and right sub-arrays are sorted, no additional work is needed to combine them.
5. Base Case: The base case of the recursion is when the sub-array has only one or zero elements. In this case, the sub-array is already sorted, and the recursion stops.

The key insight of Quick Sort is that it reduces the problem size with each partitioning step. On average, each partitioning step halves the problem size, leading to an average-case time complexity of O(n log n). However, in the worst case, the partitioning might not be balanced, leading to a time complexity of O(n^2). To avoid worst-case scenarios, techniques like choosing a good pivot strategy (median-of-three, random pivot) can be used.

Here’s a summary of the Quick Sort process:

1. Choose a pivot.
2. Partition the array around the pivot.
3. Recursively sort the sub-arrays to the left and right of the pivot.
4. Combine the sorted sub-arrays to get the final sorted array.

This process efficiently sorts the entire array in-place without the need for additional memory for merging.

Input/ Output