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 : 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(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 : 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(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.


Comments

No responses found. Be the first to comment...


  • Do not include your name, "with regards" etc in the comment. Write detailed comment, relevant to the topic.
  • No HTML formatting and links to other web sites are allowed.
  • This is a strictly moderated site. Absolutely no spam allowed.
  • Name:
    Email: