<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<META NAME="Generator" CONTENT="MS Exchange Server version 5.5.2653.12">
<TITLE>Sorting speed improvement</TITLE>
</HEAD>
<BODY>
<P><FONT SIZE=2>Hello,</FONT>
</P>
<P> <FONT SIZE=2>Yesterday I implemented an improved sorting algorithm (Postman Sort) in the</FONT>
<BR><FONT SIZE=2>QStringList class that I'm using right now. This algorithm is O(n) !!!!</FONT>
</P>
<P> <FONT SIZE=2>I have not measured the performance improvement because the implementation is not</FONT>
<BR><FONT SIZE=2>optimal at all and I am not very familiar with the QT classes.</FONT>
</P>
<P> <FONT SIZE=2>Anyway, this algorithm can be implemented in all the places that need sorting things, like the file lists, .......</FONT></P>
<P> <FONT SIZE=2>Here you are the implementation.</FONT>
</P>
<P><FONT SIZE=2>Regards to everybody.</FONT>
</P>
<BR>
<BR>
<BR>
<P><FONT SIZE=2>void QStringList::sort()</FONT>
<BR><FONT SIZE=2>{</FONT>
<BR> <FONT SIZE=2>// Very inneficient way of using the PostMan sort</FONT>
<BR> <FONT SIZE=2>// But should be faster than the HeapSort, as it</FONT>
<BR> <FONT SIZE=2>// as only O(n) complexity.</FONT>
<BR> <FONT SIZE=2>// More information on <A HREF="http://postmansort.sourceforge.net" TARGET="_blank">http://postmansort.sourceforge.net</A> (alpha and spanish)</FONT>
<BR> <FONT SIZE=2>// Google using postman sort</FONT>
</P>
<P> <FONT SIZE=2>// Fist, to know to maximum length of the strings</FONT>
<BR><FONT SIZE=2> int max_len=0;</FONT>
<BR><FONT SIZE=2> for ( QStringList::ConstIterator it = begin(); it != end(); ++it )</FONT>
<BR> <FONT SIZE=2>if ( (*it).length()>max_len )</FONT>
<BR> <FONT SIZE=2> max_len=(*it).length();</FONT>
</P>
<P> <FONT SIZE=2> // The good implementation needs 256 intermedate lists.</FONT>
<BR> <FONT SIZE=2> // But does not need to copy elements from list to list</FONT>
<BR> <FONT SIZE=2> // It is enought to move them (in a list implemented with</FONT>
<BR> <FONT SIZE=2> // pointers, just move the pointer ).</FONT>
</P>
<P> <FONT SIZE=2> // I'm doing this my first day with the QT classes.</FONT>
<BR><FONT SIZE=2> QStringList lst[256];</FONT>
</P>
<P><FONT SIZE=2> for ( int i = max_len; i >0 ; i--)</FONT>
<BR><FONT SIZE=2> {</FONT>
<BR> <FONT SIZE=2>// Split the list using the character in the specified position</FONT>
<BR> <FONT SIZE=2>for ( QStringList::ConstIterator it = begin(); it != end(); ++it )</FONT>
<BR> <FONT SIZE=2>lst[(*it).at(i)].append(*it);</FONT>
<BR> <FONT SIZE=2>// Join again the lists in the default</FONT>
<BR> <FONT SIZE=2>clear();</FONT>
<BR> <FONT SIZE=2>for ( int j = 0; j<256; j++)</FONT>
<BR> <FONT SIZE=2>{</FONT>
<BR> <FONT SIZE=2>// Reconstruct the original list</FONT>
<BR> <FONT SIZE=2>// !!! There is no fast concat ???? !!!!!!!!!!!!!!!!!!!!!!!!!!!!!</FONT>
<BR> <FONT SIZE=2>for ( QStringList::ConstIterator it = lst[j].begin(); it != lst[j].end(); ++it )</FONT>
<BR> <FONT SIZE=2>append(*it);</FONT>
<BR> <FONT SIZE=2>lst[j].clear();</FONT>
<BR> <FONT SIZE=2>}</FONT>
<BR> <FONT SIZE=2>}</FONT>
<BR><FONT SIZE=2>}</FONT>
</P>
</BODY>
</HTML>