Iyfjky

Question

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)
 
 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. . . !nn";

 //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?

(In void merge_sort(), counting the size unconditionally looks less clutter and may be no slower - faster, even.) — Aug 28 at 10:02
@greybeard I'm not sure what you mean by your comment. Mind explaining? — Aug 30 at 2:57
Try changing if (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 use rhs[size];. — Aug 30 at 3:44
@greybeard if I remove the condition then the size will increase every iteration through the collection. The value will no longer represent the actually number of elements in the container. Is there perhaps another way I can clean it up or obtain the size of the container from the iterators passed in? — Aug 30 at 4:07
that's also assuming I don't rewrite recursively as suggested by both Martin and snowhawk — Aug 30 at 4:08

score 8 · Accepted Answer · 2018-08-29 08:35:30Z

Bubble Sort

Are Random-Access Iterators overconstraining the requirements? Looking over the operations, you need to support the following

begin != end - Inequality comparison for iterators (Forward Iterator)

temp_lhs = begin - Copy-assignable (Iterator)

++temp_lhs - Incrementable (Iterator)

--end - Prefix decrement (Bidirectional Iterator)

Multipass (Forward Iterator)

Your bubble_sort supports iterators that are Random Access or Bidirectional.

 template <typename BidirIterator, typename Comparator = 
 std::less<typename std::iterator_traits<RandIterator>::value_type>>
 void bubble_sort(...)

Down with typename has been accepted for c++20. Until you have access to that feature, use helper traits to help with the readability.

 template <typename Iterator> 
 using value_type_t = typename std::iterator_traits<Iterator>::value_type;

 template <typename BidirIterator, typename Comparator = 
 std::less<value_type_t<BidirIterator>>>
 void bubble_sort(...)

c++14 introduced transparent comparators. From std::less<>,

The standard library provides a specialization of std::less when T is not specified, which leaves the parameter types and return type to be deduced.

You may omit the type in the comparator and let it be deduced.

 template <typename BidirIterator, typename Comparator = std::less<>>
 void bubble_sort(...)

 std::swap(*temp_lhs, *temp_rhs);

What happens if swap is specialized as a customization point for your dereferenced iterator type? You could use the ADL two-step,

 using std::swap;
 swap(*temp_lhs, *temp_rhs);

Or you could use std::iter_swap, which does the two-step and dereference for you.

 std::iter_swap(temp_lhs, temp_rhs);

You'll notice a pattern where you guard a swap with a comparison check,

if (cmp(rhs, lhs)) 
 std::iter_swap(lhs, rhs);

That's a candidate for an algorithm!

template <typename FwdIterator, typename Compare>
bool iter_swap_if(FwdIterator lhs, FwdIterator rhs, Compare cmp) 
 bool result = cmp(*rhs, *lhs);
 if (result) 
 std::iter_swap(lhs, rhs);
 
 return result;

You can write a version of bubble sort for Forward iterators by assigning the known previous to end as your new end. Bubble sort is also nice in that a pass with no swaps means it's sorted and can exit early.

template <typename FwdIterator, typename Compare = std::less<>>
inline void bubble_sort(FwdIterator first, FwdIterator last, Compare cmp = Compare) std::next(first) == last) 
 return; 
 

 for (bool swapped = true; swapped; /* */) 
 swapped = false;
 auto curr = first;
 for (auto next = std::next(curr); next != end; (void)++next, ++curr) 
 swapped 
 last = curr;

Selection Sort

As with bubble_sort, Random-Access iterators is overconstraining your iterator requirement.

begin != end - Inequality comparison for iterators (Forward Iterator)

smallest = begin - Copy-assignable (Iterator)

++begin - Incrementable (Iterator)

So Forward iterator is your requirement.

 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;

If you don't want to use std::min_element, then extract the minimum element finding algorithm from your selection_sort and place it into its own abstraction.

 for (; first != last; ++first) 
 // std::iter_swap(first, std::min_element(first, last, cmp));
 auto smallest = std::min_element(first, last, cmp);
 std::iter_swap(first, smallest);

Don't let reinventing-the-wheel prevent you from rewriting or reusing existing abstractions.

