Java Insertion Sort Implementation

Insertion sort starts by assuming the first element in the list is already sorted, then loops through the rest of elements in the list and inserts each element into the correction position in the previous sorted elements. There will be an outer loop that goes through each element and this element will be saved to a temporary variable. An inner loop will go backwards starting from the current index-1 until it reaches to the first position or it finds the correct position for the element of the current outer index. Each of the inner loop will move the element one position up if it hasn’t find a correct position for the value to be inserted, which is the value of the current outer loop index which is saved in the temporary variable. This temporary variable will be inserted to the correct position once the inner loop finds the correct position for it.

Here is an example of insertion sort in Java

public class InsertionSort {
	
	//insertion sort using two for loops
    public static void insertionSort1(int [] num)
    {
    	int nextValue=0;//the next value to insert
    	int count=0;
    	//looping through the unsorted list, starting from position 1 because position 0 is considered sorted
    	for(int i=1; i<num.length; i++)
    	{
    		nextValue=num[i];//sets the next value to be the value of current index, and this value will be inserted into the correct position after the inner loop ends
    		int j;
    		for(j=i-1; j>=0; j--)
    		{
    			//if the value of the element is greater than the next value, move the position up by 1
    			//else stop the loop, and insert the next value
    			if(num[j]>nextValue)
    			{
    				num[j+1]=num[j];
    			}
    			else
    			{
    				break;
    			}
    			count++;
    		}
    		num[j+1]=nextValue;//insert the next value into the correct position, j+1 because the last operation in the for loop decremented the j by 1
    		System.out.print("During sorting: ");printArr(num);
    	}
    	System.out.println("Total number of loops: "+count);
    }
    
    //insertion sort using an outer for loop and an inner while loop
    public static void insertionSort2(int[] num)
    {
    	int nextValue=0;//the next value to insert
    	int j=0;
    	int count=0;
    	for(int i=1; i<num.length; i++)
    	{
    		nextValue=num[i];//sets the next value to be the value of current index, and this value will be inserted into the correct position after the inner loop ends
    		j=i-1;
    		//while the value of the element is greater than the next value and j is greater than or equal than 0, 
    		//move the position up by 1
    		while(j>=0 && num[j]>nextValue)
    		{
    			num[j+1]=num[j];
    			j--;
    			count++;
    		}
    		num[j+1]=nextValue;//insert the next value into the correct position, j+1 because the last operation in the while loop decremented the j by 1
    		System.out.print("During sorting: ");printArr(num);
    	}
    	System.out.println("Total number of loop: "+count);
    }
    
	public static void printArr(int[] arr)
	{
		for(int i=0; i<arr.length; i++)
		{
			System.out.print(arr[i]+" ");
		}
		System.out.println();
	}
	public static void main(String []args) { 
		int [] intArr={3,4,64,3,1,13,8,22};
		System.out.print("Before: ");printArr(intArr);
		InsertionSort.insertionSort1(intArr);
		System.out.print("After: ");printArr(intArr);
	  }

}

output of the above insertion sort

Before: 3 4 64 3 1 13 8 22 
During sorting: 3 4 64 3 1 13 8 22 
During sorting: 3 4 64 3 1 13 8 22 
During sorting: 3 3 4 64 1 13 8 22 
During sorting: 1 3 3 4 64 13 8 22 
During sorting: 1 3 3 4 13 64 8 22 
During sorting: 1 3 3 4 8 13 64 22 
During sorting: 1 3 3 4 8 13 22 64 
Total number of loops: 10
After: 1 3 3 4 8 13 22 64 


See Bubble Sort, Merge Sort and other Sortings

Search within Codexpedia

Custom Search

Search the entire web

Custom Search