Sorting Method

[timperrett]

Hi there,

I am working my way through Chris P.'s Learn to Program, and am
currently working on a sorting method (to ask the user for a list of
words and then print them alphabetized.) He suggests that we write
this program twice–once using recursion, and once using loops. I am
currently working on the recursion program, which is the hard part for
me; using loops doesn’t really give me a problem.

I guess the real root of my problem is my inability to understand
methods and parameters. I also don’t really understand the need to
employ a wrapper…something else the book recommends. Obviously the
book’s recommendations have one-up on me, as Mr. Pine is able to write
such a program and I am not.

Here is the code I have right now, please tear it apart if necessary–
I just really want to move forward but am nto willing to look up
somebody else’s method; I think that what I am trying to do should
work, it just…doesn’t.

$input = [’’]
$unsorted_array = []
$sorted_array = []

while not $input.empty?
$input = gets.chomp
$unsorted_array.push $input

end

def recursive_sort
if $unsorted_array[0] < $unsorted_array[1]
$sorted_array.push && $unsorted_array.shift
else
$unsorted_array.push $unsorted_array[1] && $unsorted_array.shift
end
puts $sorted_array
end

recursive_sort

I keep getting a number of errors, and changing things around…I was
getting a stack overflow error for awhile, as well as an EXTREMELY
frustrating “can’t compare string to nil” error on the line comparing
unsorted_array(0) to unsorted_array(1). I don’t even know what I
changed to make it go away–and the frustrating part is that I have no
idea why my array contained a nil value in the first place…and as I
was writing this I realized it must have been the ENTER that was
returned as nil? That’s all I can think of, but now when I run the
program nothing happens at all. No errors, but no data output, either.

I would greatly appreciate any insight somebody could offer on this.
Thanks in advance!

[timperrett]

2010/1/22 Tim P. [email protected]:

methods and parameters. I also don’t really understand the need to
$unsorted_array = []
else
$unsorted_array.push $unsorted_array[1] && $unsorted_array.shift
end
puts $sorted_array
end

recursive_sort

There is no recursion since recursive_sort does not call itself.

I would greatly appreciate any insight somebody could offer on this.
Thanks in advance!

If you have a recursive function (or method for that matter) you need
at least two branches in your function: one that steps into the
recursion and one that does not (terminates the recursion):

irb(main):001:0> def r_count(c) puts c; if c > 0; then r_count(c-1);
end; end
=> nil
irb(main):002:0> r_count 5
5
4
3
2
1
0
=> nil
irb(main):003:0>

Otherwise you will see the stack overflow error that you have seen.

I don’t know which recursive sorting algorithm you want to implement
but you could check here for explanations on some of them:

Sorting algorithm

For general remarks about recursion

Recursion

Kind regards

robert

[timperrett]

On Fri, Jan 22, 2010 at 1:25 PM, Tim P. [email protected]
wrote:

I guess the real root of my problem is my inability to understand
methods and parameters.

Hi,

A method is a “named piece of code” you can invoke from your program.
For example:

irb(main):055:0> def a_method
irb(main):056:1> puts “hi”
irb(main):057:1> end
=> nil
irb(main):058:0> a_method
hi

A method can receive parameters, which are objects bound to local
variables of the method. Inside the method you can use those
variables. For example:

irb(main):059:0> def a_method(message)
irb(main):060:1> puts message
irb(main):061:1> end
=> nil
irb(main):062:0> a_method(“hi, there”)
hi, there

There, the message variable is bound to the string you pass the method
when you call it.

A recursive method is a method that calls itself. You need a way to
stop that, because if not you will end up with an infinite stack of
calls. For example:

irb(main):063:0> def a_method(number)
irb(main):064:1> if number < 1
irb(main):065:2> puts “finished with #{number}”
irb(main):066:2> else
irb(main):067:2* puts number
irb(main):068:2> a_method(number - 1)
irb(main):069:2> end
irb(main):070:1> end
=> nil
irb(main):071:0> a_method(5)
5
4
3
2
1
finished with 0

The “if number < 1” is the end condition. Note that when we call
a_method(number - 1) we are calling the method again, passing a
different parameter. So the first time we call a_method from the
outside, number is 5. Then we print it, and call a_method with 4 as
the parameter, so the method executes again with number being 4, and
so on until we call it with number being 0, which triggers the if
condition, stopping the recursion.

A more complex example would involve using the return value of the
method. For example:

irb(main):072:0> def factorial n
irb(main):073:1> return 1 if (n == 0 || n == 1)
irb(main):074:1> return n * factorial(n-1)
irb(main):075:1> end
=> nil
irb(main):076:0> factorial 5
=> 120