Bottom-Up Merge Sort

As Martin noted, this is a long function and really could benefit from one abstraction.

 template <typename RandIterator, typename Comparator = std::less<>>
 inline void merge_sort(RandIterator begin, RandIterator end, Comparator cmp = Comparator()) 
 while each successively longer chunk of pow2 is less than length
 for each paired chunk
 inplace_merge(first, mid, last, cmp);

inplace_merge can be reused for top-down merge sort and other merge operations.

Any glaring mistakes? (I don't feel like my testing is as good as it should be.)

Don't forget about the empty set! merge_sort segfaults when begin and end are equal. Test on containers with varying shape/size characteristics. Think about what possible states your input arguments can possibly be. Use different types (pairs for stability testing). This is what I threw at it.

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>

#define TEST_SORT(NAME) 
template <typename I, typename C = std::less<>> 
void test_ ## NAME (I first, I last, C cmp = C) 
 std::cout << #NAME << ":n"; 
 std::for_each(first, last, (auto t) 
 bruglesco:: NAME ## _sort(begin(t), end(t), cmp); 
 std::cout << std::boolalpha << std::is_sorted(begin(t), end(t)) << ","; 
 ); 
 std::cout << "nn"; 
 

TEST_SORT(selection)
TEST_SORT(bubble)
TEST_SORT(merge)

#undef TEST_SORT

int main() 
 using C = std::vector<int>;

 auto empty = C;
 auto singleton = C0;
 auto doubleton = C0, 1;
 auto random = C6, 4, 1, 5, 8, 2, 3, 0, 9, 7;
 auto ascend = C0, 1, 2, 3, 4, 5, 6, 7, 8, 9;
 auto descend = C9, 8, 7, 6, 5, 4, 3, 2, 1, 0;
 auto one_off = C0, 1, 3, 2, 4, 5, 7, 6, 8, 9;
 auto few_unique = C0, 1, 2, 0, 1, 2, 0, 1, 2, 0;
 auto organ = C5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5;
 auro hill = C0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0;

 auto sets = std::vector<C>empty, singleton, doubleton, random, ascend
 descend, one_off, few_unique, organ, hill;

 test_selection(begin(sets), end(sets));
 test_bubble(begin(sets), end(sets));
 test_merge(begin(sets), end(sets));

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.

Bubble sort - can return early if no swaps happen during a pass. Also, don't sleep on the performance of bubble sort with small sets of cheap to copy data or are working with nearly sorted data.

Selection sort - the interval you loop over may be [first, last-1) since the minimum element from [last-1, last) will always be the last remaining element at position last-1.

Merge sort - Using a buffer for merging reduces the number of comparisons from linearithmic to linear. Bubble/Insertion sort can often be faster on small sets of values. Measure to find the threshold where Bubble or Insertion sort outperform Merge Sort for an adaptive approach.

I believe I managed to maintain stability(which was not a requirement.) No?

Bubble sort - No. The negation on the compare result swaps on equal. You really wanted cmp(*temp_rhs, *temp_lhs).

Selection sort - No. Rotate instead of swap.

Merge sort - Yes!

Any issues with readability or decisions I should have documented?

Answered in the review.

Now that's a nice review!
â€“Â Deduplicator
Aug 28 at 9:47 — Aug 28 at 9:47

Martin York 71.2k481247 · Answer 2 · 2018-08-28 06:06:23Z

I'll assume you have tested them enough to say they work for normal situations.

Overall.

Though perfectly fine. Your use on the outer loop "looks" strange. Personally I would replace them with for() loops. But that's just me.

Swap

Your use of swap works for integers and normal built in types. But it may not work for all types (some types have their own swap in their own namespace).

So the idiomatic way to use swap is:


 using std::swap;
 swap(a, b);

Assuming a and b are type NameSpace::Type. Then if there is a swap function defined NameSpace for type Type then Koning lookup will find it. Otherwise the compiler will find swap in the local scope (imported from std) and use that.

But don't do that. There is a standard swap function for iterators that encapsulates all the above correctly. std::iter_swap().

So rather than:

std::swap(*temp_lhs, *temp_rhs);

use:

std::iter_swap(temp_lhs, temp_rhs); // Guaranteed correct swap.

Bubble Sort

You missed the standard optimization. If you do a pass and there was zero swaps required in the last past then the container is sorted and you can exit. This great property of bubble sort gives it a best case complexity of O(n) (ie if it is already sorted then its a single pass).

I am sure you can simplify the iterator manipulation so you don't have an extra comparison against end.

Selection Sort

You have an extra comparison against begin every iteration of the outer loop. Then you test to see if begin and smallest are the same at the end of the loop. Not sure that is an optimization or a pessimization. If you have found this to be a general case optimization then you should comment it.

Merge Sort

Looks like it should work.

But writing it all in one method like that hurts my brain. I prefer when it is split into two logical methods. But writing it as one may be a requirement to do everything in place. If so make that point in a comment.

Finaley

What are the performance characteristics of your sort in relation to std::sort?

On a sample size of 8,000 randomly generated integers std::sort sorted the data in 2ms, my merge did it in 241ms, selection took 878ms and bubble took 787,010ms. — Aug 28 at 12:57
@bruglesco Just to note, the big 3 implementations of std::sort use introsort, an adaptive top-down quicksort that falls back to heap-sort after a fixed depth is reached or insertion sort once a fixed sub-length is reached. — Aug 28 at 23:35
(When there is reason to edit this post, try ADL (Koenig lookup) and Finally.) — Aug 29 at 4:12

Toby Speight 18.7k13695 · Answer 3 · 2018-08-28 08:04:32Z

Martin has given you a good review of the sort code itself; I'll not repeat that. Instead, I'll look at the example usage code, and see how we can adapt that to be a more rigorous test of the functionality.

Firstly, although the visual comparison can be helpful when debugging, it can be tedious to have to inspect the results every time you make changes. Instead, we can make the program self-checking: exit with a success (zero) status if the tests pass, and a non-zero (error) status if any fail:

return !std::is_sorted(test_collection.begin(), test_collection.end());

Another inconvenience is that we must edit the program's source to test each algorithm. It would be helpful if a single program would test all three algorithms in one run. Let's write a helper function to do the repetitive parts, and allow us to re-use the same starting position for each sort:

#include <algorithm>
#include <array>
#include <iostream>

template<class RandomAccessIterator,
 class Comparator = std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>>
bool is_sort_correct(RandomAccessIterator a, RandomAccessIterator b,
 std::function<void(RandomAccessIterator,RandomAccessIterator, Comparator)> sort,
 Comparator cmp = Comparator())

 sort(a, b, cmp);
 return std::is_sorted(a, b, cmp);


int main()

 const std::array<int,11> test_collection 2, 97, 849, 38, 2, 13, 17, 2, 2, 22, 9 ;
 using Iter = typename decltype(test_collection)::iterator;

 auto failure_count = 0u;

 
 auto result_vector = test_collection;
 failure_count += !is_sort_correct(result_vector.begin(), result_vector.end(), bruglesco::bubble_sort<Iter>);
 

 
 auto result_vector = test_collection;
 failure_count += !is_sort_correct(result_vector.begin(), result_vector.end(), bruglesco::merge_sort<Iter>);
 

 
 auto result_vector = test_collection;
 failure_count += !is_sort_correct(result_vector.begin(), result_vector.end(), bruglesco::selection_sort<Iter>);
 

 return failure_count > 0;

It's about this point that we might want to consider moving to a unit-test framework (there are several to choose from). This helps in several ways; the most useful to me are

improved diagnostics when tests fail (e.g. showing expected and actual values of compared expressions)

ability to run the same tests many times on different data, and the same data through different tests

At this point, one could add further tests - I'd recommend adding tests of using a non-default comparator argument, and sorting collections of user-defined types. (We'll need a user-defined type anyway, if we want to test the stability of the sort).

