Insert sorting algorithm implemented by C++ and Go.

insertion_sort.cpp

/*
 * @author  duruyao
 * @file    insertion_sort.cpp
 * @desc
 * @date    2021-10-02
 * @version 1.0
 */

#include <vector>
#include <iostream>

/**
 * insertionSort sorts data set by insertion sorting algorithm.
 *
 * ---time complexity---
 *
 * best    case:    O(1)
 * average case:    O(n ^ 2)
 * worst   case:    O(n ^ 2)
 *
 * ---when to use---
 *
 * (1) data set is small OR
 * (2) elements of data set are almost ordered OR
 * (3) less code is required.
 *
 * ---parameters and return---
 *
 * @tparam T        is a certain data type
 * @param input     is a data set to be sorted
 * @param begin     is the first index
 * @param end       is the index past the last index
 * @param cmpFunc   is a function for comparing elements of data set
 */
template<typename T>
void insertionSort(std::vector<T> &input, int begin, int end, int (*cmpFunc)(const T &, const T &)) {
    for (auto i = begin + 1; i < end; i++) {
        for (auto j = i - 1; j >= begin && cmpFunc(input[j], input[j + 1]) > 0; j--) {
            std::swap(input[j], input[j + 1]);
        }
    }
}

int cmpInt(const int &n1, const int &n2) {
    return n1 - n2;
}

template<typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &input) {
    for (auto &it : input) { os << it << " "; }
    return os;
}

int main(int argc, char **argv) {
    std::vector<int> array;
    for (int i = 0; i < 40; array.push_back(random() % 100), i++);
    std::cout << array << std::endl;
    insertionSort(array, 0, (int) array.size(), cmpInt);
    std::cout << array << std::endl;
    return 0;
}

insertion_sort.go

package main

import (
	"fmt"
	"math/rand"
)

// InsertionSort sorts data set by insert sorting algorithm.
//
// ---time complexity---
//
// best    case:    O(1)
// average case:    O(n ^ 2)
// worst   case:    O(n ^ 2)
//
// ---when to use---
//
// (1) data set is small OR
// (2) elements of data set are almost ordered OR
// (3) less code is required.
//
// ---parameters and return---
//
// @param input     is a data set to be sorted
// @param cmpFunc   is a function for comparing elements of data set
//
func InsertionSort(input []interface{}, cmpFunc func(interface{}, interface{}) int) {
	for i := 1; i < len(input); i++ {
		for j := i - 1; j >= 0 && cmpFunc(input[j], input[j+1]) > 0; j-- {
			input[j], input[j+1] = input[j+1], input[j]
		}
	}
}

func CmpInt(n1 interface{}, n2 interface{}) int {
	return n1.(int) - n2.(int)
}

func main() {
	var input []interface{}
	for i := 0; i < 40; i++ {
		input = append(input, rand.Int()%100)
	}
	fmt.Println(input)
	InsertionSort(input, CmpInt)
	fmt.Println(input)
}