C Program To Perform Insertion Sort

• Take elements from the given array one by one.
• Insert it at right position
• Continue the above operations until all the elements in the given array are sorted.

Input:  6 4 9 2 3

Insert key "4" at right position 

4 6 9 2 3

4 6 9 2 3

Insert key "9" at right position

4 6 9 2 3

4 6 9 2 3

Insert key "2" at right position

4 6 2 9 3

4 2 6 9 3

2 4 6 9 3 

2 4 6 9 3

Insert key "3" at right position

2 4 6 3 9

2 4 3 6 9

2 3 4 6 9

See Also:

C Program To Perform Insertion Sort

C Program To Perform Shell Sort

C Program To Perform Bubble Sort

C Program To Perform Quick Sort

C Program To Perform Radix Sort

C Program To Perform Selection Sort

C Program To Perform Heap Sort

C Program To Perform Merge Sort

C Program To Perform External Sorting

C Program To Perform Sorting Using Binary Search Tree

Example program for Insertion Sort:

---

  #include <stdio.h>
  #include <stdlib.h>

  void insertion_sort(int *data, int n) {
        int i, j, temp;
        for (i = 1; i < n; i++) {
                /*
                 * temp is the key that needs to be inserted
                 * at right place
                 */
                temp = data[i];
                /*
                 * elements at data[0] to data[i-1] are sorted.
                 * If key is greater than data[i-1], then key is in
                 * right place.  So, we can skip below processing
                 */
                for (j = i; j > 0 && data[j-1] > temp; j--) {
                        data[j] = data[j-1];
                }
                /* place key at right place */
                data[j] = temp;
        }
  }

  int main() {
        int n, i, *data;
        printf("Insertion Sort Example:\n");
        printf("=======================\n");
        printf("Enter the no of entries:")
        scanf("%d", &n);
        data = (int *)malloc(sizeof (int) * n);
        for (i = 0; i < n; i++)
                scanf("%d", &data[i]);
        printf("Original data:\n");
        for (i = 0; i < n; i++)
                printf("%2d", data[i]);
        printf("\n");
        insertion_sort(data, n);
        printf("After Sorting:\n");
        for (i = 0; i < n; i++)
                printf("%2d", data[i]);
        printf("\n");
        return 0;
  }

  Output: (C Program To Implement Insertion Sorting)

  Insertion Sort Example:
  =======================
  Enter the no of entries:5
  6 4 9 2 3
  Original data:
  6 4 9 2 3
  After Sorting:
  2 3 4 6 9