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^)$.
- Best case: $(n)$.
- Average case for a random array: $(n^)$.

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