Implement insertion sort |Data Structure in C|

Introduction

     Sorting is a fundamental operation in computer science, and Insertion Sort is one of the simplest yet effective sorting algorithms. In this blog post, we'll explore a C program that implements Insertion Sort, breaking down the code to provide a step-by-step guide on how this algorithm efficiently organizes elements in ascending order.  

Code

    
     
    #include<stdio.h>
    #include<conio.h>
    void main() {
        int a[20], i, j, k, n;
        clrscr();
        
        // Input: Number of elements in the array
        printf("Enter the number of elements: ");
        scanf("%d", &n);
    
        // Input: Elements of the array
        printf("Enter the elements:\n");
        for(i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
    
        // Insertion Sort Algorithm
        for(j = 1; j < n; j++) {
            k = a[j];
            for(i = j - 1; i >= 0 && k < a[i]; i--)
                a[i + 1] = a[i];
            a[i + 1] = k;
        }
    
        // Output: Sorted list
        printf("Sorted list is:\n");
        for(i = 0; i < n; i++)
            printf("%d\n", a[i]);
    
        getch();
    }
       
     

Output

    Enter the number of elements: 5
    Enter the elements:
    5 2 8 1 9
    Sorted list is:
    1
    2
    5
    8
    9
       

Explanation

1. Header Files:

The program includes the standard input/output header <stdio.h> and the console I/O header <conio.h>.

2. Main Function:

The main function initiates the program.

Users are prompted to enter the number of elements in the array and the array elements themselves.

3. Insertion Sort Algorithm:

The program employs a nested loop structure to implement the Insertion Sort algorithm.

For each element in the array (starting from the second element), it is compared and moved to its correct position in the sorted part of the array.

4. Result Display:

The program prints the sorted list after the Insertion Sort process.

5. User Interaction:

Users receive clear feedback regarding the number of elements entered and the sorted list.

Conclusion

     This C program demonstrates the elegance of Insertion Sort, a simple yet efficient algorithm for sorting arrays. Understanding how elements are gradually inserted into their correct positions contributes to a foundational understanding of sorting algorithms. Experiment with different arrays, analyze the flow of the program, and observe how Insertion Sort efficiently organizes elements in ascending order. This example serves as an excellent introduction to the world of sorting algorithms in programming. Happy coding!