Sort implementation similar with std::sort().

mystd_sort.cpp

/*
  ## Sort Implementation

  * Selection Sort (Iterative / Recursive)
  * Bubble Sort (Iterative / Recursive)
  * Insertion Sort (Iterative / Recursive)

  * Interfaces is similar with std::sort()
  * Support comparator
 */

#include <vector>
// for std::swap
#include <algorithm>
#include <cassert>
#include <cstdio>

template<typename Iterator>
void print_data(Iterator begin, Iterator end)
{
	for(auto curr = begin ; curr != end ; ++curr) {
		printf("%d ", *curr);
	}
	printf("\n");
}

namespace mystd
{
	struct AscendingCompare {
		bool operator() (int i,int j) { return (i<j); }
	} ascending_compare;

	struct DescendingCompare {
		bool operator() (int i,int j) { return (i>j); }
	} descending_compare;

	template<typename Iterator, class Compare>
	Iterator find_compare(Iterator begin, Iterator end, Compare compare)
	{
		Iterator found = begin;
		typename Iterator::value_type val = *found;

		for(auto curr = begin ; curr != end ; ++curr) {
			if(compare(*curr, val)) {
				val = *curr;
				found = curr;
			}
		}
		return found;

	}

	namespace sort_selection
	{
		template<typename Iterator, class Compare>
		void iterative(Iterator begin, Iterator end, Compare compare)
		{
			for(Iterator curr = begin ; curr != (end - 1); ++curr) {
				Iterator found = find_compare(curr, end, compare);
				std::swap(*found, *curr);
			}
		}

		template<typename Iterator>
		void iterative(Iterator begin, Iterator end)
		{
			iterative(begin, end, ascending_compare);
		}


		template<typename Iterator, class Compare>
		void recursive(Iterator begin, Iterator end, Compare compare)
		{
			if(begin == end) {
				return;
			}

			Iterator found = find_compare(begin, end, compare);
			std::swap(*begin, *found);
			recursive(begin + 1, end, compare);
		}

		template<typename Iterator>
		void recursive(Iterator begin, Iterator end)
		{
			recursive(begin, end, ascending_compare);
		}
	}

	namespace sort_bubble
	{
		template<typename Iterator, class Compare>
		void iterative(Iterator begin, Iterator end, Compare compare)
		{
			for(auto i = begin ; i != (end-1) ; ++i) {
				for(auto j = i + 1 ; j != end ; ++j) {
					if(compare(*i, *j) == false) {
						std::swap(*i, *j);
					}
				}
			}
		}

		template<typename Iterator>
		void iterative(Iterator begin, Iterator end)
		{
			iterative(begin, end, ascending_compare);
		}

		template<typename Iterator, class Compare>
		void recursive(Iterator begin, Iterator end, Compare compare)
		{
			if(begin == end) {
				return;
			}

			Iterator curr = begin;
			Iterator next = curr + 1;

			while(next != end) {
				if(compare(*curr, *next) == false) {
					std::swap(*curr, *next);
				}
				++curr;
				++next;
			}

			recursive(begin, end - 1, compare);
		}

		template<typename Iterator>
		void recursive(Iterator begin, Iterator end)
		{
			recursive(begin, end, ascending_compare);
		}
	}

	namespace sort_insertion
	{
		template<typename Iterator, class Compare>
		void iterative(Iterator begin, Iterator end, Compare compare)
		{
			for(auto curr = begin ; curr != end ; ++curr) {
				auto curr_val = *curr;

				Iterator insertion_it = begin;
				for(insertion_it = begin ; insertion_it != curr ; ++insertion_it) {
					if(compare(curr_val, *insertion_it)) {
						break;
					}
				}

				for(auto it = curr; it != insertion_it ; --it) {
					std::swap(*it, *(it-1));
				}

				*insertion_it = curr_val;
			}
		}

		template<typename Iterator>
		void iterative(Iterator begin, Iterator end)
		{
			iterative(begin, end, ascending_compare);
		}


