Insertion Sort Algorithm

♣ PSEUDOCODE ::

---

INSERTION-SORT(A)
    for j = 1 to A.length - 1
        key = A[j]
        // Insert A[j] into the sorted sequence A[0 ... j-1].
        i  = j - 1
        while i >= 0 and A[i] > key
            A[i + 1] = A[i]
            i = i - 1
        A[i + 1] = key

♣ C / C++ Code ::

---

void InsertionSort(int A[], int len)
{
    int i, j, key;
    for(j = 1; j <= len-1; j++) {
        key = A[j];
        i = j - 1;
        while(i >= 0 && A[i] > key) {
            A[i+1] = A[i];
            i--;
        }
        A[i+1] = key;
    }
}

♣ JAVA Code ::

---

static void InsertionSort(int A[]) {
    int i, j, key;
    for (j = 1; j <= A.length - 1; j++) {
        key = A[j];
        i = j - 1;
        while (i >= 0 && A[i] > key) {
            A[i + 1] = A[i];
            i--;
        }
        A[i + 1] = key;
    }
}

♣ PHP Code ::

---

function InsertionSort($A, $len) {
    for($j=1; $j<=$len-1; $j++):
        $key = $A[$j];
        $i = $j - 1;
        while($i >= 0 && $A[$i] > $key):
            $A[$i+1] = $A[$i];
            $i--;
        endwhile;
        $A[$i+1] = $key;
    endfor;
    return $A;
}

♣ Related UVa Problems ::

---

• 299 - Train Swapping
• 612 - DNA Sorting
• 10327 - Flip Sort

সাহল ইবনে হুনাইফ (রাঃ) হতে বর্ণিত আছে, তিনি বলেন, রাসূলুল্লাহ (সাঃ) বলেছেনঃ যদি কোন লোক পবিত্র অন্তরে শাহাদাত লাভের উদ্দেশ্যে দু'আ করে তাহলে সে নিজের বিছানায় মারা গেলেও তাকে আল্লাহ শহীদদের স্তরে পৌঁছিয়ে দেবেন । (মুসলিমঃ ১৯০৯)