Insertion sort in c | Insertion sort algorithm | Insertion sort example

In this article insertion sort in c we give the information about insertion sort algorithm, insertion sort example and  insertion sort program in c.

Insertion Sort in C:

Insertion sort is implemented by inserting particular elements at the proper position. In insertion sort, the element is inserted before or after and the comparison is started from the first elements.

Since a first element has no other elements before it, so it does not require any comparison. Second elements requires 1 comparison, 3rd require 2 comparisons, 4th requires 3 comparisons and so on. The last elements require n-1 comparisons.

Consider an array with n elements. The process of insertion each element at proper place is as follows:

Iteration 1:     a[0] is already sorted because of only one element.

Iteration 2:     a[1] is inserted before or after a[0]. So a[0] & a[1] are sorted.

Iteration 3:     a[2] is inserted before a[0], in-between a[0], a[1], or after a[1]. So a[0], a[1] & a[2] are sorted and so on.

Algorithm:

Step 1:            start

2:                    Read n element of an array a.

3:                    Let i=0

4:                    Let j=0

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

temp = a[j]

a[j]=a[i]

6:                   let k=i

7:                   a[k] = a [k-1]

8:                   Calculate k=k-1

9:                   if k>j then go to step 7

10:                 a[k+1]=temp

11:                 calculate j=j+1

12:                 if j<I then go to step 5

13:                 i=i+1

14:                 printf sorted array

15:                  stop

Example:

Consider array elements as 29,  21,  37,  17,  5

Iteration 1:

29

21 37 17

5

Insert  21 at 0th position as 29>21 and shift 29 right by one position

21

29 37 17

5

 

Iteration 2:

21

29 37 17

5

No change as 21 < 29

21

29 37 17

5

No change 29<37

Iteration 3:

21

29 37 17

5

Insert 17 at 0th position as 17<21 and shift all elements to right by one position

17

21 29 37

5

No change as 21<37

17

21 29 37

5

No change 29<37

Iteration 4:

17

21 29 37

5

Insert 5 at 0th position as 5<17 and shift all elements to right by one position.

5

17 21 29

37

No change 17<37

5

17 21 29

37

No change 21<37

5

17 21 29

37

No change 29<37

The Sorted list is as follows:

5

17 21 29

37

 

/* C Program to sort an array in ascending order using Insertion Sort */

int main()

{

int i, j, temp;

int arr[6]={34, 2, 15, 56, 26, 4};

printf(“\n Insertion Sort ”)

printf(“\n Unsorted List of Array : “);

for(i=0;i<6;i++)

printf(“\t %d”,arr[i]);

for (i = 1 ; i <6 ; i++)

{

j = i;

while ( j > 0 && arr[j-1] > arr[j])

{

temp     = arr[j];

arr[j]   = arr[j-1];

arr[j-1] = temp;

j–;

}

}

printf(“\nSorted list in ascending order:”);

for (i = 0; i <6; i++)

{

printf(“\t%d”, arr[i]);

}

return 0;

}

Output:

Insertion Sort

Unsorted List of Array : 34   2   15   56   26   4

Sorted list in ascending order: 2   4    15    26    34     56

Related Link:

Some More: DBMS/ WT/ DMDW

Santosh Nalawade

Work as Assistant Professor and Web Developer.

Leave a Reply

Your email address will not be published. Required fields are marked *