Classes | |
class | MergeInPlace |
class | MergeWithBuffer |
Functions | |
template<typename IT , typename Compare = std::less_equal<typename std::iterator_traits<IT>::value_type>> | |
void | Bubble (const IT &begin, const IT &end) |
template<typename Container , typename IT , typename Aggregator = MergeWithBuffer<Container, IT>> | |
void | MergeSort (const IT &begin, const IT &end) |
template<typename IT , typename Compare = std::less_equal<typename std::iterator_traits<IT>::value_type>> | |
IT | Partition (const IT &begin, const IT &pivot, const IT &end) |
template<typename IT , typename Compare = std::less_equal<typename std::iterator_traits<IT>::value_type>> | |
void | QuickSort (const IT &begin, const IT &end) |
template<typename IT > | |
void | RaddixSort (const IT &begin, const IT &end, unsigned int base=10) |
Function Documentation
void SHA_Sort::Bubble | ( | const IT & | begin, |
const IT & | end | ||
) |
Bubble Sort - Partition-Exchange Sort Proceed an in-place bubble-sort on the elements. sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps needed: it indicates that the list is sorted.
- Complexity
- O(N²) in average case and O(N²) on worst case.
- Remarks
- : Although the algorithm is simple, it is too slow and impractical for most problem.
- Template Parameters
-
IT type using to go through the collection. Compare functor type (std::less_equal in order, std::greater_equal for inverse order).
- Parameters
-
begin,end iterators to the initial and final positions of the sequence to be sorted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
- Returns
- void.
Definition at line 47 of file bubble.hxx.
void SHA_Sort::MergeSort | ( | const IT & | begin, |
const IT & | end | ||
) |
MergeSort - John von Neumann in 1945 Proceed merge-sort on the elements whether using an in-place strategy or using a buffer.
- Complexity
- O(N * log(N)).
- Template Parameters
-
IT type using to go through the collection.
- Parameters
-
begin,end iterators to the initial and final positions of the sequence to be sorted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
- Returns
- void.
- Todo:
- add compare template functor
Definition at line 148 of file merge.hxx.
IT SHA_Sort::Partition | ( | const IT & | begin, |
const IT & | pivot, | ||
const IT & | end | ||
) |
Partition-Exchange Proceed an in-place patitionning on the elements.
- Complexity
- O(N).
- Template Parameters
-
IT type using to go through the collection. Compare functor type (std::less_equal for smaller elements in left partition, std::greater_equal for greater elements in left partition).
- Parameters
-
begin,end const iterators to the initial and final positions of the sequence to be pivoted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last. pivot iterator on which the partition is delimited between begin and end.
- Returns
- new pivot iterator.
Definition at line 44 of file partition.hxx.
void SHA_Sort::QuickSort | ( | const IT & | begin, |
const IT & | end | ||
) |
Quick Sort - Partition-Exchange Sort Proceed an in-place quick-sort on the elements.
- Complexity
- O(N * log(N)) in average case and O(N²) on worst case.
- Remarks
- : this algorithm performs in general 2 to 3 time faster than a classic merge sort.
- : this algorithm is easily parallelizable.
- Template Parameters
-
IT type using to go through the collection. Compare functor type (std::less_equal in order, std::greater_equal for inverse order).
- Parameters
-
begin,end iterators to the initial and final positions of the sequence to be sorted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
- Returns
- void.
Definition at line 43 of file quick.hxx.
void SHA_Sort::RaddixSort | ( | const IT & | begin, |
const IT & | end, | ||
unsigned int | base = 10 |
||
) |
LSD Raddix Sort - Non-comparative integer sorting algorithm Proceed a raddix-sort on the elements contained in [begin, end[
- Warning
- Works properly only with integral type of non-negative values.
- Complexity
- O(d * N) with d max number of digits.
- Template Parameters
-
IT type using to go through the collection.
- Parameters
-
begin,end iterators to the initial and final positions of the sequence to be sorted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last. base base in which the numbers are represented.
- Returns
- void.
Definition at line 45 of file raddix.hxx.