Insertion Sort

Insertion sort : Pick an element in the array and position it in its appropriate place in the natural ordering.

e.g. Array 5,4,3,2,1

Pass 1:

Input : 5,4,3,2,1

4 is lesser than 5, so re-position 4.

Output: 4,5,3,2,1

Pass 2:

Input :4,5,3,2,1

3 is lesser than 4, so re-position 3.

Output: 3,4,5,2,1

 

Pass 3:

Input :3,4,5,2,1

2 is lesser than 3, so re-position 3.

Output: 2,3,4,5,1

 

Pass 4:

Input :2,3,4,5,1

1 is lesser than 2, so re-position 2.

Output: 1,2,3,4,5

Array is now sorted.

So, the complexity of the sorting lies in re positioning the array elements.

  • Worst case: O(n^2).
  • Best case: O(n).
  • Average case for a random array: O(n^2).

I have written a small program to compare the elements using insertion sort algorithm.

 

public class InsertionSort 
{
 public static void main(String[] args) 
 {
 int arr[] = {28,26,1,7,13,12,9,-1,6,6,6,6,5,6,4,3,2,1};
 
 for(int i = 1 ; i < arr.length ; i++)
 {
 if(arr[i] < arr[i-1])
 {
 boolean shift = false;
 int temp = -100;
 for(int j = 0 ; j <= i ; j++)
 {
 
 if(shift)
 {
 int temp1 = arr[j];
 arr[j] = temp;
 temp = temp1;
 continue;
 }
 
 if(arr[j] > arr[i])
 {
 temp = arr[j];
 arr[j] = arr[i];
 shift = true;
 }
 }
 }
 }
 
 for(int i : arr)
 {
 System.out.println(i);
 }
 }
}


 

Stay well and happy coding 🙂

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s