Insertion Sort in DSA (PHP) – Complete Guide

📌 What is Insertion Sort?

Insertion Sort ek simple sorting algorithm hai jo cards arrange karne jaisa kaam karta hai 🃏

👉 Hum ek-ek element uthate hain aur usko correct position par insert kar dete hain sorted part me.

⚙️ How Insertion Sort Works

Step-by-step:

First element ko sorted maan lo
Next element uthao
Usko previous elements se compare karo
Correct position par insert karo
Process repeat karo

📊 Example (Dry Run)

Array:
[5, 3, 4, 1, 2]

Pass 1:

3 ko 5 se compare → insert before
➡️ [3, 5, 4, 1, 2]

Pass 2:

4 ko correct position par insert
➡️ [3, 4, 5, 1, 2]

Pass 3:

1 sabse aage
➡️ [1, 3, 4, 5, 2]

Pass 4:

2 correct position par
➡️ [1, 2, 3, 4, 5]

💻 Insertion Sort in PHP (Code Example)

<?php
function insertionSort($arr) {
    $n = count($arr);    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i - 1;        // Move elements greater than key
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }        $arr[$j + 1] = $key;
    }    return $arr;
}// Example
$array = [5, 3, 4, 1, 2];
$sortedArray = insertionSort($array);
print_r($sortedArray);?>

<?php
function insertionSort($arr) {
    $n = count($arr);    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i - 1;        // Move elements greater than key
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }        $arr[$j + 1] = $key;
    }    return $arr;
}// Example
$array = [5, 3, 4, 1, 2];
$sortedArray = insertionSort($array);
print_r($sortedArray);?>

⚡ Key Insight

👉 Insertion Sort me array gradually sorted hota hai (left side sorted part banta hai)

⏱️ Time & Space Complexity

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

Space Complexity:
👉 O(1) (in-place)

👍 Advantages

Simple & intuitive
Efficient for small datasets
Best for almost sorted arrays
Stable sorting algorithm

👎 Disadvantages

Large datasets ke liye slow
O(n²) worst case
Comparisons zyada ho sakte hain

🎯 When to Use Insertion Sort?

Small data sets
Nearly sorted arrays
Real-time data sorting
Online sorting (data aata rahe tab bhi use ho sakta hai)

🔥 Insertion Sort vs Selection vs Bubble

Feature	Insertion	Selection	Bubble
Best Case	O(n)	O(n²)	O(n)
Stable	✅ Yes	❌ No	✅ Yes
Efficient	Best for nearly sorted	Not efficient	Moderate
Swaps	Less	Minimum	More

🚀 Conclusion

Insertion Sort ek powerful aur simple algorithm hai jo especially nearly sorted data ke liye best perform karta hai. Beginners ke liye ye DSA ka strong foundation banata hai.

No comments yet! You be the first to comment.

DSA