Sorting

Detailed Description

Functions to sort ranges.

We provide alternatives to std::sort that keep track of the number of swaps that have to be performed to put a range into a sorted order.

Functions
template<std::forward_iterator ForwardIt, class Compare = std::less<>>
std::size_t	itertools::bubble_sort (ForwardIt first, ForwardIt last, Compare comp={})
	Bubble sort elements in the given range.
template<std::ranges::forward_range Range, class Compare = std::less<>>
std::size_t	itertools::bubble_sort (Range &&rng, Compare comp={})
	Bubble sort elements in the given range.
template<std::bidirectional_iterator BidirIt, class Compare = std::less<>>
std::size_t	itertools::insertion_sort (BidirIt first, BidirIt last, Compare comp={})
	Insertion sort elements in the given range.
template<std::ranges::bidirectional_range Range, class Compare = std::less<>>
std::size_t	itertools::insertion_sort (Range &&rng, Compare comp={})
	Insertion sort elements in the given range.

Function Documentation

bubble_sort() [1/2]

template<std::forward_iterator ForwardIt, class Compare = std::less<>>

std::size_t itertools::bubble_sort	(	ForwardIt	first,
		ForwardIt	last,
		Compare	comp = {} )

#include <itertools/sort.hpp>

Bubble sort elements in the given range.

Sort the elements in the range [first, last) in the order prescribed by the comparison function comp. The underlying sorting algorithm is a stable bubble sort, i.e. already sorted elements will not be swapped. The number of swaps necessary to get the elements into sorted order is recorded and returned.

Computational complexity: \( \mathcal{O}(n^2) \).

This function is eager and puts the range in sorted order.

Template Parameters

ForwardIt	Forward iterator type.
Compare	Comparison function type.

Parameters

first	Forward iterator to the first element of the range.
last	Forward iterator to the element after the last of the range.
comp	Comparison function callable with two dereferenced iterators.

Returns

Number of swaps necessary to sort the range.

Definition at line 57 of file sort.hpp.

bubble_sort() [2/2]

template<std::ranges::forward_range Range, class Compare = std::less<>>

std::size_t itertools::bubble_sort	(	Range &&	rng,
		Compare	comp = {} )

#include <itertools/sort.hpp>

Bubble sort elements in the given range.

See itertools::bubble_sort for more details.

Template Parameters

Range	Forward range type.
Compare	Comparison function type.

Parameters

rng	A forward range to sort.
comp	Comparison function callable with two dereferenced iterators.

Returns

Number of swaps necessary to sort the range.

Definition at line 116 of file sort.hpp.

insertion_sort() [1/2]

template<std::bidirectional_iterator BidirIt, class Compare = std::less<>>

std::size_t itertools::insertion_sort	(	BidirIt	first,
		BidirIt	last,
		Compare	comp = {} )

#include <itertools/sort.hpp>

Insertion sort elements in the given range.

Sort the elements in the range [first, last) in the order prescribed by the comparison function comp. The underlying sorting algorithm is a stable insertion sort, i.e. already sorted elements will not be swapped. The number of swaps necessary to get the elements into sorted order is recorded and returned.

Computational complexity: \( \mathcal{O}(n^2) \).

This function is eager and puts the range in sorted order.

Template Parameters

BidirIt	Bidirectional iterator type.
Compare	Comparison function type.

Parameters

first	Bidirectional iterator to the first element of the range.
last	Bidirectional iterator to the element after the last of the range.
comp	Comparison function callable with two dereferenced iterators.

Returns

Number of swaps necessary to sort the range.

Definition at line 92 of file sort.hpp.

insertion_sort() [2/2]

template<std::ranges::bidirectional_range Range, class Compare = std::less<>>

std::size_t itertools::insertion_sort	(	Range &&	rng,
		Compare	comp = {} )

#include <itertools/sort.hpp>

Insertion sort elements in the given range.

See itertools::insertion_sort for more details.

Template Parameters

Range	Bidirectional range type.
Compare	Comparison function type.

Parameters

rng	A bidirectional range to sort.
comp	Comparison function callable with two dereferenced iterators.

Returns

Number of swaps necessary to sort the range.

Definition at line 132 of file sort.hpp.