Sort an Array using Insertion Sort in C

To sort an array using insertion sort in C, we repeatedly pick an element and insert it into its correct position in the sorted portion of the array. This process continues until the entire array is sorted. Insertion sort is simple, efficient for small datasets, and works well when the array is nearly sorted.

Understanding Insertion Sort

Insertion sort works by dividing the array into a sorted and an unsorted part. Initially, the first element is considered sorted. Then, we pick each subsequent element from the unsorted part and place it in its correct position within the sorted part by shifting elements as needed.

Examples of Insertion Sort in C

1. Sorting an Array in Ascending Order

In this example, we will implement insertion sort algorithm to sort an integer array in ascending order.

main.c

</>
Copy
#include <stdio.h>

// Function to perform insertion sort
void insertionSort(int arr[], int size) {
    for (int i = 1; i < size; i++) {
        int key = arr[i];
        int j = i - 1;

        // Shift elements to the right to create position for key
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

// Function to print array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int numbers[] = {5, 2, 9, 1, 5, 6};
    int size = sizeof(numbers) / sizeof(numbers[0]);

    insertionSort(numbers, size);
    printArray(numbers, size);

    return 0;
}

Explanation:

  1. The function insertionSort() takes an array and its size as input.
  2. A loop starts from the second element (i = 1) and assigns it to key.
  3. Elements larger than key are shifted right to create space for key.
  4. The key is placed in its correct position.
  5. The function printArray() prints the sorted array.

Output:

1 2 5 5 6 9

2. Sorting an Array in Descending Order

In this example, we modify the insertion sort algorithm to sort the array in descending order.

main.c

</>
Copy
#include <stdio.h>

// Function to perform insertion sort in descending order
void insertionSortDescending(int arr[], int size) {
    for (int i = 1; i < size; i++) {
        int key = arr[i];
        int j = i - 1;

        // Shift elements to the right if they are smaller than key
        while (j >= 0 && arr[j] < key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

// Function to print array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int numbers[] = {3, 8, 4, 1, 9, 7};
    int size = sizeof(numbers) / sizeof(numbers[0]);

    insertionSortDescending(numbers, size);
    printArray(numbers, size);

    return 0;
}

Explanation:

  1. The function insertionSortDescending() sorts the array in descending order.
  2. A loop starts from the second element (i = 1) and assigns it to key.
  3. Elements smaller than key are shifted right.
  4. The key is placed in its correct position.
  5. The function printArray() prints the sorted array.

Output:

9 8 7 4 3 1

Conclusion

In this tutorial, we implemented insertion sort in C with two variations:

  1. Ascending Order: Elements were inserted in increasing order.
  2. Descending Order: Elements were inserted in decreasing order.

Insertion sort is a simple sorting algorithm suitable for small datasets. It is efficient when the array is nearly sorted.