Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
thrill::common::qsort_local Namespace Reference

Functions

template<typename Compare , typename Iterator >
void InsertionSort (Iterator left, Iterator right, Compare cmp)
 
template<typename Iterator , typename Compare >
Iterator median3 (Iterator a, Iterator b, Iterator c, Compare cmp)
 
template<typename ValueType >
void rotate3 (ValueType &a0, ValueType &a1, ValueType &a2)
 Assigns a0 <- a1, a1 <- a2, and a2 <- a0. More...
 
template<typename ValueType >
void rotate4 (ValueType &a0, ValueType &a1, ValueType &a2, ValueType &a3)
 Assigns a0 <- a1, a1 <- a2, a2 <- a3, and a3 <- a0. More...
 
template<typename Compare , typename Iterator >
void sort3 (Iterator x, Iterator y, Iterator z, Compare cmp)
 Sort three items, stable, 2-3 compares, 0-2 swaps. More...
 
template<typename Compare , typename Iterator >
void sort4 (Iterator x1, Iterator x2, Iterator x3, Iterator x4, Compare cmp)
 Sort four items, stable, 3-6 compares, 0-5 swaps. More...
 
template<typename Compare , typename Iterator >
void sort5 (Iterator x1, Iterator x2, Iterator x3, Iterator x4, Iterator x5, Compare cmp)
 Sort five items, 4-10 compares, 0-9 swaps. More...
 
template<typename Iterator , typename Compare >
void sort_samples (Iterator *A, size_t size, Compare cmp)
 Sort iterators by their content, used for sorting pivot samples. More...
 

Function Documentation

void thrill::common::qsort_local::InsertionSort ( Iterator  left,
Iterator  right,
Compare  cmp 
)

Definition at line 113 of file qsort.hpp.

References tlx::swap().

Referenced by thrill::common::qsort_three_pivots().

Iterator thrill::common::qsort_local::median3 ( Iterator  a,
Iterator  b,
Iterator  c,
Compare  cmp 
)

Definition at line 145 of file qsort.hpp.

void thrill::common::qsort_local::rotate3 ( ValueType &  a0,
ValueType &  a1,
ValueType &  a2 
)

Assigns a0 <- a1, a1 <- a2, and a2 <- a0.

Definition at line 32 of file qsort.hpp.

Referenced by thrill::common::qsort_three_pivots(), and thrill::common::qsort_two_pivots_yaroslavskiy().

void thrill::common::qsort_local::rotate4 ( ValueType &  a0,
ValueType &  a1,
ValueType &  a2,
ValueType &  a3 
)

Assigns a0 <- a1, a1 <- a2, a2 <- a3, and a3 <- a0.

Definition at line 41 of file qsort.hpp.

Referenced by thrill::common::qsort_three_pivots().

void thrill::common::qsort_local::sort3 ( Iterator  x,
Iterator  y,
Iterator  z,
Compare  cmp 
)

Sort three items, stable, 2-3 compares, 0-2 swaps.

Definition at line 51 of file qsort.hpp.

References tlx::swap().

void thrill::common::qsort_local::sort4 ( Iterator  x1,
Iterator  x2,
Iterator  x3,
Iterator  x4,
Compare  cmp 
)

Sort four items, stable, 3-6 compares, 0-5 swaps.

Definition at line 76 of file qsort.hpp.

References tlx::swap().

void thrill::common::qsort_local::sort5 ( Iterator  x1,
Iterator  x2,
Iterator  x3,
Iterator  x4,
Iterator  x5,
Compare  cmp 
)

Sort five items, 4-10 compares, 0-9 swaps.

Definition at line 93 of file qsort.hpp.

References tlx::swap().

void thrill::common::qsort_local::sort_samples ( Iterator *  A,
size_t  size,
Compare  cmp 
)

Sort iterators by their content, used for sorting pivot samples.

Definition at line 166 of file qsort.hpp.

Referenced by thrill::common::qsort_three_pivots(), and thrill::common::qsort_two_pivots_yaroslavskiy().