Loading...
Searching...
No Matches
Auxiliary Algorithms
Algorithms

## Detailed Description

This group contains some algorithms implemented in LEMON in order to make it easier to implement complex algorithms.

## Files

file | radix_sort.h
| Radix sort.

## Functions

template<typename Iterator, typename Functor>
void | radixSort (Iterator first, Iterator last, Functor functor)
| Sorts the STL compatible range into ascending order.
template<typename Iterator, typename Functor>
void | stableRadixSort (Iterator first, Iterator last, Functor functor)
| Sorts the STL compatible range into ascending order in a stable way.

## Function Documentation

## radixSort()

template<typename Iterator, typename Functor>

void radixSort | ( | Iterator | first,
|  | Iterator | last,
|  | Functor | functor )

The `radixSort` sorts an STL compatible range into ascending order. The radix sort algorithm can sort items which are mapped to integers with an adaptable unary function `functor` and the order will be ascending according to these mapped values.

It is also possible to use a normal function instead of the functor object. If the functor is not given it will use the identity function instead.

This is a special quick sort algorithm where the pivot values to split the items are choosen to be 2k for each `k`. Therefore, the time complexity of the algorithm is O(log(c)*n) and it uses O(log(c)) additional space, where `c` is the maximal value and `n` is the number of the items in the container.

Parameters

  first | The begin of the given range.
  last | The end of the given range.
  functor | An adaptible unary function or a normal function which maps the items to any integer type which can be either signed or unsigned.

See also
  stableRadixSort()

## stableRadixSort()

template<typename Iterator, typename Functor>

void stableRadixSort | ( | Iterator | first,
|  | Iterator | last,
|  | Functor | functor )

This function sorts an STL compatible range into ascending order according to an integer mapping in the same as radixSort() does.

This sorting algorithm is stable, i.e. the order of two equal elements remains the same after the sorting.

This sort algorithm use a radix forward sort on the bytes of the integer number. The algorithm sorts the items byte-by-byte. First, it counts how many times a byte value occurs in the container, then it copies the corresponding items to another container in asceding order in O(n) time.

The time complexity of the algorithm is O(log(c)*n) and it uses O(n) additional space, where `c` is the maximal value and `n` is the number of the items in the container.

Parameters

  first | The begin of the given range.
  last | The end of the given range.
  functor | An adaptible unary function or a normal function which maps the items to any integer type which can be either signed or unsigned.

See also
  radixSort()