C Program to Implement Insertion Sort Using Pointers

Introduction

Insertion Sort is a simple and efficient sorting algorithm that builds the final sorted array one element at a time. It works similarly to how you might sort playing cards in your hands: taking one card at a time and placing it in the correct position among the cards already in your hand. In C, you can implement Insertion Sort using pointers to directly manipulate the elements of the array. This guide will show you how to write a C program to implement Insertion Sort using pointers.

Example:

• Input: Array [5, 2, 9, 1, 5, 6]
• Output: Sorted array [1, 2, 5, 5, 6, 9]

Problem Statement

Create a C program that:

• Takes an array of integers as input from the user.
• Uses pointers to implement the Insertion Sort algorithm to sort the array.
• Displays the sorted array.

Solution Steps

1. Include the Standard Input-Output Library: Use #include <stdio.h> for standard input-output functions.
2. Declare the Array and Pointer Variables: Declare an integer array to store the elements and pointers for accessing and manipulating the elements.
3. Input the Array Elements: Use a loop to take input for the array elements from the user.
4. Implement Insertion Sort Using Pointers: Use pointers to traverse the array and insert each element in its correct position in the sorted part of the array.
5. Display the Sorted Array: Use printf to display the sorted array.

C Program to Implement Insertion Sort Using Pointers

#include <stdio.h>

int main() {
    // Step 2: Declare the array and pointer variables
    int arr[100], n;
    int *ptr1, *ptr2, key;

    // Step 3: Input the number of elements and the array elements
    printf("Enter the number of elements: ");
    scanf("%d", &n);

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

    // Step 4: Implement Insertion Sort using pointers
    for (int i = 1; i < n; i++) {
        key = arr[i];
        ptr1 = &arr[i - 1];
        ptr2 = &arr[i];

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

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

    return 0;  // Return 0 to indicate successful execution
}

Explanation

Step 2: Declare the Array and Pointer Variables

• The integer array arr is declared to store the elements of the array.
• The pointers ptr1 and ptr2 are used to traverse and compare elements in the array during sorting.
• The variable key is used to store the current element being inserted into its correct position.

Step 3: Input the Array Elements

• The program prompts the user to enter the number of elements in the array and stores this value in n.
• A for loop is used to take input for each element of the array.

Step 4: Implement Insertion Sort Using Pointers

• The program uses a for loop to implement the Insertion Sort algorithm:
  • The loop starts from the second element (i = 1) because the first element is considered already sorted.
  • The key variable stores the value of the current element being sorted.
  • The pointer ptr1 is initialized to point to the last element of the sorted part of the array (arr[i-1]), and ptr2 is initialized to point to the current element (arr[i]).
  • A while loop is used to shift elements in the sorted part of the array that are greater than the key one position ahead.
  • Once the correct position is found, the key is placed at that position using the pointer ptr2.

Step 5: Display the Sorted Array

• The program uses a for loop to display the sorted array.

Return 0

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

Output Example

Example Output:

Enter the number of elements: 6
Enter the elements of the array: 5 2 9 1 5 6
Sorted array: 1 2 5 5 6 9

Conclusion

This C program demonstrates how to implement Insertion Sort using pointers. It covers basic concepts such as pointer manipulation, array traversal, and sorting algorithms, making it a useful example for beginners learning C programming.