Creating my own method for sorting an array

[Joe User]

Hi,

I'm working through the Learning To Program book(2nd edition) and am
stuck on the sort/recursion exercise (page 93/94). The exercise is to
roll your own sort method for use on an array. The suggestions are to
create an additional two arrays; 1) for the sorted words 2) another
for the unsorted words, take the list of words, find the smallest, and
put it on the end of the already-sorted list. The remaining items go on
the
unsorted. The idea being to recurse through the list of unsorted words
adding elements to the sorted list until done.

There are several routes I could take to get closer but I'm trying to
stay within the constraints of the book. That means I can use .each,
push, .pop, .length, .join, and .last. Hopefully I'm not leaving
anything out. Certainly I could use the .sort method and I could look
at the answer in the book but the idea is creating my own for the
experience. But I'm stuck. I'm hoping for a nudge in the right
direction instead of someone telling me outright
how to do it.

In English what I think I need to do is take each element of the array
and compare it to the rest of the elements and if it's the smallest,
push it onto the sorted list and push the remaining elements onto the
unsorted. Then call the method again with the sorted and unsorted
lists. That's the recursion part.

I guess the problem I'm having is knowing how to check each element of
the unsorted array against the other elements. I can check if the
current element is smaller than the other elements using < (less than)
but that doesn't mean it's the smallest in the whole array. So I would
only want to
push it onto sorted array if it's smaller than everything else.

This is about as far as I can get and it's not close to working. Plus
it seems like a mess to me.


#!/usr/bin/ruby
#

def sort some_array
recursive_sort some_array, []
end

def recursive_sort unsorted_array, sorted_array
until 0 == unsorted_array[unsorted_array.length]
unsorted_array.each do |outer|
unsorted_array.each do |inner|
if outer < inner
sorted_array.push(outer)
else
unsorted_array.push(inner)
end
end
end
end
puts sorted_array
recursive_sort unsorted_array, sorted_array
end

a = ['c', 'b', 'a', 'd']
sort(a)

Any hints welcome.
Thank-you.

 

[Marnen Laibow-Koser]

Hi,

I'm working through the Learning To Program book(2nd edition) and am
stuck on the sort/recursion exercise (page 93/94). The exercise is to
roll your own sort method for use on an array. The suggestions are to
create an additional two arrays; 1) for the sorted words 2) another
for the unsorted words, take the list of words, find the smallest, and
put it on the end of the already-sorted list. The remaining items go on
the
unsorted. The idea being to recurse through the list of unsorted words
adding elements to the sorted list until done.

In Ruby, this is frankly stupid. No Ruby programmer would do this in
any other way than by using the .sort method, providing a comparator
block, and letting Ruby take care of the bookkeeping.

With that in mind...

There are several routes I could take to get closer but I'm trying to
stay within the constraints of the book. That means I can use .each,
.push, .pop, .length, .join, and .last. Hopefully I'm not leaving
anything out. Certainly I could use the .sort method and I could look
at the answer in the book but the idea is creating my own for the
experience. But I'm stuck. I'm hoping for a nudge in the right
direction instead of someone telling me outright
how to do it.

In English what I think I need to do is take each element of the array
and compare it to the rest of the elements and if it's the smallest,
push it onto the sorted list and push the remaining elements onto the
unsorted. Then call the method again with the sorted and unsorted
lists. That's the recursion part.

That would certainly be a way of doing it. Have you written automated
tests to encapsulate these requirements? If not, do so before writing
another line of code.

I guess the problem I'm having is knowing how to check each element of
the unsorted array against the other elements. I can check if the
current element is smaller than the other elements using < (less than)
but that doesn't mean it's the smallest in the whole array.

Sure it does. (Of course, this is quite computationally inefficient.)

So I would
only want to
push it onto sorted array if it's smaller than everything else.

You're supposed to write a sort algorithm from scratch *before* they
tell you about bubble sort and quicksort? Get real! That's silly --
and you'll never use it in Ruby anyway.

Best,

 

[Robert Klemme]

Joe User wrote:

Somehow I believe I heard that name somewhere already...

In Ruby, this is frankly stupid. =A0No Ruby programmer would do this in
any other way than by using the .sort method, providing a comparator
block, and letting Ruby take care of the bookkeeping.

I don't see how that is a stupid exercise. I reckon this is not
mainly an exercise to introduce sorting but rather to get accustomed
with class Array and probably algorithms in general.

That would certainly be a way of doing it. =A0Have you written automated
tests to encapsulate these requirements? =A0If not, do so before writing
another line of code.

