# Sorting Techniques - Insertion Sort and Selection Sort

Arranging a list of elements in an order (ascending or descending) is called sorting. There are different types of sorting techniques in which one technique is better than its predecessor. In this article, I am going to discuss the two sorting techniques insertion sort and selection sort with their algorithms and C programs.

## Insertion Sort

Insertion Sort is a sorting technique which comes under the category of sorting by insertion. It is also called as straight insertion sort. The procedure of straight insertion sort is as follows. Suppose there are n elements E1, E2, …… En in the list. Then, the n elements lead to 'n-1' iterations. In 'i'th iteration, compare the 'i'th element with the elements before it i.e. E1, E2, …… Ei-1. If there is any disorder, place 'i'th element between the elements immediately less than (greater than) it and immediately greater than (less than) it to obtain ascending (descending) order. Complete 'n-1' iterations to obtain the sorted list. To understand this method clearly, let us take an example. The insertion sort for the list 12, 67, 23, 78, 33, 13, 17, 89, 34, 25 (n=10) is done as follows.

12 67 23 78 33 13 17 89 34 25
Iteration 1 : Compare 67 with its previous elements and put it where it belongs.
12 67 23 78 33 13 17 89 34 25 (67 is greater then 12)
Iteration 2 : Compare 23 with its previous elements and put it where it belongs.
12 23 67 78 33 13 17 89 34 25 (23 should lie between 12 & 67)
Iteration 3 : Compare 78 with its previous elements and put it where it belongs.
12 23 67 78 33 13 17 89 34 25 (78 is greater then 67)
Iteration 4 : Compare 33 with its previous elements and put it where it belongs.
12 23 33 67 78 13 17 89 34 25 (33 should lie between 23 & 67)
Iteration 5 : Compare 13 with its previous elements and put it where it belongs.
12 13 23 33 67 78 17 89 34 25 (13 should lie between 12 & 23)
Iteration 6 : Compare 17 with its previous elements and put it where it belongs.
12 13 17 23 33 67 78 89 34 25 (17 should lie between 13 & 23)
Iteration 7 : Compare 89 with its previous elements and put it where it belongs.
12 13 17 23 33 67 78 89 34 25 (89 is greater then 78)
Iteration 8 : Compare 34 with its previous elements and put it where it belongs.
12 13 17 23 33 34 67 78 89 25 (34 should lie between 33 & 67)
Iteration 9 : Compare 25 with its previous elements and put it where it belongs.
12 13 17 23 25 33 34 67 78 89 (25 should lie between 23 & 33)

### Algorithm for Insertion Sort

InsertionSort

`Input : A list a[1], a[2], …… a[n].Output : A list b[1], b[2], …… b[n] (input list in ascending order).1  : START2  : b[1]=a[1]3  : for j=2 to n do4  : k=a[j]5  : flag=TRUE6  : i=j-17  : while(flag=TRUE) do8  : if(k<b[i]) then9  : i=i-110 : if(i=0) then11 : flag=FALSE12 : endIf13 : else14 : flag=FALSE15 : endIf16 : endWhile17 : p=j18 : while(p>i+1) do19 : b[p]=b[p-1]20 : p=p-121 : endWhile22 : b[i+1]=k;23 : endFor24 : STOP`

### C Program for Insertion Sort

Program
#include<stdio.h>
#include<conio.h>
void main(void)
{
int i,j,n,temp,a[25];
clrscr();
printf("Enter number of elements : ");
scanf("%d",&n);
printf("Enter the list before sorting : ");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=1;i<n;i++)
{
temp=a[i];
j=i-1;
while((temp<a[j])&&(j>=0))
{
a[j+1]=a[j];
j=j-1;
}
a[j+1]=temp;
}
printf("The list after sorting is :");
for(i=0;i<n;i++)
printf(" %d",a[i]);
getch();
}

Output
Enter number of elements : 10
Enter the list before sorting : 12 67 23 78 33 13 17 89 34 25
The list after sorting is : 12 13 17 23 25 33 34 67 78 89

