IT++ 4.3.1
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 \(\Theta(n\log n)\) 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 \(\Theta(n\log n)\) 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 \(\Theta(n^2)\) 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 \(\Theta(n\log n)\) 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:

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.

Constructor & Destructor Documentation

◆ Sort()

template<class T>
itpp::Sort< T >::Sort ( SORTING_METHOD method = INTROSORT)
inline

Constructor that sets Intro Sort method by default.

Definition at line 103 of file sort.h.

Member Function Documentation

◆ set_method()

template<class T>
void itpp::Sort< T >::set_method ( SORTING_METHOD method)
inline

Set sorting method.

Definition at line 106 of file sort.h.

◆ get_method()

template<class T>
SORTING_METHOD itpp::Sort< T >::get_method ( ) const
inline

Get current sorting method.

Definition at line 109 of file sort.h.

◆ sort()

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
lowStart index of a subvector to be sorted
highEnd index of a subvector to be sorted
dataData 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().

Referenced by itpp::Vec< double >::sort().

◆ sort_index()

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
lowStart index of a subvector to be sorted
highEnd index of a subvector to be sorted
dataData 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().

Referenced by itpp::Vec< double >::sort_index().

◆ intro_sort()

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
lowStart index of a subvector to be sorted
highEnd index of a subvector to be sorted
max_depthMaximum recursion depth before switching to heap sort recommended value: log2 of the length of the data vector
dataData 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().

◆ intro_sort_index()

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
lowStart index of a subvector to be sorted
highEnd index of a subvector to be sorted
max_depthMaximum recursion depth before switching to heap sort recommended value: log2 of the length of the data vector
dataData 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: