Quick Sort in DSA (PHP) – Complete Guide

📌 What is Quick Sort?

Quick Sort ek Divide and Conquer algorithm hai jo array ko efficiently sort karta hai.

👉 Ye ek pivot element choose karta hai
👉 Phir array ko 2 parts me divide karta hai:

Smaller than pivot
Greater than pivot

⚙️ How Quick Sort Works

Step-by-step:

Ek pivot element choose karo
Array ko partition karo (pivot ke left chhote, right bade)
Left aur right subarrays ko recursively sort karo
Final sorted array milta hai

📊 Example (Dry Run)

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

Step 1: Pivot = 5

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

Step 2: Pivot = 1

[] 1 []

Step 3: Pivot = 9

[7,8] 9 [10]

Final Sorted Array:

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

💻 Quick Sort in PHP (Code Example)

<?php
function quickSort($arr) {
    if (count($arr) < 2) {
        return $arr;
    }    $pivot = $arr[0];
    $left = [];
    $right = [];    for ($i = 1; $i < count($arr); $i++) {
        if ($arr[$i] <= $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }    return array_merge(
        quickSort($left),
        [$pivot],
        quickSort($right)
    );
}// Example
$array = [10, 7, 8, 9, 1, 5];
$sortedArray = quickSort($array);
print_r($sortedArray);
?>

<?php
function quickSort($arr) {
    if (count($arr) < 2) {
        return $arr;
    }    $pivot = $arr[0];
    $left = [];
    $right = [];    for ($i = 1; $i < count($arr); $i++) {
        if ($arr[$i] <= $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }    return array_merge(
        quickSort($left),
        [$pivot],
        quickSort($right)
    );
}// Example
$array = [10, 7, 8, 9, 1, 5];
$sortedArray = quickSort($array);
print_r($sortedArray);
?>

⚡ Key Insight

👉 Quick Sort me pivot selection sabse important hota hai
👉 Good pivot = fast sorting 🚀
👉 Bad pivot = slow performance 😬

⏱️ Time & Space Complexity

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

Space Complexity:
👉 O(log n) (recursive stack)

👍 Advantages

Very fast in practice 🚀
In-place sorting (no extra array needed in optimized version)
Widely used in real-world systems

👎 Disadvantages

Worst case O(n²)
Not stable
Pivot selection tricky

🎯 When to Use Quick Sort?

Large datasets
Fast performance required
In-memory sorting
Interview preparation

🔥 Quick Sort vs Merge Sort

Feature	Quick Sort	Merge Sort
Average Time	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
Speed	Faster in practice	Stable

🚀 Conclusion

Quick Sort ek high-performance sorting algorithm hai jo real-world applications me widely use hota hai. Interviews me ye sabse important sorting algorithm mana jata hai 🔥

No comments yet! You be the first to comment.

DSA