Max sort

First, find the largest item in the array, and exchange it with the last entry. Then, find the next largest item and exchange it with the last but one entry. Continue in this way until the entire array is sorted. This method is called max or selection sort because it works by repeatedly selecting the largest remaining item.

title

/// ========== MAX sort ==========
    
    // helper function: find the maximum value in a given range
    template<class Iter>
    Iter findMax(Iter begin, Iter j) {
        auto max = begin;   // position of the maximum value
        for (auto i = begin; i < j; ++i)
            if (*(i + 1) > *max)
                max = i + 1;
    
        return max; 
    }
    
    template<class Iter>
    void maxSort(Iter begin, Iter end) {
        for (auto j = end - 1; j > begin; --j) {    // loop through from back to forward
            auto max = findMax(begin, j);           // find max value beetwen index (0 - j)
            std::swap(*j, *max);                    // swap max value with the actual last element
        }
    }

The main provide test functions for testing the sort algorithm.

#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 << "*** Max sort: ***\n";
    testSorting<decltype(test)> (test, maxSort);
    std::cout << "\n";
    
    delete[] test;