sorting

[Van Jacques]

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 = 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 <=> 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 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 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 <=> x[j] ) == 1
swap(x,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

 

[Armin Roehrl]

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.

 

[nainar]

[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, a[j]), two variables x and
y are created, and the values of a and a[j] are copied to it. Executing
the body effectively interchanges the values of x and y, but not those of
a 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:

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] !

 

[Dmitry V. Sabanin]

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] !

 

[nainar]

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] !

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

 

[Dan Doel]

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

 

[T. Onoma]

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.

 

[nainar]

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.

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