Search

Insertion Sort

Insertion Sort is a stable comparison sort algorithm with poor performance. Insertion Sort uses the insertion method and while it can perform at O(n) in the best case, it performs at O(n2) in the average and worst case.

Table of contents

Performance

Best
Ω(n)
Average
Θ(n2)
Worst
O(n2)

Code

public static void main(String[] args)
{
    int[] array = {12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8};
    insertionSort(array);
    System.out.println(java.util.Arrays.toString(array));
}

static void insertionSort(int[] array) {
    // start at the first index and iterate through to the end
    for (int i = 1; i < array.length; i++)
    {
        int currentIndex = i;
        /*
         * Check:
         *      1. that currentIndex is at least 1
         *      2. that the item directly before the currentIndex is greater than the item at currentIndex
         *
         * If both conditions are met, swap the indexes
         */
        while (currentIndex > 0 && array[currentIndex - 1] > array[currentIndex])
        {
            int temp = array[currentIndex];
            array[currentIndex] = array[currentIndex - 1];
            array[currentIndex - 1] = temp;
            currentIndex--;
        }
    }
}
public class InsertionSortGeneric<T extends Comparable<? super T>> {
    public static void main(String[] args)
    {
        // example using Strings
        String[]                     arrayOfStrings = {"Andree", "Leana", "Faviola", "Loyce", "Quincy", "Milo", "Jamila", "Toccara", "Nelda", "Blair", "Ernestine", "Chara", "Kareen", "Monty", "Rene", "Cami", "Winifred", "Tara", "Demetrice", "Azucena"};
        InsertionSortGeneric<String> stringSorter   = new InsertionSortGeneric<>();
        stringSorter.insertionSort(arrayOfStrings);
        System.out.println(java.util.Arrays.toString(arrayOfStrings));

        // example using Doubles
        Double[]                     arrayOfDoubles = {0.35, 0.02, 0.36, 0.82, 0.27, 0.49, 0.41, 0.17, 0.30, 0.89, 0.37, 0.66, 0.82, 0.17, 0.20, 0.96, 0.18, 0.25, 0.37, 0.52};
        InsertionSortGeneric<Double> doubleSorter   = new InsertionSortGeneric<>();
        doubleSorter.insertionSort(arrayOfDoubles);
        System.out.println(java.util.Arrays.toString(arrayOfDoubles));
    }

    void insertionSort(T[] array)
    {
        // start at the first index and iterate through to the end
        for (int i = 1; i < array.length; i++)
        {
            int currentIndex = i;
            /*
             * Check:
             *      1. that currentIndex is at least 1
             *      2. that the item directly before the currentIndex is greater than the item at currentIndex
             *
             * If both conditions are met, swap the indexes
             */
            while (currentIndex > 0 && array[currentIndex - 1].compareTo(array[currentIndex]) > 0)
            {
                T temp = array[currentIndex];
                array[currentIndex] = array[currentIndex - 1];
                array[currentIndex - 1] = temp;
                currentIndex--;
            }
        }
    }
}
#include <vector>
#include <iostream>

void insertionSort(std::vector<int> &arr) {
    // start at the first index and iterate through to the end
    for (int i = 1; i < arr.size(); i++) {
        int currentIndex = i;
        /*
         * Check:
         *      1. that currentIndex is at least 1
         *      2. that the item directly before the currentIndex is greater than the item at currentIndex
         *
         * If both conditions are met, swap the indexes
         */
        while (currentIndex > 0 && arr[currentIndex - 1] > arr[currentIndex]) {
            int temp = arr[currentIndex];
            arr[currentIndex] = arr[currentIndex - 1];
            arr[currentIndex - 1] = temp;
            currentIndex--;
        }
    }
}

int main() {
    std::vector<int> arr = {12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8};
    insertionSort(arr);
    for (int i; i < arr.size(); i++) {
        std::cout << arr[i];
        if (i < arr.size() - 1) std::cout << ", ";
    }
}
func insertionSort(array: inout [Int]) {
    // start at the first index and iterate through to the end
    for i in 1..<array.count {
        var currentIndex = i
        /*
         * Check:
         *      1. that currentIndex is at least 1
         *      2. that the item directly before the currentIndex is greater than the item at currentIndex
         *
         * If both conditions are met, swap the indexes
         */
        while currentIndex > 0 && array[currentIndex - 1] > array[currentIndex] {
            let temp = array[currentIndex]
            array[currentIndex] = array[currentIndex - 1]
            array[currentIndex - 1] = temp
            currentIndex -= 1
        }
    }
}

var array = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]
insertionSort(array: &array)
print(array)
function insertionSort(array) {
  // start at the first index and iterate through to the end
  for (let i = 1; i < array.length; i++) {
    let currentIndex = i
    /*
     * Check:
     *      1. that currentIndex is at least 1
     *      2. that the item directly before the currentIndex is greater than the item at currentIndex
     *
     * If both conditions are met, swap the indexes
     */
    while (currentIndex > 0 && array[currentIndex - 1] > array[currentIndex]) {
      let temp = array[currentIndex]
      array[currentIndex] = array[currentIndex - 1]
      array[currentIndex - 1] = temp
      currentIndex--
    }
  }
}

let array = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]
insertionSort(array)
alert(array)
def insertion_sort(array):
    # start at the first index and iterate through to the end
    i = 1
    while(i < len(array)):
        currentIndex = i
        # Check:
        #      1. that currentIndex is at least 1
        #      2. that the item directly before the currentIndex is greater than the item at currentIndex
        #
        # If both conditions are met, swap the indexes
        while (currentIndex > 0 and array[currentIndex - 1] > array[currentIndex]):
            temp = array[currentIndex]
            array[currentIndex] = array[currentIndex - 1]
            array[currentIndex - 1] = temp
            currentIndex -= 1
        i += 1

if __name__ == '__main__':
    array = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]
    insertion_sort(array)
    print(array)
algorithm insertion_sort(Array) is
  for i ← 1 to length(Array) do
    currentIndex ← i
    while currentIndex > 0 and Array[currentIndex - 1] > Array[currentIndex] do
      temp ← Array[currentIndex]
      Array[currentIndex] ← Array[currentIndex - 1]
      Array[currentIndex - 1] ← temp
      currentIndex ← currentIndex - 1
    end while
    i ← i + 1
  end for
end function

Walkthrough

Insertion Sort consists of a while-loop nested in a for-loop. The algorithm executes in the following steps:

  1. Loop through every value of the array starting with the first index. This is because we will be comparing each index with the previous index.
  2. Save the current index of the for-loop to a variable named currentIndex.
  3. Start the while-loop and check these 2 conditions:
    1. That the currentIndex is at least 1
    2. That the value at the previous index is greater than the value at currentIndex
  4. If the above conditions are true, swap the values at the currentIndex and previous index.
  5. Decrement the currentIndex and go back to the start of the while-loop.

Discussion