understanding Array.sort

[Guest]

hi,
I had posted a question in the group "how to arrange arrays in increasing
order" Although i got an answer using IComparable Interface by Harfried
,which is given below.
Dim InputArray()() As Integer = _
New Integer()() { _
New Integer() {2, 0, 0}, _
New Integer() {1, 0, 0}, _
New Integer() {6, 0, 0}, _
New Integer() {3, 0, 0} _
}
Array.Sort(InputArray, New FooComparer)
...
...
...
Public Class FooComparer
Implements IComparer

Public Function Compare( _
ByVal x As Object, _
ByVal y As Object _
) As Integer Implements IComparer.Compare
Dim xx As Integer() = DirectCast(x, Integer())
Dim yy As Integer() = DirectCast(x, Integer())
Return yy(0) - xx(0)
End Function
End Class
/////


However, i fail to understand how 'compare' method works. In particular,
when we are comparing only two element at a time how does it sort all the
elements in order ? Am i missing something in understanding array. Can
someone give me some ideas as i need it to apply to some other classes.

TIA

 

[Samuel R. Neff]

The framework internally uses a quicksort algorithim to loop through
the data and call your Compare method as needed to sort the items.
You don't need to bother with looping or comparing multiple
items--it's handled internally by the framework.

For a better explanation, add a Console.WriteLine call inside your
compare method and then call Array.Sort. You'll see your method gets
called many times.

HTH,

Sam

However, i fail to understand how 'compare' method works. In particular,
when we are comparing only two element at a time how does it sort all the
elements in order ? Am i missing something in understanding array. Can
someone give me some ideas as i need it to apply to some other classes.

TIA

B-Line is now hiring one VB.NET developer for
WinForms + WebServices position with ASPX in future.
Seaking mid to senior level developer. For
information or to apply e-mail sam_blinex_com.

 

[Tom Dacon]

Any computer sorting algorithm consists of three main parts:

the picker, which decides which two items to compare next
the comparer, which decides which one of two items should precede the
other in the output array,
the swapper, which uses what the comparer told it to adjust the
locations of the two items

When you talk about bubble-sorts, quicksorts, and so on, you're really
talking about the picker part of the sorter. Most of the speed of a sort
algorithm comes from the algorithm the picker uses, but sometimes the
swapper can do useful things, like leaving the actual items in place but
swapping references to them.

So your implementation of IComparer is supplying just the comparer part of
the algorithm. Each time it's called, all you are concerned with is telling
the sorter which one of the two should come before the other.

HTH,
Tom Dacon
Dacon Software Consulting

 

[Herfried K. Wagner [MVP]]

Irfan,

However, i fail to understand how 'compare' method works. In particular,
when we are comparing only two element at a time how does it sort all the
elements in order ? Am i missing something in understanding array. Can
someone give me some ideas as i need it to apply to some other classes.

Sorting algorithm
<URL:http://en.wikipedia.org/wiki/Sorting_algorithm>

 

[Guest]

thanks for the reply,
just to close the loop...
Since the compare method returns 1, 0 or -1 when two elements are compared,
does it mean when the result is greater than 1, the element being compared
moves up and when it is less then one, it moves down ?

irfan

 

[Tom Dacon]

Yeah, basically that's it.

If you implement your own IComparer, its Compare method gets objects X and
Y. If you return a negative number, that says that X should precede Y in the
output; if you return zero, that says they're equal; if you return a
positive number, that says that X should follow Y in the output.