# Sorting Method

**URL:** <https://www.ruby-forum.com/t/sorting-method/182093>\
**Category:** Ruby\
**Created:** [January 22, 2010, 1:26pm UTC](https://www.ruby-forum.com/t/sorting-method/182093 "2010-01-22T13:26:49Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![timperrett](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/c5a1d2/32.png) [@timperrett](https://www.ruby-forum.com/u/timperrett)\
**Post date:** [January 22, 2010, 1:26pm UTC](https://www.ruby-forum.com/t/sorting-method/182093/1 "2010-01-22T13:26:49Z")

</div>

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!

---

<div class="post-metadata">

**Author:** ![timperrett](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/c5a1d2/32.png) [@timperrett](https://www.ruby-forum.com/u/timperrett)\
**Post date:** [January 22, 2010, 2:13pm UTC](https://www.ruby-forum.com/t/sorting-method/182093/2 "2010-01-22T14:13:39Z")

</div>

2010/1/22 Tim P. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid):

> 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](https://en.wikipedia.org/wiki/Sorting_algorithm)**
>
> In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) that require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output.
> Formally, the output of ...

For general remarks about recursion

> **[Recursion](https://en.wikipedia.org/wiki/Recursion#Recursion_in_computer_science)**
>
> Recursion occurs when the definition of a concept or process depends on a simpler version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics and computer science, where a function being defined is applied within its own definition. While this apparently defines an infinite number of instances (function values), it is often done in such a way that no infinite loop or infinite chain of references

Kind regards

robert

---

<div class="post-metadata">

**Author:** ![timperrett](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/c5a1d2/32.png) [@timperrett](https://www.ruby-forum.com/u/timperrett)\
**Post date:** [January 22, 2010, 2:14pm UTC](https://www.ruby-forum.com/t/sorting-method/182093/3 "2010-01-22T14:14:50Z")

</div>

On Fri, Jan 22, 2010 at 1:25 PM, Tim P. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
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.

---

<div class="post-metadata">

**Author:** ![timperrett](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/c5a1d2/32.png) [@timperrett](https://www.ruby-forum.com/u/timperrett)\
**Post date:** [January 22, 2010, 8:46pm UTC](https://www.ruby-forum.com/t/sorting-method/182093/4 "2010-01-22T20:46:30Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![timperrett](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/c5a1d2/32.png) [@timperrett](https://www.ruby-forum.com/u/timperrett)\
**Post date:** [January 23, 2010, 9:17am UTC](https://www.ruby-forum.com/t/sorting-method/182093/5 "2010-01-23T09:17:20Z")

</div>

Hi,

On Fri, Jan 22, 2010 at 8:45 PM, Tim P. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
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](http://pastie.org/790990)