confused, need help with a sorting program

[johny.lam]

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 <
unsorted_array[i+1])
unsorted_array, unsorted_array[i+1] = unsorted_array[i+1],
unsorted_array
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 < 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.

 

[Sebastian Hungerecker]

if (unsorted_array[i+1] != nil) and (unsorted_array <
unsorted_array[i+1])
unsorted_array, unsorted_array[i+1] = unsorted_array[i+1],
unsorted_array
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) 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 < 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

 

[Daniel Lucraft]

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

 

[Daniel Lucraft]

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

 

[Sebastian Hungerecker]

Sebastian Hungerecker wrote:

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?

 

[Daniel Lucraft]

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

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