Sorting speed improvement

[stephane Petithomme]

On Wednesday 23 April 2003 16:16, Jaime Torres wrote:
> 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 ).

Unicode??? Should need 65536 list!

>
> 	    // 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();
> 		}
> 	}
> }