DSA Quick Sort
DSA Quick Sort – Complete Explanation
(Concept • Manual Run-Through • Algorithm • Implementation • Time Complexity)
Quick Sort is one of the fastest and most popular sorting algorithms in DSA.
It works using the Divide and Conquer technique and is widely used in practice.
What is Quick Sort?
Quick Sort:
-
Selects a value called the pivot
-
Rearranges the array so that:
-
Values smaller than pivot go to the left
-
Values greater than pivot go to the right
-
-
Recursively applies the same logic to left and right sub-arrays
-
Continues until sub-arrays have 0 or 1 element
In this explanation, the last element is chosen as the pivot.
Simple Idea (One Line)
Pick a pivot → partition array → recursively sort left & right parts
How Quick Sort Works (Steps)
-
Choose a pivot element
-
Move smaller values to the left of the pivot
-
Move larger values to the right of the pivot
-
Place the pivot in its correct position
-
Recursively apply the same steps on left and right sub-arrays
-
Stop when sub-array size ≤ 1
Manual Run-Through (Step by Step)
Initial Array
Step 1: Choose Pivot
Last element is chosen as pivot.
Step 2: Partition Around Pivot
All elements are greater than 3 → swap pivot with first element.
✔ Pivot 3 is now in correct position.
Step 3: Sort Right Sub-array
Sub-array:
Choose pivot = 11
Rearrange:
✔ Pivot 11 placed correctly.
Step 4: Sort Left Sub-array of 11
Sub-array:
Pivot = 7
Swap:
Final Sorted Array
What Happened in the Manual Run?
✔ Pivot chosen
✔ Array partitioned into smaller parts
✔ Pivot placed in correct position
✔ Sub-arrays reduced in size
✔ Recursion stopped when sub-array size ≤ 1
📌 Each recursive call makes the problem smaller and faster to solve.
Partition Logic (Lomuto Partition Scheme)
📌 This returns the final index of the pivot.
Quick Sort Implementation (Python)
Output
Time Complexity of Quick Sort
Quick Sort sorts n elements.
⏱ Time Complexity Table
| Case | Condition | Time Complexity |
|---|---|---|
| Best Case | Balanced partitions | O(n log n) |
| Average Case | Random order | O(n log n) |
| Worst Case | Pivot always smallest/largest | O(n²) |
📌 Worst case happens when:
-
Array is already sorted
-
Poor pivot selection
Why Average Case Is Fast?
-
Each recursive call splits the array
-
Depth of recursion ≈ log n
-
Each level does O(n) work
Space Complexity
| Metric | Value |
|---|---|
| Extra Space | O(log n) |
| Reason | Recursion stack |
| Type | In-place |
Advantages of Quick Sort
✔ Very fast on average
✔ In-place sorting
✔ Cache-friendly
✔ Widely used in practice
Disadvantages of Quick Sort
❌ Worst-case O(n²)
❌ Not stable
❌ Recursive overhead
How to Avoid Worst Case
✔ Random pivot selection
✔ Median-of-three pivot
✔ Shuffle array before sorting
Exam / Interview Questions (Quick Sort)
Q1. Why is Quick Sort called “Quick”?
👉 Because of its fast average performance
Q2. Is Quick Sort stable?
👉 No
Q3. Worst-case time complexity?
👉 O(n²)
Q4. Why is Quick Sort faster than Bubble Sort?
👉 Fewer comparisons & divide-and-conquer approach
Final Summary
✔ Quick Sort uses divide & conquer
✔ Pivot-based partitioning
✔ Recursive sorting of sub-arrays
✔ Average time complexity: O(n log n)
✔ Worst case: O(n²)
✔ One of the most important DSA algorithms
