|
| From: | Rhys Weatherley <address@hidden> |
| Subject: | [Dotgnu-pnet-commits] CVS: pnetlib/runtime/System Array.cs,1.17,1.18 |
| Date: | Mon, 14 Apr 2003 01:23:35 -0400 |
Update of /cvsroot/dotgnu-pnet/pnetlib/runtime/System
In directory subversions:/tmp/cvs-serv8904/runtime/System
Modified Files:
Array.cs
Log Message:
Use quicksort for sorting Array and ArrayList instances.
Index: Array.cs
===================================================================
RCS file: /cvsroot/dotgnu-pnet/pnetlib/runtime/System/Array.cs,v
retrieving revision 1.17
retrieving revision 1.18
diff -C2 -r1.17 -r1.18
*** Array.cs 14 Apr 2003 04:49:11 -0000 1.17
--- Array.cs 14 Apr 2003 05:23:33 -0000 1.18
***************
*** 1031,1171 ****
}
! // Inner version of "Sort". Based on the Quicksort implementation
! // described in R. Sedgewick, "Algorithms in C++", Addison-Wesley, 1992.
! public static void InnerSort(Array keys, Array items,
! int lower, int upper,
! IComparer comparer)
! {
! // Temporary hack - use a dumb sort until I can figure
! // out what is wrong with the Quicksort code -- Rhys.
! int i, j, cmp;
! Object valuei;
! Object valuej;
! for(i = lower; i < upper; ++i)
{
! for(j = i + 1; j <= upper; ++j)
{
! valuei = keys.GetValue(i);
! valuej = keys.GetValue(j);
! if(comparer != null)
{
! cmp = comparer.Compare(valuei, valuej);
}
! else
{
! cmp =
((IComparable)valuei).CompareTo(valuej);
}
! if(cmp > 0)
{
! keys.SetValue(valuej, i);
! keys.SetValue(valuei, j);
if(items != null)
{
! valuei = items.GetValue(i);
! valuej = items.GetValue(j);
! items.SetValue(valuej, i);
! items.SetValue(valuei, j);
}
}
}
! }
! #if false
! int i, j, cmp;
! Object testKey;
! Object valuei;
! Object valuej;
! if(lower < upper)
! {
! // If this[lower] > this[upper], then swap. This
! // helps to make the loops below terminate predictably.
! testKey = keys.GetValue(upper);
! valuei = keys.GetValue(lower);
! if(comparer != null)
{
! cmp = comparer.Compare(valuei, testKey);
! }
! else
! {
! cmp = ((IComparable)valuei).CompareTo(testKey);
! }
! if(cmp > 0)
! {
! keys.SetValue(valuei, upper);
! keys.SetValue(testKey, lower);
! testKey = valuei;
! if(items != null)
{
! valuei = items.GetValue(lower);
! valuej = items.GetValue(upper);
! items.SetValue(valuej, lower);
! items.SetValue(valuei, upper);
}
}
!
! // Partition the array.
! i = lower - 1;
! j = upper;
! for(;;)
{
! do
! {
! ++i;
! valuei = keys.GetValue(i);
! if(comparer != null)
! {
! cmp = comparer.Compare(valuei,
testKey);
! }
! else
! {
! cmp =
((IComparable)valuei).CompareTo(testKey);
! }
! }
! while(cmp < 0);
! do
! {
! --j;
! valuej = keys.GetValue(j);
! if(comparer != null)
! {
! cmp = comparer.Compare(valuej,
testKey);
! }
! else
! {
! cmp =
((IComparable)valuej).CompareTo(testKey);
! }
! }
! while(cmp > 0);
! if(i >= j)
! {
! break;
! }
! keys.SetValue(valuej, i);
! keys.SetValue(valuei, j);
! if(items != null)
{
! valuei = items.GetValue(i);
! valuej = items.GetValue(j);
! items.SetValue(valuej, i);
! items.SetValue(valuei, j);
}
}
- valuei = keys.GetValue(i);
- valuej = keys.GetValue(upper);
- keys.SetValue(valuej, i);
- keys.SetValue(valuei, upper);
- if(items != null)
- {
- valuei = items.GetValue(i);
- valuej = items.GetValue(upper);
- items.SetValue(valuej, i);
- items.SetValue(valuei, upper);
- }
-
- // Sort the sub-partitions.
- InnerSort(keys, items, lower, i - 1, comparer);
- InnerSort(keys, items, i + 1, upper, comparer);
}
! #endif
}
--- 1031,1107 ----
}
! // Inner version of "Sort".
! private static void InnerSort(Array keys, Array items,
! int lower, int upper,
! IComparer comparer)
! {
! int i, j;
! Object pivot, temp;
! if((upper - lower) < 1)
! {
! // Zero or one elements - this partition is already
sorted.
! return;
! }
! do
{
! // Pick the middle of the range as the pivot value.
! i = lower;
! j = upper;
! pivot = keys.GetValue(i + ((j - i) / 2));
!
! // Partition the range.
! do
{
! // Find two values to be swapped.
! while(comparer.Compare(keys.GetValue(i), pivot)
< 0)
! {
! ++i;
! }
! while(comparer.Compare(keys.GetValue(j), pivot)
> 0)
{
! --j;
}
! if(i > j)
{
! break;
}
!
! // Swap the values.
! if(i < j)
{
! temp = keys.GetValue(i);
! keys.SetValue(keys.GetValue(j), i);
! keys.SetValue(temp, j);
if(items != null)
{
! temp = items.GetValue(i);
!
items.SetValue(items.GetValue(j), i);
! items.SetValue(temp, j);
}
}
+ ++i;
+ --j;
}
! while(i <= j);
! // Sort the partitions.
! if((j - lower) <= (upper - i))
{
! if(lower < j)
{
! InnerSort(keys, items, lower, j,
comparer);
}
+ lower = i;
}
! else
{
! if(i < upper)
{
! InnerSort(keys, items, i, upper,
comparer);
}
+ upper = j;
}
}
! while(lower < upper);
}
***************
*** 1187,1190 ****
--- 1123,1130 ----
throw new RankException(_("Arg_RankMustBe1"));
}
+ if(comparer == null)
+ {
+ comparer = Comparer.Default;
+ }
InnerSort(array, null, array.GetLowerBound(0),
array.GetUpperBound(0), comparer);
***************
*** 1223,1226 ****
--- 1163,1170 ----
}
}
+ if(comparer == null)
+ {
+ comparer = Comparer.Default;
+ }
InnerSort(keys, items, keys.GetLowerBound(0),
keys.GetUpperBound(0), comparer);
***************
*** 1260,1263 ****
--- 1204,1211 ----
throw new ArgumentException(_("Arg_InvalidArrayRange"));
}
+ if(comparer == null)
+ {
+ comparer = Comparer.Default;
+ }
InnerSort(array, null, index, index + length - 1, comparer);
}
***************
*** 1313,1316 ****
--- 1261,1268 ----
throw new
ArgumentException(_("Arg_InvalidArrayRange"));
}
+ }
+ if(comparer == null)
+ {
+ comparer = Comparer.Default;
}
InnerSort(keys, items, index, index + length - 1, comparer);
| [Prev in Thread] | Current Thread | [Next in Thread] |