From: Marnen Laibow-Koser <marnen@...>
Date: 2009-12-29T10:21:43+09:00
Subject: Re: Creating my own method for sorting an array

Joe User wrote:
> Hi,
> 
> I'm working through the Learning To Program book(2nd edition) and am
> stuck on the sort/recursion exercise (page 93/94). The exercise is to
> roll your own sort method for use on an array.  The suggestions are to
> create an additional two arrays; 1) for the sorted words 2) another
> for the unsorted words, take the list of words, find the smallest, and
> put it on the end of the already-sorted list.  The remaining items go on
> the
> unsorted.  The idea being to recurse through the list of unsorted words
> adding elements to the sorted list until done.
> 

In Ruby, this is frankly stupid.  No Ruby programmer would do this in 
any other way than by using the .sort method, providing a comparator 
block, and letting Ruby take care of the bookkeeping.

With that in mind...

> There are several routes I could take to get closer but I'm trying to
> stay within the constraints of the book.  That means I can use .each,
> .push, .pop, .length, .join, and .last.  Hopefully I'm not leaving
> anything out.  Certainly I could use the .sort method and I could look
> at the answer in the book but the idea is creating my own for the
> experience.  But I'm stuck.  I'm hoping for a nudge in the right
> direction instead of someone telling me outright
> how to do it.
> 
> In English what I think I need to do is take each element of the array
> and compare it to the rest of the elements and if it's the smallest,
> push it onto the sorted list and push the remaining elements onto the
> unsorted.  Then call the method again with the sorted and unsorted
> lists. That's the recursion part.

That would certainly be a way of doing it.  Have you written automated 
tests to encapsulate these requirements?  If not, do so before writing 
another line of code.

> 
> I guess the problem I'm having is knowing how to check each element of
> the unsorted array against the other elements.  I can check if the
> current element is smaller than the other elements using < (less than)
> but that doesn't mean it's the smallest in the whole array.  

Sure it does.  (Of course, this is quite computationally inefficient.)

> So I would
> only want to
> push it onto sorted array if it's smaller than everything else.
> 

You're supposed to write a sort algorithm from scratch *before* they 
tell you about bubble sort and quicksort?  Get real!  That's silly -- 
and you'll never use it in Ruby anyway.

Best,
--
Marnen Laibow-Koser
http://www.marnen.org
marnen@marnen.org
-- 
Posted via http://www.ruby-forum.com/.