🚀 DSA: Quicksort Algorithm

Master the Fastest Divide-and-Conquer Sorting Technique

Welcome back to GoNimbus DSA tutorials!
In this lesson, we’ll explore Quicksort — a powerful, efficient, and widely used sorting algorithm that follows the divide-and-conquer strategy.

---

🔍 What Is Quicksort?

Quicksort sorts an array by choosing a pivot element and rearranging the remaining elements such that:

• All smaller (or equal) values go to the left of the pivot.
• All greater values go to the right of the pivot.

Then, it applies the same logic recursively to both sub-arrays until the entire list is sorted.

💡 Recursion means that a function calls itself to solve smaller versions of the same problem.

---

⚡ Speed:

✅ Fast — Average time complexity: O(n log n)
⚠️ Worst Case — O(n²) (happens when the pivot is always the smallest or largest element)

---

🧩 How Quicksort Works (Step-by-Step)

1. Choose a Pivot:
   Select any element from the array as the pivot (in this tutorial, we’ll pick the last element).
2. Partition the Array:
   Move all smaller values to the left of the pivot, and all larger values to the right.
3. Place the Pivot:
   Swap the pivot into its correct sorted position.
4. Repeat (Recursion):
   Apply Quicksort again to the left and right sub-arrays until every sub-array is sorted.

---

🧠 Manual Walkthrough

Let’s take an example to understand this visually.

Array: [11, 9, 12, 7, 3]

Step 1: Choose the pivot → 3
Everything greater than 3 goes to the right. Swap 3 with 11.
→ [3, 9, 12, 7, 11]

Step 2: Choose the next pivot → 11
Arrange numbers so smaller ones are on the left.
→ [3, 9, 7, 11, 12]

Step 3: Now sort [9, 7] → swap to [7, 9]

✅ Result: [3, 7, 9, 11, 12] — the array is sorted!

✨ Each pivot divides the array into smaller parts, making sorting faster with every recursion.

---

🧮 Quicksort Implementation (Python Example)

Here’s how we can implement Quicksort in Python:

def partition(array, low, high):
    pivot = array[high]
    i = low - 1

    for j in range(low, high):
        if array[j] <= pivot:
            i += 1
            array[i], array[j] = array[j], array[i]

    array[i+1], array[high] = array[high], array[i+1]
    return i+1


def quicksort(array, low=0, high=None):
    if high is None:
        high = len(array) - 1

    if low < high:
        pivot_index = partition(array, low, high)
        quicksort(array, low, pivot_index - 1)
        quicksort(array, pivot_index + 1, high)


my_array = [64, 34, 25, 12, 22, 11, 90, 5]
quicksort(my_array)
print("Sorted array:", my_array)

Output:

Sorted array: [5, 11, 12, 22, 25, 34, 64, 90]

---

🧭 Understanding the Code

• partition() → Chooses the pivot and arranges elements around it.
• quicksort() → Calls itself recursively to sort sub-arrays.
• The recursion stops when there’s only 1 or 0 elements in a sub-array.

---

⏱️ Quicksort Time Complexity

Scenario	Time Complexity	Explanation
Best Case	O(n log n)	Pivot splits array evenly each time
Average Case	O(n log n)	Most real-world cases
Worst Case	O(n²)	Pivot always chosen poorly (like smallest/largest element)

⚡ Average Case (O(n log n)) is why Quicksort is one of the fastest comparison-based sorting algorithms used in production systems.

---

💡 Why Quicksort Is So Popular

✅ Highly efficient for large datasets
✅ Works in-place (requires minimal extra memory)
✅ Widely used in standard libraries (C, C++, Python, Java)
✅ Performs faster than most O(n²) sorting algorithms like Bubble or Insertion sort

---

🧰 Visualization Example

Imagine dividing your deck of cards using one card as a reference — everything smaller goes left, everything larger goes right.
Now repeat this for each pile until all cards are sorted. That’s exactly how Quicksort works!

---

📊 Time Complexity Comparison

Algorithm	Average Case	Worst Case
Bubble Sort	O(n²)	O(n²)
Selection Sort	O(n²)	O(n²)
Insertion Sort	O(n²)	O(n²)
Quicksort	O(n log n)	O(n²)

---

🎯 Key Takeaways

• Quicksort is fast, recursive, and efficient for most data sets.
• Average performance beats many simpler algorithms.
• Pivot choice is critical — random or median pivot selection can help avoid worst-case scenarios.

---

🧠 Practice Exercise

Try sorting the following array using Quicksort manually:
[8, 2, 5, 1, 9, 3]

Can you list the pivot and sub-arrays at each recursive step?

---

---