Quick Sort

Quick Sort Algorithm

Bubble Sort and Selection Sort are very slow for large datasets. If you have millions of items, you need a faster algorithm.

Quick Sort is exactly that. It is heavily used in real-world software because of its incredible speed.

1. The Divide and Conquer Strategy

Quick Sort uses a strategy called Divide and Conquer.

Instead of trying to sort the whole array at once, it breaks the array into smaller, easier-to-sort pieces. It solves the small pieces, and by doing so, the whole array becomes sorted!

2. How Quick Sort Works

Quick Sort relies on a core concept called Partitioning.

Here is the step-by-step process:

1. Pick a Pivot: Choose one element from the array to be the "pivot" (often the last element).
2. Partitioning: Rearrange the array so that every number smaller than the pivot is placed on its left. Every number larger than the pivot is placed on its right.
3. Lock it in: The pivot is now in its exact, final sorted position!
4. Repeat: Apply the exact same steps to the left sub-array and the right sub-array.

Partitioning: The pivot (4) moves to the middle. Smaller items go left. Larger items go right.

Because the left and right halves keep getting split into smaller and smaller arrays, the sorting happens incredibly fast.

3. A Step-by-Step Example

Let's sort this array: [8, 2, 5, 3, 9, 4]

Step 1: First Partition

• We pick the last element as the pivot: 4.
• We move smaller numbers (2, 3) to the left of 4.
• We move larger numbers (8, 5, 9) to the right of 4.
• Array becomes: [2, 3, 4, 8, 5, 9].
• The number 4 is now permanently sorted!

Step 2: Sort the Left Side

• Look at the left side: [2, 3].
• Pivot is 3. 2 is smaller, so it stays on the left.
• Left side is now completely sorted.

Step 3: Sort the Right Side

• Look at the right side: [8, 5, 9].
• Pivot is 9. Both 8 and 5 are smaller, so they go to the left.
• Array is now [8, 5, 9]. The 9 is permanently sorted.
• Now look at [8, 5]. Pivot is 5. The 8 is larger, so it goes to the right.
• Array becomes [5, 8].

Final Result: [2, 3, 4, 5, 8, 9]. The whole array is sorted!

4. Quick Sort Code Example

Here is a beginner-friendly Python implementation. Notice how the function calls itself (which is called Recursion).

def quick_sort(arr):
    # A single item (or empty array) is already sorted!
    if len(arr) <= 1:
        return arr
    # 1. Pick the pivot (we choose the last element)
    pivot = arr[-1]
    # 2. Create arrays for smaller and larger elements
    smaller = []
    larger = []
    # 3. Partition the data
    for i in range(len(arr) - 1):
        if arr[i] < pivot:
            smaller.append(arr[i])
        else:
            larger.append(arr[i])
    # 4. Recursively sort the left and right, then combine!
    return quick_sort(smaller) + [pivot] + quick_sort(larger)

numbers = [8, 2, 5, 3, 9, 4]
print("Original:", numbers)
print("Sorted:", quick_sort(numbers))

5. Time Complexity

• Average Time Complexity: O(n log n). By constantly splitting the array in half, the algorithm runs incredibly efficiently. This is why it is preferred for large data.
• Worst Case Time Complexity: O(n²). If the array is already sorted and you always pick the last element as the pivot, it degrades into a slow algorithm. (Advanced versions of Quick Sort pick a random pivot to avoid this).