Forum: Ruby confused, need help with a sorting program

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
A1c25e5f91dd3ec51ac4bf0478ea3e71?d=identicon&s=25 johny.lam (Guest)
on 2007-07-19 10:31
(Received via mailing list)
I was doing the recursive sorting program in Chapter 10 of Chris
Pine's learning to program and i wrote this:

def sort some_array
recursive_sort some_array, []
end

def recursive_sort unsorted_array, sorted_array
  if unsorted_array.length != 0
    0.upto(unsorted_array.length-2) do |i|
      if (unsorted_array[i+1] != nil) and (unsorted_array[i] <
unsorted_array[i+1])
        unsorted_array[i], unsorted_array[i+1] = unsorted_array[i+1],
unsorted_array[i]
      end
    end
    sorted_array.push(unsorted_array.last)
    unsorted_array.pop
    sort(unsorted_array)
  end

  if unsorted_array.length==0
    puts sorted_array
  end
end

word=[]

puts 'Input Words'
while word.last!=''
word.push gets.chomp.downcase
end

sort(word)

---------------------------------------------------------

what i don't get is that this program sorts the words into reverse
alphabetical order.
but if i switch the less than sign in "if (unsorted_array[i+1] != nil)
and (unsorted_array[i] < unsorted_array[i+1])" to a greater than sign
the program works correctly.

what i am trying to is move the smallest word into the sorted_array
but if i use the greater than sign wouldn't the move the biggest word
into the sorted_array?

i'm really new to this, so please pardon my misunderstanding.
7a561ec0875fcbbe3066ea8fe288ec77?d=identicon&s=25 Sebastian Hungerecker (Guest)
on 2007-07-19 11:12
(Received via mailing list)
johny.lam wrote:
> if (unsorted_array[i+1] != nil) and (unsorted_array[i] <
>                                                unsorted_array[i+1])
>   unsorted_array[i], unsorted_array[i+1] = unsorted_array[i+1],
>                                                           unsorted_array[i]
> end
> [...]
> what i don't get is that this program sorts the words into reverse
> alphabetical order.

Ok, let's look at what the above code does: It looks at an item in the
array
(unsorted_array[i]) and at the one after it (unsorted_array[i+1]). Then
it
checks whether the item is less than the next one and if so, it switches
them.
Ultimately this will result in an array in which every element is more
than
the element after it, i.e. an array sorted in descending order.


> but if i switch the less than sign in "if (unsorted_array[i+1] != nil)
> and (unsorted_array[i] < unsorted_array[i+1])" to a greater than sign
> the program works correctly.

Yes, because then it will switch the two items if the current item is
more
than the next one, which will result in an array in which every element
is
less than the next, i.e. an array sorted in ascending order, which is
what
you want.


> what i am trying to is move the smallest word into the sorted_array
> but if i use the greater than sign wouldn't the move the biggest word
> into the sorted_array?

The code doesn't create a new array. It just switches the items in the
array
around untill the array is sorted. Of course the items should only be
switched
if they are not already in the right order. So you check whether the
items are
in the wrong order (i.e. whether the current item is more than the next
one)
and if so, switch the items.


HTH,
Sebastian
0158871402c1ecfa57952e8a379cfd10?d=identicon&s=25 Daniel Lucraft (lucraft)
on 2007-07-19 11:14
johny.lam wrote:
> I was doing the recursive sorting program in Chapter 10 of Chris
> Pine's learning to program and i wrote this:
>
> what i don't get is that this program sorts the words into reverse
> alphabetical order.

> what i am trying to is move the smallest word into the sorted_array
> but if i use the greater than sign wouldn't the move the biggest word
> into the sorted_array?

Yes, that's true. The problem here is that you are not calling the
function recursively with sorted_array. The sorted_array is getting
discarded at each level and replaced with [] each time, since you're
calling 'sort' instead of 'recursive_sort'.

There is a little illusion here, which you will see if you change the
'puts' to a 'p'. You are not actually getting an full array out the end,
it just looks like you are because you are printing the elements one at
a time.

You need to pass the sorted_array down into the next level of
recursive_sort, by
changing

  unsorted_array.pop
  sort(unsorted_array)

to

  unsorted_array.pop
  recursive_sort(unsorted_array, sorted_array)

Now this will print out the sorted array n times, since as each
recursive_sort returns, it will look at the now empty unsorted_array and
then print sorted_array. I'd get rid of

  if unsorted_array.length==0
    p sorted_array   # <-- was 'puts'
  end

altogether and arrange it so that the sort function returns the sorted
array:

  def recursive_sort unsorted_array, sorted_array
    ...
    return sorted_array
  end

  ...

  # call the sort function
  p sort(word)



best,
Dan
0158871402c1ecfa57952e8a379cfd10?d=identicon&s=25 Daniel Lucraft (lucraft)
on 2007-07-19 11:18
Sebastian Hungerecker wrote:
> The code doesn't create a new array. It just switches the items in the
> array
> around untill the array is sorted. Of course the items should only be

Sorry to contradict you Sebastian: the original array isn't sorted, but
cleared out by this code, since he's calling unsorted_array.pop at each
level. It only looks like it ends up sorted because of the puts ["bar"]
at the end of each call.

The '<' is actually the right way round if you going to do it this way
and pop the last (smallest) element of the list each time and push it
onto another array.

best,
Dan
7a561ec0875fcbbe3066ea8fe288ec77?d=identicon&s=25 Sebastian Hungerecker (Guest)
on 2007-07-19 11:33
(Received via mailing list)
Daniel Lucraft wrote:
> Sebastian Hungerecker wrote:

> > The code doesn't create a new array. It just switches the items in the
> > array
> > around untill the array is sorted. Of course the items should only be
>
> Sorry to contradict you Sebastian:

Yeah, seems I didn't read the code carefully enough. I only focussed on
the
part that I quoted.


> the original array isn't sorted, but
> cleared out by this code, since he's calling unsorted_array.pop at each
> level.

But before it pops, it actually does sort the unsorted array in the
0.upto
part, doesn't it?
0158871402c1ecfa57952e8a379cfd10?d=identicon&s=25 Daniel Lucraft (lucraft)
on 2007-07-19 11:40
Sebastian Hungerecker wrote:
> Daniel Lucraft wrote:
>> Sebastian Hungerecker wrote:
> Yeah, seems I didn't read the code carefully enough. I only focussed on
> the
> part that I quoted.

I actually wrote that post twice over :-). I spend too much time here...

>> the original array isn't sorted, but
>> cleared out by this code, since he's calling unsorted_array.pop at each
>> level.
>
> But before it pops, it actually does sort the unsorted array in the
> 0.upto
> part, doesn't it?

Yep. If it wasn't popped but just took the last element (and kept track
of you place), you'd end up with a new array that was sorted correctly,
and the original array would be sorted in place, in reverse.

This is all very verbal. Recursion is one of those things you have to
expend an enormous amount of words to make your meaning understood.

best,
Dan
This topic is locked and can not be replied to.