Help with exercise from Chris Pine's Ruby Book: Sort without using .sort

aris · July 25, 2012, 2:32am

Hello all, I’m a n00b that’s just getting into programming.

I’m going through Chris P.'s excellent book ‘Learn to Program’. I was
doing pretty good until I hit chapter 10 and ran into an exercise that
asks you to sort an array without using .sort.

It’s meant to use loops and not recursion (that comes later). I’ve been
spending a lot of
time on it and now I’m not quite sure how to get it working. It looks
like it’s in an infinite
loop and I’m not sure why. Can anyone point out what I need to get it
working? Right now I just want to get it working (no matter how ugly)
before I look to
improve.

File attached and pasted below

Thanks

J

word = [‘beta’, ‘zeta’, ‘alpha’, ‘depha’, ‘cina’, ‘emma’, ‘bonny’,
‘falco’]

copy array to new unsorted array

unsorted = word

initialize new sorted array

sorted = []

initialize new unsorted array used in loop

new_unsorted = []

#first loop that ends when unsort is empty
while unsorted.length > 0

#this take the last position in the unsort array pops it off aand points
smallest variable at it.
smallest = unsorted.pop

#nested loop that does actually word comparison and finds smallest word
while creating a new array. It ends when it has cycled through array
unsorted.each do |testword|
if testword < smallest
new_unsorted.push smallest
smallest = testword
else
new_unsorted.push testword
end
end

#Adds smallest word to sort array
sorted.push smallest
#unsorted array now assigned to the new_unsorted which no longer has
smallest word in it before it loops back.
unsorted = new_unsorted
end

#prints out sorted array
puts sorted
puts
#prints out inital unsorted array
puts word
puts
#prints out initial unsorted array with sort method to QA
puts word.sort

sjames · July 25, 2012, 3:14am

Hi,

You have to re-initialize new_unsorted with an empty array for every
iteration. Otherwise it will just keep growing.

It’s also important to note that Ruby’s variables are references. This
means that variable assignment does not copy the value from the right
variable to the left. Instead, it makes both variables point to the same
object.

As an example:
a = [1, 2]
b = a # b points to the same array as a
b.pop # this also affects a
p a

If you want a copy, you have to actually create it:
b = a.dup # or a.clone, which is more strict

#--------------
word = [
‘beta’,
‘zeta’,
‘alpha’,
‘depha’,
‘cina’,
‘emma’,
‘bonny’,
‘falco’
]

unsorted = word.dup
sorted = []
until unsorted.empty?
new_unsorted = []
smallest = unsorted.pop
unsorted.each do |testword|
if testword < smallest
new_unsorted.push smallest
smallest = testword
else
new_unsorted.push testword
end
end
sorted.push smallest
unsorted = new_unsorted
end
#--------------

The rest is OK. Of course this algorithm is neither efficient nor
pretty, but you already said that you just want to get it working.

sjames · July 25, 2012, 8:19am

Hello Jan E.,

Thank you very much for your help and crystal clear explanation. My
misunderstanding of how variables work was the root cause of my
confusion. Based on your advice building the recursive version of the
sort only took me a few minutes. I really appreciate you taking the time
to answer my questions.

James

My recursive sort: (ugly I’m sure)

def sort_wrap arr
sort_meth arr, []

end

def sort_meth unsorted, sorted
if unsorted.length == 0
return sorted
end
new_unsorted = []
smallest = unsorted.pop

unsorted.each do |testword|
if testword < smallest
new_unsorted.push smallest
smallest = testword
else
new_unsorted.push testword
end
end
sorted.push smallest
unsorted = new_unsorted

sort_meth new_unsorted, sorted
end

puts (sort_wrap([‘beta’, ‘zeta’, ‘alpha’, ‘depha’, ‘cina’, ‘emma’,
‘bonny’, ‘falco’]))

sjames · July 25, 2012, 9:01am

Your method is of course correct. But you don’t really use the
recursion, since you basically just replaced the while loop with a
method repeatedly calling itself.

You might want to reduce the problem to a smaller task first. For
example, you could write a method that finds the minimum of an array and
returns both the minimum and the rest of the array. You can then use
this simple method to recursively build a sorted array:

#-----------------------
def find_min array
min, rest =
array.first, []
array.drop(1).each do |element|
if element < min
rest << min
min = element
else
rest << element
end
end
return min, rest
end

