3
\$\begingroup\$

I'm learning C++, data structures and algorithms and decided to implement some sorting algorithms using generic iterators instead of array indices.

This post contains code for insertion sort and other three variants: insertion sort with binary search, insertion sort with interpolation search and shell sort. As implied by the name, the first two variants uses a binary search and an interpolation search, respectively, instead of linearly search for the correct place to insert the key. Shell sort is a well known variant that sorts elements at distant positions and then successively reduces this distance.

Also, I decided to measure the running time and would like to known if my approach is correct. The results were consistent with the theoretical results that I was expecting after reading an algorithm book, but is there any best practice regarding time measurement that I'm missing?

I'm compiling with flags g++ -std=c++17 -g -Wall -Wextra -pedantic-errors I executed the code using valgrind, but it was much slower, so I only used arrays of maximum size 1000 when running with valgrind.

I'm learning C++ through a C++11 book and trying to learn C++14 and C++17 best practices on the fly. I appreciate any advice on how make it more compatible with modern best practices.

Sorting.h

#ifndef SORTING_H
#define SORTING_H

#include <iterator>
#include <functional>

namespace algorithms 
{
    template<typename RandomIt, typename Compare = std::less<>>
    void insertion_sort(RandomIt first, RandomIt last, Compare compare = Compare{});

    template<typename RandomIt, typename Compare = std::less<>>
    void binary_insertion_sort(RandomIt first, RandomIt last, Compare compare = Compare{});

    // Only works for numeric types
    template<typename RandomIt, typename Compare = std::less<>>
    void interpolation_insertion_sort(RandomIt first, RandomIt last, Compare compare = Compare{});

    template<typename RandomIt, typename Compare = std::less<>>
    void shell_sort(RandomIt first, RandomIt last, Compare compare = Compare{});

    // namespace detail is used for implementation details: not intended for external usage
    namespace detail 
    {
        template<typename RandomIt, typename Compare, typename T = typename std::iterator_traits<RandomIt>::value_type>
        RandomIt binary_search(RandomIt first, RandomIt last, const T& target, Compare compare);

        template<typename RandomIt, typename Compare, typename T = typename std::iterator_traits<RandomIt>::value_type>
        RandomIt interpolation_search(RandomIt first, RandomIt last, const T& target, Compare compare);

        template<typename RandomIt, typename SearchFunction, typename Compare>
        void insertion_sort(RandomIt first, RandomIt last, SearchFunction search, Compare compare);
    }
}

#include "Sorting.inl"

#endif // SORTING_H

Sorting.inl

namespace algorithms 
{
    /*
    The standard version of insertion_sort does not delegate the common work for 
    detail::insertion_sort because it would incur in a unnecessary cost of 
    a linear search to find the correct position and then an iteration to move
    elements. Instead, it can search the right position and move elements on a single pass.
    */
    template<typename RandomIt, typename Compare>
    void insertion_sort(RandomIt first, RandomIt last, Compare compare)
    {
        if (first != last)
        {
            for (auto it = first + 1; it != last; ++it)
            {
                auto key = std::move(*it);
                auto backward_it = it;

                for ( ; backward_it != first && compare(key, *(backward_it - 1)); --backward_it)
                {
                    *(backward_it) = std::move(*(backward_it - 1));
                }

                *backward_it = std::move(key);
            }
        }
    }

    template<typename RandomIt, typename Compare>
    void binary_insertion_sort(RandomIt first, RandomIt last, Compare compare)
    {
        detail::insertion_sort(first, last, detail::binary_search<RandomIt, Compare>, compare);
    }

    template<typename RandomIt, typename Compare>
    void interpolation_insertion_sort(RandomIt first, RandomIt last, Compare compare)
    {
        detail::insertion_sort(first, last, detail::interpolation_search<RandomIt, Compare>, compare);
    }

    template<typename RandomIt, typename Compare>
    void shell_sort(RandomIt first, RandomIt last, Compare compare)
    {
        if (first != last)
        {
            int h = 1;
            auto range_size = last - first;

            // Compute Knuth Sequence
            while (h < range_size / 3)
            {
                h = 3 * h + 1;

            }

            while (h > 0)
            {
                auto h_sequence_first = first + h;
                for (auto it = h_sequence_first; it != last; ++it)
                {
                    auto key = std::move(*it);
                    auto backward_it = it;

                    for ( ; backward_it >= h_sequence_first && compare(key, *(backward_it - h)); backward_it -= h)
                    {
                        *(backward_it) = std::move(*(backward_it - h));
                    }

                    *backward_it = std::move(key);
                }

                h = h / 3;
            }
        }
    }

