shell sort


See On Github

Data

Contributor

Generic placeholder thumbnail

by 3Hren

in c++

Source Code

#pragma once

#include <iostream>

struct knuth_gap_generator_t {
    template<typename T>
    static int next_gap_value(T gap) {
        return 3 * gap + 1;
    }

    template<typename T>
    static int prev_gap_value(T gap) {
        return (gap - 1) / 3;
    }
};

template<class GapGenerator, class RandomAccessIterator>
inline int init_gap(RandomAccessIterator begin, RandomAccessIterator end) {
    typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_type;

    difference_type gap = 0;
    const difference_type size = std::distance(begin, end);
    while (true) {
        const difference_type next = GapGenerator::next_gap_value(gap);
        if (next > size) {
            break;
        }

        gap = next;
    }

    return gap;
}

template<class RandomAccessIterator>
void insertion_sort(RandomAccessIterator begin, RandomAccessIterator end, typename std::iterator_traits<RandomAccessIterator>::difference_type gap = 1) {
    for (RandomAccessIterator i = begin + gap; i != end; ++i) {
        for (RandomAccessIterator j = i; j >= begin + gap; j -= gap) {
            if (*j < *(j - gap)) {
                std::iter_swap(j, j - gap);
            } else {
                break;
            }
        }
    }
}

template<class RandomAccessIterator, class GapGenerator = knuth_gap_generator_t>
void shell_sort(RandomAccessIterator begin, RandomAccessIterator end) {
    int gap = init_gap<GapGenerator>(begin, end);

    while (gap >= 1) {
        insertion_sort(begin, end, gap);
        gap = GapGenerator::prev_gap_value(gap);
    }
}
#include <assert.h>

#include <cstdlib>
#include <iostream>
#include <vector>

#include "shell_sort.hpp"

namespace aux {

template<class RandomAccessIterator>
bool is_sorted(RandomAccessIterator begin, RandomAccessIterator end) {
    for (RandomAccessIterator it = begin; it != end - 1; ++it) {
        if (*it > *(it + 1)) {
            return false;
        }
    }

    return true;
}

} // namespace aux

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "Usage: shell_sort_test N" << std::endl;
        exit(1);
    }

    const int N = std::stoi(argv[1]);

    std::srand(std::time(0));

    std::vector<int> data;
    data.reserve(N);
    for (int i = 0; i < N; ++i) {
        data.push_back(std::rand() % N);
    }

    shell_sort(data.begin(), data.end());

    assert(aux::is_sorted(data.begin(), data.end()));
}