Insertion Sort

Problem

Sort an array using insertion sort.

Solution

As a typical adaptive sort, insertion sort excels at handling partially sorted lists and pairs well with other common sorting algorithms like Quicksort Algorithm and Merge Sort Algorithm.

Insertion sort is a sorting algorithm that positions an unsorted element in its correct place during each iteration.

The mechanism of insertion sort is akin to organizing cards in your hand during a card game.

We start by assuming the first card is already sorted. Then, we pick an unsorted card. If this card is greater than the one in hand, it is placed to the right; otherwise, it is placed to the left. This process is repeated for each unsorted card until all cards are in their correct positions.

Pseudocode

INSERTION_SORT(array) // array is zero-based
  for i := 1 to length(array)
    for j := i to 0
      if array[j-1] > array[j]
        swap array[j] and array[j-1]

Note: if using a dynamic structure to store entries such as linked list, you would eliminate multiple times of swapping and only one entry insertion is required for each iteration.

Example

Every time we select the element from the array, we compare it with previous values and if it is less than previous one, then we insert the element so that the array sorted again.

Here is the video if you want to play and pause:

Code

Java

private void insertionSort(int[] nums) {
	for (int i = 1; i < nums.length; i++) {
		for (int j = i; j >= 1; j--) {
			if (nums[j] >= nums[j - 1]) break;
			swap(nums, j, j - 1);
		}
	}
}
private void swap(int[] nums, int i, int j) {
	nums[i] = nums[i] ^ nums[j];
	nums[j] = nums[i] ^ nums[j];
	nums[i] = nums[i] ^ nums[j];
}

We can also write like this (in built swapping):

public void insertionSort(int[] nums) {
	int size = nums.length;

	for (int step = 1; step<size; step++) {
		int key = nums[step];
		int j = step - 1;

		// Compare key with each element on the left of it until an element smaller than
		// it is found.
		// For descending order, change key<array[j] to key>array[j].
		while (j >= 0 && key<array[j]) {
			nums[j + 1] = nums[j];
			--j;
		}

		// Place key at after the element just smaller than it.
		nums[j + 1] = key;
	}
}

Algorithm Analysis

Insertion Sort is a [stable and adaptive sorting] method that is frequently used in various technical systems. It generally needs Ο(n2) comparisons and swaps, but if the input is almost sorted, it may only require Ο(n) comparisons and swaps.

Although Insertion Sort is highly efficient for nearly sorted lists, it still involves many swaps to completely sort a list. Shell Sort addresses the limitations of Insertion Sort.

This revised version conveys the same information in a different structure to avoid plagiarism.

Complexity Summary

Different Data structures

Which sorting algorithm is easily adaptable to singly linked lists? Ans - Insertion Sort on List#Similar Question