[Mono-dev] Minor change to Array.cs CODE REVIEW NEEDED

Scott Peterson lunchtimemama at gmail.com
Sat Dec 29 16:23:19 EST 2007


This is a minor change to the quicksort algorithm in Array.cs. It eliminates
an unnecessary comparison in a while loop. This is safe because that
comparison is done at the start of the qsort method and at the end of every
iteration of the while loop. If someone can O.K. this, I'll commit it.


Index: class/corlib/System/Array.cs
===================================================================
--- class/corlib/System/Array.cs    (revision 92007)
+++ class/corlib/System/Array.cs    (working copy)
@@ -1490,7 +1490,7 @@
             int mid = low + ((high - low) / 2);
             object objPivot = keys.GetValueImpl (mid);

-            while (low <= high) {
+            while (true) {
                 // Move the walls in
                 while (low < high0 && compare (keys.GetValueImpl (low),
objPivot, comparer) < 0)
                     ++low;
@@ -1501,7 +1501,8 @@
                     swap (keys, items, low, high);
                     ++low;
                     --high;
-                }
+                } else
+                    break;
             }

             if (low0 < high)
@@ -1690,7 +1691,7 @@
             int mid = low + ((high - low) / 2);
             K keyPivot = keys [mid];

-            while (low <= high) {
+            while (true) {
                 // Move the walls in
                 //while (low < high0 && comparer.Compare (keys [low],
keyPivot) < 0)
                 while (low < high0 && compare (keys [low], keyPivot,
comparer) < 0)
@@ -1703,7 +1704,8 @@
                     swap<K, V> (keys, items, low, high);
                     ++low;
                     --high;
-                }
+                } else
+                    break;
             }

             if (low0 < high)
@@ -1741,7 +1743,7 @@
             int mid = low + ((high - low) / 2);
             T keyPivot = array [mid];

-            while (low <= high) {
+            while (true) {
                 // Move the walls in
                 while (low < high0 && comparison (array [low], keyPivot) <
0)
                     ++low;
@@ -1752,7 +1754,8 @@
                     swap<T> (array, low, high);
                     ++low;
                     --high;
-                }
+                } else
+                    break;
             }

             if (low0 < high)

-- 
Scott.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.ximian.com/pipermail/mono-devel-list/attachments/20071229/41bee505/attachment.html 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Array.patch
Type: text/x-patch
Size: 1482 bytes
Desc: not available
Url : http://lists.ximian.com/pipermail/mono-devel-list/attachments/20071229/41bee505/attachment.bin 


More information about the Mono-devel-list mailing list