I have implemented function templates that take a begin and end iterator as well as an optional comparator for user-defined types. It was my intention to mimic the usage of std::sort
. The three sorting algorithms I used were bubble sort, selection sort and merge sort. I perform merge sort in place.
#ifndef BRUGLESCO_DATASORTER_SORTING_FUNCTIONS_H
#define BRUGLESCO_DATASORTER_SORTING_FUNCTIONS_H
#include <cstddef>
#include <functional>
#include <iterator>
#include <utility>
namespace bruglesco {
template <typename RandIterator,
typename Comparator = std::less<typename std::iterator_traits<RandIterator>::value_type>>
inline void bubble_sort(RandIterator begin,
RandIterator end,
Comparator cmp = Comparator())
{
while (begin != end)
{
for (auto temp_lhs = begin; temp_lhs != end; ++temp_lhs)
{
auto temp_rhs = temp_lhs;
++temp_rhs;
if (temp_rhs != end && !cmp(*temp_lhs, *temp_rhs))
{
std::swap(*temp_lhs, *temp_rhs);
}
}
--end;
}
}
template <typename RandIterator,
typename Comparator = std::less<typename std::iterator_traits<RandIterator>::value_type>>
inline void selection_sort(RandIterator begin,
RandIterator end,
Comparator cmp = Comparator())
{
while (begin != end)
{
auto smallest = begin;
for (auto temp = begin; temp != end; ++temp)
{
if (cmp(*temp, *smallest))
{
smallest = temp;
}
}
if (smallest != begin)
{
std::swap(*smallest, *begin);
}
++begin;
}
}
template <typename RandIterator,
typename Comparator = std::less<typename std::iterator_traits<RandIterator>::value_type>>
inline void merge_sort(RandIterator begin,
RandIterator end,
Comparator cmp = Comparator())
{
bool unsorted{ true };
std::size_t size = 0;
std::size_t sub_size = 1;
while (unsorted)
{
auto lhs = begin;
auto rhs = begin;
for (std::size_t i = 0; i < sub_size; ++i)
{
++rhs;
if (sub_size == 1) { ++size; }
}
while (rhs != end)
{
std::size_t left_count = sub_size;
std::size_t right_count = sub_size;
while (left_count > 0 && right_count > 0)
{
if (rhs == end) { break; }
if (cmp(*rhs, *lhs))
{
auto temp_lhs = rhs;
auto temp_rhs = rhs;
--temp_lhs;
while (temp_rhs != lhs)
{
std::swap(*temp_lhs, *temp_rhs);
--temp_lhs;
--temp_rhs;
}
++lhs;
if (rhs == end) { break; }
++rhs;
--right_count;
if (sub_size == 1) { ++size; }
}
else
{
++lhs;
--left_count;
}
}
for (std::size_t i = 0; i < left_count; ++i)
{
++lhs;
}
for (std::size_t i = 0; i < right_count; ++i)
{
if (rhs == end || lhs == end) { break; }
++lhs;
++rhs;
if (sub_size == 1) { ++size; }
}
for (std::size_t i = 0; i < sub_size; ++i)
{
if (rhs == end) { break; }
++rhs;
if (sub_size == 1) { ++size; }
}
}
sub_size *= 2;
if (sub_size > size) { unsorted = false; }
}
}
}
#endif // !BRUGLESCO_DATASORTER_SORTING_FUNCTIONS_H
I also have a small usage example:
#include "sorting_functions.h"
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> test_collection{ 2, 97, 849, 38, 2, 13, 17, 2, 2, 22, 9 };
for (auto& item : test_collection)
{
std::cout << item << '\n';
}
std::cout << "\nSorting. . . !\n\n";
//bruglesco::bubble_sort(test_collection.begin(), test_collection.end());
//bruglesco::merge_sort(test_collection.begin(), test_collection.end());
//bruglesco::selection_sort(test_collection.begin(), test_collection.end());
//std::sort(test_collection.begin(), test_collection.end());
for (auto& item : test_collection)
{
std::cout << item << '\n';
}
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}
A couple of things I would love review on.
- Any glaring mistakes? (I don't feel like my testing is as good as it should be.)
- Any performance optimizations I can make? *Assume for the sake of discussion that each function needs to represent said algorithm. (The best optimization for bubble sort is of course use a different algorithm.) Also assume that merge-sort needs to be done in-place.
- I believe I managed to maintain stability(which was not a requirement.) No?
- Any issues with readability or decisions I should have documented?
void merge_sort()
, counting thesize
unconditionally looks less clutter and may be no slower - faster, even.) \$\endgroup\$ – greybeard Aug 28 '18 at 10:02if (sub_size == 1) { ++size; }
to just++size;
(for looks & speed). I have no opinion on whether or not it is better to try and leave out++rhs;
and userhs[size];
. \$\endgroup\$ – greybeard Aug 30 '18 at 3:44