Insertion Sort Algorithm in Java

Insertion Sort Algorithm in Java

The Insertion-Sort Algorithm

In this post, we describe a simple sorting algorithm known as insertion-sort. Insertion sort is a sorting algorithm that builds a final sorted array (sometimes called a list) one element at a time. The algorithm proceeds by considering one element at a time, placing the element in the correct order relative to those before it. We start with the first element in the array, which is trivially sorted by itself. When considering the next element in the array. if it is smaller than the first, we sawp them. Next we consider the third element in the array, swapping it leftward until it is in its proper order relative to the first two elements. We continue in this manner with the fourth element, the fifth, and so on, until the whole array is sorted. We can express the insertion-sort algorithm in pseudocode as shown below:

Algorithm InsertionSort(A):

    Input: An array A of n comparable elements

    Output: The array A with elements rearranged in nondecreasing order

    for k from 1 to n - 1 do

        Insert A[k] at its proper location within A[0], A[1],...,A[k]

This is a simple, high-level description of insertion-sort. A Java implementation of insertion-sort is provided below, using an outer loop to consider each element in turn, and an inner loop that moves a newly considered element to its proper location relative to the (sorted) subarray of elements that are to its left. If an array is already sorted, the inner loop of insertion-sort does only one comparison, determines that there is no swap needed, and returns back to the outer loop. Of course, we might have to do a lot more work than this if the input array is extremely out of order. In fact, we will have to do the most work if the input array is in decreasing order.

/** Insertion-sort of an array of integers into nondecreasing order */
public static void insertionSort(int[] data) {
	for (int i = 1; i < data.length; i++) { // begin with second character
		int cur = data[i]; // time to insert temp = data[i]
		int j = i; // find correct index j for cur
		while (j > 0 && data[j - 1] > cur) { // thus, data[j - 1] must go after cur
			data[j] = data[j - 1]; // slide data[j - 1] rightward
			j--; // and consider previous j for cur
		}
		data[j] = cur; // this is the proper place for cur
	}
}
        

              

                                             

                   

Complexity of Insertion Sort

Insertion sort runs in O(n) time in its best case and runs in O(n2) in its worst and average cases.

Best Case Analysis:
Insertion sort performs two operations: it scans through the list, comparing each pair of elements, and it swaps elements if they are out of order. Each operation contributes to the running time of the algorithm. If the input array is already in sorted order, insertion sort compares O(n) elements and performs no swaps (the inner loop is never triggered). Therefore, in the best case, insertion sort runs in O(n) time.

Worst and Average Case Analysis:

The worst case for insertion sort will occur when the input list is in decreasing order. To insert the last element, we need at most n-1 comparisons and at most n−1 swaps. To insert the second to last element, we need at most n-2 comparisons and at most n-2 swaps, and so on. The number of operations needed to perform insertion sort is therefore: 2×(1+2+⋯+n−2+n−1). To calculate the recurrence relation for this algorithm, use the following summation:

∑q = p(p + 1)/2; (q = 1 to p)

It follows that

2( n - 1)(n - 1 + 1 )/2 = n(n - 1) ≅ O(n2)

When analyzing algorithms, the average case often has the same complexity as the worst case. So insertion sort, on average, takes O(n2) time.