Maybe it's a bit early to start writing tests when someone is starting
to learn to program... When I started learning software development I
certainly got more kick out of a working program than a working unit
test before hand.

Sure it does. =A0(Of course, this is quite computationally inefficient.)

As I said, I don't believe this is the point of the exercise.

"Joe", a hint for your "finding the smallest" rock that you are stuck
on: you need only a single pass on the Array to find the smallest (or
largest) element. Just start with an empty "current smallest",
iterate through the Array (using #each for example) and compare the
"current smallest" with the "current iterated". You know what you
have to do if you find an element that is smaller than the "current
smallest"... You can then remove it from the unsorted Array by using
#delete_at or #delete, append it to the sorted and repeat.

Kind regards

robert

--=20
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

 

[Joe User]

"Joe", a hint for your "finding the smallest" rock that you are stuck
on: you need only a single pass on the Array to find the smallest (or
largest) element. Just start with an empty "current smallest",
iterate through the Array (using #each for example) and compare the
"current smallest" with the "current iterated". You know what you
have to do if you find an element that is smaller than the "current
smallest"... You can then remove it from the unsorted Array by using
#delete_at or #delete, append it to the sorted and repeat.

Kind regards

robert

Thank-you for the clue.
Joe

 

[Marnen Laibow-Koser]

Somehow I believe I heard that name somewhere already...


I don't see how that is a stupid exercise. I reckon this is not
mainly an exercise to introduce sorting but rather to get accustomed
with class Array and probably algorithms in general.

Then they probably should have picked a better example, or at least
explained common sort algorithms before turning you loose v

Maybe it's a bit early to start writing tests when someone is starting
to learn to program...

No. Testing is a fundamental part of programming, though it is often
neglected.

When I started learning software development I
certainly got more kick out of a working program than a working unit
test before hand.

It's the working test beforehand that lets you know when you have a
working program. It really is best to write the tests first. Read up
on test-first development and apply it religiously -- it really is worth
it.

As I said, I don't believe this is the point of the exercise.

Perhaps not. And it may be a good exercise for learning algorithmic
concepts. But really, it teaches you nothing good about writing
idiomatic, efficient Ruby.

Best,

 

[Alex]

Then they probably should have picked a better example, or at least
explained common sort algorithms before turning you loose v


No. Testing is a fundamental part of programming, though it is often
neglected.

Way to kill the enjoyment of programming, dude. This guy is a new
programmer, and you're talking to him about tests? When I started out, I
certainly didn't care a single bit (GASP!) about how well-written my
programs were, or if they followed good design patterns and whatnot.
Exposing him to this stuff is just going to make it even more confusing tha=
n
it needs to be.

It's the working test beforehand that lets you know when you have a
working program. It really is best to write the tests first. Read up
on test-first development and apply it religiously -- it really is worth
it.

Yeah, the way I tell if I have a working program is (generally) to run it.
True, a new programmer could write a test to ensure that his "hello world"
program works right, but isn't that a little silly?

Perhaps not. And it may be a good exercise for learning algorithmic
concepts. But really, it teaches you nothing good about writing
idiomatic, efficient Ruby.

Best,

Seriously, guys... He's trying to write a sort algorithm. I wrote many of
them when I was starting out, trying to figure out what was going on. What'=
s
the problem here? Let's give him some guidance, not talk about how dumb it
is to write that, because no one would use it in "the real world." You know
what else no one ever used in the real world? That slot machine program I
first wrote. All those "hello world" programs I wrote. All the algorithms I
re-implemented, trying to learn how they worked. Does the fact that no one
will ever use them make them worthless? Or maybe the experience I gained
from writing all that worthless code made me a better programmer.


Alex

 

[Marnen Laibow-Koser]

Way to kill the enjoyment of programming, dude. This guy is a new
programmer, and you're talking to him about tests?

Yup. It's more fun to program with good tests. You can go faster, and
you can see things work right away.

Anyway, if he's really a new programmer, he shouldn't be writing sort
algorithms.

When I started out, I
certainly didn't care a single bit (GASP!) about how well-written my
programs were, or if they followed good design patterns and whatnot.
Exposing him to this stuff is just going to make it even more confusing
than
it needs to be.

I didn't say a word about design patterns. All I recommended was tests.
These actually make it less confusing, since you can more clearly see
what's going on.

And we'd all be better programmers if we thought about good practice as
an integral part of the craft, not something bolted on later.

Yeah, the way I tell if I have a working program is (generally) to run
it.

The tests run it for you. Have you ever actually tried this? Sounds
like not.

True, a new programmer could write a test to ensure that his "hello
world"
program works right, but isn't that a little silly?

For "hello world", yes. For anything more complex, no. And a sort
implementation is certainly complex.

Seriously, guys... He's trying to write a sort algorithm. I wrote many
of
them when I was starting out, trying to figure out what was going on.
What's
the problem here? Let's give him some guidance, not talk about how dumb
it
is to write that, because no one would use it in "the real world."

I did give him some guidance. Now, since you brought it up...what
guidance have *you* given him?

You
know
what else no one ever used in the real world? That slot machine program
I
first wrote. All those "hello world" programs I wrote. All the
algorithms I
re-implemented, trying to learn how they worked. Does the fact that no
one
will ever use them make them worthless? Or maybe the experience I gained
from writing all that worthless code made me a better programmer.

I'm sure it did. I know I've done similar exercises. But I did want
the OP to realize that he shouldn't expect to ever do this in a real
Ruby program.

Alex

Best,

 

[Phillip Gawlowski]

Yup. It's more fun to program with good tests. You can go faster, and
you can see things work right away.

Hahahaha. No.
Tests are a safety net (and a rather thin one), that a beginner doesn't
need.

It's a good habit to get into, yes. After a beginner knows what this
"programming" thing is, and thus can understand what tests are, and how
to write a good test. A *test* is another level of abstraction that a
beginner at programming doesn't need, and doesn't understand as yet.

And an improperly written test is worse than no test at all: It makes
you believe that your code is correct when it isn't.

Anyway, if he's really a new programmer, he shouldn't be writing sort
algorithms.

Why not? It's the most basic algorithm there is, allow fancy-pants
things like recursion to be explored with (comparative) ease.

I didn't say a word about design patterns. All I recommended was tests.
These actually make it less confusing, since you can more clearly see
what's going on.

Tests *are* a design pattern.

And we'd all be better programmers if we thought about good practice as
an integral part of the craft, not something bolted on later.

Every apprentice, in any craft, learns the basics of a craft first, and
*then* moves on to the complex things.

Would you expect a carpenter to be able to plan a table before s/he is
able to hold a drill properly?

The tests run it for you. Have you ever actually tried this? Sounds
like not.

Tests don't run a program. They check if a part of a program, an atomic
piece, is correct as defined by the test.

For "hello world", yes. For anything more complex, no. And a sort
implementation is certainly complex.

You don't need tests for something complex. Nor do you need them for
something "simple". You need them for something that requires *correctness*.

I did give him some guidance. Now, since you brought it up...what
guidance have *you* given him?

Good guidance: Not to listen to know-it-alls unable to grasp what's
appropriate for a given situation and what isn't.

 

[Alex]

[Note: parts of this message were removed to make it a legal post.]

Yup. It's more fun to program with good tests. You can go faster, and
you can see things work right away.

Anyway, if he's really a new programmer, he shouldn't be writing sort
algorithms.

I guess that's where our opinions differ, again. I don't think it's fun to
write tests. I also don't think there's anything a new programmer "should"
be doing. He/she should be doing whatever interests them, and
learning/having fun.

I didn't say a word about design patterns. All I recommended was tests.
These actually make it less confusing, since you can more clearly see
what's going on.

And we'd all be better programmers if we thought about good practice as
an integral part of the craft, not something bolted on later.

I agree and disagree with this. It's a confusing feeling.

The tests run it for you. Have you ever actually tried this? Sounds
like not.

Yeah, I've done the whole automated testing thing. Not my style, what can I
say? I think tests can be very valuable in the right situation, don't get me
wrong, but teaching a novice programmer about them is just confusing,
methinks.

For "hello world", yes. For anything more complex, no. And a sort
implementation is certainly complex.

How is a sort implementation complex? For a full-fledged, high quality sort
implementation, maybe. For a student just writing what is (probably) a
single method sort? That's going to be an exciting unit test.

I did give him some guidance. Now, since you brought it up...what
guidance have *you* given him?

I haven't given him any advice, as you so keenly pointed out. I'm sure there
are much more talented programmers who can handle that task, I'm just trying
to save a new programmer some of the confusion that's so rampant with
beginners.

I'm sure it did. I know I've done similar exercises. But I did want
the OP to realize that he shouldn't expect to ever do this in a real
Ruby program.

Really, the point I'm trying to make is that he shouldn't be concerned with
the "real world" yet. He should try to have fun and learn at the same time,
not be bashed over the head with more complexity.

 

[Aldric Giacomoni]

Anyway, if he's really a new programmer, he shouldn't be writing sort
algorithms.

While I may agree with that in theory, I remember that my first
programming course included sorting algorithms - useful, because they
teach you to manipulate data in your head and in your code.

I didn't say a word about design patterns. All I recommended was tests.
These actually make it less confusing, since you can more clearly see
what's going on.

And we'd all be better programmers if we thought about good practice as
an integral part of the craft, not something bolted on later.

That is definitely true; maybe we should write a new "programming for
beginners" book.. ;-)

I'm sure it did. I know I've done similar exercises. But I did want
the OP to realize that he shouldn't expect to ever do this in a real
Ruby program.

Which, by now, if he hasn't been scared away from Ruby, he knows..

 

[Marnen Laibow-Koser]

Hahahaha. No.
Tests are a safety net (and a rather thin one), that a beginner doesn't
need.

I could not disagree with you more -- at least if we're talking about
TDD-style tests. Writing tests first allows the beginner to reify his
thinking about what he wants the program to do, and to know at once when
he has got the program to do it.

(Old-style a posteriori tests certainly aren't necessary for beginners.)

It's a good habit to get into, yes. After a beginner knows what this
"programming" thing is, and thus can understand what tests are, and how
to write a good test. A *test* is another level of abstraction that a
beginner at programming doesn't need, and doesn't understand as yet.

I don't think you're right. A beginning programmer has to explicitly
break things down into bits to be able to develop them at all. It
shouldn't be hard to write a rudimentary test for each bit as part of
that process.

Sure, this is unnecessary at the hello-world stage. But by the time
you're writing something with the complexity of a recursive sort, I
think it's a good idea. I know I'd have learned faster if I'd known
about this technique sooner.

And an improperly written test is worse than no test at all: It makes
you believe that your code is correct when it isn't.

Of course. So can no test at all.

Why not? It's the most basic algorithm there is, allow fancy-pants
things like recursion to be explored with (comparative) ease.

There are better introductions to recursion. Look at any Lisp book for
better ideas.

Tests *are* a design pattern.

Not in the usual sense of that term.

Every apprentice, in any craft, learns the basics of a craft first, and
*then* moves on to the complex things.

Good practice is basic.

Would you expect a carpenter to be able to plan a table before s/he is
able to hold a drill properly?

Perhaps. Conceptual ability to plan a design has nothing to do with
physical skill to hold a drill.

Tests don't run a program.

OK, the test runner software runs the program. Split hairs if you like;
my point stands.

They check if a part of a program, an atomic
piece, is correct as defined by the test.

Right. And that's something that is helpful for programmers at any
level, from novice to Ward Cunningham.

You don't need tests for something complex. Nor do you need them for
something "simple". You need them for something that requires
*correctness*.

If a program is worth writing, it requires correctness.

Good guidance: Not to listen to know-it-alls unable to grasp what's
appropriate for a given situation and what isn't.

Yup. The application of this maxim is left as an exercise.

Best,

 

[Josh Cheek]

[Note: parts of this message were removed to make it a legal post.]

Sigh, just so we can move on:
If you run this, and the tests pass, then your sort function probably works.

If you need a tip, here is the code I wrote to make it pass
http://pastie.org/760568


require 'test/unit'

def sort( unsorted , sorted = Array.new )
# your code here
end

def get_index_of_min( ary )
# your code here
end


class SortTest < Test::Unit::TestCase
def test_single_chars
assert_equal ['a','b','c','d'] , sort(['c', 'b', 'a', 'd'])
end
def test_double_chars
assert_equal ['ab','cd','ef','gh','ij','kl'] ,
sort(['ab','kl','ij','cd','gh','ef'])
end
def test_numbers
assert_equal [1,2,3,4] , sort([3,2,4,1])
end
def test_empty_array
assert_equal [] , sort([])
end
def test_nil
assert_equal nil , sort(nil)
end
end




If you are running from the terminal, it should look something like this, if
it completes correctly. If it does not, it will tell you which test failed,
and show you what it expected to get, and what it actually got.

$ ruby selection_sort.rb
Loaded suite selection_sort
Started
.....
Finished in 0.000673 seconds.

5 tests, 5 assertions, 0 failures, 0 errors




And for the record, I also don't think it makes sense to start writing tests
before you know how to write code. Though I would agree that it should be
taught earlier than it is (at my school, it isn't taught at all).