score 8 · Accepted Answer · 2018-08-29 08:35:30Z

Bubble Sort

Are Random-Access Iterators overconstraining the requirements? Looking over the operations, you need to support the following

begin != end - Inequality comparison for iterators (Forward Iterator)

temp_lhs = begin - Copy-assignable (Iterator)

++temp_lhs - Incrementable (Iterator)

--end - Prefix decrement (Bidirectional Iterator)

Multipass (Forward Iterator)

Your bubble_sort supports iterators that are Random Access or Bidirectional.

 template <typename BidirIterator, typename Comparator = 
 std::less<typename std::iterator_traits<RandIterator>::value_type>>
 void bubble_sort(...)

Down with typename has been accepted for c++20. Until you have access to that feature, use helper traits to help with the readability.

 template <typename Iterator> 
 using value_type_t = typename std::iterator_traits<Iterator>::value_type;

 template <typename BidirIterator, typename Comparator = 
 std::less<value_type_t<BidirIterator>>>
 void bubble_sort(...)

c++14 introduced transparent comparators. From std::less<>,

The standard library provides a specialization of std::less when T is not specified, which leaves the parameter types and return type to be deduced.

You may omit the type in the comparator and let it be deduced.

 template <typename BidirIterator, typename Comparator = std::less<>>
 void bubble_sort(...)

 std::swap(*temp_lhs, *temp_rhs);

