Sorting Method

Discussion in 'Ruby' started by Tim Pollard, Jan 22, 2010.

  1. Tim Pollard

    Tim Pollard Guest

    Hi there,

    I am working my way through Chris Pine'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!
    Tim Pollard, Jan 22, 2010
    #1
    1. Advertising

  2. 2010/1/22 Tim Pollard <>:
    > Hi there,
    >
    > I am working my way through Chris Pine'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; =A0I think that what I am trying to do should
    > work, it just...doesn't.
    >
    > =A0$input =3D ['']
    > =A0$unsorted_array =3D []
    > =A0$sorted_array =3D []
    >
    > =A0 =A0while not $input.empty?
    > =A0 =A0$input =3D gets.chomp
    > =A0 =A0$unsorted_array.push $input
    > =A0end
    >
    > def recursive_sort
    > =A0 =A0 =A0if $unsorted_array[0] < $unsorted_array[1]
    > =A0 =A0 =A0 =A0$sorted_array.push && $unsorted_array.shift
    > =A0 =A0 =A0else
    > =A0 =A0 =A0 =A0$unsorted_array.push $unsorted_array[1] && $unsorted_array=

    shift
    > =A0 =A0 =A0end
    > =A0 =A0puts $sorted_array
    > end
    >
    > recursive_sort


    There is no recursion since recursive_sort does not call itself.

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


    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; e=
    nd
    =3D> nil
    irb(main):002:0> r_count 5
    5
    4
    3
    2
    1
    0
    =3D> 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:

    http://en.wikipedia.org/wiki/Sorting_algorithm

    For general remarks about recursion

    http://en.wikipedia.org/wiki/Recursion#Recursion_in_computer_science

    Kind regards

    robert

    --=20
    remember.guy do |as, often| as.you_can - without end
    http://blog.rubybestpractices.com/
    Robert Klemme, Jan 22, 2010
    #2
    1. Advertising

  3. On Fri, Jan 22, 2010 at 1:25 PM, Tim Pollard <> 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.
    Jesús Gabriel y Galán, Jan 22, 2010
    #3
  4. Tim Pollard

    Tim Pollard Guest

    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
    Tim Pollard, Jan 22, 2010
    #4
  5. Tim Pollard

    Roger Braun Guest

    Hi,

    On Fri, Jan 22, 2010 at 8:45 PM, Tim Pollard <> 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

    --
    Roger Braun
    http://yononaka.de
    -tuebingen.de
    Roger Braun, Jan 23, 2010
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    2
    Views:
    1,419
    James Kanze
    Jul 6, 2010
  2. Jason
    Replies:
    0
    Views:
    380
    Jason
    Oct 4, 2006
  3. Kyung won Cheon
    Replies:
    0
    Views:
    200
    Kyung won Cheon
    Nov 21, 2008
  4. Tom Kirchner

    sorting by multiple criterias (sub-sorting)

    Tom Kirchner, Oct 11, 2003, in forum: Perl Misc
    Replies:
    3
    Views:
    472
    Michael Budash
    Oct 11, 2003
  5. Íéêüëáïò Êïýñáò

    Sorting a set works, sorting a dictionary fails ?

    Íéêüëáïò Êïýñáò, Jun 10, 2013, in forum: Python
    Replies:
    12
    Views:
    155
    Ulrich Eckhardt
    Jun 10, 2013
Loading...

Share This Page