From: vanjac12@... (Van Jacques)
Date: 2003-12-04T17:42:07+09:00
Subject: sorting

I'm not sure where to post about this problem, so
please suggest appropriate places if you have suggestions.
(I always say this, thinking I will post it to some new newsgroup).

I am writing a practice program (in ruby--not improtant)
to sort an array of n arbitrary integers a[i] (i = 0, ..., n-1),
putting them in increasing order.
I want to rearrange the array a so that

a[0] <= a[1] <= ... <= a[n-1]

The integers will have to be permuted by a member
of the permutation group on n objects S_n.

Any permutation p can be written as a product of
interchanges, so the basic subroutine (does the term
subroutine date me?) will be to swap 2 integers.

ruby has the following comparison; x <=> y

which returns - 1 if x < y
		0 if x = y
	      + 1 if x > y
for example,

 3 <=> 1  # 3 > 1 so <=> returns 1
=> 1
 3 <=> 3  # 3 == 3 so <=> returns 0
=> 0
 3 <=> 5  # 3 < 5 so <=> returns -1
=> -1

Thus if we compared 2 elements  of the array

  a[i] <=> a[j]

and get + 1, we swap them. Otherwise, do nothing, as they are in order.

To swap two numbers x and y, call

swap(x,y)
z = x
x = y
y = z
end

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?

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?

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.

Van