Insertion Sort Algorithm (With Code in C++/Python/java)

Insertion Sort

Insertion sort is a sorting algorithm that sorts a list of items in ascending or descending order by iterating through the list and inserting each element into its correct position in the sorted portion of the list.

Characteristics of Insertion Sort

• Insertion sort is a comparison-based sorting algorithm.
• It has a time complexity of O(n^2) in the worst case and O(n) in the best case.
• It requires O(1) auxiliary space.
• It is stable, meaning that it preserves the relative order of elements with equal keys.
• It is in place, meaning that it does not require any additional space beyond the input array.

Working of Insertion Sort

The algorithm works by iterating through the list and inserting each element into its correct position in the sorted portion of the list. To do this, it compares the current element with the elements in the sorted portion of the list, moving them to the right as necessary to make room for the current element. This process is repeated until the entire list is sorted.

Time Complexity

The time complexity of insertion sort is O(n^2) in the worst case and O(n) in the best case. This means that the algorithm takes longer to run on larger lists, and the time it takes to run increases quadratically with the size of the list.

Auxiliary Space

The auxiliary space required by insertion sort is O(1), meaning that it does not require any additional space beyond the input array.

Best Case

The best case for insertion sort occurs when the list is already sorted in the correct order. In this case, the algorithm will only need to make a single pass through the list and will not have to perform any insertions, resulting in a time complexity of O(n).

Worst Case

The worst case for insertion sort occurs when the list is sorted in the opposite order that it needs to be (i.e. the list is already sorted in ascending order and needs to be sorted in descending order, or the list is already sorted in descending order and needs to be sorted in ascending order). In this case, the algorithm will have to perform a full pass through the list for every element, resulting in a time complexity of O(n^2).

Insertion Sort Algorithm

The insertion sort algorithm works by iterating through a list of items and inserting each element into its correct position in the sorted portion of the list.

pseudocode

Here is the pseudocode for the insertion sort algorithm:

procedure insertionSort(A: array of items)
  for i = 1 to length(A) - 1
    key = A[i]
    j = i - 1
    while j >= 0 and A[j] > key
      A[j + 1] = A[j]
      j = j - 1
    A[j + 1] = key

This algorithm works by starting at the second element in the list (A[1]) and inserting it into the sorted portion of the list by comparing it to the elements before it. If the element is smaller than an element before it, it is swapped with that element. This process is repeated until the element is in its correct position in the sorted portion of the list. The algorithm then moves on to the next element in the list and repeats the process until the entire list is sorted.

Here is an example of the insertion sort algorithm in C++:

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
  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--;
    }
    arr[j + 1] = key;
  }
}

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++) {
    cout << arr[i] << " ";
  }
  return 0;
}

Here is an example of the insertion sort algorithm in Python:

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

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

Here is an example of the insertion sort algorithm in Java:

public class InsertionSort {
  public static void insertionSort(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--;
      }
      arr[j + 1] = key;
    }
  }

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