Sorting arrays

I’m having some major comprehension problems in figuring out this
problem.
In the event that this is not appropriate for the list, my apologies
and feel free to flame me. I’m just so stuck right now. I have
checked the wikipedia algorithm page and even used the insertion sort
but it doesn’t fit my case.

So I start by collecting a group of words which get put into the list[]
array.
The task is to compare the words in list[] using < operator. The ones
that are true go into the “sorted array”, the ones that fail go into
the “unsorted array”.

The next step is to use the same operation but between the sorted and
unsorted arrays, till all is sorted in (yep) the sorted array. I’ve
been every which way and Sunday on this but so far have had little
luck and plenty of strange results.

My latest incarnation is this and it’s only the first iteration (list
to either sorted or unsorted. I’m already aware that it makes no sense
but I don’t have everything already tried nor would that make sense
either. I’m kind of stuck using each do for loops and pop push for
moving elements.

s_words.push(que_words[0]) #i do this to get at least one word into
the sorted array
que_words.each do |x|
s_words.each do |y|
if x < y
s_words.push(x)
end
end
end

        que_words.each do |s|
          s_words.each do |t|
            if s == t
              u_words.push(s)
end

end
end

Stuart

On Jun 28, 2006, at 23:59, Dark A. wrote:

So I start by collecting a group of words which get put into the
list[] array.
The task is to compare the words in list[] using < operator. The ones
that are true go into the “sorted array”, the ones that fail go into
the “unsorted array”.

Compare a word to which other word? Their neighbours? The first
element in list? Random other words? Are you certain you know
exactly what has to be done? You won’t be able to program it if you
can’t describe it. Maybe posting the actual text of the assignment?
Out of curiosity, is this for some sort of coursework? Or do you
just like setting yourself obscure problems?

The next step is to use the same operation but between the sorted and
unsorted arrays, till all is sorted in (yep) the sorted array. I’ve
been every which way and Sunday on this but so far have had little
luck and plenty of strange results.

Trying to peer through the confusion over what you’re actually trying
to do, it really, really does sound like insertion sort, simply with
separate arrays for the sorted and unsorted portions of the input
(possibly to keep people from just grabbing a simple answer from the
web?)

Looking at your code, one thing stands out: if you push onto the
sorted array simply when x < y for some y in the middle of the sorted
array, the sorted array will no longer be sorted (unless y happens to
be the last element of the sorted array or equal to it). You
definitely want some sort of insertion there rather than a push. The
push there will end up simply appending the unsorted array to the
sorted one, since it always adds the unsorted word to the end of the
array.

I’ll give you a hint that might help your experimentation: at no
point should your sorted array ever be unsorted. If you code this
test right in, you’ll at least know when you’re on the wrong track.

class Array
def sorted?
self == self.sort
end
end

Using that, you can do a check to see if the array is still in sorted
order when you change it. If it’s ever not in sorted order, you’ve
messed up. Example:

add x to the array, but not with push, right?

unless sorted.sorted?
puts “sorted array in unsorted order after adding #{x}!”
puts sorted
exit
end

matthew smillie.

On Jun 28, 2006, at 5:59 PM, Dark A. wrote:

I’m having some major comprehension problems in figuring out this
problem.
In the event that this is not appropriate for the list, my apologies
and feel free to flame me. I’m just so stuck right now.

You’ve come to the right place and we are happy to help. Welcome.

The next step is to use the same operation but between the sorted and
unsorted arrays, till all is sorted in (yep) the sorted array. I’ve
been every which way and Sunday on this but so far have had little
luck and plenty of strange results.

My wife came to me for help last night for this exact problem in the
Learn to Program book. :wink: Here’s two pieces of advice we talked about:

  1. Feel free to skip chapter 10 altogether. I consider recursion to
    be a fairly advanced topic, so it’s awful strange for it to pop up
    here in a book for those who have never programmed before. I’m
    pretty sure he’s just trying to give you more practice with methods
    and build your confidence, but that only works if you are
    successful. :wink: You can safely come back to this chapter when you
    know more and are better prepared for the challenge.
  2. If you want to press on, see if this description of the problem
    makes a little more sense: One way to sort an Array is to constantly
    move the lowest element out of it, and into a result Array. If you
    do this for all elements in the Array, you sort it. For example:

Unsorted: [1, 3, 2]
Sorted: [ ]

The lowest element here is 1, so we need to shift it to the other Array.

Unsorted: [3, 2]
Sorted: [1]

Now the lowest element is 2. We again move it to the end of the
other Array.

Unsorted: [3]
Sorted: [1, 2]

There’s only one number left, so it must be the lowest. Let’s move
it and we are done.

Unsorted: [ ]
Sorted: [1, 2, 3]

Hope that helps.

James Edward G. II

##################################

WARNING: Spoilers follow!

##################################

On Jun 29, 2006, at 4:09 PM, Dark A. wrote:

implement the sort.
We’re going to know better ways because we know more of the
language. Don’t doubt what you have learned though! Chris is
carefully feeding you the key tools and they can be used to do just
about anything, with enough effort.

Here’s a solution I’m pretty sure only uses what you have learned up
to chapter 10:

#!/usr/local/bin/ruby -w

def sort(array)
recursive_sort(array, [])
end

def recursive_sort(unsorted, sorted)

find the lowest element

lowest = nil
unsorted.each do |item|
if lowest == nil || item < lowest
lowest = item
end
end

add it to our sorted list

sorted.push(lowest)

make a new unsorted list, minus the low guy

new_unsorted = [ ]
added = false
unsorted.each do |item|
if added == false and item == lowest
added = true
else
new_unsorted.push(item)
end
end

return sorted list if we are done, or recurse to keep sorting

if new_unsorted.size == 0
sorted
else
recursive_sort(new_unsorted, sorted)
end
end

list = [‘zeta’, ‘beta’, ‘alpha’, ‘beta’]
puts sort(list)

END

Hope that helps.

James Edward G. II

On 6/29/06, James Edward G. II [email protected] wrote:

On Jun 28, 2006, at 5:59 PM, Dark A. wrote:

You’ve come to the right place and we are happy to help. Welcome.

Thank you , that’s very kind!

My wife came to me for help last night for this exact problem in the
Learn to Program book. :wink: Here’s two pieces of advice we talked about:

I feel much better hearing of Dana’s experience.

  1. Feel free to skip chapter 10 altogether. I consider recursion to
    be a fairly advanced topic, so it’s awful strange for it to pop up
    here in a book for those who have never programmed before. I’m
    pretty sure he’s just trying to give you more practice with methods
    and build your confidence, but that only works if you are
    successful. :wink: You can safely come back to this chapter when you
    know more and are better prepared for the challenge.

The “sort” project is divided, one is just the sort and Chris
recommends doing a second version using recursion. His explanation of
recursion was digestable but perhaps for a beginner not as easy to
implement. Challenges are okay.

  1. If you want to press on, see if this description of the problem
    makes a little more sense: One way to sort an Array is to constantly
    move the lowest element out of it, and into a result Array. If you
    do this for all elements in the Array, you sort it. For example:

My biggest problem was that in my mind one had to solve the problem
using the tools covered in the book. Judging from the other examples
others here were kind to offer up, I don’t feel that there was enough
in the previous chapters to arm , at least myself, with the tools to
implement the sort. I was very much locked into the notion for some
time to figure it out based on what I already knew. Having re-read
chapters and examples, and read through the array class in the
reference docs I was still struggling to find the right way.
While something like “Insertion sort” was pretty clear to understand
once I saw it, most of why I understood it didn’t come from the book
but from using PHP in the past.

Stuart

On 6/29/06, James Edward G. II [email protected] wrote:

#!/usr/local/bin/ruby -w

def sort(array)
recursive_sort(array, [])
end

def recursive_sort(unsorted, sorted)

find the lowest element

lowest = nil
unsorted.each do |item|

This line (following) is the one that hung me.

 if lowest == nil || item < lowest

After many iterations of various attempts, embarassingly I picked the
worst and most incomplete to post. I get it now somewhat, though the
‘aha!’ moment is still not hitting. I’ll attempt to analyze. Your
looking for the item that is smaller (or less then) then nil. How can
any of the items be smaller then nil ? I know I’m missing something
here, but my thoughts were locked into comparing item < item, This is
why one of the attempts made went like this :

unsorted.each do |x|
unsorted.reverse_each do |y|
if x < y

   lowest = item
 end

end

Yep, I’m good at push.

add it to our sorted list

sorted.push(lowest)

This was explained previously to me

make a new unsorted list, minus the low guy

new_unsorted = [ ]
added = false
unsorted.each do |item|

item == lowest meaning that there was already something assigned to
lowest ?

else

James Edward G. II

It helps yes, thank you very much. Wish I would have came up with it
myself. I’ll need to find a tougher sort to attempt at some point.
Meanwhile Chris is not letting up and with 4 more chapters to go I
have my work cut out for me.

Stuart

2006/6/30, Dark A. [email protected]:

lowest = nil
any of the items be smaller then nil ? I know I’m missing something
here, but my thoughts were locked into comparing item < item,

No, precedence is first == and < then ||. So this code checks whether
either lowest hasn’t been set to something meaningful (i.e. not nil)
or the current item is smaller than the current min.

Never compare a boolean with a boolean to get a boolean value. Use
boolean logic:

if !added and item == lowest

 if added == false and item == lowest

Comparing with false and true is especially problematic in Ruby
because there are multiple values which are interpreted as “true” and
“false”. Especially these will break

x=1
if x == true
x=nil
if x == false

Kind regards

robert

On Jun 29, 2006, at 6:53 PM, Dark A. wrote:

any of the items be smaller then nil ?
Nope we’re not comparing anything with nil. This code handles the
very first comparison, where we always want to take the item, because
it’s the only thing we’ve seen and therefore must be the lowest. To
handle that, I initialize lowest to nil and then replace lowest if
it’s still nil (first item check), or the new item is lower (all
other checks).

 else
   new_unsorted.push(item)
 end

end

Yes, the code earlier ensures that we have the lowest item. Now I’m
just copying the list and skipping the first occurrence of that item,
since we moved it to the other list.

It helps yes, thank you very much. Wish I would have came up with it
myself.

You will improve. It comes with practice, I promise. Keep at it.
We all started where you did!

James Edward G. II

I have a question on the code below that James shared with me. While
he might be best to answer if anyone has an idea please feel free to
reply.

I’m looking in particular , def recursive_sort. The list is first
passed into def sort which immediately puts it into the
recursive_sort. The two parameters are unsorted (which I understand)
and the [] which I don’t understand. I think maybe this is taking
the first element of the unsorted array and putting it into sorted.
Is that correct ? TIA
Stuart

On 7/8/06, Matthew S. [email protected] wrote:

the first element of the unsorted array and putting it into sorted.
(‘array’) and an empty array (that’s what [] means). An empty array
The key thing to note here is that these two arrays are exactly the
sort of thing you could pass into recursive_sort: an unsorted array,
and a sorted array.

Are you saying to use these two types of arrays it must be done with a
recursive method ?

lowest, and so on, and that ensure that the sorted array is always in
3. – [‘zeta’] – [‘alpha’, ‘beta’, ‘beta’]
sorted: [‘alpha’, ‘beta’, ‘beta’, ‘zeta’]
something like this:

And you end up with the sorted array.

Hope that helps a bit,
matthew smillie.

You explained it with great detail so I hope over time it starts to sink
in. Much obliged!
Stuart

On Jul 8, 2006, at 22:41, Dark A. wrote:

Stuart
[James’ code below]

First, the formal to the recursive_sort method are an unsorted array
(named ‘unsorted’), and an array that’s in sorted order (named
‘sorted’).

The call in sort uses actual parameters of the array being sorted
(‘array’) and an empty array (that’s what [] means). An empty array
is in sorted order by definition.

So, starting off with an empty sorted array, recursive_sort finds the
lowest element (not the first element) in the unsorted array, adds
it to the sorted array, and removes it from the unsorted array.

At this point, the method has a sorted array with one element, and an
unsorted array where every element is >= everything in the sorted
array (since we took out the lowest element).

The key thing to note here is that these two arrays are exactly the
sort of thing you could pass into recursive_sort: an unsorted array,
and a sorted array.

So that’s exactly what we do, pass those two arrays as the parameters
to another call of recursive_sort. The next call has one small
wrinkle, are we sure that when we move the lowest element from the
unsorted array to the sorted array, that the sorted array is still
sorted?

The answer’s yes, because in the first call, we moved the lowest
element. In the second call, we’re moving the next-lowest element,
and we’re using ‘push’ to put it on the end of the list. So, we’re
going to pushing the lowest, then the next-lowest, then the next-next-
lowest, and so on, and that ensure that the sorted array is always in
sorted order. This is basically the same strategy you used before in
your loop, just done using recursion.

Here’s a walk-through of the array values for each call for James’
example:

-- unsorted array -- sorted array
  1. – [‘zeta’, ‘beta’, ‘alpha’, ‘beta’] – []
  2. – [‘zeta’, ‘beta’, ‘beta’] – [‘alpha’]
  3. – [‘zeta’, ‘beta’] – [‘alpha’, ‘beta’]
  4. – [‘zeta’] – [‘alpha’, ‘beta’, ‘beta’]

0 is the parameters from the first call to #recursive_sort made from
#sort. 1 is the parameters to the next call of recursive_sort (which
is made inside the first call). 2 is the parameters to the next call
of recursive_sort, and so on.

