Insertion sort

One element from the array is selected and is compared to the one side of the array and inserted to the proper position while shifting the rest of the elements accordingly.

Insertion algorithm

Insertion algorithm selects one element from start (position 2nd, C array index =1). It is saved to a temporary variable. Then it is compared to the left side elements one by one. If the element is bigger then the selected element, it is shifted to right. A hole is created while this shifting. Then this process is repeated till index reaches to first element. Element is not moved when value is less than the selected element. The hole is not shifted in this case. Now finally the selected element (from the temporary variable) is moved to hole. Now this element reached to its proper position. After this the next position or array index 2 is selected. Then we repeat the same process. Gradually all the left side elements are moved and becomes sorted. This entire process repeats till selection of array position goes to max (count-1). Finally entire array is sorted and selected element is inserted to its proper position.

void insertion_sort(int elements[], int count)
{
  int selection, index;
  for(selection = 1; selection < count; selection++)
  {
    int tmp = elements[selection];
    for (index = selection; index > 0 &&
      tmp < elements[index - 1]; index--) /* compare */
    {
10        elements[index] = elements[index - 1]; /*move */
11      }
12      /* insert it to the hole */
13      elements[index] = tmp; /* insert */
14    }
15 
16  }

Insertion sort code

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

#include<stdio.h>
int array[5] = { 4, 9, 5, 1, 0 };
void print_aray(int elements[], int count)
{
  for (int index = 0; index < count; index ++)
  {
    printf("%d, ",elements[index]);
10    }
11    printf("\n");
12  }
13 
14  void insertion_sort(int elements[], int count)
15  {
16    int selection, index;
17    for(selection = 1; selection < count; selection++)
18    {
19      int tmp = elements[selection];
20      printf("Position #%d value %d\n",
21             selection,
22             elements[selection]);
23      print_aray(elements, count);
24 
25      /* compare and shift */
26      for (index = selection;
27           index > 0 && tmp < elements[index - 1];
28           index--) 
29      {
30        printf("move %d -> %d \n",
31               elements[ index-1],
32               elements[index]);
33        elements[index] = elements[index - 1]; /*move right */
34        print_aray(elements, count);
35      }
36      printf("insert @%d = %d\n",index, tmp);
37      /* insert it to the hole */
38      elements[index] = tmp; 
39 
40      print_aray(elements, count);
41      printf("\n");
42    }
43 
44  }
45  int main(int argc, char *argv[])
46  {
47 
48    printf("Insertion sort\n");
49    print_aray(array, 5);
50 
51    insertion_sort(array, 5);
52 
53  }

Steps and Iterations (diagrams)

insertion sort step1 iteration stages

insertion sort step2 iteration stages

insertion sort step3 iteration stages

insertion sort step4 iteration stages

Output

Insertion sort
4, 9, 5, 1, 0,
Position #1 value 9
4, 9, 5, 1, 0,
insert @1 = 9
4, 9, 5, 1, 0,

Position #2 value 5
4, 9, 5, 1, 0,
move 9 -> 5
4, 9, 9, 1, 0,
insert @1 = 5
4, 5, 9, 1, 0,

Position #3 value 1
4, 5, 9, 1, 0,
move 9 -> 1
4, 5, 9, 9, 0,
move 5 -> 9
4, 5, 5, 9, 0,
move 4 -> 5
4, 4, 5, 9, 0,
insert @0 = 1
1, 4, 5, 9, 0,

Position #4 value 0
1, 4, 5, 9, 0,
move 9 -> 0
1, 4, 5, 9, 9,
move 5 -> 9
1, 4, 5, 5, 9,
move 4 -> 5
1, 4, 4, 5, 9,
move 1 -> 4
1, 1, 4, 5, 9,
insert @0 = 0
0, 1, 4, 5, 9,

Press any key to continue

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, 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