[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

how does sort work?

Chris Sepic

2/2/2008 11:40:00 PM

I'm confused as to how the sort method works.

If I have:
a = [ "d", "a", "e", "c", "b" ]

I know that
a.sort {|x,y| x <=> y } (or just .sort)
= ["a", "b", "c", "d", "e"]

and
a.sort {|x,y| y <=> x }
= ["e", "d", "c", "b", "a"]

I understand how the <=> operator works, but what exactly is going on in
the block? What are x and y assigned to?
--
Posted via http://www.ruby-....
10 Answers

Greg P

2/3/2008 12:41:00 AM

0


"Chris Sepic" <chris.sepic@gmail.com> wrote in message
news:3be71570cbfeb7f18c389ab412785977@ruby-forum.com...
> I'm confused as to how the sort method works.
>
> If I have:
> a = [ "d", "a", "e", "c", "b" ]
>
> I know that
> a.sort {|x,y| x <=> y } (or just .sort)
> = ["a", "b", "c", "d", "e"]
>
> and
> a.sort {|x,y| y <=> x }
> = ["e", "d", "c", "b", "a"]
>
> I understand how the <=> operator works, but what exactly is going on in
> the block? What are x and y assigned to?

I'm used to sorting not be a language concept. I think I'm gonna like Ruby.

I think this operator is overloaded, but in this context means "comparison."
In the index of Mats' .chm file in the docs, I find several different
entries.

--
Gerry Ford

"The apple was really a peach."
-- Allison Dunn on the garden of eden


7stud --

2/3/2008 1:46:00 AM

0

Chris Sepic wrote:
> I'm confused as to how the sort method works.
>
> If I have:
> a = [ "d", "a", "e", "c", "b" ]
>
> I know that
> a.sort {|x,y| x <=> y } (or just .sort)
> = ["a", "b", "c", "d", "e"]
>
> and
> a.sort {|x,y| y <=> x }
> = ["e", "d", "c", "b", "a"]
>
> I understand how the <=> operator works, but what exactly is going on in
> the block? What are x and y assigned to?

Sorting arrays is a complex topic that has been given a lot of attention
in computer programming. The goal is to sort the array with the fewest
comparisons, i.e. to sort it as fast as possible. You can google the
topic and read about different sorting methods--you might start by
searching 'bubble sort'.

The sort method uses an "algorithm" (or methodology) to sort the array.
In order to sort an array you have to compare the elements in the array.
The fewer times you have to compare the elements to arrive at a sorted
array the better. When ruby needs to compare two elements in the
process of sorting an array, ruby assigns the two elements to the
variables x and y. Your block then decides which of the two elements
should come first in the array. Ruby takes that result and proceeds
with the process of sorting the array.

It should be obvious to you that your block has to be called more than
once in order for ruby to sort your array--you can't sort a 5 element
array by doing one comparison of two of the elements. But what is the
minimum number of comparisons ruby needs to make in order to sort your
array?


--
Posted via http://www.ruby-....

SpringFlowers AutumnMoon

2/3/2008 2:02:00 AM

0

Chris Sepic wrote:
> I'm confused as to how the sort method works.
>
> If I have:
> a = [ "d", "a", "e", "c", "b" ]
>
> I know that
> a.sort {|x,y| x <=> y } (or just .sort)
> = ["a", "b", "c", "d", "e"]
>
> and
> a.sort {|x,y| y <=> x }
> = ["e", "d", "c", "b", "a"]
>
> I understand how the <=> operator works, but what exactly is going on in
> the block? What are x and y assigned to?


to understand this, you can think of "sort" taking a function as a
parameter. and sort() will pass 2 numbers to this function, and
rearragne the elements according to the return value of -1, 0, or 1.

that's it. to understand it fully, you can read about "iterators" in
Ruby. where you can take a block as a function, and "yield" arguments
to this function, and get back a return value.

--
Posted via http://www.ruby-....

Chris Sepic

2/3/2008 3:09:00 AM

0

> to understand this, you can think of "sort" taking a function as a
> parameter. and sort() will pass 2 numbers to this function, and
> rearragne the elements according to the return value of -1, 0, or 1.
>
> that's it. to understand it fully, you can read about "iterators" in
> Ruby. where you can take a block as a function, and "yield" arguments
> to this function, and get back a return value.

I understand sorting and sorting algorithms - I was tripped up by the
function as a parameter thing. Thanks!




--
Posted via http://www.ruby-....

Todd Benson

2/3/2008 3:13:00 AM

0

On Feb 2, 2008 8:02 PM, SpringFlowers AutumnMoon
<summercoolness@gmail.com> wrote:
> Chris Sepic wrote:
> > I'm confused as to how the sort method works.
> >
> > If I have:
> > a = [ "d", "a", "e", "c", "b" ]
> >
> > I know that
> > a.sort {|x,y| x <=> y } (or just .sort)
> > = ["a", "b", "c", "d", "e"]
> >
> > and
> > a.sort {|x,y| y <=> x }
> > = ["e", "d", "c", "b", "a"]
> >
> > I understand how the <=> operator works, but what exactly is going on in
> > the block? What are x and y assigned to?
>
>
> to understand this, you can think of "sort" taking a function as a
> parameter. and sort() will pass 2 numbers to this function, and
> rearragne the elements according to the return value of -1, 0, or 1.

That's right. Basically, #sort gives you, on each iteration, two
elements out of your list based on it's own sort algorithm (I think it
uses a quicksort version?). Your code can do whatever it wants to
with these elements, as long as your block returns a -1, 0, or 1 each
time. For example, your sort may be based on a suffix instead of a
beginning character or number (i.e. hexagon vs pentagram when the
order I want is n-grams to come before n-gons). Thus, you can define
the characteristics that must be sorted by, and those characteristics
can be sophisticated if you need them to be.

