huc::sort Namespace Reference

Classes
class	MergeInPlace
class	MergeWithBuffer

Functions
template<typename IT , typename Compare = std::less<typename std::iterator_traits<IT>::value_type>>
void	Bubble (const IT &begin, const IT &end)
template<typename IT , typename Compare = std::less<typename std::iterator_traits<IT>::value_type>>
void	Cocktail (const IT &begin, const IT &end)
template<typename IT , typename Compare = std::less<typename std::iterator_traits<IT>::value_type>>
void	Comb (const IT &begin, const IT &end)
template<typename IT , typename Aggregator = MergeWithBuffer<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<typename std::iterator_traits<IT>::value_type>>

void huc::sort::Bubble	(	const IT &	begin,
		const IT &	end
	)

Bubble Sort - Proceed an in-place sort on the elements.

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 41 of file bubble.hxx.

  {
    const auto distance = static_cast<const int>(std::distance(begin, end));
    if (distance < 2)
      return;

    int endIdx = -1;
    bool hasSwapped;
    // for each element - bubble it up until the end.
    for (auto it = begin; it < end - 1; ++it, --endIdx)
    {
      hasSwapped = false;
      for (auto curIt = begin; curIt < end + endIdx; ++curIt)
        if (Compare()(*(curIt + 1), *curIt))
        {
          std::swap(*(curIt + 1), *curIt);
          hasSwapped = true;
        }

      if (!hasSwapped)
        break;
    }
  }

template<typename IT , typename Compare = std::less<typename std::iterator_traits<IT>::value_type>>

void huc::sort::Cocktail	(	const IT &	begin,
		const IT &	end
	)

Cocktail Sort - Proceed an in-place sort on the elements.

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 41 of file cocktail.hxx.

    {
      const auto distance = static_cast<const int>(std::distance(begin, end));
      if (distance < 2)
        return;

      int beginIdx = 0;
      int endIdx = distance - 1;
      bool hasSwapped = true;
      while (hasSwapped && beginIdx < distance - 1)
      {
        hasSwapped = false;
        // for each element from beginning - bubble it up until the end.
        for (auto it = begin + beginIdx; it < begin + endIdx; ++it)
          if (Compare()(*(it + 1), *it))
          {
            std::swap(*it, *(it + 1));
            hasSwapped = true;
          }
        --endIdx;

        if (!hasSwapped)
          break;

        // for each element from the end- bubble it down until the beginning.
        for (auto it = begin + endIdx - 1; it >= begin + beginIdx; --it)
          if (Compare()(*(it + 1), *it))
          {
            std::swap(*it, *(it + 1));
            hasSwapped = true;
          }

        ++beginIdx;
      }
    }

template<typename IT , typename Compare = std::less<typename std::iterator_traits<IT>::value_type>>

void huc::sort::Comb	(	const IT &	begin,
		const IT &	end
	)

Comb Sort - Proceed an in-place sort on the elements.

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 41 of file comb.hxx.

    {
      const auto distance = static_cast<const int>(std::distance(begin, end));
      if (distance < 2)
        return;

      auto gap = distance;
      double shrink = 1.3;
      bool hasSwapped = true;
      while (hasSwapped)
      {
        hasSwapped = false;

        gap /= shrink;
        if (gap > 1)
          hasSwapped = true;
        else
          gap = 1;

        for (auto it = begin; it + gap < end; ++it)
          if (Compare()(*(it + gap), *it))
          {
            std::swap(*it, *(it + gap));
            hasSwapped = true;
          }
      }
    }

template<typename IT , typename Aggregator = MergeWithBuffer<IT>>

void huc::sort::MergeSort	(	const IT &	begin,
		const IT &	end
	)

MergeSort - Proceed sort on the elements whether using an in-place strategy or using a buffer one.

Template Parameters

IT	type using to go through the collection.
Aggregator	functor type used to aggregate two sorted sequences.

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 141 of file merge.hxx.

    {
      const auto ksize = static_cast<const int>(std::distance(begin, end));
      if (ksize < 2)
        return;

      auto pivot = begin + ksize / 2;

      // Recursively break the vector into two pieces
      MergeSort<IT, Aggregator>(begin, pivot);
      MergeSort<IT, Aggregator>(pivot, end);

      // Merge the two pieces
      Aggregator()(begin, pivot, end);
    }

template<typename IT , typename Compare = std::less_equal<typename std::iterator_traits<IT>::value_type>>

IT huc::sort::Partition	(	const IT &	begin,
		const IT &	pivot,
		const IT &	end
	)

Partition-Exchange - Proceed an in-place patitionning on the elements.

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 43 of file partition.hxx.

    {
      if (std::distance(begin, end) < 2 || pivot == end)
        return pivot;

      auto pivotValue = *pivot;       // Keep the pivot value;
      std::swap(*pivot, *(end - 1));  // Put the pivot at the end for convenience
      auto store = begin;             // Put the store pointer at the beginning

      // Swap each smaller before the pivot item
      for (auto it = begin; it != end - 1; ++it)
      {
        if (Compare()(*it, pivotValue))
        {
          std::swap(*store, *it);
          ++store;
        }
      }

      // Replace the pivot at its good position
      std::swap(*(end - 1), *store);

      return store;
    }

template<typename IT , typename Compare = std::less_equal<typename std::iterator_traits<IT>::value_type>>

void huc::sort::QuickSort	(	const IT &	begin,
		const IT &	end
	)

Quick Sort - Proceed an in-place sort on the elements.

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 40 of file quick.hxx.

    {
      const auto distance = static_cast<const int>(std::distance(begin, end));
      if (distance < 2)
        return;

      auto pivot = begin + (rand() % distance);                   // Pick Random Pivot € [begin, end]
      auto newPivot = Partition<IT, Compare>(begin, pivot, end);  // Proceed partition

      QuickSort<IT, Compare>(begin, newPivot);   // Recurse on first partition
      QuickSort<IT, Compare>(newPivot + 1, end); // Recurse on second partition
    }

template<typename IT >

void huc::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.

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.

    {
      if (std::distance(begin, end) < 2)
        return;

      // Create a bucket for each possible value of a digit
      std::vector<std::queue<typename std::iterator_traits<IT>::value_type>> buckets(base);

      // For all possible digit
      for (size_t powBase = 1;
           powBase < std::numeric_limits<typename std::iterator_traits<IT>::value_type>::max();
           powBase *= base)
      {
        // Push each number into the bucket of its digit value
        for (auto it = begin; it != end; ++it)
          buckets[static_cast<int>(*it / powBase) % base].push(*it);

        // Dequeu back all the values
        auto itSrc = begin;
        for (auto it = buckets.begin(); it != buckets.end(); ++it)
          while (!it->empty())
          {
            *(itSrc++) = it->front();
            it->pop();
          }
      }
    }