def min_sort array
return array if array.empty?
min, rest =
find_min array
[min] + min_sort(rest)
end
#-----------------------

sjames · July 29, 2012, 8:21pm

Lars H. wrote in post #1070091:

You might want to reduce the problem to a smaller task first. For
example, you could write a method that finds the minimum of an array and
returns both the minimum and the rest of the array. You can then use
this simple method to recursively build a sorted array:

Though that might defeat the purpose of the exersize, there already
exists such a method, Array#min.

If using Array#min (or some self-implemented version of min) is
permitted, sorting can be done as simple as:

sorted = unsorted.size.times.map { unsorted.delete unsorted.min }

Ugh… Array#delete is an operation which modifies the source array.
Mixing functional-style with side effects is pretty horrible IMO.

Anyway, that code doesn’t even work properly:

unsorted = [9,7,5,5,3,1]
=> [9, 7, 5, 5, 3, 1]

sorted = unsorted.size.times.map { unsorted.delete unsorted.min }
=> [1, 3, 5, 7, 9, nil]

However, picking one lowest element each time (a “selection sort”) is a
reasonable approach to solve the problem, albeit not an efficient
algorithm in practice.

You might also like to try a “quicksort”-style approach: partition array
into two parts, where all elements of one are lower than all elements of
the other; sort each part recursively; then concatenate the sorted
parts.

unsorted=[9,7,5,5,3,1]
=> [9, 7, 5, 5, 3, 1]

pivot = unsorted[rand unsorted.size]
=> 5

sub1, sub2 = unsorted.partition { |e| e < pivot }
=> [[3, 1], [9, 7, 5, 5]]

sjames · July 30, 2012, 6:18am

I used to program back in the 80s and my method is totally different
from what most people would do now, but I wanted to share how I solved
the problem. There are a lot of easier ways, but this does work.

a little program to accept a list of words, sort them without using

the sort method, and output them in alphabetical order
j = 0
words = []
words2 = []
a_word = ‘a’ # dummy initialization to get into the until loop below
i = 0
puts “Type a word and press (Enter a blank line to quit):”

Loop to accept an unspecified number of words-- creates original array

until a_word.empty?
a_word = gets.chomp
if a_word != “”
words.push a_word
i += 1
end # end if
end # end until

while words.length > 0
i = words.length - 1

I will sort by looking for the lowest value word in the original

array and pushing it on to the new array
a_word = words[0] # initialize with the first element in the array
a_index = 0
for j in 1…i
b_word = words[j] # assign second element to a var
if a_word.upcase > b_word.upcase # compare the two words
a_word = words[j]
a_index = j # variable so I can reference the words pushed onto
the new array
end # end if
end # end for
words2.push a_word # push smallest word onto new array
words.delete_at(a_index) # delete the lowest element in the original
array
i -= words.length
end # end while
puts words2

sjames · July 25, 2012, 9:10am

On 07/25/2012 09:01 AM, Jan E. wrote:

Your method is of course correct. But you don’t really use the
recursion, since you basically just replaced the while loop with a
method repeatedly calling itself.

You might want to reduce the problem to a smaller task first. For
example, you could write a method that finds the minimum of an array and
returns both the minimum and the rest of the array. You can then use
this simple method to recursively build a sorted array:

Though that might defeat the purpose of the exersize, there already
exists such a method, Array#min.

If using Array#min (or some self-implemented version of min) is
permitted, sorting can be done as simple as:

sorted = unsorted.size.times.map { unsorted.delete unsorted.min }

sjames · July 30, 2012, 10:49am

Hi,

Using a dummy object as a workaround and keeping it throughout the whole
program is also not that pretty.

Why not initialize the word with gets.chomp? This also allows you to get
rid of the somewhat redundant “if word == ‘’”:

word = gets.chomp
until word.empty?
words.push word
word = gets.chomp
end

And of course there are also one-liners for this.

What I also would like to note: These low level sorting algorithms are
certainly interesting and teach you a lot about general programming, but
they have very little to do with “the Ruby way” of doing things.

I mean, with all that “for” and “while” loops and counters, the code
looks almost like good old BASIC. Ruby generally tries to avoid this low
level stuff in favor of a more abstract, more “intelligent” approach
(which is hardly possible in this case).

Just so that you know that Ruby is not just some kind of prettified
BASIC.

sjames · July 31, 2012, 4:56pm

