Quick Sort

Quick Sort is another efficient, comparison-based sorting algorithm that uses the "divide and conquer" strategy. While its worst-case performance is O(n²), its average-case performance is O(n log n), making it one of the fastest sorting algorithms in practice.

The key to Quick Sort's efficiency is the partitioning step. A good partitioning algorithm places the pivot in a way that splits the array into two roughly equal-sized sub-arrays. Unlike Merge Sort, Quick Sort is an in-place sorting algorithm, meaning it requires only a small, constant amount of extra space (O(log n) for the recursion stack).

Quick Sort Visualization

Step 1 of 0

Current Action

Ready to start

Phase

Ready

Pivot Value

None

Pivot (P)

Current Element (j)

Boundary (i)

Swapping

Active Range

Not Active

Partition-based Sorting: Quick sort picks a pivot, partitions elements (smaller left, larger right), then recursively sorts sub-arrays. Average time: O(n log n), Worst case: O(n²).

Quick Sort Algorithm

Quick Sort is a highly efficient, in-place, unstable, comparison-based sorting algorithm. Like Merge Sort, it's a classic example of the "divide and conquer" paradigm.

Algorithm Steps

Partition: Pick a 'pivot' element from the array. Partition the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.
Recurse: Recursively apply the above steps to the sub-arrays of elements with smaller and greater values.
The base case of the recursion is arrays of size zero or one, which are always sorted.

Quick Sort


def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 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