Re: Working through Ch.10 for learning to program 2.0 (Chris Pine)

JD JD wrote in post #1117223:
> My guess is it would involve a while loop that does a swap something
> like this:
>
> if a>b
> X++
> Y++
> elsif a==b
> check next letter and compare
> else
> swap a and b

Here's a bit of advice, with which I think everyone will agree: this is 
confusing, and because it's confusing, it's the wrong thing to do.  What 
you're writing is a description of an algorithm, however the way you're 
writing it is a little bit "bottom-up" -- that is, you're starting by 
writing something that looks like "computer language", and trying to 
squeeze that into your mental model for sorting.

The way to write an algorithm is:
1. start with a prose description of the actions (in plain language, 
like you're talking to a human)
2. trim the description down to smaller, more "atomic" or simple actions
3. repeat #2
4. repeat #3
5. when the actions are all very small and simple, add some syntax (like 
semicolons or braces or dollar signs)

After step 5, you have your algorithm, implemented in the programming 
language of your choice.

Here are a couple of descriptions of sorting algorithms, written at one 
step below prose:

1. look at each item in the list, comparing it to the next item:
1.1. if the next item is less than the current item, swap them
2. when you reach the end of the list, if you did any swaps, go back to 
step 1 and start over

That's called "bubble sort."

1. designate a second list, called the "sorted list"
2. take an item from the unsorted list (call the item "X")
3. look at each item in the sorted list:
3.1. if X is less than the unsorted item, put X into the sorted list 
immediately before the unsorted item that's bigger than it
4. if you get to the end of the unsorted list without putting X in, add 
X to the end of the unsorted list
5. if any items remain in the unsorted list, go back to step 2 and 
repeat

That's called "insertion sort."

There are lots of others, but I'm given to understand that these are the 
easiest to describe and understand.

Personally I find bubble sort easier to implement recursively, but 
they're both quite simple once you get the operations small enough, and 
add in some syntax.

-- 
Posted via http://www.ruby-forum.com/.