Re: sorting

Is there some reason why this won't work:

x.sort!

? If you're not not familiar with the !-suffixed methods in Ruby, they mean
"do in place". So x.sort returns a sorted array leaving x unchanged, while
x.sort! Makes x into a sorted array.

So this
a = [8,4,6,2,5]
a.sort!

... sets a to [2,4,5,6,8]

Incidentally, Ruby also makes operations like swap() rather simple:

x, y = y, x

...is valid and does what you'd expect.

HTH,,

Mike

-----Original Message-----
From: [e-mail] [mailto:[e-mail]] 
Sent: 04 December 2003 08:42
To: [e-mail]
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


***************************************************************************
This communication (including any attachments) contains confidential information.  If you are not the intended recipient and you have received this communication in error, you should destroy it without copying, disclosing or otherwise using its contents.  Please notify the sender immediately of the error.

Internet communications are not necessarily secure and may be intercepted or changed after they are sent.  Abbey National Treasury Services plc does not accept liability for any loss you may suffer as a result of interception or any liability for such changes.  If you wish to confirm the origin or content of this communication, please contact the sender by using an alternative means of communication.

This communication does not create or modify any contract and, unless otherwise stated, is not intended to be contractually binding.

Abbey National Treasury Services plc. Registered Office:  Abbey National House, 2 Triton Square, Regents Place, London NW1 3AN.  Registered in England under Company Registration Number: 2338548.  Regulated by the Financial Services Authority (FSA).
***************************************************************************