When you get to 3, though, things are a little different. The method
finds the lowest element in the sorted array (‘zeta’ at this point),
does the push, and creates a new unsorted list, they’ll look like this:
new_unsorted: []
sorted: [‘alpha’, ‘beta’, ‘beta’, ‘zeta’]
If you look at the if statemetn at the bottom of the method, you’ll
see that rather than making another call to recursive_sort, when the
new_unsorted list is empty the method returns the sorted array.

Note that this is the first value returned in any of the calls so far!

It’s important to remember when you’re debugging recursive methods
that they generally consist of a large chain of method calls until
some termination condition is met, followed by a large chain of
returns. In this case, the calls and returns are structured
something like this:

call #0 asks for the result of call #1
call #1 asks for the result of call #2
call #2 asks for the result of call #3

call #3 returns a result: the sorted array

call #2 returns the result of call #3
call #1 returns the result of call #2
call #0 returns the result of call #1

And you end up with the sorted array.

Hope that helps a bit,
matthew smillie.

On 7/8/06, Matthew S. [email protected] wrote:

So, starting off with an empty sorted array, recursive_sort finds the
lowest element (not the first element) in the unsorted array, adds
it to the sorted array, and removes it from the unsorted array.

I’m trying to take this in one step at a time. Only I can’t grasp, the
mechanics of the first step. In theory I follow what’s supposed to be
going
on but that’s not helping my understanding. I re-created the first step
slightly and dropped the recursion.