    namespace detail
    {
        template<typename RandomIt, typename Compare, typename T = typename std::iterator_traits<RandomIt>::value_type>
        RandomIt binary_search(RandomIt first, RandomIt last, const T& target, Compare compare)
        {           
            while (first < last)
            {
                auto distance = last - first;
                auto middle = first + (distance / 2);

                if (*middle == target)
                {
                    return middle;
                }
                else if (compare(*middle, target)) // less than target
                {
                    first = middle + 1;
                }
                else
                {
                    last = middle;
                }
            }

            return first;
        }

        template<typename RandomIt, typename Compare, typename T = typename std::iterator_traits<RandomIt>::value_type>
        RandomIt interpolation_search(RandomIt first, RandomIt last, const T& target, Compare compare)
        {
            while (first < last)
            {
                auto& left = *first;
                auto& right = *(last - 1);

                if (compare(target, left))
                {
                    return first;
                }
                else if (compare(right, target))
                {
                    return last;
                }

                auto middle = first + (double(last - 1 - first)) * ((double(target) - double(left)) / (double(right) - double(left)));

                if (*middle == target)
                {
                    return middle;
                }
                else if (compare(*middle, target)) // less than target
                {
                    first = middle + 1;
                }
                else 
                {
                    last = middle;
                }
            }

            return first;
        }

        template<typename RandomIt, typename SearchFunction, typename Compare>
        void insertion_sort(RandomIt first, RandomIt last, SearchFunction search, Compare compare)
        {
            if (first != last)
            {
                for (auto it = first + 1; it != last; ++it)
                {
                    auto correct_position = search(first, it, *it, compare);

                    auto key = std::move(*it);

                    for (auto backward_it = it; backward_it != correct_position; --backward_it)
                    {
                        *backward_it = std::move(*(backward_it - 1));
                    }

                    *correct_position = std::move(key);
                }
            }
        }
    }
}

test.cpp

#include <array>
#include <cassert>
#include <iostream>
#include <random>
#include <vector>
#include "Sorting.h"

template<typename T>
using Matrix = std::vector<std::vector<T>>;

template<typename T, typename Compare>
void assert_equal(const std::vector<T>& vector1, std::vector<T> vector2, Compare compare)
{
    // vector1 is  assumed to be already sorted
    // vector2 is passed by copy to prevent changing the original vector
    std::sort(vector2.begin(), vector2.end(), compare);
    assert(vector1 == vector2);
}

template<typename T, typename Compare>
void assert_sorted(const std::vector<T>& vector, Compare compare)
{
    assert(std::is_sorted(vector.begin(), vector.end(), compare));
}

template<typename T, typename Function, typename Compare = std::less<>>
void test_sort(const Matrix<T>& original, Function function, Compare compare = Compare{})
{
    for (const auto& vector : original)
    {
        std::vector<T> to_sort { vector };
        function(to_sort, compare);

        assert_sorted(to_sort, compare);
        assert_equal(to_sort, vector, compare);
    }
}

template<typename T>
void test_sorting_algorithms(const Matrix<T>& original)
{
    test_sort(original, [](auto& vector, auto compare) { algorithms::insertion_sort(vector.begin(), vector.end(), compare); });
    test_sort(original, [](auto& vector, auto compare) { algorithms::insertion_sort(vector.begin(), vector.end(), compare); }, std::greater<>());

    test_sort(original, [](auto& vector, auto compare) { algorithms::binary_insertion_sort(vector.begin(), vector.end(), compare); });
    test_sort(original, [](auto& vector, auto compare) { algorithms::binary_insertion_sort(vector.begin(), vector.end(), compare); }, 
                std::greater<>());

    test_sort(original, [](auto& vector, auto compare) { algorithms::interpolation_insertion_sort(vector.begin(), vector.end(), compare); });
    test_sort(original, [](auto& vector, auto compare) { algorithms::interpolation_insertion_sort(vector.begin(), vector.end(), compare); }, 
                std::greater<>());

    test_sort(original, [](auto& vector, auto compare) { algorithms::shell_sort(vector.begin(), vector.end(), compare); });
    test_sort(original, [](auto& vector, auto compare) { algorithms::shell_sort(vector.begin(), vector.end(), compare); }, 
                std::greater<>());
}