		template<typename Iterator, class Compare>
		void recursive_r(Iterator begin, Iterator sorted, Iterator end, Compare compare)
		{
			if(sorted == end) {
				return;
			}

			typename Iterator::value_type curr_val = *sorted;

			Iterator insertion_it = begin;
			for(insertion_it = begin ; insertion_it != sorted ; ++insertion_it) {
				if(compare(curr_val, *insertion_it)) {
					break;
				}
			}

			for(auto it = sorted ; it != insertion_it ; it--) {
				std::swap(*it, *(it-1));
			}

			*insertion_it = curr_val;
			recursive_r(begin, sorted + 1, end, compare);
		}

		template<typename Iterator, class Compare>
		void recursive(Iterator begin, Iterator end, Compare compare)
		{
			recursive_r(begin, begin, end, compare);
		}

		template<typename Iterator>
		void recursive(Iterator begin, Iterator end)
		{
			recursive_r(begin, begin, end, ascending_compare);
		}
	}
}

template<typename Data>
bool test_equal_data(const Data &a, const Data &b, const char *file, int line)
{
	bool success = (a == b);
	if(success == false) {
		printf("src : ");
		print_data(a.begin(), a.end());
		printf("dst : ");
		print_data(b.begin(), b.end());

		if(success == false) {
			printf("two data is not equal : %s:%d\n", file, line);
			assert(!"not equal list");
		}
	}
	return success;
}
#define TEST_EQUAL_DATA(A, B) test_equal_data(A, B, __FILE__, __LINE__)



int main()
{
	const std::vector<int> original_data = { 23, 78, 45, 8, 32, 56 };

	std::vector<int> asc_data(original_data);
	std::sort(asc_data.begin(), asc_data.end());

	std::vector<int> desc_data(original_data);
	std::sort(desc_data.begin(), desc_data.end(), mystd::descending_compare);

	std::vector<int> data;
	{
		// iterative
		data = original_data;
		mystd::sort_selection::iterative(data.begin(), data.end());
		TEST_EQUAL_DATA(data, asc_data);

		data = original_data;
		mystd::sort_bubble::iterative(data.begin(), data.end());
		TEST_EQUAL_DATA(data, asc_data);

		data = original_data;
		mystd::sort_insertion::iterative(data.begin(), data.end());
		TEST_EQUAL_DATA(data, asc_data);
	}
	{
		// recursive
		data = original_data;
		mystd::sort_selection::recursive(data.begin(), data.end());
		TEST_EQUAL_DATA(data, asc_data);

		data = original_data;
		mystd::sort_bubble::recursive(data.begin(), data.end());
		TEST_EQUAL_DATA(data, asc_data);

		data = original_data;
		mystd::sort_insertion::recursive(data.begin(), data.end());
		TEST_EQUAL_DATA(data, asc_data);
	}
	{
		// iterative + compare
		data = original_data;
		mystd::sort_selection::iterative(data.begin(), data.end(), mystd::descending_compare);
		TEST_EQUAL_DATA(data, desc_data);

		data = original_data;
		mystd::sort_bubble::iterative(data.begin(), data.end(), mystd::descending_compare);
		TEST_EQUAL_DATA(data, desc_data);

		data = original_data;
		mystd::sort_insertion::iterative(data.begin(), data.end(), mystd::descending_compare);
		TEST_EQUAL_DATA(data, desc_data);
	}
	{
		// recursive + compare
		data = original_data;
		mystd::sort_selection::recursive(data.begin(), data.end(), mystd::descending_compare);
		TEST_EQUAL_DATA(data, desc_data);

		data = original_data;
		mystd::sort_bubble::recursive(data.begin(), data.end(), mystd::descending_compare);
		TEST_EQUAL_DATA(data, desc_data);

		data = original_data;
		mystd::sort_insertion::recursive(data.begin(), data.end(), mystd::descending_compare);
		TEST_EQUAL_DATA(data, desc_data);

	}
	return 0;
}