Here the stop condition is when n is 0 or 1, for which the value of
the factorial is 1. For any other value, we multiply the number by the
factorial of the previous number. In order for you to better
understand the call flow, let’s add some print statements:

irb(main):077:0> def factorial n
irb(main):078:1> puts “factorial called with #{n}”
irb(main):079:1> result = 0
irb(main):080:1> if (n == 0 || n == 1)
irb(main):081:2> result = 1
irb(main):082:2> else
irb(main):083:2* result = n * factorial(n-1)
irb(main):084:2> puts “factorial of #{n} is #{result}”
irb(main):085:2> result
irb(main):086:2> end
irb(main):087:1> end
=> nil
irb(main):088:0> factorial 5
factorial called with 5
factorial called with 4
factorial called with 3
factorial called with 2
factorial called with 1
factorial of 2 is 2
factorial of 3 is 6
factorial of 4 is 24
factorial of 5 is 120
=> 120

As you can see, the calls to factorial chain one on top of another
until we reach the stop condition, then the first result is returned
(1) and the next result can be calculated (2*1 = 2), and returned,
then the next and so on.

This doesn’t shed any direct light to your sorting problem, but I hope
it can clear up a little bit recursion and method calls for you.

Jesus.

[timperrett]

Hi again,

Both of you were quite helpful in your explanations, and I think I
understand parameters and recursion a bit better now. I guess the
current hangup for me is trying to make these parameters applicable to
my sorting method. Also, I decided to try not to use global variables,
as I read that they are bad practice…but then I run into the problem
of not being able to call my arrays in my method. Here is the code
again:

def recursive_sort

input = [’’]
unsorted_array = []
sorted_array = []

while not input.empty?
input = gets.chomp
unsorted_array.push input
end
  if unsorted_array[0] < unsorted_array[1]
    sorted_array.push && unsorted_array.shift
  else

unsorted_array.push (unsorted_array[1]) && unsorted_array.shift
end
puts sorted_array
end

recursive_sort

So I guess now my question is twofold: how do I include my initial
array assignments and the input = gets.chomp method without them
looping? I think I am starting to understand how to get the recursive
method as a WHOLE to stop, but I do not want the user to be able to
input more words every time the method calls itself, either. That is
why I was using global variables in the first place, but I suppose
there has to be a way to do it without…

Finally, using parameters to call the method: My initial problem was,
I suppose, that I expected parameters to be neatly defined. Using the
factorial example, method_factorial (n) just didn’t make sense to me
because I thought that n would have to be a static number (rather than
whatever is written after method_factorial). So, I think that sheds
some light on my wrapper question too–by having a wrapper it would
allow me to call the recursive method with only one parameter instead
of two, correct?

I just don’t understand what my program is supposed to do it I
arbitrarily write, say:

recursive_sort 418, 958

The parameters should be the arrays to be sorted, correct? I guess I’m
just not fully wrapping my head around the problem, and this message
is probably confusing, so I apologize. Just trying to understand it
fully. I think it is coming slowly, but I don’t know why I’m having
such a difficult time with this.

Thanks for your initial responses, Robert and
Jesús.
Regards,
Timothy

[timperrett]

Hi,

On Fri, Jan 22, 2010 at 8:45 PM, Tim P. [email protected]
wrote:

So I guess now my question is twofold: how do I include my initial
array assignments and the input = gets.chomp method without them
looping?

Just don’t put the input part into your recursive method. Do the input
first, then sort it.

Finally, using parameters to call the method: My initial problem was,
I suppose, that I expected parameters to be neatly defined. Using the
factorial example, method_factorial (n) just didn’t make sense to me
because I thought that n would have to be a static number (rather than
whatever is written after method_factorial). So, I think that sheds
some light on my wrapper question too–by having a wrapper it would
allow me to call the recursive method with only one parameter instead
of two, correct?

Yes, that’s right.

I just don’t understand what my program is supposed to do it I
arbitrarily write, say:

recursive_sort 418, 958

The recursive sort method is supposed to the same as a regular sort
method: Sort one array.

irb(main):003:0> unsorted = [545,3,23435,2,68,4,4,234]
=> [545, 3, 23435, 2, 68, 4, 4, 234]
irb(main):004:0> recursive_sort(unsorted)
=> [2, 3, 4, 4, 68, 234, 545, 23435]

This is an example of a recursive sort. Both the resursive_sort_helper
and insert_into_sorted are written in a recursive style. What this
means is that both call themselves in their method bodies.

http://pastie.org/790990