Sorting speed improvement

[Jaime Torres]

Hello,

	Yesterday I implemented an improved sorting algorithm (Postman Sort)
in the
QStringList class that I'm using right now. This algorithm is O(n) !!!!

	I have not measured the performance improvement because the
implementation is not
optimal at all and I am not very familiar with the QT classes.

	Anyway, this algorithm can be implemented in all the places that
need sorting things, like the file lists, .......

	Here you are the implementation.

Regards to everybody.




void QStringList::sort()
{
	// Very inneficient way of using the PostMan sort
	// But should be faster than the HeapSort, as it
	// as only O(n) complexity.
	// More information on http://postmansort.sourceforge.net (alpha and
spanish)
	// Google using postman sort

	// Fist, to know to maximum length of the strings
   int max_len=0;
    for ( QStringList::ConstIterator it = begin(); it != end(); ++it )
	if ( (*it).length()>max_len )
	    max_len=(*it).length();

	    // The good implementation needs 256 intermedate lists.
	    // But does not need to copy elements from list to list
	    // It is enought to move them (in a list implemented with
	    // pointers, just move the pointer ).

	    // I'm doing this my first day with the QT classes.
    QStringList lst[256];

    for ( int i = max_len; i >0 ; i--)
    {
		// Split the list using the character in the specified
position
		for ( QStringList::ConstIterator it = begin(); it != end();
++it )
			lst[(*it).at(i)].append(*it);
		// Join again the lists in the default
		clear();
		for ( int j = 0; j<256; j++)
		{
			// Reconstruct the original list
			// !!! There is no fast concat ????
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
			for ( QStringList::ConstIterator it =
lst[j].begin(); it != lst[j].end(); ++it )
				append(*it);
			lst[j].clear();
		}
	}
}
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.kde.org/pipermail/kde-optimize/attachments/20030423/a007b500/attachment.htm