This blog is under construction

Saturday, 16 February 2013

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


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


No comments:

Post a Comment