Sorting Algorithm

In this tutorial we will learn about Insertion sort algorithm.

In this technique we pick an element and then insert it at the appropriate position in ascending or descending order.

In pass 1, element `a[1]`

is inserted either before or after `a[0]`

so that `a[0]`

and `a[1]`

are sorted.

In pass 2, element `a[2]`

is inserted either before `a[0]`

or between `a[0]`

and `a[1]`

or after `a[1]`

so that `a[0]`

, `a[1]`

and `a[2]`

are sorted.

In a similar way the process is carried out n-1 times.

- Insertion sort requires n – 1 pass to sort an array of n elements.
- In each pass we insert the current element at the appropriate place so that the elements in the current range is in order.
- In each pass we have k comparisons, where k is the pass number.

So, 1st pass requires 1 comparison,

kth pass requires k – 1 comparisons and

the last pass requires n – 1 comparisons

```
/**
* a[0:n-1] is an array of n elements.
* temp is a variable to facilitate exchange.
*/
InsertionSort(a,n)
Begin
for k = 1 to n-1 by 1 do //this is for pass
Set temp = a[k];
Set j = k-1;
while( temp < a[j] and j >= 0) do
Set a[j+1] = a[j];
Set j = j-1;
endwhile
Set a[j+1] = temp;
endfor
End
```

```
#include <stdio.h>
//function declaration
void insertionSort(int *a, int n);
int main(){
//variable declaration
int arr[5], i;
//input
for(i = 0; i < 5; i++)
scanf("%d", &arr[i]);
//sort
insertionSort(arr, 5); //passing arr address and no. of elements
//output
for(i = 0; i < 5; i++)
printf("%d\n", arr[i]);
return 0;
}
//function definition
void insertionSort(int *a, int n){
int k, j, temp;
for(k = 1; k <= n-1; k++){
temp = a[k];
j = k-1;
while(temp < a[j] && j >= 0){
a[j+1] = a[j];
j--;
}
a[j+1] = temp;
}
}
```

1st pass requires 1 comparison

2nd pass required 2 comparison

... last pass requires (n-1) comparison

So, total comparison = 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n^{2})