28 Jan 2014, 18:42
Generic-user-small

Evan Payne (2 posts)

So this is definitely feeling like a rite of passage, because I am stuck! I looked at the answer in the back of the book and everything in the code makes COMPLETE sense, except for the very end (the actual recursion). I will copy the entire code for context:

  `def sort arr`
  
    `rec_sort arr, []`

  `end`

 `def rec_sort unsorted, sorted`

    `if unsorted.length <=0`

      `return sorted`

 `end`

  `smallest = unsorted.pop`

  `still_unsorted = []`
  
  `unsorted.each do |x|`

  `if x < smallest`

    `still_unsorted.push smallest`

    `smallest = x`

  `else`

    `still_unsorted.push x`

  `end`

`end`
  
`sorted.push smallest`

`rec_sort still_unsorted, sorted #I do not understand this` 

end

puts (sort(['can', 'feel', 'singing', 'like', 'a', 'can']))

I understand that the method is calling itself, but with the first argument replaced with “still_unsorted”. However, it seems like this would pose a problem once the method is run with this new argument. For example, after the initial “if” statement, it would now look like this:

`smallest        = still_unsorted.pop`

`still_unsorted   = []`

`still_unsorted.each do |x|`

  `if x < smallest`

    `still_unsorted.push smallest` 

    `smallest = x`

  `else`

    `still_unsorted.push x`

  `end`

`end`

`sorted.push smallest`

`rec_sort still_unsorted, sorted`

Is this how the code reads after the method calls itself? It seems like it wouldn’t work. I just wanted to make sure I’m not missing some key concept here.

Thanks for any help, suggestions!

29 Jan 2014, 17:12
Med__2008.08.19.09.44.43_pragsmall

Chris Pine (58 posts)

No, but I think I see where your confusion is coming from.

Variables are just labels. And labels can be swapped around. When you call rec_sort from within rec_sort, you basically get a new copy of rec_sort, with new labels (new local variables).

So it’s kind of like the first call to rec_sort had variables unsorted_0 and still_unsorted_0. Then, when it calls itself, there’s a new rec_sort with unsorted_1 and still_unsorted_1. In that case, your code would look more like this:

smallest = still_unsorted_0.pop
still_unsorted_1 = []

still_unsorted_0.each do |x|
  if x < smallest
    still_unsorted_1.push smallest
    smallest = x
  else
    still_unsorted_1.push x
  end
end
  
sorted.push smallest

rec_sort still_unsorted_1, sorted

That last call creates yet another copy of rec_sort, along with still_unsorted_2, etc.

Each time you call rec_sort, you get new labels for unsorted and sorted. They point to whatever you passed in to that call.

Does that help at all?

29 Jan 2014, 18:32
Generic-user-small

Evan Payne (2 posts)

Yes, it does. Thank you so much for your help!

Really glad I bought the book with such a helpful author!

28 Feb 2014, 19:59
Generic-user-small

Peter Sivilay (2 posts)

Longtime lurker here. If I may piggyback on this topic rather than opening a new one, I’m struggling in reading the flow of the code, and the ending as well when I try to work it out by inputting the values myself. Particularly, do I replace every unsorted parameter with still_unsorted after calling rec_sort with the still_unsorted parameter? That’s a little confusing with the reassigning…

So on the first run for puts sort [‘d’, ‘b’, ‘c’, ‘a’] it would be read at the end as rec_sort [‘d’, ‘b’, ‘c’] , [‘a’]?

Then rec_sort is called again and it should read as rec_sort [‘d’, ‘c’], [‘a’, ‘b’]?

Then again rec_sort [‘d’], [‘a’, ‘b’, ‘c’]

Then we go again and ‘d’ is smallest and is popped and is it at this point where the first if block of code with <= 0 runs and doesn’t try to call each again?

Or do we play it out since ‘d’ hasn’t made it into the sorted array yet? And so ‘d’ < ‘d’ is false, pushes ‘d’ into still_unsorted and pushes ‘d’ (smallest) into sorted and we are done?

But isn’t there still ‘d’ in still_unsorted and so if unsorted was changed to still_unsorted, then still_unsorted <= 0 within the first if block of code is still false and cannot end the program with that remaining ‘d’?

Or is that if block and the unsorted.length within it untouched and unchanged, even after we’ve changed to still_unsorted? So while still_unsorted has the ‘d’ still, unsorted is empty, even though we changed it to still_unsorted?

Apologies! You can see how my brain easily screws it up the ending what with all that reassigning going on.

06 Mar 2014, 15:39
Med__2008.08.19.09.44.43_pragsmall

Chris Pine (58 posts)

It does the check before the pop, so it goes through the function for 'd' also. The last call to rec_sort would be like this:

rec_sort [], ['a', 'b', 'c', 'd']

Then it does the check and exits right away.

As for the time when it does 'd', by the time it gets to the each, that the 'd' has already been popped, so the array is empty. (They are never compared to themselves unless there are more than one of them in the array.) each called on an empty array doesn’t do anything (because there are no elements to process). So it pushes 'd'.

Make sense?

21 Mar 2014, 15:30
Generic-user-small

Peter Sivilay (2 posts)

Ah yes it does. It is probably over thinking on my part. Thanks for the succinct response Mr. Pine!

13 Apr 2014, 15:40
Generic-user-small

James Allen (2 posts)

I was very proud of my clunky, mechanical original version of sort, the non-recursive one.. actually this is the dictionary sort which differs from the original only with the addition of .downcase.

But when I tried the book’s suggested recursive solution my program continually crashes with syntax errors. concerned I can’t type properly, I paste it, nothing changes. what am I missing?

raw = [‘tender’,’batter’, ‘Batter’, ‘apple’, ‘orange’,’example’, ‘wtf’,’wrench’,’ass’,’San Francisco’,’Achilles’]

def sorter list puts base = 0 # takes the ‘base’ word as a comparison and then compares it to each successive object in the array and swaps the positions of the ‘lower’ word. while base < list.length compare = base +1 while compare < list.length if list [base].downcase > list [compare].downcase original = list [base] new = list [compare] list [base] = new list [compare] = original end compare = compare + 1 end base = base + 1 end return list end puts sorter(raw)

15 Apr 2014, 00:16
Med__2008.08.19.09.44.43_pragsmall

Chris Pine (58 posts)

Really hard to tell from here, as the formatting in your message is all messed up. It could be any number of unexpected characters (curly-single-quote instead of straight-single-quote, some weird unicode whitespace instead of regular spaces, etc).

21 Apr 2014, 08:23
Generic-user-small

James Allen (2 posts)

Thanks for the response. The problem is some intractable unicode issue. Don’t know if it’s a function of using so much Japanese text. But I understand your solution to the task.

Thanks!

  You must be logged in to comment