Insertion Sort In Java

Chapter: Data Structures Last Updated: 10-02-2018 02:10:25 UTC

Program:

            /* ............... START ............... */
                
public class JavaInsertionSort {

	public static void insertionSort(int array[]) {
		int n = array.length;
		for (int j = 1; j < n; j++) {
			int key = array[j];
			int i = j - 1;
			while ((i > -1) && (array[i] > key)) {
				array[i + 1] = array[i];
				i--;
			}
			array[i + 1] = key;
		}
	}

	public static void main(String a[]) {
		int[] arr1 = { 9, 14, 3, 2, 43, 11, 58, 22 };
		System.out.println("Before Insertion Sort");
		for (int i : arr1) {
			System.out.print(i + " ");
		}
		System.out.println();

		insertionSort(arr1);

		System.out.println("After Insertion Sort");
		for (int i : arr1) {
			System.out.print(i + " ");
		}
	}
}
                /* ............... END ............... */
        

Output

Before Insertion Sort
9 14 3 2 43 11 58 22 
After Insertion Sort
2 3 9 11 14 22 43 58

Notes:

• Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. Every repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain.
• Insertion sort is efficient for sorting smaller number of elements.
• Best case insertion sort is when the input array is already sorted. In this case insertion sort has a linear running time (i.e., Θ(n)).
• Worst case is input array sorted in reverse order. This will give insertion sort a quadratic running time (i.e O(n2)).

Tags

Insertion Sort, Java, Data Structures

1