Monday, December 30, 2013

Insertion Sorting Logic

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain. -Wiki

The insertion sorting logic is as follows: An array with one element is already sorted. For multiple elements, take an element starting from index 1 into temp variable, and sort its left, then place the temp to its correct location.
Now take 2nd element into temp variable, and sort its indices 0, 1 and 2. Put value at temp to appropriate location.
We are looking left of the pivot element that we have stored in temp variable in each iteration, while gradually moving towards right direction while sorting the portion of the array from the pivot to the beginning. The appropriate location is found when do not find a value in the left side of array which can be sorted after comparing with temp, so we put temp there.

Complexity:
Best - O(n), average - O(n^2), worst - O(n^2)

package org.algorithms.sorting;

import java.util.Arrays;

public class InsertionSortDemo {
    public static void main(String[] args) {
        int[] numbers = {5,4,3,2,1};
        System.out.println(Arrays.toString(numbers));
        
        if (numbers.length > 1)
            doInsertionSort(numbers);
        
        System.out.println(Arrays.toString(numbers));
    }

    public static void doInsertionSort(int[] input){
        for (int i = 1; i < input.length; i++) {
            int j = i;
            //does not runs for sorted array, leaving best case to O(n)
            while (j>0 && input[j-1] > input[j]) {
                swap(input, j, j - 1);
                j--;
            }
            //O(n^2) even for sorted array
            /*for(int j = i ; j > 0 ; j--) {
                System.out.println("ran ");
                if(input[j] < input[j-1])
                    swap(input,j,j-1);
                    }*/
        }
    }

    private static void swap(int[] input, int i, int j) {
        int temp = input[i];
        input[i] = input[j];
        input[j] = temp;
    }
}

Visualization:

5 4 3 2 1 (in)

i=1
j=1 :: 4 5 3 2 1
i=2
j=2 :: 4 3 5 2 1
j=1 :: 3 4 5 2 1
i=3
j=3 :: 3 4 2 5 1
j=2 :: 3 2 4 5 1
j=1 :: 2 3 4 5 1
i=4
j=4 :: 2 3 4 1 5
j=3 :: 2 3 1 4 5
j=2 :: 2 1 3 4 5
j=1 :: 1 2 3 4 5

No comments:

Post a Comment

Liked or hated the post? Leave your words of wisdom! Thank you :)