On 7/30/2012 1:49 AM, Jan E. wrote:

words.push word
looks almost like good old BASIC. Ruby generally tries to avoid this low
level stuff in favor of a more abstract, more “intelligent” approach
(which is hardly possible in this case).

Just so that you know that Ruby is not just some kind of prettified
BASIC.

Hi,

Using a dummy object as a workaround and keeping it throughout the
whole
program is also not that pretty.

Why not initialize the word with gets.chomp? This also allows you to
get
rid of the somewhat redundant “if word == ‘’”:

word = gets.chomp
until word.empty?
words.push word
word = gets.chomp
end

And of course there are also one-liners for this.

What I also would like to note: These low level sorting algorithms
are
certainly interesting and teach you a lot about general programming,
but
they have very little to do with “the Ruby way” of doing things.

I mean, with all that “for” and “while” loops and counters, the code
looks almost like good old BASIC. Ruby generally tries to avoid this
low
level stuff in favor of a more abstract, more “intelligent” approach
(which is hardly possible in this case).

Just so that you know that Ruby is not just some kind of prettified
BASIC.

I have been pondering why you posted any response at all to my
‘solution.’ I did preface it by saying I had been a pogrammer in the
80s. At that point in Chris P.'s tutorial next to nothing has been
covered about object oriented programming or ‘the Ruby way.’ Your post
was not helpful, and mostly denigrating. Just saying. Learning the Ruby
way is the reason for doing these little tutorials.

The purpose of my response was to show a solution that worked, but maybe
I was wrong to even think I could participate in this forum since I
don’t quite understand ‘The Ruby Way’ yet.

sjames · July 31, 2012, 6:11pm

I have been pondering why you posted any response at all to my
‘solution.’ I did preface it by saying I had been a pogrammer in the
80s. At that point in Chris P.'s tutorial next to nothing has been
covered about object oriented programming or ‘the Ruby way.’ Your post
was not helpful, and mostly denigrating. Just saying. Learning the Ruby
way is the reason for doing these little tutorials.

The purpose of my response was to show a solution that worked, but maybe
I was wrong to even think I could participate in this forum since I
don’t quite understand ‘The Ruby Way’ yet.

nonsense!!
Ruby or not the point was to get it done.
ruby does give you another way\level to work stuff out but it depends on
the program\er goals.

it reminds me a thing i head about python “The Zen of Python”.
I have heard a podcast explaining each one of these zen of python and
the reason for each one of them from a guy that worked with Tim Peters
that wrote “The Zen of Python”.

it was indeed nice to hear a sentence like:
“Beautiful is better than ugly”

And these guys compared “Beautiful Lady” to “Ugly Lady” and that most of
the time the Beautiful one will cheat on you while the ugly be loyal…

this is really nice to say when you do hold all the cards in the palm of
your hands.
you can get and hold the Beautiful one or to choose the other one.

I think it’s a naive way to look at life and into programming.

the only way for code to be “Beautiful” is that there is someone over
there that can understand why you define Object Oriented as Beautiful.

there is no “Ruby” or “java” or “assembly” way of doing things!!

the real sentence to describe “the ruby way” or “the java way” is that
the programmer knows: the goals the interface and the pure
implementation.

after you do know these you can sort the conflict between the interface
and the actual implementation.

if you will take a bunch of cobol programmers and will give them ruby
interface you will see that most of their approach will be similar to
“the coobol interface”.
same goes with c assembly and all the others.

if you have background you will have habits like any spoken language.
this is how the human brain mostly works.

So please this nice guy that has “the ruby way…” did you heard about
web servers? p2p networks?podcasts?

I will be more then happy to hear about this “ruby way” (really not
joking)
and no i dont want to read a bunch of books codes and blogs.
I just want to hear 1 hour of this nice guy that invented Ruby to talk
about “the ruby way” of doing things.

Thanks

sjames · July 30, 2012, 9:47am

Deborah Wyatt wrote in post #1070650:

I used to program back in the 80s and my method is totally different
from what most people would do now, but I wanted to share how I solved
the problem. There are a lot of easier ways, but this does work.

Yes, this is a perfectly good selection sort. I’d just make a couple of
comments:

(1) In the first loop, you assign to the variable ‘i’, but never use the
value; later you re-assign to ‘i’ in the second loop. Similarly, at the
end of the second loop you decrement ‘i’, but never use that value. The
initial assignment ‘j = 0’ is also superfluous. So you may as well just
delete all those lines.

