Insertion Sort

1def insertion_sort(a):2    for i in range(1, len(a)):3        key = a[i]4        j = i - 15        # Shift larger elements one slot to the right6        while j >= 0 and a[j] > key:7            a[j + 1] = a[j]8            j -= 19        a[j + 1] = key10    return a11
12
13nums = [7, 3, 9, 1, 5, 8, 2]14print("Before:", nums)15insertion_sort(nums)16print("After: ", nums)

1function insertionSort(a) {2    for (let i = 1; i < a.length; i++) {3        const key = a[i];4        let j = i - 1;5        // Shift larger elements right to open a slot for key6        while (j >= 0 && a[j] > key) {7            a[j + 1] = a[j];8            j--;9        }10        a[j + 1] = key;11    }12    return a;13}14
15const data = [5, 2, 9, 1, 7, 3];16console.log("Before:", data);17console.log("Sorted:", insertionSort([...data]));

1import java.util.Arrays;2
3public class Main {4    static void insertionSort(int[] arr) {5        for (int i = 1; i < arr.length; i++) {6            int key = arr[i];7            int j = i - 1;8            // Shift larger elements one slot to the right9            while (j >= 0 && arr[j] > key) {10                arr[j + 1] = arr[j];11                j--;12            }13            arr[j + 1] = key;14        }15    }16
17    public static void main(String[] args) {18        int[] arr = {7, 3, 9, 1, 5, 8, 2};19        System.out.println("Before: " + Arrays.toString(arr));20        insertionSort(arr);21        System.out.println("After:  " + Arrays.toString(arr));22    }23}

1#include <iostream>2#include <vector>3
4void printVec(const std::vector<int>& a) {5    for (int x : a) std::cout << x << " ";6    std::cout << "\n";7}8
9void insertionSort(std::vector<int>& a) {10    for (size_t i = 1; i < a.size(); ++i) {11        int key = a[i];12        int j = static_cast<int>(i) - 1;13        // Shift larger elements one slot to the right14        while (j >= 0 && a[j] > key) {15            a[j + 1] = a[j];16            --j;17        }18        a[j + 1] = key;19    }20}21
22int main() {23    std::vector<int> data = {7, 3, 9, 1, 5, 8, 2};24    std::cout << "Before: ";25    printVec(data);26    insertionSort(data);27    std::cout << "After:  ";28    printVec(data);29    return 0;30}

1#include <stdio.h>2
3void printArr(const int a[], int n) {4    for (int i = 0; i < n; i++) printf("%d ", a[i]);5    printf("\n");6}7
8void insertionSort(int a[], int n) {9    for (int i = 1; i < n; i++) {10        int key = a[i];11        int j = i - 1;12        // Shift larger elements one slot to the right13        while (j >= 0 && a[j] > key) {14            a[j + 1] = a[j];15            j--;16        }17        a[j + 1] = key;18    }19}20
21int main(void) {22    int data[] = {7, 3, 9, 1, 5, 8, 2};23    int n = sizeof(data) / sizeof(data[0]);24    printf("Before: ");25    printArr(data, n);26    insertionSort(data, n);27    printf("After:  ");28    printArr(data, n);29    return 0;30}

1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74nums[1] ← 75nums[2] ← 36nums[3] ← 97nums[4] ← 18nums[5] ← 59nums[6] ← 810nums[7] ← 211DECLARE i : INTEGER12DECLARE j : INTEGER13DECLARE key : INTEGER14
15// Insert each value into the sorted part on its left16FOR i ← 2 TO n17    key ← nums[i]18    j ← i - 119    WHILE j > 0 AND nums[j] > key DO20        nums[j + 1] ← nums[j]21        j ← j - 122    ENDWHILE23    nums[j + 1] ← key24NEXT i25
26FOR i ← 1 TO n27    OUTPUT nums[i]28NEXT i