# Confused, need help with a sorting program

#1

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.

#2

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

#3

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

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

#4

Daniel L. wrote:

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

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?

#5

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

#6

Sebastian H. wrote:

Daniel L. wrote:

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