Insertion Sort

Insertion sort is a simple sorting algorithm that works by building up a sorted list one element at a time. It compares each element in the list with the elements to its left until it finds the correct position to insert the current element. The algorithm has a time complexity of O(n^2) in the worst case, but performs better on partially or almost sorted lists. It is often used as a simple sorting algorithm for small data sets or as a subroutine in more complex algorithms.

Insertion Sort Algorithm

The insertion sort algorithm can be described in the following steps:

1. Start with an unsorted list of n elements.
2. Pick the first element in the unsorted list and consider it as the sorted list.
3. For each subsequent element in the unsorted list, compare it with the elements in the sorted list.
4. If the current element is smaller than any element in the sorted list, insert it in its proper position.
5. Repeat steps 3 and 4 for all elements in the unsorted list.
6. Continue this process until the entire list is sorted.

The insertion sort algorithm is simple and efficient for small data sets, but its time complexity is O(n^2) in the worst case, making it less efficient for larger data sets.

Insertion Sort in Python, Java, and C/C++

#include <stdio.h>

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

int main() {
  int arr[] = {12, 11, 13, 5, 6};
  int n = sizeof(arr) / sizeof(arr[0]);

  insertionSort(arr, n);

  int i;
  for (i = 0; i < n; i++)
    printf("%d ", arr[i]);

  return 0;
}

#include <iostream>
using namespace std;

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

int main() {
  int arr[] = {12, 11, 13, 5, 6};
  int n = sizeof(arr) / sizeof(arr[0]);

  insertionSort(arr, n);

  cout << "Sorted array: \n";
  for (int i = 0; i < n; i++)
    cout << arr[i] << " ";

  return 0;
}

class InsertionSort {
  void sort(int arr[]) {
    int n = arr.length;
    for (int i = 1; i < n; ++i) {
      int key = arr[i];
      int j = i - 1;
      while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j = j - 1;
      }
      arr[j + 1] = key;
    }
  }

  static void printArray(int arr[]) {
    int n = arr.length;
    for (int i = 0; i < n; ++i)
      System.out.print(arr[i] + " ");
    System.out.println();
  }

  public static void main(String args[]) {
    int arr[] = { 12, 11, 13, 5, 6 };

    InsertionSort ob = new InsertionSort();
    ob.sort(arr);

    System.out.println("Sorted array");
    printArray(arr);
  }
}

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

arr = [12, 11, 13, 5, 6]
insertionSort(arr)
print("Sorted array is:", arr)

Insertion Sort Applications

Insertion sort has the following applications:

1. Simple sorting: Insertion sort can be used as a simple sorting algorithm for small datasets. It is easy to understand and implement.
2. Online sorting: Insertion sort can be used for sorting elements as they are received, which is useful in real-time applications.
3. Stable sorting: Insertion sort is a stable sorting algorithm, meaning that it maintains the relative order of equal elements.
4. Partial sorting: Insertion sort performs well on partially sorted data, as it only requires minimal movement of elements.
5. Subroutine in other algorithms: Insertion sort is often used as a subroutine in other sorting algorithms, such as Shell sort and Binary Insertion Sort.
6. Adaptive sorting: Insertion sort can be made adaptive by sorting subsets of the data in a certain order, making it more efficient for certain types of data.