---

📘 Quick Sort (QuickSort) — Sorting Algorithm

Quick Sort is one of the fastest and most widely used sorting algorithms. It follows the Divide and Conquer strategy.

---

📌 Idea of Quick Sort

1. Choose a pivot element.
2. Partition the array so that:
   • Elements less than pivot → left
   • Elements greater than pivot → right
3. Recursively apply Quick Sort on left and right subarrays.
4. Combine results → sorted array.

---

📌 Why Quick Sort Is Fast?

• Very good average-case performance
• Small constant factors
• Excellent cache performance
• In-place (low memory usage)

Most programming languages use some variant of Quick Sort (or its hybrid form).

---

📘 Partitioning Methods

✔ Lomuto Partition Scheme (simple)

• Pivot = last element
• Move all smaller elements to left side

✔ Hoare Partition Scheme (efficient)

• Pivot = first or mid element
• Uses two pointers that move inward

(We will code Lomuto, as it’s simplest for learning.)

---

📘 Time Complexity

Case	Time
Best Case	O(n log n)
Average Case	O(n log n)
Worst Case	O(n²)

Worst case occurs when:

• Array already sorted
• Pivot is smallest or largest

To avoid worst-case, randomized quick sort is used.

---

📘 Space Complexity

• O(log n) for recursion (best / average)
• O(n) in worst case (skewed partitions)

---

📌 Characteristics

• In-place (no extra array)
• Not stable (order of equals not preserved)
• Very fast in practice
• Used widely in system libraries

---

📘 Python Implementation of Quick Sort (Lomuto Partition)

def quick_sort(arr, low, high):
    if low < high:
        # Partition the array
        p = partition(arr, low, high)
        
        # Recursively apply quicksort to left and right parts
        quick_sort(arr, low, p - 1)
        quick_sort(arr, p + 1, high)


def partition(arr, low, high):
    pivot = arr[high]  # Pivot = last element
    i = low - 1  # Pointer for smaller elements

    for j in range(low, high):
        # If current element is <= pivot, swap it to left part
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    # Place pivot in the correct position
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1


# Example usage:
arr = [10, 7, 8, 9, 1, 5]
quick_sort(arr, 0, len(arr) - 1)
print("Sorted array:", arr)

---

📘 Python Implementation (Randomized Quick Sort)

Prevents worst-case scenarios.

import random

def randomized_quick_sort(arr, low, high):
    if low < high:
        # Randomly select pivot index
        pivot_index = random.randint(low, high)
        arr[pivot_index], arr[high] = arr[high], arr[pivot_index]

        p = partition(arr, low, high)
        randomized_quick_sort(arr, low, p - 1)
        randomized_quick_sort(arr, p + 1, high)

(Uses the same partition() function defined above.)

---

📘 Example Output

For input:

[10, 7, 8, 9, 1, 5]

Output:

[1, 5, 7, 8, 9, 10]

---

📌 Summary for Exams

• Quick Sort uses pivot + partitioning
• Works on Divide & Conquer
• Average time = O(n log n)
• Worst case = O(n²)
• Not stable
• In-place
• Fast in real practice
• Randomized version avoids worst-case

---