SHA_Sort Namespace Reference

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

template<typename IT , typename Compare = std::less_equal<typename std::iterator_traits<IT>::value_type>>
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
ITtype using to go through the collection.
Comparefunctor type (std::less_equal in order, std::greater_equal for inverse order).
Parameters
begin,enditerators 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.

48  {
49  const auto distance = static_cast<const int>(std::distance(begin, end));
50  if (distance < 2)
51  return;
52 
53  int endIdx = -1;
54  bool hasSwapped;
55  // for each element - bubble it up until the end.
56  for (auto it = begin; it < end - 1; ++it, --endIdx)
57  {
58  hasSwapped = false;
59  for (auto curIt = begin; curIt < end + endIdx; ++curIt)
60  if (Compare()(*(curIt + 1), *curIt))
61  {
62  std::swap(*(curIt + 1), *curIt);
63  hasSwapped = true;
64  }
65 
66  if (!hasSwapped)
67  break;
68  }
69  }
template<typename Container , typename IT , typename Aggregator = MergeWithBuffer<Container, IT>>
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
ITtype using to go through the collection.
Parameters
begin,enditerators 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.

149  {
150  const auto ksize = static_cast<const int>(std::distance(begin, end));
151  if (ksize < 2)
152  return;
153 
154  auto middle = begin + ksize / 2;
155 
156  // Recursively break the vector into two pieces
157  MergeSort<Container, IT, Aggregator>(begin, middle);
158  MergeSort<Container, IT, Aggregator>(middle, end);
159 
160  // Merge the two pieces
161  Aggregator()(begin, middle, end);
162  }
template<typename IT , typename Compare = std::less_equal<typename std::iterator_traits<IT>::value_type>>
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
ITtype using to go through the collection.
Comparefunctor type (std::less_equal for smaller elements in left partition, std::greater_equal for greater elements in left partition).
Parameters
begin,endconst 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.
pivotiterator on which the partition is delimited between begin and end.
Returns
new pivot iterator.

Definition at line 44 of file partition.hxx.

45  {
46  if (std::distance(begin, end) < 2 || pivot == end)
47  return pivot;
48 
49  auto pivotValue = *pivot; // Keep the pivot value;
50  std::swap(*pivot, *(end - 1)); // Put the pivot at the end for convenience
51  auto store = begin; // Put the store pointer at the beginning
52 
53  // Swap each smaller before the pivot item
54  for (auto it = begin; it != end - 1; ++it)
55  {
56  if (Compare()(*it, pivotValue))
57  {
58  std::swap(*store, *it);
59  ++store;
60  }
61  }
62 
63  // Replace the pivot at its good position
64  std::swap(*(end - 1), *store);
65 
66  return store;
67  }
template<typename IT , typename Compare = std::less_equal<typename std::iterator_traits<IT>::value_type>>
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
ITtype using to go through the collection.
Comparefunctor type (std::less_equal in order, std::greater_equal for inverse order).
Parameters
begin,enditerators 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.

44  {
45  const auto distance = static_cast<const int>(std::distance(begin, end));
46  if (distance < 2)
47  return;
48 
49  auto pivot = begin + (rand() % distance); // Pick Random Pivot € [begin, end]
50  auto newPivot = Partition<IT, Compare>(begin, pivot, end); // Proceed partition
51 
52  QuickSort<IT, Compare>(begin, newPivot); // Recurse on first partition
53  QuickSort<IT, Compare>(newPivot + 1, end); // Recurse on second partition
54  }
template<typename IT >
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
ITtype using to go through the collection.
Parameters
begin,enditerators 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.
basebase in which the numbers are represented.
Returns
void.

Definition at line 45 of file raddix.hxx.

46  {
47  if (std::distance(begin, end) < 2)
48  return;
49 
50  // Create a bucket for each possible value of a digit
51  std::vector<std::queue<typename std::iterator_traits<IT>::value_type>> buckets(base);
52 
53  // For all possible digit
54  for (size_t powBase = 1;
55  powBase < std::numeric_limits<typename std::iterator_traits<IT>::value_type>::max();
56  powBase *= base)
57  {
58  // Push each number into the bucket of its digit value
59  for (auto it = begin; it != end; ++it)
60  buckets[static_cast<int>(*it / powBase) % base].push(*it);
61 
62  // Dequeu back all the values
63  auto itSrc = begin;
64  for (auto it = buckets.begin(); it != buckets.end(); ++it)
65  while (!it->empty())
66  {
67  *(itSrc++) = it->front();
68  it->pop();
69  }
70  }
71  }