def sort(list)
sorted = []
unsorted = []

lowest = nil
list.each do |item|
if lowest == nil || item < lowest
lowest = item
end
end

sorted.push(lowest)
puts sorted

end
mylist = [‘five’, ‘three’, ‘one’, ‘ten’, ‘eight’]
sort mylist

Amazingly :), ‘eight’ is pushed into the first element of the sorted
array.
When I asked some posts back through about the elements being compared
to
nil I was told that wasn’t the case. However, lowest is being set to
nil.
Then the statement lowest is equal to nil, or item smaller then lowest
(or
nil). I believe nil has a value, which is 0 or false. However how can
any
item be smaller then it. Bottom line is I’m not seeing the magic here
in
the comparison to find the correct element.
My apologies for my density with this code.

Stuart

Hi –

On Sun, 9 Jul 2006, Dark A. wrote:

slightly and dropped the recursion.
end
nil I was told that wasn’t the case. However, lowest is being set to nil.
Then the statement lowest is equal to nil, or item smaller then lowest (or
nil). I believe nil has a value, which is 0 or false. However how can any
item be smaller then it. Bottom line is I’m not seeing the magic here in
the comparison to find the correct element.
My apologies for my density with this code.

I haven’t been following this thread but let me try to explain.

nil’s value is nil. nil is an object. It has a Boolean value of
false, but it is, itself, just the object nil.

