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

ruby-talk
1

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

I'm going through Chris Pine'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

Attachments:
http://www.ruby-forum.com/attachment/7625/chap10sort_loop.rb

···

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

2

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.clone
sorted = []
while unsorted.length > 0
  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.

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

3

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']))

···

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

4

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
#-----------------------

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

5

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> (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

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

6

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. :wink:

···

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

7

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. :wink:

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. :wink:

···

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

8

@ 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<Integer>();
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. :slight_smile:

···

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

9

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 }

···

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:

--
Lars Haugseth

10

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.

···

--
Posted via http://www.ruby-forum.com/\.

11

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 Pine'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.

···

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

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. :wink:

> 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. :wink:

12

@ 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
...
....
...

echo $?

1

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

···

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

13

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'.

14

Lars Haugseth 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]]

···

--
Posted via http://www.ruby-forum.com/\.

15

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 Pine'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 :smiley:

16

Eliezer,

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