C Program to Sort an Array Using Insertion Sort

Introduction

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists compared to more advanced algorithms like quicksort or merge sort. However, it is easy to implement and works well for small datasets. This guide will show you how to write a C program to sort an array using the Insertion Sort algorithm.

Problem Statement

Create a C program that:

• Takes the size of the array as input from the user.
• Takes the elements of the array as input.
• Sorts the array using the Insertion Sort algorithm.
• Displays the sorted array.

Example:

• Input: Array size = 5, Elements = [64, 34, 25, 12, 22]
• Output: Sorted array = [12, 22, 25, 34, 64]

Solution Steps

1. Include the Standard Input-Output Library: Use #include <stdio.h> to include the standard input-output library, which is necessary for using printf and scanf functions.
2. Write the Main Function: Define the main function, which is the entry point of every C program.
3. Declare Variables: Declare variables to store the array size, the array elements, and the variables needed for sorting.
4. Input the Array Size: Use scanf to take input from the user for the size of the array.
5. Input the Array Elements: Use a loop to take input from the user for the elements of the array.
6. Implement Insertion Sort: Use nested loops to perform the Insertion Sort algorithm on the array.
7. Display the Sorted Array: Use printf to display the sorted array.

C Program

#include <stdio.h>

/**
 * C Program to Sort an Array Using Insertion Sort
 * Author: https://www.javaguides.net/
 */
int main() {
    // Step 1: Declare variables to hold the array size, elements, and sorting variables
    int n, key, j;

    // Step 2: Prompt the user to enter the size of the array
    printf("Enter the number of elements in the array: ");
    scanf("%d", &n);

    // Step 3: Declare an array to hold the elements
    int arr[n];

    // Step 4: Input the array elements
    printf("Enter %d elements:\n", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    // Step 5: Implement Insertion Sort
    for (int i = 1; i < n; i++) {
        key = arr[i]; // Select the element to be inserted
        j = i - 1;

        // Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key; // Insert the key element at its correct position
    }

    // Step 6: Display the sorted array
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;  // Step 7: Return 0 to indicate successful execution
}

Explanation

Step 1: Declare Variables

• The variable n is declared to store the size of the array. key is used to hold the current element being sorted, and j is used as an index for the elements being compared.

Step 2: Input the Array Size

• The program prompts the user to enter the size of the array using printf. The scanf function then reads the input and stores it in the variable n.

Step 3: Declare the Array

• The program declares an array arr of size n to hold the elements provided by the user.

Step 4: Input the Array Elements

• The program uses a for loop to take input for each element of the array. The loop iterates from 0 to n-1, reading the elements using scanf.

Step 5: Implement Insertion Sort

• The program uses a for loop to iterate through the array starting from the second element (index 1). For each element:
  • Step 5.1: The key variable stores the current element to be inserted into the sorted part of the array.
  • Step 5.2: A while loop shifts elements of the sorted part of the array to the right if they are greater than key.
  • Step 5.3: The key element is then inserted at its correct position in the sorted part of the array.

Step 6: Display the Sorted Array

• After the sorting process is complete, the program displays the sorted array using a for loop and the printf function.

Step 7: Return 0

• The return 0; statement indicates that the program executed successfully.

Output Example

Example:

Enter the number of elements in the array: 5
Enter 5 elements:
64
34
25
12
22
Sorted array: 12 22 25 34 64

Another Example:

Enter the number of elements in the array: 4
Enter 4 elements:
9
1
4
7
Sorted array: 1 4 7 9

Conclusion

This C program demonstrates how to sort an array using the Insertion Sort algorithm. It covers basic concepts such as arrays, loops, and conditional statements, making it a useful example for beginners learning C programming and sorting algorithms.