Introduction:
Insertion Sort is a simple sorting technique which is efficient for sorting small arrays and lists. The Insertion sort splits the array into two sub-arrays. The first array is always sorted and increases in size as the sort continues while the second sub-array is unsorted which contains all the elements that are yet to be inserted into the first sub-array and decreases in size as the sort continues. Insertion sort is more efficient than bubble sort because in insertion sort the elements comparisons are less as compare to bubble sort. But Insertion Sort is expensive compared to quick sort, heap sort, or merge sort because it requires shifting all following elements over by one.
In this program we have used binary search technique for finding the appropriate position for the key element which reduces the searching time by a great margin.
Java Code for Insertion Sort:
import java.io.*;
class Insertion{
private int num; //number of elements
private int[] arr; //stores array of elements
public static void main(String[] args){
Insertion x=new Insertion();
x.insert();
}
public void insert(){
int pos; //postion of the key element
int key; //key element
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
try{
System.out.print("Enter total no. of numbers: ");
num=Integer.parseInt(br.readLine());
arr=new int[num];
System.out.println("Enter the numbers: ");
for(int i=0;i<num;i++){
System.out.print("Enter number "+i+": ");
arr[i]=Integer.parseInt(br.readLine());
}
}catch(IOException e){
e.printStackTrace();
}
//insertion sort
for(int i=1;i<num;i++){
key=arr[i];
pos=binarySearch(0,i-1,key); //finds where the element will be stored
for(int j=i;j>pos;j--) //shifts the other elements by 1 position to the right
arr[j]=arr[j-1];
arr[pos]=key; //places the key element in the pos position
}
//printing the elements
for(int i=0;i<num;i++)
System.out.println(i+" : "+arr[i]);
}
//uses binary search technique to find the position where the element will be inserted
public int binarySearch(int low,int high,int key){
int mid;
while(low<=high){
mid=(low+high)/2;
if(key>arr[mid])
low=mid+1;
else if(key<arr[mid])
high=mid-1;
else
return mid;
}
return low;
}
}
Conclusion:
The best case input is an array that is already sorted. In this case insertion sort has a linear running time (i.e., O(n)).
The simplest worst case input is an array sorted in reverse order. The set of all worst case inputs consists of all arrays where each element is the smallest or second-smallest of the elements before it. In these cases every iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element. This gives insertion sort a quadratic running time (i.e., O(n2)).
The average case is also quadratic, which makes insertion sort impractical for sorting large arrays.
If you have any questions regarding the post please use the comments below. 😛
