FX::QValueListQSort< type, movePolicy, swapPolicy, comparePolicy > Class Template Reference
[Qt Template Library]

#include <qvaluelist.h>

List of all members.


Detailed Description

template<class type, template< class > class movePolicy = Pol::itMove, template< class > class swapPolicy = Pol::itSwap, template< class > class comparePolicy = Pol::itCompare>
class FX::QValueListQSort< type, movePolicy, swapPolicy, comparePolicy >

Lets you quickly sort a QValueList with custom swapper.

This is a fully generic sorting routine which permits compile-time polymorphic instantiation of custom move, swap and compare routines letting you enable a whole new world of sorting lists eg; sorting multiple lists which are in the same order simultaneously by combining iterators to each entry within each into a core list (see below). This particular implementation mixes three algorithms to achieve the best performance - small lists (<12) are insertion sorted, medium lists (40,000) are merge sorted and large lists are quick sorted. With optimisation enabled, the outputted code is surprisingly slim and efficient.

In fact, for std::list this sort implementation is substantially more efficient than the STL's as it completely avoids copy construction which can take a significant amount of time. Items are swapped and moved by relinking their nodes within the linked list which is perhaps about six pointer exchanges.

Unfortunately there is precious little code on the internet showing how to do an inplace sort on a std::list via only iterators - they seem to assume that std::sort does all you'll ever need. The trouble with iterators is that when you move them, the relative ordering of the range alters as well as the old iterator itself becoming invalid. Hence I came up with my own solution which for small lists does a form of insertion sort whereby the list is scanned for items in the wrong place which when found cause another search to find where best to put it. Thus the best case is O(n) compares with zero moves. However, because this algorithm does not shift elements down or up like an insertion sort, it's worst case is O(n^2) compares with O(n) moves.

What about average case? Well, I'm not too hot on this, but the average permutations for a sequence is n*(n-1)/4 therefore that's the number of times another half list scan is caused. Hence, average case is also O(n^2) compares with O(n/2) moves. This sort is stable (does not reorder identical elements).

For medium sized lists, the merge algorithm is used. This has the advantage of requiring only O(n log n) for both average and worst-case scenarios as well as the sort output being created sequentially (thus very useful for sorting bigger-than-memory data). The disadvantage is that it costs up to half the list to store temporary data (I've chosen a maximum of 640Kb here or 40,000 nodes) as well becoming quite inefficient in travelling the linked list nodes in order to calculate the median.

Thus for larger lists, the quick sort algorithm is used which doesn't have the need for temporary space nor needs to traverse the linked list pointers as it chooses the first item as pivot. This obviously means you will get worst-case performance on nearly sorted data ie; O(n^2) whereas its average case is O(n log n). Unfortunately, quick sort is an unstable sort whereby identical elements will get reordered.

Note:
As yet, merge sorting remains unimplemented. Either a quick or insertion sort is chosen as appropriate.

Usage:

If you have three interdependent lists in the same order and want to sort them, usually it's best to consider merging those lists somehow. If that's impossible or unwise, then you'll need to sort them all at the same time.

A good example is FX::QDir which this class was originally written for. It maintains a QStringList of directory names and creates the QFileInfoList for those same names only on demand as this is an expensive operation (often in the order of milliseconds). If however it's already generated, it's wasteful to throw them away just because the sort order has changed - therefore, QDir uses this class to sort the string list and if the QFileInfo list is also available, then that too.

Best thing to do is to look at its source (one of the many benefits of open source). I should point out that the indirection item list which holds iterators pointing into the string and file info classes must take care during swaps to not swap itself, only its client data. This particular problem soaked up over a day of my time as I couldn't figure out what was going wrong. Hence I mention it here now and hope to save you all some time! :)

See also:
FX::QValueList, FX::Pol::itMove, FX::Pol::itSwap, FX::Pol::itCompare, FX::Pol::itRevCompare

Public Types

typedef QValueList< type > list
typedef list::iterator iterator

Public Member Functions

 QValueListQSort (QValueList< type > &list, int _sorttype=QVLQSortDefault)
void run (int _sorttype=QVLQSortDefault)

Protected Types

typedef std::pair< int, iterator > intit

Protected Attributes

listmylist
int sorttype

Constructor & Destructor Documentation

template<class type, template< class > class movePolicy = Pol::itMove, template< class > class swapPolicy = Pol::itSwap, template< class > class comparePolicy = Pol::itCompare>
FX::QValueListQSort< type, movePolicy, swapPolicy, comparePolicy >::QValueListQSort ( QValueList< type > &  list,
int  _sorttype = QVLQSortDefault 
) [inline]

Constructs a new instance. Setting no sort type sets them all.


Member Function Documentation

template<class type, template< class > class movePolicy = Pol::itMove, template< class > class swapPolicy = Pol::itSwap, template< class > class comparePolicy = Pol::itCompare>
void FX::QValueListQSort< type, movePolicy, swapPolicy, comparePolicy >::run ( int  _sorttype = QVLQSortDefault  )  [inline]

Runs the sort.

Referenced by FX::QPtrList< type >::sort().


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

(C) 2002-2008 Niall Douglas. Some parts (C) to assorted authors.
Generated on Fri Jun 13 22:29:04 2008 for TnFOX by doxygen v1.5.6