Insertion sort

Insertion sort algorithm that people often use to sort bridge hands is to consider the cards one at a time, inserting each into its proper place among those already considered (keeping them sorted). In a computer implementation, we need to make space for the current item by moving larger items one position to the right, before inserting the current item into the vacated position.

title

/// ========== Insertation sort ==========
    template<class Iter>
    void insertionSort(Iter begin, Iter end) {
        for (auto j = begin; j != end - 1; ++j) {   // loop through the range
            auto value = *(j + 1);                  // insert value
            auto i = j;                             // loop variable
            while (i >= begin && *i > value) {      // while next element is greater and the range is correct 
                *(i + 1) = *i;                      // push the values away and move the pointer
                i--;
            }
            *(i + 1) = value;  // if correct place found insert the value
        }
    }

The main provide us testing function for demonstrate insertion sort.

#include <iostream>
    #include <random>
    #include <functional>
    #include <ctime>
    
    const int n = 10;
    
    ////////// Using random generator engine //////////
    std::default_random_engine gen((unsigned int)std::time(0));
    std::uniform_int_distribution<int> distribution(1, 50);
    auto randInt = std::bind(distribution, gen); // using randInt() generate integer number between (1-50)
    
    template<class Iter>
    void printArray(Iter begin, Iter end) {
        for (auto i = begin; i != end; i++) {
            std::cout << *i << ", ";
        }
        std::cout << std::endl;
    }
    
    template<class Iter>
    void testSorting(int* testArray, void(*sort)(Iter, Iter)) {
        std::cout << "original:  ";
        printArray(testArray, testArray + n);
    
        sort(testArray, testArray + n);
        std::cout << "sorted:  ";
        printArray(testArray, testArray + n);
    }

std::cout << "Testing sort algorithms ...\n\n";
    
    int* test = new int[n];
    
    auto generate = [](decltype(test[0]) i){ i = randInt(); };
    std::for_each (test, test + n, generate);
    
    std::cout << "*** Insertion sort: ***\n";
    testSorting<decltype(test)> (test, insertionSort);
    std::cout << "\n";
    
    delete[] test;