Insertion sort C++

insertion_sort.cpp

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>

/*
O(n^2) in avg and worst.
*/

// Implementation using std::find_if
std::vector<int> sort(std::vector<int>& array) {
    int sz = array.size();
    auto pos = -1;
    int element;
    for(int i = 1; i < sz; i+=1) {
        // Find through sub-sorted array 0..i
        auto it = std::find_if(
            array.begin(), array.begin() + i, 
            [value = array[i]](int element) {
                return value < element;
            }
        );
        if(it == (array.begin() + i))
            continue;
        
        // Insert and remove
        pos = std::distance(array.begin(), it);
        element = array[i];
        array.erase(array.begin() + i);
        array.insert(array.begin() + pos, element);
    }
    return array;
}


// Raw Implementation
std::vector<int> sort(std::vector<int>& array) {
    int sz = array.size();
    int pos, element;
    for(int i = 1; i < sz; i+=1) {
        pos = -1;
        for(int j = 0; j < i; j+=1) {
            if(array[j] > array[i]) {
                pos = j;
                break;
            }
        }
        if(pos == -1) continue;
        element = array[i];
        array.erase(array.begin() + i);
        array.insert(array.begin() + pos, element);
    }
    return array;
}


// Tests
void test_empty_array() {
    std::vector<int> empty;
    empty = sort(empty);
    assert(empty.empty() && "Test with empty array failed");
}

void test_single_element() {
    std::vector<int> single = {1};
    single = sort(single);
    assert(single[0] == 1 && "Test with single element failed");
}

void test_sorted_array() {
    std::vector<int> sorted = {1, 2, 3, 4, 5};
    sorted = sort(sorted);
    assert(std::is_sorted(sorted.begin(), sorted.end()) && "Test with sorted array failed");
}

void test_reverse_sorted_array() {
    std::vector<int> reverse_sorted = {5, 4, 3, 2, 1};
    reverse_sorted = sort(reverse_sorted);
    assert(std::is_sorted(reverse_sorted.begin(), reverse_sorted.end()) && "Test with reverse sorted array failed");
}

void test_large_array() {
    std::vector<int> large(1000);
    for (int i = 0; i < 1000; ++i) {
        large[i] = 1000 - i; // Create reverse order
    }
    large = sort(large);
    assert(std::is_sorted(large.begin(), large.end()) && "Test with large array failed");
}

void test_array_with_duplicates() {
    std::vector<int> duplicates = {2, 3, 2, 3, 2};
    duplicates = sort(duplicates);
    assert(std::is_sorted(duplicates.begin(), duplicates.end()) && "Test with array of duplicates failed");
}

void test_all_identical_elements() {
    std::vector<int> identical(10, 5); // 10 elements, all are 5
    identical = sort(identical);
    assert(std::is_sorted(identical.begin(), identical.end()) && "Test with all identical elements failed");
}


// Main
void run_all_tests() {
    test_empty_array();
    test_single_element();
    test_sorted_array();
    test_reverse_sorted_array();
    test_large_array();
    test_array_with_duplicates();
    test_all_identical_elements();
}

int main() {
    run_all_tests();
    std::cout << "All tests passed successfully!\n";
    return 0;
}