From: Peter <Peter.Vanbroekhoven@...>
Date: 2003-12-04T19:24:28+09:00
Subject: Re: sorting

[snip]
> To swap two numbers x and y, call
>
> swap(x,y)
> z = x
> x = y
> y = z
> end

This won't work in Ruby. If you call swap(a[i], a[j]), two variables x and
y are created, and the values of a[i] and a[j] are copied to it. Executing
the body effectively interchanges the values of x and y, but not those of
a[i] and a[j]. Consider replacing a call to swap with a simple

  a[i], a[j] = a[j], a[i]

> If x = a[i] and y = a[j], this interchanges the 2 numbers.
>
> I am thinking this thru as I go, and I am old and not as
> tireless or smart as I used to be.
>
> There is only so much I can do without getting feedback
> from running an actual program to let me know where
> I am going wrong.
>
> Do you think this is a good start on the problem?

You are clearly going in the direction of bubblesort, which is a
well-known sorting algorithm. So you're doing well :-)

> Any suggestions on what to do next?
>
> I was thinking of something like this. (One thing about ruby,
> is that without knowing the language, you can read the
> program). If we are going to compare a[i] and a[j], we only
> want to consider i < j, to avoid doing everything twice.
>
> 0.upto(n-2) |i|
> ii = i+1
>   ii.upto(n-1) |j|
>     if ( x[i] <=> x[j] ) == 1
>      swap(x[i],x[j])
>     end
>   end
> end
>
> Do you think this will work?

Yes. For i == 0, it will seek out the smallest element and put it first.
Then you leave a[0] alone for the rest. Then you seek out the smallest
element in the remainder of the array and put it first , i.e., in a[1].
And so on. It's not quite bubble sort, but I think it will work.

> For 2 numbers, i = 0, ii = 1 = j==> works
> For 3 numbers, i = 0 ii = 1 = j
> => (a0,a1)  ordered ==>  new(a0,a1) = (b0,b1) then
> then j = 2  => (b0,a2) ordered => (c0,c2).
>
> I am already confused as to what this program would actually do.
> Perhaps this is not the way to do it at all.
> I guess I will have to write it and try it out.
> That's often the way to things anyway.
>
> Any suggestions for improvements are welcome.
>
> I imagine that many people have had to do something like this
> during their life, especially programmers.
> I am a physicist, but I'm surprised that I've never seen a sort
> program--it seems so basic.

There are many. See e.g.,

  http://en.wikipedia.org/wiki/Sort_algorithm

Peter