lti::quickPartialSort2< T, U > Class Template Reference
[Basic Statistics]

Quick partial sort with colateral effects. More...

#include <ltiQuickPartialSort.h>

Inheritance diagram for lti::quickPartialSort2< T, U >:

[legend]

Collaboration diagram for lti::quickPartialSort2< T, U >:

[legend]

List of all members.

Public Member Functions
	quickPartialSort2 ()
	quickPartialSort2 (const quickPartialSort2< T, U > &other)
virtual	~quickPartialSort2 ()
virtual const char *	getTypeName () const
bool	apply (vector< T > &keys, vector< U > &data) const
bool	apply (std::vector< T > &keys, vector< U > &data) const
bool	apply (const int pivotIndex, vector< T > &keys, vector< U > &data) const
bool	apply (const int pivotIndex, std::vector< T > &keys, vector< U > &data) const
virtual functor *	clone () const
Protected Member Functions
T	findMedian (vector< T > &vct, vector< U > &data, const int &begin, const int &end, const int &medianPos) const
int	partition (vector< T > &vct, vector< U > &data, const int &begin, const int &end) const
T	findMedian (std::vector< T > &vct, vector< U > &data, const int &begin, const int &end, const int &medianPos) const
int	partition (std::vector< T > &vct, vector< U > &data, const int &begin, const int &end) const

---

Detailed Description

template<class T, class U>
class lti::quickPartialSort2< T, U >

Quick partial sort with colateral effects.

This class is used to extract the n smallest elements of a vector, without requiring to complete the sort, while a second vector is sorted exactly the same way.

It is usually employed when you just required, for example, the three smallest elements of a vector.

If the so-called pivot-index is equal to vct.size()/2 (where vct is the vector you want to partially sort), then this functor is equivalent to the quickMedian.

The type of the vector elements T must accept the operator< and operator=.

Note that this functor always sorts in increasing order. If you need the n greatest elements, then just give as pivot-index vct.size()-n, and the last elements are the ones you are looking for.

See also:

lti::quickMedian2, lti::sort2, lti::quickPartialSort

---

Constructor & Destructor Documentation

template<class T, class U>

lti::quickPartialSort2< T, U >::quickPartialSort2

(

)

default constructor

template<class T, class U>

lti::quickPartialSort2< T, U >::quickPartialSort2

(

const quickPartialSort2< T, U > &

other

)

copy constructor

Parameters:

other

the object to be copied

template<class T, class U>

virtual lti::quickPartialSort2< T, U >::~quickPartialSort2

(

)

[virtual]

destructor

---

Member Function Documentation

template<class T, class U>

bool lti::quickPartialSort2< T, U >::apply	(	const int	pivotIndex,
		std::vector< T > &	keys,
		vector< U > &	data
	)			const

Partially sort the vector keys and reorder the elements of data accordingly.

Both vectors must have the same size.

Parameters:

	pivotIndex	pivot position on the given vector. The result has the first "pivotIndex" elements smaller or equal the rest of the vector elements.
	keys	vector<T> with the key data. This vector will be partially sorted.
	data	vector<U> with data to be sorted the same way as the keys. You can for example use a ivector initialized with the index values (i.e. data(i)=i), so that after the apply method you can check which elements are below the median and which above.

Returns:

true if successful, false otherwise.

template<class T, class U>

bool lti::quickPartialSort2< T, U >::apply	(	const int	pivotIndex,
		vector< T > &	keys,
		vector< U > &	data
	)			const

Partially sort the vector keys and reorder the elements of data accordingly.

Both vectors must have the same size.

Parameters:

	pivotIndex	pivot position on the given vector. The result has the first "pivotIndex" elements smaller or equal the rest of the vector elements.
	keys	vector<T> with the key data. This vector will be partially sorted.
	data	vector<U> with data to be sorted the same way as the keys. You can for example use a ivector initialized with the index values (i.e. data(i)=i), so that after the apply method you can check which elements are below the median and which above.

Returns:

true if successful, false otherwise.

template<class T, class U>

bool lti::quickPartialSort2< T, U >::apply	(	std::vector< T > &	keys,
		vector< U > &	data
	)			const

Partially sort the vector keys and reorder the elements of data accordingly.

Both vectors must have the same size.

Parameters:

	keys	vector<T> with the key data. This vector will be partially sorted.
	data	vector<U> with data to be sorted the same way as the keys. You can for example use a ivector initialized with the index values (i.e. data(i)=i), so that after the apply method you can check which elements are below the median and which above.

Returns:

true if successful, false otherwise.

template<class T, class U>

bool lti::quickPartialSort2< T, U >::apply	(	vector< T > &	keys,
		vector< U > &	data
	)			const

Partially sort the vector keys and reorder the elements of data accordingly.

Both vectors must have the same size.

Parameters:

	keys	vector<T> with the key data. This vector will be partially sorted.
	data	vector<U> with data to be sorted the same way as the keys. You can for example use a ivector initialized with the index values (i.e. data(i)=i), so that after the apply method you can check which elements are below the median and which above.

Returns:

true if successful, false otherwise.

template<class T, class U>

virtual functor* lti::quickPartialSort2< T, U >::clone

(

)

const [virtual]

returns a pointer to a clone of this functor.

Reimplemented from lti::quickPartialSort< T >.

template<class T, class U>

T lti::quickPartialSort2< T, U >::findMedian	(	std::vector< T > &	vct,
		vector< U > &	data,
		const int &	begin,
		const int &	end,
		const int &	medianPos
	)			const [protected]

this method calculates the median in a recursively form

template<class T, class U>

T lti::quickPartialSort2< T, U >::findMedian	(	vector< T > &	vct,
		vector< U > &	data,
		const int &	begin,
		const int &	end,
		const int &	medianPos
	)			const [protected]

this method calculates the median in a recursively form

template<class T, class U>

virtual const char* lti::quickPartialSort2< T, U >::getTypeName

(

)

const [virtual]

returns the name of this type ("quickPartialSort2")

Reimplemented from lti::quickPartialSort< T >.

template<class T, class U>

int lti::quickPartialSort2< T, U >::partition	(	std::vector< T > &	vct,
		vector< U > &	data,
		const int &	begin,
		const int &	end
	)			const [protected]

this method chooses a pivot-value and ensures that lower values lie at the left and higher values at the right of its final position, which will be returned.

template<class T, class U>

int lti::quickPartialSort2< T, U >::partition	(	vector< T > &	vct,
		vector< U > &	data,
		const int &	begin,
		const int &	end
	)			const [protected]

this method chooses a pivot-value and ensures that lower values lie at the left and higher values at the right of its final position, which will be returned.

---

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

• ltiQuickPartialSort.h