[Scummvm-cvs-logs] SF.net SVN: scummvm:[51524] scummvm/trunk/common/algorithm.h

lordhoto at users.sourceforge.net lordhoto at users.sourceforge.net
Sat Jul 31 01:42:50 CEST 2010


Revision: 51524
          http://scummvm.svn.sourceforge.net/scummvm/?rev=51524&view=rev
Author:   lordhoto
Date:     2010-07-30 23:42:50 +0000 (Fri, 30 Jul 2010)

Log Message:
-----------
JANITORIAL: Some small explanation about stability of sorting algorithms.

Special thanks to lskovlun for his suggestion to add this.

Modified Paths:
--------------
    scummvm/trunk/common/algorithm.h

Modified: scummvm/trunk/common/algorithm.h
===================================================================
--- scummvm/trunk/common/algorithm.h	2010-07-30 23:24:45 UTC (rev 51523)
+++ scummvm/trunk/common/algorithm.h	2010-07-30 23:42:50 UTC (rev 51524)
@@ -199,8 +199,19 @@
  * It compares data with the given comparator object comp.
  *
  * Like std::sort this is not guaranteed to be stable.
- * Actually as the time of writing our implementation
- * is unstable.
+ *
+ * Two small quotes from wikipedia about stability:
+ *
+ * Stable sorting algorithms maintain the relative order of records with
+ * equal keys.
+ *
+ * Unstable sorting algorithms may change the relative order of records with
+ * equal keys, but stable sorting algorithms never do so.
+ *
+ * For more information on that topic check out:
+ * http://en.wikipedia.org/wiki/Sorting_algorithm#Stability
+ *
+ * NOTE: Actually as the time of writing our implementation is unstable.
  */
 template<typename T, class StrictWeakOrdering>
 void sort(T first, T last, StrictWeakOrdering comp) {


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.




More information about the Scummvm-git-logs mailing list