Re: An inefficiency in Array.Sort

Two points. First, MS documentation says they use QuickSort which does not
use a temporary array, and Array.Sort is an in-place sort. Second, my claim
is that when sorting array a(), Array.Sort compares a(i) to a(i), not that
they repeatedly compare a(i) to a(j) (did I understand you correctly?). The
former really makes no sense at all, especially presuming a QuickSort
algorithm.

"James Hahn" wrote:

You are assuming that it is inefficient to compare the same elements, which
may not be the case.

It is possible that the sort algorithm loses track of the original array
index. This can happen if it does a bulk copy from the source array to the
destination array. The bulk copy can save many compares if one source
sub-array is shorter than the other. The unnecesary comparisons of the same
items is more than offset by the comparisons thus saved.

You would need to know the algorithm used before being able to assert that
it would be worhtwhile to eliminate the unnecessary comparisons.

"AMercer" <AMercer@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote in message
news:8072AB00-0120-4F6A-B6C6-12026515CE90@xxxxxxxxxxxxxxxx
The class below exhibits an inefficiency in Array.Sort, namely comparing
an
array element to itself several times during Array.Sort's execution. To
recreate the problem, paste the code below in a test program, instantiate
TestArraySort, and call TestSort.

I have never seen Array.Sort fail, so all I am claiming is an
inefficiency.
I stumbled on this while experimenting with generic interfaces. I suggest
this be forwarded to MS for review.

-------------------

Public Class TestArraySort ' expose an inefficiency in Array.Sort
' Array.Sort performs unnecessary comparisons by comparing an element to
itself.
Implements Collections.Generic.IComparer(Of Integer) ' for Array.Sort
with
generic comparer

Public a() As Integer ' the array being sorted, visible from a break in
Compare()

Public Function Compare(ByVal x As Integer, ByVal y As Integer) As
Integer _
Implements System.Collections.Generic.IComparer(Of Integer).Compare
Debug.Assert(x <> y) ' fail if keys are equal
Return x - y
End Function

Public Sub TestSort() ' Call this to cause an assertion failure in
Compare
Randomize()
Dim n As Integer = 5
ReDim a(n)
For i As Integer = 1 To n
a(i) = CInt(Rnd(1) * 100) ' random data
a(i) = a(i) * 100 + i ' guarantee keys are unequal
Next
Array.Sort(a, 1, n, Me) ' sort using Compare() above
End Sub

End Class



.

Relevant Pages

  • Re: Need help sorting by specific fields in file.
    ... > I have a file that I need to sort and currently I am just ... You're sorting an array. ... grab the first 6 characters off of all of them, ... That's just a basic grab the first 6 numbers and compare approach. ...
    (perl.beginners)
  • Re: Fortran templates
    ... into "having a method which sorts the client-side array". ... have to explicitly define the type of data to compare. ... code, whereas in my Fortran quicksort-with-callbacks, you must define ... However, if you want to sort *strings*, you will have to define ...
    (comp.lang.fortran)
  • Re: Function that compares 2 alpha-numeric values?
    ... > Does anyone have a code snippet to compare those values so I can sort ... > the array of alpha-numeric values that include both characters and ... Run a sort on the numbers array, ...
    (comp.lang.javascript)
  • Re: how does sort work?
    ... i.e. to sort it as fast as possible. ... The sort method uses an "algorithm" to sort the array. ... In order to sort an array you have to compare the elements in the array. ... When ruby needs to compare two elements in the ...
    (comp.lang.ruby)
  • Re: PHP - I give up.
    ... /* Compares A and B, given auxiliary data AUX, and returns a ... typedef int algo_predicate_func (const void *data, ... SIZE bytes each, using COMPARE for comparisons. ... first element in ARRAY that matches TARGET, ...
    (comp.programming)
Loading