understanding Array.sort

[Irfan Mumtaz]

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(Inpu tArray, New FooComparer)
...
...
...
Public Class FooComparer
Implements IComparer

Public Function Compare( _
ByVal x As Object, _
ByVal y As Object _
) As Integer Implements IComparer.Compa re
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

[Tom Dacon]

Re: understanding Array.sort

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

"Irfan Mumtaz" <spamMe@spam.ne t> wrote in message
news:AAC1C200-2E21-4415-9666-2F1D13980025@mi crosoft.com...[color=blue]
> 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(Inpu tArray, New FooComparer)
> ..
> ..
> ..
> Public Class FooComparer
> Implements IComparer
>
> Public Function Compare( _
> ByVal x As Object, _
> ByVal y As Object _
> ) As Integer Implements IComparer.Compa re
> 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
>[/color]

[Samuel R. Neff]

Re: understanding Array.sort


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.WriteLi ne call inside your
compare method and then call Array.Sort. You'll see your method gets
called many times.

HTH,

Sam

[color=blue]
>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[/color]


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.

[Herfried K. Wagner [MVP]]

Re: understanding Array.sort

Irfan,

"Irfan Mumtaz" <spamMe@spam.ne t> schrieb:[color=blue]
> 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.[/color]

Sorting algorithm
<URL:http://en.wikipedia.or g/wiki/Sorting_algorit hm>

--
M S Herfried K. Wagner
M V P <URL:http://dotnet.mvps.org/>
V B <URL:http://dotnet.mvps.org/dotnet/faqs/>

[Irfan Mumtaz]

Re: understanding Array.sort

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" wrote:
[color=blue]
> 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
>
> "Irfan Mumtaz" <spamMe@spam.ne t> wrote in message
> news:AAC1C200-2E21-4415-9666-2F1D13980025@mi crosoft.com...[color=green]
> > 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(Inpu tArray, New FooComparer)
> > ..
> > ..
> > ..
> > Public Class FooComparer
> > Implements IComparer
> >
> > Public Function Compare( _
> > ByVal x As Object, _
> > ByVal y As Object _
> > ) As Integer Implements IComparer.Compa re
> > 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
> >[/color]
>
>
>[/color]

[Tom Dacon]

Re: understanding Array.sort

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.

"Irfan Mumtaz" <spamMe@spam.ne t> wrote in message
news:F5BF2D4B-7F90-49FE-9E44-4175168B3D1C@mi crosoft.com...[color=blue]
> thanks for the reply,
> just to close the loop...
> Since the compare method returns 1, 0 or -1 when two elements are[/color]
compared,[color=blue]
> does it mean when the result is greater than 1, the element being[/color]
compared[color=blue]
> moves up and when it is less then one, it moves down ?
>
> irfan
>
>
> "Tom Dacon" wrote:
>[color=green]
> > 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[/color][/color]
the[color=blue][color=green]
> > 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[/color][/color]
of[color=blue][color=green]
> > the algorithm. Each time it's called, all you are concerned with is[/color][/color]
telling[color=blue][color=green]
> > the sorter which one of the two should come before the other.
> >
> > HTH,
> > Tom Dacon
> > Dacon Software Consulting
> >
> > "Irfan Mumtaz" <spamMe@spam.ne t> wrote in message
> > news:AAC1C200-2E21-4415-9666-2F1D13980025@mi crosoft.com...[color=darkred]
> > > hi,
> > > I had posted a question in the group "how to arrange arrays in[/color][/color][/color]
increasing[color=blue][color=green][color=darkred]
> > > order" Although i got an answer using IComparable Interface by[/color][/color][/color]
Harfried[color=blue][color=green][color=darkred]
> > > ,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(Inpu tArray, New FooComparer)
> > > ..
> > > ..
> > > ..
> > > Public Class FooComparer
> > > Implements IComparer
> > >
> > > Public Function Compare( _
> > > ByVal x As Object, _
> > > ByVal y As Object _
> > > ) As Integer Implements IComparer.Compa re
> > > 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[/color][/color][/color]
particular,[color=blue][color=green][color=darkred]
> > > when we are comparing only two element at a time how does it sort all[/color][/color][/color]
the[color=blue][color=green][color=darkred]
> > > 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[/color][/color][/color]
classes.[color=blue][color=green][color=darkred]
> > >
> > > TIA
> > >[/color]
> >
> >
> >[/color][/color]