What happens if swap is specialized as a customization point for your dereferenced iterator type? You could use the ADL two-step,

 using std::swap;
 swap(*temp_lhs, *temp_rhs);

Or you could use std::iter_swap, which does the two-step and dereference for you.

 std::iter_swap(temp_lhs, temp_rhs);

You'll notice a pattern where you guard a swap with a comparison check,

if (cmp(rhs, lhs)) 
 std::iter_swap(lhs, rhs);

That's a candidate for an algorithm!

template <typename FwdIterator, typename Compare>
bool iter_swap_if(FwdIterator lhs, FwdIterator rhs, Compare cmp) 
 bool result = cmp(*rhs, *lhs);
 if (result) 
 std::iter_swap(lhs, rhs);
 
 return result;

You can write a version of bubble sort for Forward iterators by assigning the known previous to end as your new end. Bubble sort is also nice in that a pass with no swaps means it's sorted and can exit early.

template <typename FwdIterator, typename Compare = std::less<>>
inline void bubble_sort(FwdIterator first, FwdIterator last, Compare cmp = Compare) std::next(first) == last) 
 return; 
 

 for (bool swapped = true; swapped; /* */) 
 swapped = false;
 auto curr = first;
 for (auto next = std::next(curr); next != end; (void)++next, ++curr) 
 swapped 
 last = curr;

Selection Sort

As with bubble_sort, Random-Access iterators is overconstraining your iterator requirement.

begin != end - Inequality comparison for iterators (Forward Iterator)

smallest = begin - Copy-assignable (Iterator)

++begin - Incrementable (Iterator)

So Forward iterator is your requirement.

 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;

If you don't want to use std::min_element, then extract the minimum element finding algorithm from your selection_sort and place it into its own abstraction.

 for (; first != last; ++first) 
 // std::iter_swap(first, std::min_element(first, last, cmp));
 auto smallest = std::min_element(first, last, cmp);
 std::iter_swap(first, smallest);

Don't let reinventing-the-wheel prevent you from rewriting or reusing existing abstractions.

Bottom-Up Merge Sort

As Martin noted, this is a long function and really could benefit from one abstraction.

 template <typename RandIterator, typename Comparator = std::less<>>
 inline void merge_sort(RandIterator begin, RandIterator end, Comparator cmp = Comparator()) 
 while each successively longer chunk of pow2 is less than length
 for each paired chunk
 inplace_merge(first, mid, last, cmp);

inplace_merge can be reused for top-down merge sort and other merge operations.

