Insertion Sort in Java

If you are a programmer, you must have already heard about sorting a lot. Sorting is basically arranging the elements either in ascending order or in descending order. There are so many sorting algorithms available to sort the elements, and every algorithm has different ways to sort, different complexity. So it depends on the specific scenario and the number of elements as to which algorithm should be used. Insertion is also one of the commonly used sorting algorithms with O(n^2) complexity and is performed like we sort the playing cards in our hands. In this topic, we are going to learn about Insertion Sort in Java.

Start Your Free Software Development Course

Web development, programming languages, Software testing & others

How does Insertion Sort Work in Java?

Let’s understand the working of Insertion sort using an example.

Suppose there is an array with the name arr having the below-mentioned elements:

10 5 8 20 30 2 9 7

Step #1 – Insertion sort starts with the 2nd element of the array, i.e. 5, considering the 1st element of the array assorted in itself. Now the element 5 is compared with 10 since 5 is less than 10, so 10 is moved 1 position ahead, and 5 is inserted before it.

Now the resulting array is:

5 10 8 20 30 2 9 7

Step #2 – Now the element arr[2], i.e. 8 is compared with the element arr[1], i.e. 10. As 8 is smaller than its preceding element 10, it is shifted one step ahead from its position, and then it is compared with 5. Since 8 is greater than 5, so it is inserted after it.

Then the resulting array is :

5 8 10 20 30 2 9 7

Step #3 – Now that element 20 is compared with 10 since it is greater than 10, it remains in its position.

5 8 10 20 30 2 9 7

Step #4 – Element 30 is compared with 20, and since it is greater than 20, no changes would be made, and the array remains as it is. Now the array would be

5 8 10 20 30 2 9 7

Step #5 – Element 2 is compared with 30, as it is smaller than 30, it is shifted one position ahead then it is compared with 20,10, 8, 5, one by one and all the elements get shifted to 1 position ahead, and 2 is inserted before 5.

The resulting array is:

2 5 8 10 20 30 9 7

Step #6 – Element 9 is compared with 30 since it is smaller than 30; it is compared with 20, 10 one by one, and the element gets shifted 1 position ahead, and 9 is inserted before 10 and after 8.

The resulting array is:

2 5 8 9 10 20 30 7

Step #7 – Element 7 is compared with 30, and since it is smaller than 30, it is compared with 30, 20, 10, 9, 8, and all the elements are shifted 1 position ahead one by one, and 7 is inserted before 8.

The resulting array would become:

2 5 7 8 9 10 20 30

In this way, all the elements of the array are sorted using the insertion sort, starting the comparison with the preceding element.

Examples to Implement Insertion Sort in Java

Insertion Sort in Java is a simple sorting algorithm suitable for all small data sets.

Code:

public class InsertionSort {
public static void insertionSort(int arr[]) { for (int j = 1; j < arr.length; j++) { int key = arr[j]; int i = j-1;
while ( (i > -1) && ( arr[i] > key ) ) { arr[i+1] = arr[i]; i--; }
arr[i+1] = key;
}
}
static void printArray(int arr[]) { int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i<len; i++)
System.out.print(arr[i] + " " );
System.out.println();
}
public static void main(String args[]){ int[] arr1 = {21,18,15,23,52,12,61};
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
}
}

Output:

12 15 18 21 23 52 61

Explanation:

• In the above program of Insertion Sort, the insertionSort() function is used to sort the original array elements. Sorting starts from the second element as the first element considers to be sorted in itself. So the loop of ‘j’ starts from the index 1 of the array. ‘i’ is the variable keeping track of the index just before the ‘j’ in order to compare the value.’
• key’ is the variable holding the value of the current element which is to be arranged in sorted position. while() loop is executed if the current value is less than the leftmost value so that the shifting of elements can be processed, and at the end, insertion of the current element at the right position can be performed. printArray() function is used to finally print the sorted array.

1. Best Case

In the insertion sort, the best case would be when all the elements of the array are already sorted. So when any element is compared to its leftmost element, it is always greater, and hence no shifting and insertion of elements will be processed. In this case, the best case complexity would be linear, i.e. O(n).

2. Worst Case

In the above code of insertion sort, the worst case would be when the array is in reverse order so every time when the element is compared with its leftmost element, it is always smaller and then compared with all the proceeding elements that take place and shifting and insertion is done. In this case, the complexity of the insertion sort is O(n^2).

3. Average Case

Even in an average case, insertion sort has O(n^2) complexity in which some elements do not require shifting, whereas some elements are shifted from their positions and insertion at the right position is performed.

4. Best Use

Insertion sort is best to use when the size of an array is not very large, or only a small number of elements need to be sorted in which almost all the elements are sorted, and only some changes need to be made. Insertion sort is one of the fastest algorithms for small size arrays, even faster than the Quick Sort. In fact, quicksort uses Insertion sort when sorting its small parts of the array.

Conclusion

The above explanation clearly shows the working and the implementation of Insertion Sort in Java. In other programming languages, too, the logic to perform Insertion sort remains the same only the Syntax changes. Before implementing any sorting algorithm, it is very important to do some analysis of the scenario where sorting needs to be done as not every sorting algorithm fits in all scenarios.

The above is the detailed content of Insertion Sort in Java. For more information, please follow other related articles on the PHP Chinese website!