Collection of sorting algorithms and their implementation in C++11/14
This repo contains a collection of C++ implementations of a number of sorting algorithms. It also contains tests (written using google test suite) and benchmark for each of the algorithms.
Compiling and running the tests requires Google Test Google Benchmark and Cmake
cd sorting_algoritmsmkdir build && cd buildcmake -DCMAKE_BUILD_TYPE=Release ..make./sorting_tests./sorting_benchmark
- Each algoirithm implementation should be in its own file in the
sourcefolder. - Make sure that the interface for the sorting algorithm is the following:
// CMP_FN has type: D -> D -> bool
template < typename Iterator, typename CMP_FN>
void awesome_sorting_algorithm(Iterator s, Iterator e, CMP_FN cmp)- Write the relative tests: each tests in its own file in the
testsfolder - The minimal tests are:
#ifndef DS_AWESOME_ALGORITHM_SORT_TESTS_H_
#define DS_AWESOME_ALGORITHM_SORT_TESTS_H_
#include <gtest/gtest.h>
#include <sorting_test_utils.h>
#include <merge_sort.h>
//#include <common.h>
#include<vector>
TEST_P(RandomVectorSortTest, awesome_sorting_algorithm){
std::cout<<"Input size = "<<v.size()<<std::endl;
ASSERT_EQ(v.size(),SIZE);
DS::awesome_sorting_algorithm(begin(v),end(v),DS::lt<TYPE>);
ASSERT_EQ(v.size(),SIZE);
ASSERT_EQ(checksorting(v,ASCENDING),true);
}
TEST_P(RandomVectorSortTest, mergesort_ascending){
std::cout<<"Input size = "<<v.size()<<std::endl;
ASSERT_EQ(v.size(),SIZE);
DS::awesome_sorting_algorithm(begin(v),end(v),DS::gt<TYPE>);
ASSERT_EQ(v.size(),SIZE);
ASSERT_EQ(checksorting(v,DESCENDING),true);
}
#ENDIF // DS_AWESOME_ALGORITHM_SORT_TESTS_H_- Write a benchmark for the algorithm
- Each benchmark in a separate file
- A minimal benchmark could be the following
static void selection_sort_BM(benchmark::State& state) {
while (state.KeepRunning())
{
state.PauseTiming();
Container v;
populateRandom(v, state.range(0)); //numbers of elements
state.ResumeTiming();
DS::selection_sort(begin(v), end(v), DS::gt<TYPE>);
}
}
BENCHMARK(selection_sort_BM)->Unit(benchmark::kMillisecond)->Range(RANGE_START, RANGE_END);
#endif //DS_SELECTION_SORT_BENCH_H_- Make sure the only timed portion of the code is the sorting. Any initialization that is not relevant for measuring the speed of the algorithm should not be counted (use
state.PauseTiming();andstate.ResumeTiming();as in the example).