📘 Quick Sort (with Running Time Analysis)

1️⃣ Introduction

Quick Sort is a highly efficient Divide-and-Conquer sorting algorithm.

🔹 Idea

Select a pivot element
Partition the array into:
- Elements less than pivot
- Elements greater than pivot
Recursively sort the partitions

It is widely used due to its excellent average-case performance.

2️⃣ Working Principle (Divide & Conquer)

🔹 Steps

Divide: Choose a pivot and partition the array
Conquer: Recursively apply Quick Sort on subarrays
Combine: No extra work needed (already sorted in place)

3️⃣ Algorithm (Quick Sort)

🔹 Pseudocode

QuickSort(A, low, high):
   if low < high:
       p = Partition(A, low, high)
       QuickSort(A, low, p-1)
       QuickSort(A, p+1, high)

🔹 Partition Function (Lomuto Method)

Partition(A, low, high):
   pivot = A[high]
   i = low - 1

   for j = low to high-1:
       if A[j] <= pivot:
           i = i + 1
           swap A[i] and A[j]

   swap A[i+1] and A[high]
   return i+1

4️⃣ Example (Step-by-Step)

🔹 Given Array:

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

🔹 Step 1: Choose Pivot (5)

Partition:

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

🔹 Step 2: Left Subarray [1]

Already sorted

🔹 Step 3: Right Subarray [8, 9, 10, 7]

Pivot = 7

[7, 8, 9, 10]

🔹 Final Sorted Array:

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

✔ Sorted successfully

5️⃣ Running Time Analysis

🔹 Recurrence Relation

Best / Average Case:

[
T(n) = 2T(n/2) + O(n)
]

Worst Case:

[
T(n) = T(n-1) + O(n)
]

6️⃣ Time Complexity

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

👉 Worst case occurs when:

Array is already sorted
Poor pivot selection

7️⃣ Space Complexity

Recursive stack:
- Best/Average → O(log n)
- Worst → O(n)

8️⃣ Recursion Tree Analysis (Concept)

🔹 Balanced Partition

Depth = log n
Work per level = n

Total:
[
O(n \log n)
]

🔹 Unbalanced Partition

Depth = n
Work per level = n

Total:
[
O(n²)
]

9️⃣ Characteristics of Quick Sort

✔ In-place sorting
✔ Very fast in practice
✔ Not stable
✔ Performance depends on pivot

🔟 Advantages

Faster than Merge Sort in practice
Requires less memory
Good cache performance
Widely used in real systems

1️⃣1️⃣ Disadvantages

Worst-case O(n²)
Not stable
Recursive overhead

1️⃣2️⃣ Comparison with Merge Sort

Feature	Quick Sort	Merge Sort
Time (Avg)	O(n log n)	O(n log n)
Worst Case	O(n²)	O(n log n)
Space	O(log n)	O(n)
Stability	No	Yes

🔚 Conclusion

Quick Sort is one of the fastest sorting algorithms in practice, especially for large datasets.

Its efficiency depends on good pivot selection, making average performance excellent but worst-case performance poor.

📌 Exam Tip

👉 Always include:

Partition concept
Recurrence relation
Time complexity cases
Example

Quick sort