Skip to content
DATA STRUCTURE
DATA STRUCTURE

Learn everything about Data structures.

  • Algorithms
  • DSA
  • Array
  • Stack
  • Queue
  • Matrix
  • Programs
DATA STRUCTURE

Learn everything about Data structures.

Insertion Sorting in C Programming

YASH PAL, October 7, 2022March 7, 2023

INSERTION SORTING: – An insertion sort is one that sorts a set of records by inserting records into an existing sorted file. If the initial file is sorted only one comparison is made on each pass so that the sort is O (N). If the file is initially sorted in reverse order, the sort is O (N²). The simple insertion sort is still usually better than the bubble sort. The closer the file is to sorted order, the more efficient the simple insertion sort becomes. The average number of comparisons in the simple insertion sort (by considering all possible permutations of the input array) is also O (n²). The space requirements for the sort consist of only one temporary variable.

[br]

Both the selection sort and the simple insertion sort are more efficient than the bubble sort Selection sort requires fewer assignments than insertion sort but more companions The insertion sort algorithm is a very slow algorithm when n is very large. Insertion sort is usually used only when n is small. This algorithm is very popular with bridge players when they first sort their cards In this procedure, we pick up a particular value and then insert it at the appropriate place in the sorted sub-list. The worst-case performance occurs when the input array elements are in descending order. The first pass makes 1 comparison, the second pass makes 2 and the last pass makes an N – 1 comparison. So total comparisons are 1.2 * [N – 2) (N – 1) = NIN – 1 / 2 = O (N²).

[br]

Algorithm – Insertion sorting in c.

INSERTION_SORT (A, N).

Here A is an array with N elements. This algorithm sorts the array A with N elements in ascending order.

1. Repeat Steps 2 to 5 for I=2 to N

2. Set ITEM: = A [1].

3. Set J: = 1-1.

4. Repeat Steps while J > = 1 AND A [J] > ITEM:

         (a) Set A [J + 1] = A [J]. [Moves element forward.]

         (b) Set J: = J – 1.

    [End of Step 4 loop]

5. Set A [J + 1]: = ITEM. [Inserts element in the proper place.]

    [End of Step 1 loop.]

6. Return.

[br]

Insertion sorting program in C.

#include<stdio.h>
#include<conio.h>
#define SIZE 10
void insertion_sort(int [],int);

void main()
{
    int a[SIZE],i,n;
    clrscr();
    printf("Enter how many elements");
    scanf("%d",&n);

    /*Input Array */

    for(i=0;i<n;i++)
    {
        printf("Enter element %d ",i+1);
        scanf("%d",&a[i]);
    }

    insertion_sort(a,n);

    /* Output Array */

    for(i=0;i<n;i++)
        printf("%d",a[i]);

    getch();
}

void insertion_sort(int a[], int n)
{
    int i,j,item;

    for(i=1;i<n;i++)
    {
        item = a[i];

        /*Shifting */

        for(j=i-1;j>=0 && a[j] > item; j--)
            a[j+1] = a[j];

        /* insert */
        a[j+1] = item;
    }
}

[br]

Also, Read

  1. Sorting Techniques in Data Structures
  2. Selection sorting in C Programming
  3. Bubble Sorting in C Programming
  4. Shell Sorting in C Programming
  5. Merge Sorting in C Programming
  6. Radix Sorting in C Programming
  7. Quick Sorting in C Programming
  8. Heap Sorting in C Programming
  9. Selection Sorting Algorithm
insertion sorting Sorting techniques DSAinsertion sortingsorting techniques

Post navigation

Previous post
Next post

Leave a Reply

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

  • HackerRank Dynamic Array Solution in Python
  • HackerRank 2D Array DS solution in Python
  • HackeRank Array – DS solution in Python
  • Streaming Demystified: How Much Data Does Your Favorite Show Really Use?
  • Parenthesis Matching program in C programming
  • HackerRank Dynamic Array Solution in Python
  • HackerRank 2D Array DS solution in Python
  • HackeRank Array – DS solution in Python
  • Streaming Demystified: How Much Data Does Your Favorite Show Really Use?
  • Parenthesis Matching program in C programming
  • About US
  • Contact US
  • Data Structures and algorithms tutorials
  • Digital Communication Tutorials
  • DMCA
  • HackerRank All Algorithms problems solutions
  • HackerRank C problems solutions
  • HackerRank C++ problems solutions
  • HackerRank Java solutions
  • HackerRank Python solutions
  • Human Values Tutorials
  • Internet of Things Tutorials
  • Privacy Policy
©2025 DATA STRUCTURE | WordPress Theme by SuperbThemes