Any glaring mistakes? (I don't feel like my testing is as good as it should be.)

Don't forget about the empty set! merge_sort segfaults when begin and end are equal. Test on containers with varying shape/size characteristics. Think about what possible states your input arguments can possibly be. Use different types (pairs for stability testing). This is what I threw at it.

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>

#define TEST_SORT(NAME) 
template <typename I, typename C = std::less<>> 
void test_ ## NAME (I first, I last, C cmp = C) 
 std::cout << #NAME << ":n"; 
 std::for_each(first, last, (auto t) 
 bruglesco:: NAME ## _sort(begin(t), end(t), cmp); 
 std::cout << std::boolalpha << std::is_sorted(begin(t), end(t)) << ","; 
 ); 
 std::cout << "nn"; 
 

TEST_SORT(selection)
TEST_SORT(bubble)
TEST_SORT(merge)

#undef TEST_SORT

int main() 
 using C = std::vector<int>;

 auto empty = C;
 auto singleton = C0;
 auto doubleton = C0, 1;
 auto random = C6, 4, 1, 5, 8, 2, 3, 0, 9, 7;
 auto ascend = C0, 1, 2, 3, 4, 5, 6, 7, 8, 9;
 auto descend = C9, 8, 7, 6, 5, 4, 3, 2, 1, 0;
 auto one_off = C0, 1, 3, 2, 4, 5, 7, 6, 8, 9;
 auto few_unique = C0, 1, 2, 0, 1, 2, 0, 1, 2, 0;
 auto organ = C5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5;
 auro hill = C0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0;

 auto sets = std::vector<C>empty, singleton, doubleton, random, ascend
 descend, one_off, few_unique, organ, hill;

 test_selection(begin(sets), end(sets));
 test_bubble(begin(sets), end(sets));
 test_merge(begin(sets), end(sets));

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.

Bubble sort - can return early if no swaps happen during a pass. Also, don't sleep on the performance of bubble sort with small sets of cheap to copy data or are working with nearly sorted data.

Selection sort - the interval you loop over may be [first, last-1) since the minimum element from [last-1, last) will always be the last remaining element at position last-1.

Merge sort - Using a buffer for merging reduces the number of comparisons from linearithmic to linear. Bubble/Insertion sort can often be faster on small sets of values. Measure to find the threshold where Bubble or Insertion sort outperform Merge Sort for an adaptive approach.

I believe I managed to maintain stability(which was not a requirement.) No?

Bubble sort - No. The negation on the compare result swaps on equal. You really wanted cmp(*temp_rhs, *temp_lhs).

Selection sort - No. Rotate instead of swap.

Merge sort - Yes!

Any issues with readability or decisions I should have documented?

Answered in the review.

Now that's a nice review!
â€“Â Deduplicator
Aug 28 at 9:47 — Aug 28 at 9:47

Martin York 71.2k481247 · Answer 5 · 2018-08-28 06:06:23Z

I'll assume you have tested them enough to say they work for normal situations.

Overall.

Though perfectly fine. Your use on the outer loop "looks" strange. Personally I would replace them with for() loops. But that's just me.

Swap

Your use of swap works for integers and normal built in types. But it may not work for all types (some types have their own swap in their own namespace).

So the idiomatic way to use swap is:


 using std::swap;
 swap(a, b);

Assuming a and b are type NameSpace::Type. Then if there is a swap function defined NameSpace for type Type then Koning lookup will find it. Otherwise the compiler will find swap in the local scope (imported from std) and use that.

But don't do that. There is a standard swap function for iterators that encapsulates all the above correctly. std::iter_swap().

So rather than:

std::swap(*temp_lhs, *temp_rhs);

use:

std::iter_swap(temp_lhs, temp_rhs); // Guaranteed correct swap.

Bubble Sort

You missed the standard optimization. If you do a pass and there was zero swaps required in the last past then the container is sorted and you can exit. This great property of bubble sort gives it a best case complexity of O(n) (ie if it is already sorted then its a single pass).

I am sure you can simplify the iterator manipulation so you don't have an extra comparison against end.

Selection Sort

You have an extra comparison against begin every iteration of the outer loop. Then you test to see if begin and smallest are the same at the end of the loop. Not sure that is an optimization or a pessimization. If you have found this to be a general case optimization then you should comment it.

Merge Sort

Looks like it should work.

But writing it all in one method like that hurts my brain. I prefer when it is split into two logical methods. But writing it as one may be a requirement to do everything in place. If so make that point in a comment.

Finaley

What are the performance characteristics of your sort in relation to std::sort?

On a sample size of 8,000 randomly generated integers std::sort sorted the data in 2ms, my merge did it in 241ms, selection took 878ms and bubble took 787,010ms. — Aug 28 at 12:57
@bruglesco Just to note, the big 3 implementations of std::sort use introsort, an adaptive top-down quicksort that falls back to heap-sort after a fixed depth is reached or insertion sort once a fixed sub-length is reached. — Aug 28 at 23:35
(When there is reason to edit this post, try ADL (Koenig lookup) and Finally.) — Aug 29 at 4:12

Toby Speight 18.7k13695 · Answer 6 · 2018-08-28 08:04:32Z

Martin has given you a good review of the sort code itself; I'll not repeat that. Instead, I'll look at the example usage code, and see how we can adapt that to be a more rigorous test of the functionality.

Firstly, although the visual comparison can be helpful when debugging, it can be tedious to have to inspect the results every time you make changes. Instead, we can make the program self-checking: exit with a success (zero) status if the tests pass, and a non-zero (error) status if any fail:

return !std::is_sorted(test_collection.begin(), test_collection.end());

Another inconvenience is that we must edit the program's source to test each algorithm. It would be helpful if a single program would test all three algorithms in one run. Let's write a helper function to do the repetitive parts, and allow us to re-use the same starting position for each sort:

#include <algorithm>
#include <array>
#include <iostream>

template<class RandomAccessIterator,
 class Comparator = std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>>
bool is_sort_correct(RandomAccessIterator a, RandomAccessIterator b,
 std::function<void(RandomAccessIterator,RandomAccessIterator, Comparator)> sort,
 Comparator cmp = Comparator())

 sort(a, b, cmp);
 return std::is_sorted(a, b, cmp);


int main()

 const std::array<int,11> test_collection 2, 97, 849, 38, 2, 13, 17, 2, 2, 22, 9 ;
 using Iter = typename decltype(test_collection)::iterator;

 auto failure_count = 0u;

 
 auto result_vector = test_collection;
 failure_count += !is_sort_correct(result_vector.begin(), result_vector.end(), bruglesco::bubble_sort<Iter>);
 

 
 auto result_vector = test_collection;
 failure_count += !is_sort_correct(result_vector.begin(), result_vector.end(), bruglesco::merge_sort<Iter>);
 

 
 auto result_vector = test_collection;
 failure_count += !is_sort_correct(result_vector.begin(), result_vector.end(), bruglesco::selection_sort<Iter>);
 

 return failure_count > 0;

It's about this point that we might want to consider moving to a unit-test framework (there are several to choose from). This helps in several ways; the most useful to me are

improved diagnostics when tests fail (e.g. showing expected and actual values of compared expressions)

ability to run the same tests many times on different data, and the same data through different tests

At this point, one could add further tests - I'd recommend adding tests of using a non-default comparator argument, and sorting collections of user-defined types. (We'll need a user-defined type anyway, if we want to test the stability of the sort).

Category

Random preview

Sorting three ways

3 Answers 3

Bubble Sort

Selection Sort

Bottom-Up Merge Sort

Overall.

Swap

Bubble Sort

Selection Sort

Merge Sort

Finaley

Your Answer

Sign up or log in

Post as a guest

Post as a guest

3 Answers 3

3 Answers 3

Bubble Sort

Selection Sort

Bottom-Up Merge Sort

Bubble Sort

Selection Sort

Bottom-Up Merge Sort

Bubble Sort

Selection Sort

Bottom-Up Merge Sort

Bubble Sort

Selection Sort

Bottom-Up Merge Sort

Overall.

Swap

Bubble Sort

Selection Sort

Merge Sort

Finaley

Overall.

Swap

Bubble Sort

Selection Sort

Merge Sort

Finaley

Overall.

Swap

Bubble Sort

Selection Sort

Merge Sort

Finaley

Overall.

Swap

Bubble Sort

Selection Sort

Merge Sort

Finaley

Sign up or log in

Post as a guest

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Comments

Post a Comment

Popular posts from this blog

What does second last employer means? [closed]

List of Gilmore Girls characters

Confectionery

3 Answers
3

3 Answers
3

3 Answers
3