# 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 E_{1}, E

_{2}, …… E

_{n}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. E

_{1}, E

_{2}, …… E

_{i-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 : START

2 : b[1]=a[1]

3 : for j=2 to n do

4 : k=a[j]

5 : flag=TRUE

6 : i=j-1

7 : while(flag=TRUE) do

8 : if(k<b[i]) then

9 : i=i-1

10 : if(i=0) then

11 : flag=FALSE

12 : endIf

13 : else

14 : flag=FALSE

15 : endIf

16 : endWhile

17 : p=j

18 : while(p>i+1) do

19 : b[p]=b[p-1]

20 : p=p-1

21 : endWhile

22 : b[i+1]=k;

23 : endFor

24 : 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(n

^{2}) 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 E_{1}, E

_{2}, …… E

_{n}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 E

_{i}i.e. E

_{i+1}, E

_{i+2}, …… E

_{n}. 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 : START

2 : for i=1 to n-1 do

3 : j=SelectMinimum(i,n)

4 : if(i≠j) then

5 : Swap(a[i],a[j])

6 : endIf

7 : endFor

8 : 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 : START

2 : min=a[L]

3 : minLoc=L

4 : for i=L+1 to R do

5 : if(min>a[i]) then

6 : min=a[i]

7 : minLoc=i

8 : endIf

9 : endFor

10 : return minLoc

11 : STOP

**Swap**

Input: Two variables X and Y.Output: Value of X changed to Value of Y and vice versa.

1 : START

2 : temp=X

3 : X=Y

4 : Y=temp

5 : 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(n

^{2}) 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.