Sorting

ruby-talk
1

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

2

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

Ruby can do easier swaps:

x,y=3,4
x,y=y,x #-> x==4 and y==3

Here is quicksort (Tony Hoare).

def quicksort( xs )
return xs if xs.size <= 1
m = xs[0] # Split-Element
quicksort(xs.select { |i| i < m } ) +
xs.select { |i| i == m } +
quicksort(xs.select { |i| i > m } )
end
quicksort([13, 11, 74, 69, 0])
#-> [0, 11, 13, 69, 74]

I quick search on the web also showed up this link:
http://yagni.com/combsort/index.php (Bubblesort, Combsort)

If you search for insertion sort, etc. you find many other
sorting algorithms.

Have fun,
-A.

3

[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 :slight_smile:

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.,

Sorting algorithm - Wikipedia

Peter

4

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

Actually you should insert a do before |i| and |j|:

0.upto(n-2) do |i|
ii = i+1
ii.upto(n-1) do |j|
if ( x[i] <=> x[j] ) == 1
x[i],x[j]=x[j],x[i]
end
end
end

And this version works on a few random samples (I didn’t change the
algorithm, so your thinking was correct :slight_smile:

def sort(x)
n = x.length
0.upto(n-2) do |i|
ii = i+1
ii.upto(n-1) do |j|
if ( x[i] <=> x[j] ) == 1
x[i],x[j]=x[j],x[i]
end
end
end
end

Peter

5

Thanks for the help. I looked at the web sites, etc., and now have
plenty of info on sorting.

I am also happy that my program turned out fairly well :slight_smile:

BTW, Are all emails from ruby-talk posted here? Is it necessary
to subscribe if one reads this newgroup instead?

···

==============

Here is my first sort program in ruby:

x = Array.new
i = 0
puts ‘Enter some integers, end with CR.’
x[0] = gets.chomp
while x[i] != ‘’
x[i+1] = gets.chomp
i = i + 1
end
n = x.length

Find min, put in x[0], etc. Do 2, then 3 integers

0.upto(n - 2) do |i|
(i + 1).upto(n - 1) do |j|
if ( x[i] <=> x[j] ) == 1
x[i],x[j]=x[j],x[i]
end
end
end

puts n.to_s
puts
x.each {|i| print i.to_s + " "}
puts

Peter Peter.Vanbroekhoven@cs.kuleuven.ac.be wrote in message news:Pine.LNX.4.44.0312041140140.4554-100000@merlin.cs.kuleuven.ac.be…

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

Actually you should insert a do before |i| and |j|:

0.upto(n-2) do |i|
ii = i+1
ii.upto(n-1) do |j|
if ( x[i] <=> x[j] ) == 1
x[i],x[j]=x[j],x[i]
end
end
end

And this version works on a few random samples (I didn’t change the
algorithm, so your thinking was correct :slight_smile:

def sort(x)
n = x.length
0.upto(n-2) do |i|
ii = i+1
ii.upto(n-1) do |j|
if ( x[i] <=> x[j] ) == 1
x[i],x[j]=x[j],x[i]
end
end
end
end

Peter

6

If function are params are only copies , why do the two functions below
behave differently:

def f1(a)
 a=[9,8,7]
end

def f2(b)
 b[0]=[9,8,7]
end

v=[1,2,3]
f1(v)
 p v    		# prints [1,2,3]  :  'v' not changed
f2(v)
 p v		        # prints [[9,8,7],2,3] !
···

On Thu, Dec 04, 2003 at 07:24:28PM +0900, Peter wrote:

[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

7

Mailing list and newsgroup are cross-mirrored.

Gavin

···

On Saturday, December 6, 2003, 6:57:06 AM, Van wrote:

BTW, Are all emails from ruby-talk posted here? Is it necessary
to subscribe if one reads this newgroup instead?

8

If function are params are only copies , why do the two functions below
behave differently:

def f1(a)
a=[9,8,7]
end
Because in this case, not object that ‘a’ refers to is changed, but variable ‘a’ itself assigned to a new object [9,8,7].
def f2(b)
b[0]=[9,8,7]
end
But now, object that ‘b’ refers to is changed, not variable ‘b’.

v=[1,2,3]
f1(v)
p v # prints [1,2,3] : ‘v’ not changed
When variable assigned to a new object, old object still exists. And v holds reference to it, no matter what f1 did.

···

On Sunday 07 December 2003 12:43, nainar wrote:

f2(v)
p v # prints [[9,8,7],2,3] !

–
sdmitry -=- Dmitry V. Sabanin
MuraveyLabs.

9

[snip]

To swap two numbers x and y, call
def 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
If function are params are only copies, why do the two functions
below behave differently:

Function params aren’t copies; they are (1) variables that (2)
contain references to objects. Remember that in Ruby, variables are
just tags that refer to objects. They aren’t memory slots in and of
themselves like they are in other languages.

def f1(a)
a=[9,8,7]
end

In this case, it’s helpful to decorate this a bit differently:

def f1(a)
p a
a = [9, 8, 7]
p a
a
end

When you run that version of f1, you’ll notice that the object IDs
are different.

def f2(b)
b[0]=[9,8,7]
end

Again, decorated differently:

def f2(b)
p b
b[0] = [9, 8, 7]
p b
b
end

In this case, you’ll notice that the object IDs are the same. This
is becasue you’re not calling straight assignment in this case.
You’re calling b’s = method, just as if you had done:

b.send(:=, 0, [9, 8, 7])

Hopefully it makes more sense now.

-austin

···

On Sun, 7 Dec 2003 14:43:58 +0900, nainar wrote:

On Thu, Dec 04, 2003 at 07:24:28PM +0900, Peter wrote:
–
austin ziegler * austin@halostatue.ca * Toronto, ON, Canada
software designer * pragmatic programmer * 2003.12.07
* 09.29.05

10

Thanks for prompt reply. But why is a treated differentlyi from b[0] ? .

In C, parameters are passed by value , unless pointers to variables are used .

In Perl, params are passed in the '@’ array and contains references to the original
variables and assignments to the elements of @ are reflected in the original
vars(Execept when the whole ‘@_’ is assigned to at once ).

How does it work in Ruby?. I couldn’t find anything on this in docs.

v.nainar

···

On Sun, Dec 07, 2003 at 03:14:28PM +0900, Dmitry V. Sabanin wrote:

On Sunday 07 December 2003 12:43, nainar wrote:

If function are params are only copies , why do the two functions below
behave differently:

def f1(a)
a=[9,8,7]
end

Because in this case, not object that ‘a’ refers to is changed, but variable ‘a’ itself assigned to a new object [9,8,7].

def f2(b)
b[0]=[9,8,7]
end

But now, object that ‘b’ refers to is changed, not variable ‘b’.

v=[1,2,3]
f1(v)
p v    		# prints [1,2,3]  :  'v' not changed

When variable assigned to a new object, old object still exists. And v holds reference to it, no matter what f1 did.

f2(v)
p v		        # prints [[9,8,7],2,3] !

–
sdmitry -=- Dmitry V. Sabanin
MuraveyLabs.

11

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
If function are params are only copies, why do the two functions
below behave differently:

Function params aren’t copies; they are (1) variables that (2)
contain references to objects. Remember that in Ruby, variables are
just tags that refer to objects. They aren’t memory slots in and of
themselves like they are in other languages.

Sorry for the confusion. To me the value of a variable is a reference to
an object, not the object itself. And on method call, references are
copied to variables with the same name as the formal parameters. To me
that’s the simplest and most consistent view. But I can see how my
explanation above can be confusing…

Peter

12

I believe all variables are passed by reference in Ruby, since everything
is an object.

You need to explicitly use #clone or #dup to pass by value.

  • Dan
13

I find it confusing sometimes myself too, but it does “pan out” when you think
about how ruby works:

def f2(b)
b[0]=[9,8,7]
end

In this case b references the passed variable like a c pointer, so assignment
to one of its elements effects the original.

def f1(a)
a=[9,8,7]
end

In this case you have “dettached” the original reference to a, giving it a new
one, so the original is unaffected. Try this instead:

def f1(a)
a.replace [9,8,7]
end

This all has to do with what = does --it assigns reference, and is not an
inplace assignment.

T.

···

On Sunday 07 December 2003 10:41 am, nainar wrote:

In C, parameters are passed by value , unless pointers to variables are
used .

In Perl, params are passed in the '@’ array and contains references to
the original variables and assignments to the elements of @ are reflected
in the original vars(Execept when the whole ‘@_’ is assigned to at once ).

How does it work in Ruby?. I couldn’t find anything on this in docs.

14

I am beginning to understand this:
If you assign to the variable within the function the original is NOT
modified.

if you modify the variable within the function then the original is modified.

It means if the variable is a simple type like a numeric it cannot be
modified. If I try something like:
v=99
def f1(n); n=n*n ; end
f1(v)
it will not work.

Why can’t we have something simpler/more explicit like in C or even Perl?.
v.nainar

···

On Sun, Dec 07, 2003 at 08:14:01PM +0900, T. Onoma wrote:

On Sunday 07 December 2003 10:41 am, nainar wrote:

In C, parameters are passed by value , unless pointers to variables are
used .

In Perl, params are passed in the '@’ array and contains references to
the original variables and assignments to the elements of @ are reflected
in the original vars(Execept when the whole ‘@_’ is assigned to at once ).

How does it work in Ruby?. I couldn’t find anything on this in docs.

I find it confusing sometimes myself too, but it does “pan out” when you think
about how ruby works:

def f2(b)
b[0]=[9,8,7]
end

In this case b references the passed variable like a c pointer, so assignment
to one of its elements effects the original.

def f1(a)
a=[9,8,7]
end

In this case you have “dettached” the original reference to a, giving it a new
one, so the original is unaffected. Try this instead:

def f1(a)
a.replace [9,8,7]
end

This all has to do with what = does --it assigns reference, and is not an
inplace assignment.

T.

15

Hi –

I am beginning to understand this:
If you assign to the variable within the function the original is NOT
modified.

if you modify the variable within the function then the original is modified.

It means if the variable is a simple type like a numeric it cannot be
modified. If I try something like:

Variables are untyped; there’s no such thing as a variable of a simple
type. (This isn’t just pickiness; it actually makes a big
difference.)

 v=99
 def f1(n); n=n*n ; end
       f1(v)

it will not work.

Yes it will. (Try it :slight_smile: Any time you have a variable name on the lhs
of an assignment, the variable of that name gets assigned a new
reference.

n = 1
n = 2
n = “hi”
n = 99
n = n * n
n = n - 30

etc. Every time you put ‘n’ on the lhs, you’re starting from scratch;
previous values of ‘n’ have no relevance. (On the rhs, of course, the
pre-assignment n is used to evaluate the expression.)

Literal integers are different from variables; you can’t do this:

99 = 2

since that would screw the math up quite a big :slight_smile:

Why can’t we have something simpler/more explicit like in C or even Perl?.

Have another look at how Ruby does it. :slight_smile:

David

···

On Mon, 8 Dec 2003, nainar wrote:

–
David A. Black
dblack@wobblini.net

16

I am beginning to understand this:
If you assign to the variable within the function the original is NOT
modified.

if you modify the variable within the function then the original is modified.

To me the previous two sentences say exactly the opposite of each other. A
variable is local to its scope and cannot be changed outside that scope
(except by using closures). But you can change the internal state of the
object that the variable points to from anywhere (as long as you’re
allowed to access that state, of course).

It means if the variable is a simple type like a numeric it cannot be
modified. If I try something like:
v=99
def f1(n); n=n*n ; end
f1(v)
it will not work.

It does what you asked it to do, not what you meant it to do.

Actually there’s no such thing as a simple type in Ruby (the way I think
you mean simple). A numeric is also an object. An integer is special in
that you can’t change its value (in the sense that you can’t change value
of 5 to 7), but that’s called immutable (at least as far as I know they
are immutable). But not all about a numeric is immutable:

class Numeric
def assoc=(obj)
@assoc_obj = obj
end
def assoc
@assoc_obj
end
end
1.assoc = “This is number one”
2.assoc = “This is number two”
print 1.assoc # => This is number one
print 2.assoc # => This is number two
print (1 + 1).assoc # => This is number two
print 3.assoc # => nil

But this is changing the internal state of objects, not the variable.
After the code above, everywhere in the code, 1.assoc will evaluate to
“This is number one” until reassigned, and 2.assoc will evaluate to “This
is number two”, etc.

Why can’t we have something simpler/more explicit like in C or even Perl?.

What do you want to make explicit? Everything’s an object, and each
variable contains a reference to an object, so no need to make that
explicit. Maybe you want varargs. Like procedure/function arguments in
Pascal that are indicated with var, or pointers to variables like in C and
passing those to a function. But Ruby doesn’t allow that. If you really
need to write a swap method, you can do it like this:

def swap(a,b)
b,a
end

x = 1
y = 2
x, y = swap(x, y)

Any value that a method returns is explicit this way, not implicit like
when you have pointers to variables as in C and pass that to a function to
have it place its result there.

Peter

17

I think nainar meant that v would not be changed.

-t0

···

On Sunday 07 December 2003 07:26 pm, David A. Black wrote:

 v=99
 def f1(n); n=n*n ; end
       f1(v)

it will not work.

Yes it will. (Try it :slight_smile:

18

Hi –

Hi –

 v=99
 def f1(n); n=n*n ; end
       f1(v)

it will not work.

Yes it will. (Try it :slight_smile:

Having read Peter’s reply I now see that what you were expecting was
for v to change. (I had thought you were suggesting that you couldn’t
use n as the lhs of an assignment because it had stored an integer.)

My comments about lhs behavior may be relevant anyway, in the sense
that n on the lhs has nothing to do with v (i.e., you’re “starting
from scratch”).

David

···

On Mon, 8 Dec 2003, David A. Black wrote:

On Mon, 8 Dec 2003, nainar wrote:

–
David A. Black
dblack@wobblini.net