One element from the top is selected and is compares to the other rest of the elements down the line and inserted to another position and rest of the elements are shifted accordingly.

Code: Insertion Sort of 5 integer elements in ascending order.

#include <stdio.h>
void insertion_sort(int elements[], int n) 
{ 
   int i, key, j;
   printf("Insertion sort started-\n");
   for (= 1; i < n; i++) 
   { 
       
10         printf("==== Select element[%d] %d ====\n", i,elements[i]);
11         key = elements[i];
12         print_array(elements, 5);
13         
14         j = i-1; 
15    
16         while (>= 0 && elements[j] > key) 
17         { 
18             printf("Move#%d:%d %d %d\n", j,j+1,
19                                         elements[j+1],
20                                         elements[j]);
21             elements[j+1] = elements[j];
22             j = j-1; 
23             print_array(elements, 5);
24         }
25         
26         printf("Insert#%d:%d %d %d\n", i, j+1, elements[j+1], key);
27         elements[j+1] = key;
28         print_array(elements, 5);
29     } 
30     printf("Insertion sort ended\n");
31  } 
32 
33  void print_array(int array[], int count)
34  {
35    int i;
36    printf("[");
37    for(= 0; i < count; i++)
38    printf("%d, ", array[i]);
39    printf("\b\b]\n");
40  }
41  int main(int argc, char *argv[])
42  {
43    int array[5] = { 4, 9, 5, 1, 0 };
44    printf("Unsorted elements\n");
45    print_array(array, 5);
46    insertion_sort(array, 5);
47    printf("Insertion sorted elements\n");
48    print_array(array, 5);
49  }

Output

Unsorted elements
[4, 9, 5, 1, 0]
Insertion sort started-
==== Select element[1] 9 ====
[4, 9, 5, 1, 0]
Insert#1:1 9 9
[4, 9, 5, 1, 0]
==== Select element[2] 5 ====
[4, 9, 5, 1, 0]
Move#1:2 5 9
[4, 9, 9, 1, 0]
Insert#2:1 9 5
[4, 5, 9, 1, 0]
==== Select element[3] 1 ====
[4, 5, 9, 1, 0]
Move#2:3 1 9
[4, 5, 9, 9, 0]
Move#1:2 9 5
[4, 5, 5, 9, 0]
Move#0:1 5 4
[4, 4, 5, 9, 0]
Insert#3:0 4 1
[1, 4, 5, 9, 0]
==== Select element[4] 0 ====
[1, 4, 5, 9, 0]
Move#3:4 0 9
[1, 4, 5, 9, 9]
Move#2:3 9 5
[1, 4, 5, 5, 9]
Move#1:2 5 4
[1, 4, 4, 5, 9]
Move#0:1 4 1
[1, 1, 4, 5, 9]
Insert#4:0 1 0
[0, 1, 4, 5, 9]
Insertion sort ended
Insertion sorted elements
[0, 1, 4, 5, 9]

You have viewed 1 page out of 248. Your C learning is 0.00% complete. Login to check your learning progress.

 Vote 0

Similar topics related to this section

Hash Table, Sorting, Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, Heap Sort, Merge sort, Radix Sort,

# C Programming Language (Prentice Hall Software)
# Let Us C Paperback - 2006 by Yashavant Kanetkar
# Understanding and Using C Pointers Core techniques for memory management
# Data Structures Using C and C++ Paperback - 1998
# Data Structures In C Paperback - August 11, 2008 by Noel Kalicharan