There’s no issue of nil being smaller or larger than anything. The
first time through your loop, lowest is nil – which means that the
item < lowest comparison is never evaluated. The next time through,
lowest is “five”, so item < lowest is evaluated. It’s false, so the
next statement (lowest = item) is not executed.

And so forth, with the rest of the comparisons: five/three, five/one,
five/ten, five/eight. On the last one, the comparison item < lowest
is true. So lowest = item gets executed, and lowest is now “eight”.

Then you push lowest (i.e., “eight”) onto the empty array sorted.
Therefore, sorted now looks like this:

[“eight”]

Then you print it out.

That’s about it :slight_smile:

David

On 7/9/06, [email protected] [email protected] wrote:

There’s no issue of nil being smaller or larger than anything. The
first time through your loop, lowest is nil – which means that the
item < lowest comparison is never evaluated.

Okay, I sort of see that.

The next time through,

lowest is “five”, so item < lowest is evaluated. It’s false, so the
next statement (lowest = item) is not executed.

Don’t get this looking at the ‘if’ statement

if lowest == nil || item < lowest
lowest = item

First confusion is || , this I take to be ‘or’ ?
Second, if the assignment of ‘lowest = item’ comes after the ‘if’
conditional, how does any 'tem become the lowest. The way I’m reading
the
statement (using the array - mylist = [‘five’, ‘eight’, ‘one’, ‘ten’,
‘nine’]) I interpret the second iteration as
if lowest == nil or ‘five’ < lowest # lowest is still equal to
nil ?
Or could it be that in the ‘if’ block, the ‘lowest = item’ is set before
the
‘if conditons’ are checked ?

Stuart

On 7/10/06, [email protected] [email protected] wrote:

item < lowest comparison is never evaluated.

if lowest == nil || item < lowest
lowest = item

First confusion is || , this I take to be ‘or’ ?

