Insertion sort

Insertion sort is a simple sorting algorithm that builds the sorted list one element at a time by inserting each element in its correct position. It has a time complexity of O(n^2) in the worst case, which makes it relatively slow for large lists. However, it can be efficient for small lists or lists that are already partially sorted.

Here is a pseudocode implementation of the insertion sort algorithm:

procedure insertionSort(A: list of sortable items)
    n = length(A)
    for i = 1 to n-1 inclusive do
        j = i
        while j > 0 and A[j-1] > A[j] do
            swap(A[j], A[j-1])
            j = j - 1
        end while
    end for
end procedure

In this implementation, the insertionSort the procedure takes a list of items as input and sorts it using the insertion sort algorithm. The procedure uses a loop to iterate through the list and compares each element to the ones before it. If an element is smaller than its neighbors, it is swapped with the smaller element until it is in its correct position. This process is repeated until the list is sorted.

Insertion sort is a simple and easy-to-understand algorithm that can be useful in some situations where the list is already partially sorted or the list is small. However, for larger lists, it may be more efficient to use a different sorting algorithm with lower time complexity.

Code of Insertion sort in Different Languages

Java

public class InsertionSort {

    public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int j = i;
            while (j > 0 && arr[j - 1] > arr[j]) {
                // swap arr[j] and arr[j-1]
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                j--;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 1, 4, 2, 8};
        sort(arr);
        System.out.println(Arrays.toString(arr)); // [1, 2, 4, 5, 8]
    }
}

C#

using System;

namespace SortingAlgorithms
{
    public static class InsertionSort
    {
        public static void Sort(int[] arr)
        {
            int n = arr.Length;
            for (int i = 1; i < n; i++)
            {
                int j = i;
                while (j > 0 && arr[j - 1] > arr[j])
                {
                    // swap arr[j] and arr[j-1]
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                    j--;
                }
            }
        }
    }
}

c++

#include <iostream>
#include <algorithm>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int j = i;
        while (j > 0 && arr[j - 1] > arr[j]) {
            // swap arr[j] and arr[j-1]
            std::swap(arr[j], arr[j - 1]);
            j--;
        }
    }
}

int main() {
    int arr[] = {5, 1, 4, 2, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    return 0;
}

PHP

function insertionSort(array &$arr) {
    $n = count($arr);
    for ($i = 1; $i < $n; $i++) {
        $j = $i;
        while ($j > 0 && $arr[$j - 1] > $arr[$j]) {
            // swap $arr[$j] and $arr[$j-1]
            $temp = $arr[$j];
            $arr[$j] = $arr[$j - 1];
            $arr[$j - 1] = $temp;
            $j--;
        }
    }
}

$arr = [5, 1, 4, 2, 8];
insertionSort($arr);
print_r($arr); // [1, 2, 4, 5, 8]

Python

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        j = i
        while j > 0 and arr[j - 1] > arr[j]:
            # swap arr[j] and arr[j-1]
            arr[j], arr[j - 1] = arr[j - 1], arr[j]
            j -= 1

arr = [5, 1, 4, 2, 8]
insertion_sort(arr)
print(arr)  # [1, 2, 4, 5, 8]

JavaScript

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let j = i;
        while (j > 0 && arr[j - 1] > arr[j]) {
            // swap arr[j] and arr[j-1]
            [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
            j--;
        }
    }
}

const arr = [5, 1, 4, 2, 8];
insertionSort(arr);
console.log(arr);  // [1, 2, 4, 5, 8]

Conclusion

The insertion sort algorithm is a simple and easy-to-understand sorting algorithm that can be useful in some situations where the list is already partially sorted or the list is small. However, for larger lists, it may be more efficient to use a different sorting algorithm with lower time complexity. It is important to consider the specific requirements of the problem and choose the appropriate sorting algorithm to ensure that it runs efficiently and effectively.

Bubble Sort Algorithm

https://messagehimessage.com/jokes/