Insertion Sort

Insertion Sort

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 than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages, such as simplicity and efficiency for small data sets or nearly sorted lists.

Algorithm

Here’s how the Insertion Sort algorithm works:

1. Start from the second element: Begin with the second element of the array (or list). Assume the first element to be already sorted.
2. Insertion process: For each element, compare it with the elements to its left and move it to its correct position within the sorted part of the array.
3. Repeat: Continue this process for each element in the array until the entire array is sorted.

Here’s an implementation of the Insertion Sort algorithm in C:

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        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;
    }
}

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

int main() {
    int arr[] = {11, 21, 43, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: \n");
    printArray(arr, n);

    insertionSort(arr, n);

    printf("\nSorted array: \n");
    printArray(arr, n);
    
    return 0;
}

Output:

Original array: 
11 21 43 5 6 

Sorted array: 
5 6 11 21 43 

Code Explanation

1. insertionSort Function

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i]; // Select the current 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]; // Shift elements to the right
            j = j - 1;
        }
        arr[j + 1] = key; // Insert the key in its correct position
    }
}

• Purpose: Sorts the array in ascending order using the Insertion Sort algorithm.
• How it works:
  1. The outer loop (i) iterates through the array starting from the second element (i = 1).
  2. For each iteration:
     • The current element (arr[i]) is stored in the variable key.
     • The inner loop (while) shifts all elements greater than key one position to the right.
     • This creates space for key to be inserted in its correct position in the sorted part of the array.
  3. The process continues until the entire array is sorted.

2. printArray Function

void printArray(int arr[], int n) {
    int i;
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]); // Print each element
    printf("\n"); // Move to the next line after printing
}

• Purpose: Prints the elements of the array.
• How it works:
  • Iterates through the array and prints each element followed by a space.
  • After printing all elements, it adds a newline (\n) for better readability.

3. main Function

int main() {
    int arr[] = {11, 21, 43, 5, 6}; // Unsorted array
    int n = sizeof(arr) / sizeof(arr[0]); // Calculate array size
 
    printf("Original array: \n");
    printArray(arr, n); // Print original array
 
    insertionSort(arr, n); // Sort the array
 
    printf("\nSorted array: \n");
    printArray(arr, n); // Print sorted array
     
    return 0;
}

• Purpose: Drives the program.
• How it works:
  1. Declares and initializes an array arr with unsorted integers.
  2. Calculates the size of the array (n) using sizeof(arr) / sizeof(arr[0]).
  3. Prints the original array using the printArray function.
  4. Calls the insertionSort function to sort the array.
  5. Prints the sorted array using the printArray function.

Key Points

1. Insertion Sort:
   • Time Complexity: O(n²) in the worst and average cases, but O(n) in the best case (when the array is already sorted).
   • Space Complexity: O(1) (in-place sorting).
   • It is efficient for small datasets or nearly sorted arrays.
2. How Insertion Sort Works:
   • Divides the array into a sorted and an unsorted part.
   • Takes one element from the unsorted part and inserts it into its correct position in the sorted part.
   • The sorted part grows from left to right.
3. Shifting Elements:
   • Elements greater than the key are shifted to the right to make space for the key .