Insertion sort

Insertion sort is a sorting algorithm based on comparison of elements. Insertion sort is stable and has quadratic asymptotic complexity O(n^{2}). Generalized version of this algorithm is Shell sort, which is an insertion sort with diminishing increment.

Description

The idea of the insertion sort is simple:

  1. One element is sorted trivially
  2. Pick element next to the already sorted sequence and insert it to the correct place - move every element of the already sorted sequence, which has a higher value than the element being sorted, one place right, than put the element into the gap (correct place within the sequence).
  3. While array contains any unsorted elements GOTO: 2.

Advantages of insertion sort

If the input sequence is already sorted, than the insertion sort only checks the ordering and does not perform any moves. Hence if there are only few unsorted elements, the complexity of insertion sort gets close to O(n). In these cases insertion sort outperforms divide-and-conquer algorithms with asymptotic complexity O(n \cdot \log{n}) such as quicksort, merge sort or heapsort.

Also for small inputs (n \leq 10) the insertion sort tends to be faster than the algorithms mentioned above, so it might be used as a subroutine of divide-and-conquer algorithms for small sub-problems.

Visualization

Example

(3 2 8 7 6) // Initial array - sort it in descending order
(3 2 8 7 6) // Element 3 is sorted trivially
(3 2 8 7 6) // Pick 2 and insert it to the correct place (already done)
(3 2 8 7 6) // Insert 1 to the first place, move the elements 3 and 2 one place right
(8 3 2 7 6) // Insert 7 between 8 and 3, move 3 a 2 one place right
(8 7 3 2 6) // Insert 6 between 7 and 3, move 3 and 2 one place right
(8 7 6 3 2) // Sorted

Code

    function insertionSort(array a)
        for i in 0 -> a.length - 2 do
            j = i + 1
            tmp = a[j]
            while j > 0 AND tmp > a[j-1] do //create a gap
                a[j] = a[j-1]
                j--
            a[j] = tmp //insert
    /**
     * Insertion sort (descending order)
     * @param array array to be sorted
     */
    public static void insertionSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int j = i + 1;
            int tmp = array[j];
            while (j > 0 && tmp > array[j-1]) {
                array[j] = array[j-1];
                j--;
            }
            array[j] = tmp;
        }
    }
 
/**
 * Insertion sort (descending order)
 * @param array array to be sorted
 * @param size size of the array
 */
void insertionSort(int array[], int size) {
    for (int i = 0; i < size - 1; i++) {
        int j = i + 1;
        int tmp = array[j];
        while (j > 0 && tmp > array[j-1]) {
            array[j] = array[j-1];
            j--;
        }
        array[j] = tmp;
    }
}
 
       /**
        * Insertion sort (descending order)
        * @param array array to be sorted
        */
        public static void InsertionSort(int[] array)
        {
            for (int i = 0; i < array.Length - 1; i++)
            {
                int j = i + 1;
                int tmp = array[j];
                while (j > 0 && tmp > array[j - 1])
                {
                    array[j] = array[j - 1];
                    j--;
                }
                array[j] = tmp;
            }
        }
  procedure Insert(var X : ArrayType; N : integer);
  var
    J,
    K,
    Y : integer;
    Found : boolean;
  begin
    for J := 2 to N do
      begin
        Y := X[J];
        K := J - 1;
        Found := false;
        while (K >= 1)
        and (not Found) do
          if (Y < X[K]) then
            begin
              X[K + 1] := X[K];
              K := K - 1
            end
          else
            Found := true;
        X[K + 1] := Y;
      end
   end;
Rating (1): 5

See also

Comments





This article does not have any comments.