Todd

Greg P

2/3/2008 3:38:00 AM

0


"Todd Benson" <caduceass@gmail.com> wrote in message
news:eaeff8c10802021913w17eccc0ch31d9a9b18af78dfd@mail.gmail.com...
> On Feb 2, 2008 8:02 PM, SpringFlowers AutumnMoon
> <summercoolness@gmail.com> wrote:
>> Chris Sepic wrote:
>> > I'm confused as to how the sort method works.
>> >
>> > If I have:
>> > a = [ "d", "a", "e", "c", "b" ]
>> >
>> > I know that
>> > a.sort {|x,y| x <=> y } (or just .sort)
>> > = ["a", "b", "c", "d", "e"]
>> >
>> > and
>> > a.sort {|x,y| y <=> x }
>> > = ["e", "d", "c", "b", "a"]
>> >
>> > I understand how the <=> operator works, but what exactly is going on
>> > in
>> > the block? What are x and y assigned to?
>>
>>
>> to understand this, you can think of "sort" taking a function as a
>> parameter. and sort() will pass 2 numbers to this function, and
>> rearragne the elements according to the return value of -1, 0, or 1.
>
> That's right. Basically, #sort gives you, on each iteration, two
> elements out of your list based on it's own sort algorithm (I think it
> uses a quicksort version?). Your code can do whatever it wants to
> with these elements, as long as your block returns a -1, 0, or 1 each
> time. For example, your sort may be based on a suffix instead of a
> beginning character or number (i.e. hexagon vs pentagram when the
> order I want is n-grams to come before n-gons). Thus, you can define
> the characteristics that must be sorted by, and those characteristics
> can be sophisticated if you need them to be.
>
> Todd
>

Why do you put a hash in front of sort?


--
Gerry Ford

"The apple was really a peach."
-- Allison Dunn on the garden of eden


Greg P

2/3/2008 4:11:00 AM

0


"7stud --" <bbxx789_05ss@yahoo.com> wrote in message
news:6bb4c82932a54398bda16f052b3c7d00@ruby-forum.com...

