Another basic question about sorting w/o the sort method

Hi,

I worked through the exercise in Chris P.'s tutorial where you sort
an array without using the sort method
(http://pine.fm/LearnToProgram/?Chapter=07), and I got a working
solution, but I’m curious about how to improve it. Can anyone offer
some tips? I’ve looked at a couple of solutions here like this one:

def bubblesort(a)
(a.length-1).downto(0) do |i|
puts a.to_s
0.upto(i-1) do |j|
if a[j] > a[j+1]
a[j], a[j+1] = a[j+1], a[j] # swap
end
end
end
end

(from
http://groups.google.com/group/comp.lang.ruby/tree/browse_frm/thread/410b0ac3d37b2c5e/67afd36eba0bd5ec?rnum=1&q=sort+pine+exercise&_done=%2Fgroup%2Fcomp.lang.ruby%2Fbrowse_frm%2Fthread%2F410b0ac3d37b2c5e%2F35a2dc683df509a7%3Flnk%3Dgst%26q%3Dsort+pine+exercise%26rnum%3D2%26#doc_35a2dc683df509a7)

This is pretty much over my head but it looks a lot cooler. I would
like to write this way. What I don’t understand about the above is
this:

            if a[j] > a[j+1]
                a[j], a[j+1] = a[j+1], a[j] # swap

I’m reading this to mean if the jth position in a is lexically greater
than the jth + 1 position, then those two positions switch places, for
example [z, m, p, a] becomes [ m, p, a, z], but then how does ‘a’ get
to the top of the array? And is that formula of a[j], … = … a
simple equation you can use in many different ways or a more specific
method?

I tried to use only what I had learned in the tutorial up to the point
of the exercise, though I admit I flaked and looked up what the delete
method was. Here’s what I wrote:

declare variables and arrays

word = ‘start’
unsortedList = []
sortedList = []
lowercase = []
trues = 0

say hello

puts 'Hello. Type a word, press [ENTER] after every word, [ENTER] when
done: ’

get the input

while word != ‘’
word = gets.chomp
unsortedList.push word
end

downcase the list so we can sort it

unsortedList.each do |i|
lowercase.push i.downcase
end

sort the list

while lowercase.length > 0

lowercase.each do |i|

lowercase.each do |j|

  if (i <= j)
  trues = trues + 1
  end

end

if (trues == lowercase.length)
sortedList.push i
lowercase.delete(i)
trues = 0
else
trues = 0
end

end

end

see the sorted list

puts ‘-’ * 60
puts ‘Your sorted list, dude:’
puts sortedList

done

Needless to say this looks much more clunky to me though it was still a
lot of fun to do. If anyone can help with some of my questions or
comment on my solution that would be awesome,

thanks, George

[email protected] wrote:

        puts a.to_s

to the top of the array?
Because the process is repeated n-1 times. For better explanation I
suggest googling for “bubble sort” and / or to buy a book on data
structures and algorithms. IMHO this belongs on every software
developer’s desk anyway because the topic is so fundamental.

And is that formula of a[j], … = … a
simple equation you can use in many different ways or a more specific
method?

No, it’s the normal assignment operator - if you have multiple values
left and right it’s also called “parallel assignment” IIRC. I do not
know another programming language that has this feature. Basically it
ensures that all right hand sides are evaluated before the assignment
takes place. This allows to swap values like in

a,b=b,a

Kind regards

robert

Thanks Robert, that’s a good explanation. In fact I didn’t realize
bubblesort is a general term and not just a name for the method (?) of
the solution I quoted. Reading about bubblesort and all those other
sorting algorithms referenced via bubblesort has been very
illuminating!

thanks again, George

Robert K. [email protected] wrote:

And is that formula of a[j], … = … a
simple equation you can use in many different ways or a more specific
method?

No, it’s the normal assignment operator - if you have multiple values
left and right it’s also called “parallel assignment” IIRC. I do not
know another programming language that has this feature.

I do. :slight_smile: m.

On 15.10.2006 22:36, [email protected] wrote:

Thanks Robert, that’s a good explanation. In fact I didn’t realize
bubblesort is a general term and not just a name for the method (?) of
the solution I quoted. Reading about bubblesort and all those other
sorting algorithms referenced via bubblesort has been very
illuminating!

You’re welcome. Also, I just realize there is a related discussion in
/.:

http://ask.slashdot.org/article.pl?sid=06/10/05/0435200

Kind regards

robert

Robert K. wrote:

No, it’s the normal assignment operator - if you have multiple values
left and right it’s also called “parallel assignment” IIRC. I do not
know another programming language that has this feature.

FWIW, Lua supports parallel assignment:
Lua 5.1 Copyright © 1994-2006 Lua.org, PUC-Rio

a=1;b=2
a,b=b,a
=a
2
=b
1
numbers = { 1, 2, 3, 4, 5 }
a,b,c = unpack( numbers )
print( a, b, c )
1 2 3

Robert K. wrote:

No, it’s the normal assignment operator - if you have multiple values
left and right it’s also called “parallel assignment” IIRC. I do not
know another programming language that has this feature.

FWIW, Lua supports parallel assignment:

So does Python…

Regards,
Rimantas

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs