Insertion Sort Program and Complexity (Big-O)


Insertion sort is a simple sorting algorithm, which consumes one input item for each repetition, and grow a sorted output list. In every iteration, removes one item from input data, find the exact location in the sorted list and inserts it there. This process will repeat as long as no input items remain.

Points to remember

  • Data structure :  Array
  • Worst-case performance : О(n2) comparisons and swaps
  • Best-case performance : O(n) comparisons, O(1) swaps
  • Average performance: О(n2) comparisons and swaps
  • Worst-case space complexity : О(n) total, O(1) auxiliary

See Also: Data Structure and Algorithms Complexity (Big-O)

Advantage

  • Simple Implementation and efficient for small data set.
  • Not change relative order of elements which are already sorted
  • Efficient in comparison to other Quadratic Sort (i.e O(n2)) like Bubble Sort or Selection Sort.
  • Efficient for data set that are already sorted. Time Complexity( i.e O(n)).
  • Only required constant amount of memory space , as size of data set. Space
    Complexity (i.e O(1))

Disadvantage

  • Insertion sort is much less efficient on large lists in compare to algorithms such as quicksort, heapsort, or merge sort.

Insertion Sort Steps

Here * marks the value set on particular iteration.

2 6 3 8 4 1 5 0
2 6* 3 8 4 1 5 0
2 3* 6 8 4 1 5 0
2 3 6 8* 4 1 5 0
2 3 4* 6 8 1 5 0
1* 2 3 4 6 8 5 0
1 2 3 4 5* 6 8 0
0* 1 2 3 4 5 6 8

In following programs you will learn both the ways to implement Insertion Sort by For Loop and Recursion.

Insertion Sort with Loop

public class InsertionSort {
	public static void main(String[] args) {
		int[] items = { 2, 6, 3, 8, 4, 1, 5, 0 };
        System.out.println("Before Sorting :");
        printArrayTR(items);

        //Perform insertion sort
        insertionSort(items);

        System.out.println("After Sorting :");
        printArray(items);
	}

	static void insertionSort(int items[])
    {
        int n = items.length;
        for (int i = 1; i = 0 && items[j] > key) {
            	items[j + 1] = items[j];
                j = j - 1;
            }
            items[j + 1] = key;
            printArrayTR(items);
        }

    }
	static void printArray(int items[])
	{
        for (int item:items)
        {
            System.out.print(item + " ");
        }
        System.out.println();
	}
}

Output


Before Insertion Sorting :
2 6 3 8 4 1 5 0 
After Insertion Sorting :
0 1 2 3 4 5 6 8 

Insertion Sort with Recursion

public class InsertionSortRecursion {
	public static void main(String[] args) {
		int[] items = { 2, 6, 3, 8, 4, 1, 5, 0 };
        System.out.println("Before Insertion Sorting :");
        printArray(items);

        //Perform insertion sort
        insertionSort(items,items.length);

        System.out.println("After Insertion Sorting :");
        printArray(items);
	}

	static void insertionSort(int items[],int n)
	{
		//base case or termination condition
		if(n= 0 && items[j] > last)
        {
        	items[j+1] = items[j];
            j--;
        }
        items[j+1] = last;
	}

	static void printArray(int items[])
	{
        for (int item:items)
        {
            System.out.print(item + " ");
        }
        System.out.println();
	}
}

Output


Before Insertion Sorting :
2 6 3 8 4 1 5 0 
After Insertion Sorting :
0 1 2 3 4 5 6 8 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s