> It should be obvious to you that your block has to be called more than
> once in order for ruby to sort your array--you can't sort a 5 element
> array by doing one comparison of two of the elements. But what is the
> minimum number of comparisons ruby needs to make in order to sort your
> array?
I think 5-element sorts are different from 4- and 6-, and for different
reasons.

A4 has cardinality 4! Nothing goes wrong at this number. A5 has
cardinality 60, the order of an important finite, simple group. Things
break down between four and five, for example, the theory of equations.

On the other side of five is six. Somewhere between five and six is where
mankind falls, if he does a binary sort with 2^n elements. Five means your
chugging along on five different tracks. Old Bach could do six on his
organ.

At UPS, we had 16 belts. There were advantages to duality. It was a 2^4
gig.

Error on g-string, is, of course a six.


--
Gerry Ford

"The apple was really a peach."
-- Allison Dunn on the garden of eden


Robert Klemme

2/3/2008 5:20:00 PM

0

On 03.02.2008 04:09, Chris Sepic wrote:
>> to understand this, you can think of "sort" taking a function as a
>> parameter. and sort() will pass 2 numbers to this function, and
>> rearragne the elements according to the return value of -1, 0, or 1.
>>
>> that's it. to understand it fully, you can read about "iterators" in
>> Ruby. where you can take a block as a function, and "yield" arguments
>> to this function, and get back a return value.
>
> I understand sorting and sorting algorithms - I was tripped up by the
> function as a parameter thing. Thanks!

Yeah, a block is an anonymous function.

You can see how it works if you insert a print statement:

irb(main):001:0> a = [ "d", "a", "e", "c", "b" ]
=> ["d", "a", "e", "c", "b"]
irb(main):002:0> a.sort {|x,y| p [x,y]; x<=>y}
["d", "e"]
["e", "b"]
["d", "b"]
["a", "d"]
["c", "d"]
["b", "a"]
["a", "c"]
["b", "c"]
=> ["a", "b", "c", "d", "e"]
irb(main):003:0>

A nice quiz might be to find out the sorting algorithm based on this
output. :-)

Kind regards

robert

The Peeler

6/7/2013 11:26:00 AM

0

On Thu, 6 Jun 2013 22:18:00 -0500, Stupid DoDo, now posting as Michael
Baldwin, The Rectum's Croatian whore, wrote:


>> Geez, Pig Boy/The Rev'd/Goran Radavich the degenerate Serb nose -
>> picker, DOD the Croat Nazi says he's not a Jew - baiter like you &
>> that he likes & admires Jews!
>>
>> Hmm, he only hates "The Cradle Of Civilization Greece", sounds like
>> an Asian/Slav!
>
> You like Grease because you are a no shame having darkie wog like them!

Your shamelessness while performing your Nazi circle jerks together with The
Rectum in public, is astounding, Stupid DoDo! <BG>

--
Our resident psychopath, "The Rectum", addressing his Croatian lover, Stupid
DoDo:
"We're always, greeking each, other in the anus, innit!"
MID: <d4dbp8h9crkcsj9q30nqjo4nujpjm4qgdt@4ax.com>

The Peeler

6/7/2013 12:33:00 PM

0

On Fri, 7 Jun 2013 13:26:04 +0200, The Peeler
<finishingoff@themoronicRevd.invalid> wrote:

>On Thu, 6 Jun 2013 22:18:00 -0500, Stupid DoDo, now posting as Michael
>Baldwin, The Rectum's Croatian whore, wrote:
>
>
>>> Geez, Pig Boy/The Rev'd/Goran Radavich the degenerate Serb nose -
>>> picker, DOD the Croat Nazi says he's not a Jew - baiter like you &
>>> that he likes & admires Jews!
>>>
>>> Hmm, he only hates "The Cradle Of Civilization Greece", sounds like
>>> an Asian/Slav!
>>
>> You like Grease because you are a no shame having darkie wog like them!
>
>Our shamelessness while performing our pro-semitic circle jerks together with NEMO
> in public, is astounding, DoD! <BG>

It, IS Grik anus! Truly innit! <GB>