itpp::Sort< T > Class Template Reference

Class for sorting of vectors. More...

#include <itpp/base/sort.h>

Public Member Functions
	Sort (SORTING_METHOD method=INTROSORT)
	Constructor that sets Intro Sort method by default.
void	set_method (SORTING_METHOD method)
	Set sorting method.
SORTING_METHOD	get_method () const
	Get current sorting method.
void	sort (int low, int high, Vec< T > &data)
	Sorting function of a subset of a vector data.
ivec	sort_index (int low, int high, const Vec< T > &data)
	Sorting function that returns a sorted index vector.
void	intro_sort (int low, int high, int max_depth, Vec< T > &data)
	Introsort function of a subset of a vector data.
ivec	intro_sort_index (int low, int high, int max_depth, const Vec< T > &data)
	Introsort function, which returns a sorted index vector.

Detailed Description

template<class T>
class itpp::Sort< T >

Class for sorting of vectors.

A class which takes a vector, and sorts its values descending. There are two types of sort: a normal sort (accessed via the Sort::sort() function) which sorts the vector passed in the argument, and an index sort (accessed via the Sort::sort_index() function) which leaves the passed vector intact, but returns an index vector describing the sorted order.

The Sort class has four sorting methods implemented:

• Introsort [1,2]: It is a sorting algorithm developed by David Musser. I starts as a quicksort, but switches to a heapsort in cases where the recursion becomes too deep. Additionally, when sub vectors become smaller than 16 elements, it switches to an insertion sort. Introsort has a worst-case of comparisons, bu has the efficiency of the quick sort algorithm in cases where the data is well conditioned for quicksort.
• Quicksort [3]: It is a comparison sorting algorithm that has an average complexity of comparisons. For most data sets, the quicksort will be significantly more efficient than this average. However for data sets not well suited to it, quicksort may require as many as comparisons. Example of such ill-suited data sets are those which are nearly in order, and data sets with multiple elements of the same value.
• Heapsort [4]: It is a comparison sorting algorithm. While it is usually seen to be slower than quicksort routines, its worst-case requires only comparisons. This makes it an ideal quicksort replacement for data sets that that are ill-conditioned for quicksorting.
• Insertion sort [5]: An insertion sort is a simple comparison sort, which is widely considered to be one of the most efficient algorithms for very small data sets (10-20 elements). http://en.wikipedia.org/wiki/Insertion_sort

References:

• [1] http://en.wikipedia.org/wiki/Introsort
• [2] http://www.cs.rpi.edu/~musser/gp/introsort.ps
• [3] http://en.wikipedia.org/wiki/Quicksort
• [4] http://en.wikipedia.org/wiki/Heapsort
• [5] http://en.wikipedia.org/wiki/Insertion_sort

Author

Tony Ottosson (Quicksort), Mark Dobossy (Introsort, Heapsort and Insertion Sort) and Adam Piatyszek (Sort class design, code clean-up)

Definition at line 99 of file sort.h.

Member Function Documentation

template<class T >

void itpp::Sort< T >::sort	(	int	low,
		int	high,
		Vec< T > &	data
	)

Sorting function of a subset of a vector data.

Parameters

low	Start index of a subvector to be sorted
high	End index of a subvector to be sorted
data	Data vector, in which a part of it is to be sorted

Definition at line 215 of file sort.h.

References itpp::Vec< Num_T >::_data(), it_assert, it_error, itpp::levels2bits(), and itpp::Vec< Num_T >::size().

template<class T >

ivec itpp::Sort< T >::sort_index	(	int	low,
		int	high,
		const Vec< T > &	data
	)

Sorting function that returns a sorted index vector.

Parameters

low	Start index of a subvector to be sorted
high	End index of a subvector to be sorted
data	Data vector, in which a part of it is to be sorted

Definition at line 245 of file sort.h.

References itpp::Vec< Num_T >::_data(), it_assert, it_error, itpp::levels2bits(), and itpp::Vec< Num_T >::size().

template<class T >

void itpp::Sort< T >::intro_sort	(	int	low,
		int	high,
		int	max_depth,
		Vec< T > &	data
	)

Introsort function of a subset of a vector data.

Parameters

low	Start index of a subvector to be sorted
high	End index of a subvector to be sorted
max_depth	Maximum recursion depth before switching to heap sort recommended value: log2 of the length of the data vector
data	Data vector, in which a part of it is to be sorted

Note

An introsort is not a stable sort (i.e. it may not maintain the relative order of elements with equal value.)

This function uses recurrence.

Definition at line 286 of file sort.h.

References itpp::Vec< Num_T >::_data(), it_assert, and itpp::Vec< Num_T >::size().

template<class T >

ivec itpp::Sort< T >::intro_sort_index	(	int	low,
		int	high,
		int	max_depth,
		const Vec< T > &	data
	)

Introsort function, which returns a sorted index vector.

Parameters

low	Start index of a subvector to be sorted
high	End index of a subvector to be sorted
max_depth	Maximum recursion depth before switching to heap sort recommended value: log2 of the length of the data vector
data	Data vector, in which a part of it is to be sorted

Note

An Introsort is not a stable sort (i.e. it may not maintain the relative order of elements with equal value.)

This function uses recurrence.

Definition at line 295 of file sort.h.

References itpp::Vec< Num_T >::_data(), it_assert, and itpp::Vec< Num_T >::size().

---

The documentation for this class was generated from the following file:

• itpp/base/sort.h