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. More...
ivec | sort_index (int low, int high, const Vec< T > &data)
| Sorting function that returns a sorted index vector. More...
void | intro_sort (int low, int high, int max_depth, Vec< T > &data)
| Introsort function of a subset of a vector `data`. More...
ivec | intro_sort_index (int low, int high, int max_depth, const Vec< T > &data)
| Introsort function, which returns a sorted index vector. More...

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

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

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

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

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

Generated on Thu Mar 20 2014 12:26:46 for IT++ by Doxygen 1.8.6