int main()
{   
    Matrix<int> original;
    original.emplace_back(std::initializer_list<int>{}); // empty vector
    original.emplace_back(std::initializer_list<int>{ 1, 3, 5, 7, 9 }); // already sorted 
    original.emplace_back(std::initializer_list<int>{ 9, 7, 5, 3, 1 }); // reverse sorted
    original.emplace_back(std::initializer_list<int>{ 1, 3, 1, 5, 1 }); // repeated elements
    original.emplace_back(std::initializer_list<int>{ 9, 9, 9, 9, 9 }); // unique elements

    // randomly generated data
    std::random_device random_device;
    std::mt19937 mt(random_device());
    std::uniform_int_distribution<int> distribution(-100, 100);

    std::array<int, 7> vector_sizes = {{ 1, 2, 3, 5, 10, 100, 500 }};
    std::vector<int> temp;
    for (auto size: vector_sizes)
    {
        for (int i = 0; i < size; ++i)
        {
            temp.push_back(distribution(mt));
        }

        original.emplace_back(std::move(temp));
    }

    test_sorting_algorithms(original);

    std::cout << "End of Test\n";
}

time_comparison.cpp

#include <algorithm>
#include <array>
#include <cassert>
#include <chrono>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include "Sorting.h"

template<typename Fstream>
void open_file(Fstream& stream, const std::string& path)
{
    stream.close();
    stream.clear();
    stream.open(path);

    if (!stream)
    {
        std::cerr << "Error: could not find file at specified path -  " << path << "\n";
    }
}

template<typename T>
void fill_vector(std::vector<T>& vector, std::ifstream& stream)
{
    vector.clear();
    T data;
    while (stream >> data)
    {
        vector.emplace_back(data);
    }
}

template<typename F, typename... Args>
auto measure_time(F&& function, Args&&... args)
{
    auto start = std::chrono::high_resolution_clock::now();
    function(std::forward<Args>(args)...);
    auto end = std::chrono::high_resolution_clock::now();
    return std::chrono::duration_cast<std::chrono::microseconds>(end - start);
}

template<typename F>
void execution_time(const std::string& filename, F&& function)
{
    const std::array<std::string, 6> sorting_condition = {{ "Sorted", "90%Sorted", "75%Sorted", "HalfSorted", "ReverseSorted", "Random" }};
    const std::array<int, 10> sizes = {{ 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000 }};
    constexpr int experiments = 100;

    std::vector<int> to_sort;
    to_sort.reserve(10000);

    std::ifstream input_file;
    std::ofstream output_file;
    open_file(output_file, filename);

    for (const auto& sorting: sorting_condition)
    {
        output_file << "Input " << sorting << "\n";
        for (auto size: sizes)
        {
            output_file << "Size: " << size << "\t\t";

            open_file(input_file, "./data/" + sorting + std::to_string(size / 1000) + "K.txt");
            fill_vector(to_sort, input_file);
            assert(static_cast<int>(to_sort.size()) == size);

            std::chrono::microseconds average{ 0 };
            for (int i = 0; i < experiments; ++i)
            {
                average += measure_time(function, to_sort);
            }

            output_file << std::fixed << (average / experiments).count() << "\n";
        }

        output_file << "\n";
        assert(std::is_sorted(to_sort.begin(), to_sort.end()));
    }
}

int main()
{
    execution_time("Insertion Sort.txt", [](auto& vector) { algorithms::insertion_sort(vector.begin(), vector.end()); });
    execution_time("Binary Insertion Sort.txt", [](auto& vector) { algorithms::binary_insertion_sort(vector.begin(), vector.end()); });
    execution_time("Interpolation Insertion Sort.txt", [](auto& vector) { algorithms::interpolation_insertion_sort(vector.begin(), vector.end()); });
    execution_time("Shell Sort.txt", [](auto& vector) { algorithms::shell_sort(vector.begin(), vector.end()); });
}
\$\endgroup\$
  • \$\begingroup\$ Personally I would have spread this across 5 questions. There is a lot of hard thinking to do this reiew. Maybe this weekend, \$\endgroup\$ – Martin York Nov 27 '19 at 16:04
  • \$\begingroup\$ Would you prefer if I remove the "time_comparison" part and post it as another question? Since nobody answered this question yet, I guess that this does not break the rules. However, I would say that Sorting.h/Sorting.inl is tied to test.cpp and the code is somewhat short (at least in comparison to other code that I have post on this site on other opportunities). \$\endgroup\$ – M.ars Nov 27 '19 at 17:27
  • \$\begingroup\$ I think I'm used to interpolation search with upper and lower bound kept current and not re-determined for the unchanged bound and the index next to the changed one. I see that the source code on en.wikipedia does more comparisons and array accesses, still. \$\endgroup\$ – greybeard Nov 28 '19 at 1:04
  • \$\begingroup\$ @greybeard sorry, I didn't understand what you meant. Could you provide a source or example for the interpolation search implementation that you're talking about? My implementation was based on Sedgewick's book and my professor's lecture notes, but I adapted it so that the code returns an iterator to the correct place to insert the key (instead of returning -1 or nullptr, for example) \$\endgroup\$ – M.ars Nov 28 '19 at 1:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.