Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. We use this algorithm while we play any games of cards. So to remember insertion sort always remember sorting deck of cards.

Steps that we use to sort decks of cards.

  1. Divide the card into two section i.e, sorted and unsorted section by placing a marker after the first card.
  2. Repeat the 4 to 6 steps until unsorted section becomes empty.
  3. Select the first card from unsorted section.
  4. Swap the card to left until it arrives at the correct sorted position.
  5. Move the marker to the right.

Let’s understand the above steps with a simple exaplanation of cards. Assume we have a deck of 5 cards.
Cards : 6 7 3 2 5
Now follow the above steps

6 | 7 3 2 5
Compare 7 to its left cards until it arrives at the correct position. Here it is already at correct position, so no movement
Move the marker.

6 7 | 3 2 5
Compare 3 to its left cards until it arrives at the correct position.
3 6 | 7 2 5
Move the marker.

3 6 7 | 2 5
Compare 2 to its left cards until it arrives at the correct position.
2 3 6 | 7 5
Move the marker.

2 3 6 7 | 5
Compare 5 to its left cards until it arrives at the correct position.
2 3 5 6 | 7
Move the marker

2 3 5 6 7 |
We got the sorted cards.

Let’s have a code to implement the above logic. As we set the marker at first position, so out first loop start from 1 and second loop runs from 1 to the number of cards left to marker.
InsertionSort.java

package com.javalatte.itcuties.insertionsort;

public class InsertionSort {

    public static void main(String[] JavaLatte) {
        int cards[] = {6, 7, 3, 2, 5};
        int noOfCard = cards.length;
        //we place marker from 6, so first loop start at index 1
        for (int marker = 1; marker < noOfCard; marker++) {
            //j runs from 0 to no of element left to marker
            for (int j = 0; j < marker; j++) {
                if (cards[marker] < cards[j]) {
                    //swap elements
                    int tmp = cards[marker];
                    cards[marker] = cards[j];
                    cards[j] = tmp;
                }
            }
        }
        //sorted output
        for (int i = 0; i < noOfCard; i++) {
            System.out.print(cards[i] + " ");
        }
        System.out.println();//new line
    }
}

InsertionSortWhileLoop.java

package com.javalatte.itcuties.insertionsort;

public class InsertionSortWhileLoop {

    public static void main(String[] JavaLatte) {
        int cards[] = {6, 7, 3, 2, 5};
        int noOfCard = cards.length;
        //we place marker from 6, so first loop start at index 1
        int marker = 1;
        while (marker < noOfCard) {
            //j runs from 0 to no of element left to marker
            int j = 0;
            while (j < marker) {
                if (cards[marker] < cards[j]) {
                    //swap elements
                    int tmp = cards[marker];
                    cards[marker] = cards[j];
                    cards[j] = tmp;
                }
                j++;
            }
            marker++;
        }
        //sorted output
        for (int i = 0; i < noOfCard; i++) {
            System.out.print(cards[i] + " ");
        }
        System.out.println();//new line
    }
}

Advantages

  • Simple implementation
  • Efficient for (quite) small data sets
  • Only requires a constant amount O(1) of additional memory space.
  • More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n).

Performance

  • Worst Case Complexity: O(n^2) When array sorted in reverse order.
  • Average Case Complexity: O(n^2)
  • Best Case Complexity: O(n) When is array is already sorted
  • Download this sample code here.

    Leave a Reply

    Want to join the discussion?
    Feel free to contribute!

    Leave a Reply

    Your email address will not be published. Required fields are marked *


    *

    You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>