---

📘 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

1. Divide: Choose a pivot and partition the array
2. Conquer: Recursively apply Quick Sort on subarrays
3. 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

---