Re: Sorting arrays

Ruby
1

You can use the sort method on the entire Array:

sorted=[1, 2, “three”]
unsorted=[6,5,‘four’]
a = sorted+unsorted
b = a.sort { |x,y| x.to_s <=> y.to_s}
=>b is then [1, 2, 5, 6, “four”, “three”] (that’s because ‘1’ was
compared
to ‘four’ etc.)

Best regards,

Axel

2

Apologies, I can’t use array.sort. This is to build my own.

Stuart

3

On 6/28/06, [email protected] [email protected] wrote:

Best regards,

Axel

Dark A. wrote:

Apologies, I can’t use array.sort. This is to build my own.

This sounds like a homework problem…?

In either case, your description is a little fuzzy. The way you describe
it doesn’t make sense. This usually means you haven’t fully grasped the
problem. Before jumping into the programming, write out what you want to
accomplish on paper and make certain you completely understand what you
wish to do, and how you will go about it.

Then try to solve it programmatically. If you have trouble with that
piece, come back to the list. That’s my advice.

Good luck!

-Justin

4

Actually it’s from Chris P.'s book, Learning to Program. I thought
it was a bit fuzzy in the book, not so much my understanding but the
suggestions he makes to accomplish the task. His idea is to have two
additional lists, or arrays , one called “already sorted”, and the
other “unsorted”. I’m just being repetetive here to make the point of
where his advice is fuzzy. It reads as if you would use the first
array (where the strings were put) and test those against themselves
to find the smallest one, where the smallest (one that returns true)
goes into the sorted, repeat and the ones that return false go into
unsorted. Then the next iteration , or final stage is testing the
sorted list against the unsorted list.

Using “insertion sort” it seemed that things were moved around in just
the initial array.

Stuart

5

Dark A. wrote:

sorted list against the unsorted list.

Using “insertion sort” it seemed that things were moved around in just
the initial array.

Stuart

Oh, okay, sorry for my misunderstanding! I didn’t pay attention to who
had posted.
That’s not really insertion sort, no…here’s one way to do it
(warning: spoilers ahead):

#if you can use Array#min:

list = [“aword”, “cword”, “gword”, “zword”, “dword”, “qword”, “pword”]
unsorted = []
sorted = []

sorted << list.min #add the smallest to sorted
unsorted = list - sorted #add the rest to unsorted

until unsorted.empty? #when unsorted is empty, we are done
sorted << unsorted.min #put the smallest value into sorted
unsorted.delete(unsorted.min) #take it out of unsorted
end

p sorted #all sorted!

#if you can’t use Array#min:

list = [“aword”, “cword”, “gword”, “zword”, “dword”, “qword”, “pword”]
unsorted = []
sorted = []

unsorted = list.dup #make a copy of the list of words so we don’t
destroy the original!

until unsorted.empty? #when unsorted is empty, we are done

min = unsorted[0]         #get our initial 'minimum value'

unsorted.each do |word|
   if word < min                      #check the rest of the values

against it
min = word #if we find something smaller,
that’s our new min
end
end

sorted << min               #put the smallest in sorted
unsorted.delete(min)     #delete it from unsorted

end

p sorted #all sorted!

The comments should help explain what’s going on. Note that I skip the
first step (“get the smallest value from the original list, put that in
sorted, put the rest in unsorted”) in the second example, because I copy
the entire list into unsorted first.

Anyways, I hope that helps. You can probably come up with a better
version!

-Justin

6

I just started going through the replies, thank you all very much!
Anyway, this one below, just kind of blows me away so succinct!
I guess because it’s Ruby.

Stuart

On 6/29/06, Robert K. [email protected] wrote:

** more spoilers **

7

** more spoilers **

2006/6/29, Justin C. [email protected]:

#if you can use Array#min:

list = [“aword”, “cword”, “gword”, “zword”, “dword”, “qword”, “pword”]
unsorted = []
sorted = []

sorted << list.min #add the smallest to sorted
unsorted = list - sorted #add the rest to unsorted

This setup code above is superfluous.

until unsorted.empty? #when unsorted is empty, we are done
sorted << unsorted.min #put the smallest value into sorted
unsorted.delete(unsorted.min) #take it out of unsorted
end

p sorted #all sorted!

You can do

list = [“aword”, “cword”, “gword”, “zword”, “dword”, “qword”, “pword”]
unsorted = list.dup
sorted = []
until unsorted.empty? #when unsorted is empty, we are done
sorted << unsorted.min #put the smallest value into sorted
unsorted.delete(unsorted.min) #take it out of unsorted
end
p sorted

#if you can’t use Array#min:

Here’s a shorter version using inject (of course): :slight_smile:

require ‘enumerator’
unsorted = list.dup
sorted = []
until unsorted.empty?
min, pos = unsorted.
to_enum(:each_with_index).
inject {|(minel, minidx), (el, idx)| el < minel ? [el, idx] :
[minel, minidx]}
unsorted.delete_at pos
sorted << min
end
p sorted

This is the more verbose but equivalent version:

unsorted = list.dup
sorted = []

until unsorted.empty?
min = pos = nil

unsorted.each_with_index do |el, idx|
if min.nil? || el < min
min = el
pos = idx
end
end

unsorted.delete_at pos
sorted << min
end
p sorted

You can save one comparison op per loop if you do

unsorted = list.dup
sorted = []
until unsorted.empty?

unsorted is not empty, so there is an element at pos 0!

min = unsorted[0]
pos = 0

unsorted.each_with_index do |el, idx|
if el < min
min = el
pos = idx
end
end

unsorted.delete_at pos
sorted << min
end
p sorted

Kind regards

robert