Dark,

|| is another form of or

See the docs here for a full run down
http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html#UG

Hi –

On Sun, 9 Jul 2006, Dark A. wrote:

The next time through,
Second, if the assignment of ‘lowest = item’ comes after the ‘if’
conditional, how does any 'tem become the lowest. The way I’m reading the
statement (using the array - mylist = [‘five’, ‘eight’, ‘one’, ‘ten’,
‘nine’]) I interpret the second iteration as
if lowest == nil or ‘five’ < lowest # lowest is still equal to nil ?
Or could it be that in the ‘if’ block, the ‘lowest = item’ is set before the
‘if conditons’ are checked ?

No, definitely not. It’s all very linear:

if
do this
end

If the expression isn’t true, then “do this” never gets executed.

You might put some extra output in your loop, so you can see what’s
going on:

def sort(list)
sorted = []
unsorted = []

lowest = nil

list.each do |item|
puts “Comparing #{item.inspect} (item) to #{lowest.inspect}
(lowest)”
if lowest == nil || item < lowest
puts “Either lowest is nil, or #{item.inspect} is less than
#{lowest.inspect}”
puts “So lowest is now being set to #{item.inspect}”
lowest = item
end
end

puts “Loop finished: lowest is #{lowest.inspect}”
sorted.push(lowest)
puts sorted

end
mylist = [‘five’, ‘three’, ‘one’, ‘ten’, ‘eight’]
sort mylist

The output is:

Comparing “five” (item) to nil (lowest)
Either lowest is nil, or “five” is less than nil
So lowest is now being set to “five”
Comparing “three” (item) to “five” (lowest)
Comparing “one” (item) to “five” (lowest)
Comparing “ten” (item) to “five” (lowest)
Comparing “eight” (item) to “five” (lowest)
Either lowest is nil, or “eight” is less than “five”
So lowest is now being set to “eight”
Loop finished: lowest is “eight”

David

Hi –

On Sun, 9 Jul 2006, Dark A. wrote:

 if lowest == nil || item < lowest

That being the case I now understand how it’s working, but don’t
understand nil, at least in the way it works in a comparison.
Maybe it’s just something I need to accept :slight_smile:
a < b , 3 < 5 , those all seem clear, even a < 1.
oh well.

The only comparison with nil that you’re doing is:

lowest == nil

The code on the right of the || only gets executed if lowest == nil is
false. So when you do:

item < lowest

lowest is already known not to be nil.

Maybe the missing piece of the puzzle is this: When you have:

if expr1 || expr2

expr2 is never reached if expr1 is true. For example:

if 2 + 2 == 4 || 1/0 == 10
  puts "One of them is true!"
end

If 1/0 == 10 were to be executed, you would get a ZeroDivisionError –
but you don’t, because 2+2==4 is true. That’s enough to satisfy the
“or” condition, so Ruby doesn’t waste time testing the part on the
right.

David

On 7/9/06, [email protected] [email protected] wrote:

Hi –

The only comparison with nil that you’re doing is:

lowest == nil

But , from the output:
Comparing “five” (item) to nil (lowest)
Either lowest is nil, or “five” is less than nil
So lowest is now being set to “five”

The code on the right of the || only gets executed if lowest == nil is

false.

How can it be false on first pass, since it’s declared lowest = false ?

So when you do:

if 2 + 2 == 4 || 1/0 == 10
  puts "One of them is true!"
end

I thought I read somewhere that in an OR statement one or both could ==
TRUE.
I did not know that if the expression on left == true , the right would
not
be evaluated. Still I’m not sure
that’s my issue.

Stuart

On 7/9/06, [email protected] [email protected] wrote:

   puts "Either lowest is nil, or #{item.inspect} is less than #{

lowest.inspect}"
puts “So lowest is now being set to #{item.inspect}”
lowest = item
end
end

So the bottom line here is “anything” in the array (except perhaps for an
empty element) is less then nil ?

That being the case I now understand how it's working, but don't

understand nil, at least in the way it works in a comparison.
Maybe it’s just something I need to accept :slight_smile:
a < b , 3 < 5 , those all seem clear, even a < 1.
oh well.

Stuart

Hi –

On Mon, 10 Jul 2006, Dark A. wrote:

But , from the output:
Comparing “five” (item) to nil (lowest)
Either lowest is nil, or “five” is less than nil
So lowest is now being set to “five”

The code on the right of the || only gets executed if lowest == nil is

false.

How can it be false on first pass, since it’s declared lowest = false ?

I don’t see that in your code. I see this:

lowest = nil

So this:

lowest == nil

is true.

David

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs