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

InsertionSort()

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().

median3()

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

Definition at line 145 of file qsort.hpp.

rotate3()

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().

rotate4()

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().

sort3()

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().

sort4()

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().

sort5()

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().

sort_samples()

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().