Insertion Sort in C++

Below is an example of the Insertion Sort algorithm in C++. See the Insertion Sort page for more information and implementations.


insertion-sort in C++

#include <vector>
#include <iostream>

void insertionSort(std::vector<int> &arr) {
    // start at the first index and iterate through to the end
    for (int i = 1; i < arr.size(); i++) {
        int currentIndex = i;
        /*
         * Check:
         *      1. that currentIndex is at least 1
         *      2. that the item directly before the currentIndex is greater than the item at currentIndex
         *
         * If both conditions are met, swap the indexes
         */
        while (currentIndex > 0 && arr[currentIndex - 1] > arr[currentIndex]) {
            int temp = arr[currentIndex];
            arr[currentIndex] = arr[currentIndex - 1];
            arr[currentIndex - 1] = temp;
            currentIndex--;
        }
    }
}

int main() {
    std::vector<int> arr = {12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8};
    insertionSort(arr);
    for (int i; i < arr.size(); i++) {
        std::cout << arr[i];
        if (i < arr.size() - 1) std::cout << ", ";
    }
}

Discussion