CC-2 : Implement Insertion Sort Algorithm.

Description:

Insertion Sort works by building the sorted array by placing the elements of the unsorted array to their correct position one by one. It is more suited for sorting small lists rather than large lists. Given an input array, sort its elements using Insertion Sort

Test cases and expected outputs:

Input Parameters	Expected outputs
Array: 33, 3, 4, 97, 62, 122, 124, 20, 1,	Sorted Array: 1, 3, 4, 20, 33, 62, 97, 122, 124,

Pseudocode:

insertionSort(nums[]):

Integer array named nums is received as input parameter.

Initialize int variable toInsert. We will use this variable to store values of elements of the array one by one, that we will move to its correct sorted position.

Iterate through using for loop with iidx as iteration variable and values of iidx ranging from 0 to nums.length:

Set toInsert to nums[iidx].

Initialize int variable jidx and set its value to iidx.

Iterate through following steps while jiidx > 0 and nums[jidx] > toInsert:

Set nums[jidx] tonums[jidx-1].

Decrement jiidx by 1.

Set nums[jidx] to toInsert as we have found the correct sorted position of toInsert in the array.

The element of nums array have been sorted now using Insertion Sort, so return nums array from the method.

Code:

public int[] insertionSort(int[] nums){
	int toInsert;
	for (int iidx=1;iidx < nums.length;iidx++) {
		toInsert=nums[iidx];
		int jidx=iidx;
		while ((jidx >0) && (nums[jidx-1]>toInsert)) {
			nums[jidx]=nums[jidx-1];
			jidx--;
		}
		nums[jidx]=toInsert;
	}
	return nums;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class SortInsertionSort {

public int[] insertionSort(int[] nums){
	int toInsert;
	for (int iidx=1;iidx < nums.length;iidx++) {
		toInsert=nums[iidx];
		int jidx=iidx;
		while ((jidx >0) && (nums[jidx-1]>toInsert)) {
			nums[jidx]=nums[jidx-1];
			jidx--;
		}
		nums[jidx]=toInsert;
	}
	return nums;
}


public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	int[] retVal;
	try {
	
	SortInsertionSort sort=new SortInsertionSort();
	int[] nums= { 33,3,4,97,62,122, 124, 20,1};
	System.out.println("\nArray:");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < nums.length; arrayIndex++) {
		System.out.print(nums[arrayIndex]+", ");		
	} 
	System.out.println("\nSorted Array:");
	retVal=sort.insertionSort(nums);
	for (arrayIndex=0; arrayIndex < retVal.length; arrayIndex++) {
		System.out.print(retVal[arrayIndex]+", ");		
	} 
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
}
		
}

}