Table of Contents

Insertion Sort

<aside> 💡 Insertion Sort is a sorting algorithm that.

</aside>

Implementation

#include <vector>

std::vector<int> swap (std::vector<int>& hand_of_cards, int j) {
    int temp = hand_of_cards.at(j);
    hand_of_cards.at(j) = deck_of_cards.at(j-1);
    hand_of_cards.at(j-1) = temp;

    return hand_of_cards;
}

std::vector<int> insertionSort (std::vector<int>& hand_of_cards) {
    for (int i = 0; i < hand_of_cards.size(); i++) {
        int j = i;
        while (j > 0 && hand_of_cards.at(j) < hand_of_cards.at(j-1)) {
            swap(hand_of_cards, j);
            j--;
        }
    }
    return hand_of_cards;
}

int main() {
    std::vector<int> hand_of_cards = {5, 6, 2, 3};
    insertionSort(hand_of_cards);
    return 0;
}

Code Walkthrough

Time Complexity Explanation

<aside> 💡 As $n$, the size of the vector/array increases, the time it takes go through each element in the outer loop is $O(n)$ and the time it takes compare those elements and swap them in the inner loop is also $O(n)$. Thus, insertion sort has a time complexity of $O(n^2)$.

</aside>