The time complexity of insertion sort is O(n) in best case and O(n2) in average and worst cases. And O(1) is the space complexity of insertion sort in best case, average case and worst case.

## Selection Sort

Selection sort is a sorting technique which comes under the category of sorting by selection. It is also called as straight selection sort. The procedure of selection sort is as follows. Suppose there are n elements E1, E2, …… En in the list. Then, the n elements lead to 'n-1' iterations. In 'i'th iteration, swap the 'i+1'th element with minimum of all the elements after Ei i.e. Ei+1, Ei+2, …… En. To understand this method clearly, let us take an example. The selection sort for the list 12, 67, 23, 78, 33, 13, 17, 89, 34, 25 (n=10) is done as follows.

12 67 23 78 33 13 17 89 34 25
Iteration 1 : Swap first element (12) with minimum of the last ten elements.
12 13 23 78 33 67 17 89 34 25 (12 is the minimum of 12 67 23 78 33 13 17 89 34 25)
Iteration 2 : Swap second element (67) with minimum of the last nine elements.
12 13 23 78 33 67 17 89 34 25 (13 is the minimum of 67 23 78 33 13 17 89 34 25)
Iteration 3 : Swap third element (23) with minimum of the last eight elements.
12 13 17 78 33 67 23 89 34 25 (17 is the minimum of 23 78 33 67 17 89 34 25)
Iteration 4 : Swap fourth element (78) with minimum of the last seven elements.
12 13 17 23 33 67 78 89 34 25 (23 is the minimum of 78 33 67 23 89 34 25)
Iteration 5 : Swap fifth element (33) with minimum of the last six elements.
12 13 17 23 25 67 78 89 34 33 (25 is the minimum of 33 67 78 89 34 25)
Iteration 6 : Swap sixth element (67) with minimum of the last five elements.
12 13 17 23 25 33 78 89 34 67 (33 is the minimum of 67 78 89 34 33)
Iteration 7 : Swap seventh element (78) with minimum of the last four elements.
12 13 17 23 25 33 34 89 78 67 (34 is the minimum of 78 89 34 67)
Iteration 8 : Swap eighth element (89) with minimum of the last three elements.
12 13 17 23 25 33 34 67 78 89 (67 is the minimum of 89 78 67)
Iteration 9 : Swap ninth element (78) with minimum of the last two elements.
12 13 17 23 25 33 34 67 78 89 (78 is the minimum of 78 89)

### Algorithm for Selection Sort

SelectionSort

`Input : A list a[1], a[2], …… a[n].Output : The list a[1], a[2], …… a[n] after sorting (in ascending order).1 : START2 : for i=1 to n-1 do3 : j=SelectMinimum(i,n)4 : if(i≠j) then5 : Swap(a[i],a[j])6 : endIf7 : endFor8 : STOP`

SelectMinimum

`Input : A list a[1], a[2], …… a[n] with L, R as selection range i.e. L>0 and R<n+1.Output : Index of minimum element in selection range of the list a[1], a[2], …… a[n].1  : START2  : min=a[L]3  : minLoc=L4  : for i=L+1 to R do5  : if(min>a[i]) then6  : min=a[i]7  : minLoc=i8  : endIf9  : endFor10 : return minLoc11 : STOP`

Swap

`Input : Two variables X and Y.Output : Value of X changed to Value of Y and vice versa.1 : START2 : temp=X3 : X=Y4 : Y=temp5 : STOP`

### C Program for Selection Sort

Program
#include<stdio.h>
#include<conio.h>
void main(void)
{
int i,j,n,temp,a[25];
clrscr();
printf("Enter number of elements : ");
scanf("%d",&n);
printf("Enter the list before sorting : ");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
printf("The list after sorting is :");
for(i=0;i<n;i++)
printf(" %d",a[i]);
getch();
}

Output
Enter number of elements : 10
Enter the list before sorting : 12 67 23 78 33 13 17 89 34 25
The list after sorting is : 12 13 17 23 25 33 34 67 78 89

The time complexity of selection sort is O(n2) in best case, average case and worst case. And O(1) is the space complexity of selection sort in best case, average case and worst case.