(2) You could use more descriptive variable names than “words2”, “i”,
“j” to make your code easier to understand

(3) As you progress, you’ll find neat little tricks in ruby to simplify
the code, e.g. you only need to keep a_index because you can use the
return value of delete_at:

words2.push words.delete_at(a_index)

Regards,

Brian.

sjames · July 31, 2012, 7:48pm

@ Eliezer:

Yeah, I love those people who “just want to get things done” and
think that their GOTO spaghetti code is perfectly fine because “it
works”.

Sure, every language more or less “works”, but don’t tell me there is no
difference between 500 lines of Java code and 100 lines of Ruby code
doing the same thing.

Don’t tell me that

“public static final void foo bar ohLordSaveMeFromVerbosity(String
myArg, int myOtherArg)”

is just the same as

“def my_method my_arg, my_other_arg”

Don’t tell me that

“(1…100).select &:odd?”

isn’t any more clear or concise than

"
ArrayList myArrayList = new ArrayList();
for (int i = …; i <= 100; … i++)
if (i % 2 …)
yadda yadda yadda
"

When you’ve spotted the difference, then we might actually discuss how
different languages encourage different programming styles (though I’m
probably the least qualified person to talk about that).

Of course, there isn’t some kind of “style bible” saying exactly what
“The Ruby way” is. But like any other language, Ruby encourages some
pracices (like object oriented and functional programming) and
discourages others (like low level spaghetti code).

If that’s all academical nonsense to you and you “just want to get
things done”, then simply stick to your FORTRAN and be happy.

sjames · July 31, 2012, 10:18pm

On 7/31/2012 8:48 PM, Jan E. wrote:

@ Eliezer:
#forgot to mention before starting so here it is:
class Eliezer < Jan_E
def initialize
super
end
end

#and the program itself of course…

bible = Eliezer.new()

bible.eql? crap
=> nil
…
…
…

bash> echo $?
1

bash> java Eliezer
sorry undesirable Exception got caught
##end

I dont have experience with FORTRAN yet and I dont think I will use it
in the next what so ever decade.(but still I surprised myself a lot of
times)

Please refrain from using the F word!!
you do know that signaling with Letters such as P in-front of kids will
lead them to search about it in the internet and understand their
mistakes!?

anybody can talk about anything as I see it.

awhile back I had some nice conversation with a nice academic guy on
almost the same subject.
it seems like his teacher\professor as he understood had a “formula” of
“the way things should be learned and will be taught” in programming and
computer science.

He indeed was a nice guy but very hard to listen and understand that
there are different methods to do the same exact thing.
Eventually I wasn’t kicked out of whatever we did that time.

of-course as you understood he was very exception nice guy.

One small problem is that unfortunately when you do work with low level
network protocols I found myself a bit lost and on verge of inventing
the wheel just to fulfill a small task.

As I posted earlier I am still looking for a mentor that knows this
academic world you was talking about to learn from.
the main problem is that many if !most || !all of these nice
professors\teachers would like to make a living and there for wont have
too much for me.

Just to make it more clear:
Wanted someone that can make sense of most of programming and CS to me
in a human language and using metric < 4 .

Regards,
Eliezer

sjames · August 1, 2012, 12:25am

Jan, I’m not thinned skinned at all. All I was doing was demonstrating
the way I did it with my old style programming skills. Your response
came across as arrogant and superior rather than helpful. I do not
think I am the only person here who saw it that way. Just sayin’.

sjames · July 31, 2012, 6:34pm

@ Deborah:

Why so thin-skinned? I was just writing down some suggestions and
general comments on how Ruby differs from other languages.

I didn’t say “That’s wrong” or “You should have done better”. Because
that would obivously be stupid. Of course your code works, and of course
you cannot know everything about “The Ruby way” when you have just
started.

Yet still I saw no problem with writing down some improvement
suggestions. I thought that’s what a forum is for.

Apart from that: If you actually don’t want your code to be critized,
then it might be a good idea to not even post it. Because Ruby
programmers tend not to stop when “it works” but always try to improve
things.

sjames · August 1, 2012, 12:37am

Eliezer,

If you are looking for help with this stuff go to rubylearning.org
channel on freenode IRC. Victor G. is a great person to get help
from.