Insertion Sort Algorithm in CPP

1. Introduction

Insertion Sort is a simple and intuitive comparison-based sorting algorithm. It builds the final sorted array one item at a time. Think of it as playing cards: when you're dealt a hand in a card game, you might sort it by taking one card at a time and inserting it into its correct position within the sorted cards you hold.

2. Implementation Steps

1. Start from the second element (consider the first element as sorted).

2. Compare the current element with the previous elements.

3. If the current element is smaller than the previous element, compare it with the elements before the previous element.

4. Continue this process until the current element is greater than the element to its left or it reaches the start.

5. Insert the current element in its correct position in the sorted section.

3. Implementation in C++ Programming

#include<iostream>
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i]; // 2. Current element to be compared
        int j = i - 1;
        // 3. Move elements 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; // 5. Insert key in its correct position
    }
}
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    std::cout << "Sorted array: \n";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

Output:

Sorted array:
5 6 11 12 13

Explanation:

1. We consider the first element as already sorted, so we start with the second element.

2. This key element (or current element) is what we will insert into its correct position within the already sorted portion of the array.

3. Within the while loop, if the element to the left of the key (or arr[j]) is greater than the key, we shift arr[j] to the right.

4. We keep doing this shift operation until we find the correct position for our key.

5. Finally, we insert the key into its correct position.