Linear sort
M1
C-Z, and so on. S, O, R, T, I, N and G are going to play this game, and
we have to report the results:
S-O, O wins R-T, R wins I-N, I wins G-D2C(255), G wins
O-R, O wins I-G, G wins
O-G, G wins
7 games played, and we have a winner! The second best must have been
beaten by G, so it should be (the existing) I or O.
I-O, I wins
8 games played. We have a winner, and we have found a second best. Next,
we can either replay the game with the remaining 5 players in order to
find the number 3, or we can find the number 3 in the group O (beaten
bij G) and N (beaten by I).
O-N, N wins
This way, the numbers 1, 2 and 3 are found with 9 games.
The last solution gets rather complicated, so with a lot of competitors
just replaying with the remaining competitors may be both easier and
perhaps even faster.
A typical sort of S, O, R, T, I, N and G has disadvantages. The time to
sort the players can increasy dramaticly if the number of players grows,
and the time it will take to sort all players becomes unpredictable.
I do have a solution for the situation above in BASIC, but unfortunately
it contains a lot of GOTO's (REXX isn't good at that), and also it is not
"optimized". The question is obvious: anyone willing to take a shot at
this, using (classic) REXX?
T-Rex
I'm clueless on what your talking about. Maybe I've been shoveling snow too
much here in Denver.
Rex
"M1" <sp...@uni-one.nl> wrote in message
news:y82e+I0F...@uni-one.nl...
David Ruggles
is a wet but balmy 75 ;) and I couldn't follow that either.
--
Thanks,
David Ruggles
CCNA MCSE (NT) CNA A+
Network Engineer, Safe Data, Inc
910-285-7200 da...@safedatausa.com
0100011101101111011001000110110001101111011101100110010101110011011110010110
111101110101
"T-Rex" <Rex_...@csi.com> wrote in message
news:EwKea.195684$sf5.1...@rwcrnsc52.ops.asp.att.net...
Allodoxaphobia
> I don't think it's the snow shoveling. I'm over in North Carolina where it
> is a wet but balmy 75 ;) and I couldn't follow that either.
Maybe it's a poorly understood homework assignment...
M1
>> it is a wet but balmy 75 ;) and I couldn't follow that either.
> Maybe it's a poorly understood homework assignment...
Thanks for adding so much information, but what's homework?
M1
you want to sort (the cars) on performance, then it's easy to find the
number 1: that would be the winner of the event.
Then you also know for sure that the second best car always (!) lost
of number 1. Perhaps in the final, perhaps in the 1st round.
With 8 cars competing, it takes 7 (4+2+1) races to find the winner.
Because you know for sure that #2 was beaten by #1, it just takes 2
extra comparizations to find the #2 car (car #1 beat 3 cars to win).
Then you can start the race again with the 6 unsorted cars (add 2
known snails to reach 8 competiors again) to sort the remaining
cars on performance.
But you also can tell that the #3 always lost of car #1 or car #2, but
that is getting complicated. Racing again is a slower sorting method,
but easier.
The knowledge that the #2 car always raced against car #1 is a way
to save resources, because it does limit the number of comparizations/
races (there are a few other interesting advantages too).
Maintaining the race results effectivly (what are the cars that car
#1 beat, so you can find car #2) is the hard part. The question is:
has anyone a REXX solution for this?
Shmuel (Seymour J.) Metz
at 08:59 PM, sp...@uni-one.nl (M1) said:
>he question is obvious: anyone willing to take a shot at this, using
>(classic) REXX?
Why? The bubble sort has run time on the order of N^2, while other
sorts are of order N*ln(N). If I need to sort a large list, I'll look
up one of the algorithms in Knuth.
--
Shmuel (Seymour J.) Metz, SysProg and JOAT
Any unsolicited commercial junk E-mail will be subject to legal
action. I reserve the right to publicly post or ridicule any
abusive E-mail.
I mangled my E-mail address to foil automated spammers; reply to
domain Patriot dot net user shmuel+news to contact me. Do not
reply to spam...@library.lspace.org
M1
>> (classic) REXX?
> Why? The bubble sort has run time on the order of N^2, while other
> sorts are of order N*ln(N).
Because it gets rid of a worth-mentioning multiplying factor, and the
sorting time is (almost linear, the claim that it is linear is false)
predictable.
> If I need to sort a large list, I'll look up one of the algorithms
> in Knuth.
I do have a few algorithms, including results. This algorith was by
far the fastest one, and came with BASIC source. Unfortunately this
source was not portable directly. GOTO's were a problem, it is not
easy to maintain the arrays in REXX, and IMHO it still is can be
optimized. FTR: there are also a few sorting algorithms in the
INF-file RXTT*.Z...@hobbes.nmsu.edu.
My sorting, for speed reasons, can be done with a DLL, but it would
be "fun" to keep doing it in REXX with such an algorithm.
Wolfgang Riedel
There are lots of Rexximplementations of sorting (and other) algorithms
in Vladimir Zabrodsky book:
Album of Algorithms and Techniques for Standard Rexx.
Wolfgang
Ian Collier
comp.lang.rexx:
> It is a very lame game, but A will always beat B-Z, B will always beat
> C-Z, and so on. S, O, R, T, I, N and G are going to play this game, and
> we have to report the results:
>
> S-O, O wins R-T, R wins I-N, I wins G-D2C(255), G wins
>
> O-R, O wins I-G, G wins
>
> O-G, G wins
>
> 7 games played, and we have a winner! The second best must have been
> beaten by G, so it should be (the existing) I or O.
>
> I-O, I wins
>
> 8 games played. We have a winner, and we have found a second best.
You realise of course that if there had been more players then you
would have required more than just this one game to find the second
best. In fact you need about log2(N) games to find the second best
of N competitors.
> A typical sort of S, O, R, T, I, N and G has disadvantages. The time to
> sort the players can increasy dramaticly if the number of players grows,
> and the time it will take to sort all players becomes unpredictable.
What you have here seems to be somewhat similar to a heap-sort. It
is actually nowhere near linear, but its asymptotic behaviour, namely
N*log(N), is the best that can theoretically be achieved for a sort
using binary comparisons [a "radix sort" is often faster but requires
extra storage]. In practice, heap-sort is often beaten by quicksort;
however, the behaviour of heap-sort is always predictable, while
quicksort can occasionally degenerate into O(N^2) behaviour.
Your algorithm can be viewed as two steps: firstly, playing all the
initial games to determine the winner; secondly, eliminating the winner
and replaying all the games in which it took part to determine which
one comes next. This step is repeated until all the players have been
eliminated in order. The problem is that representing the games played
and the winner of each is fairly difficult.
For a rather naïve representation, let us represent the winner by
swapping the elements so that the winner always appears on the left.
Our array begins with the letters SORTING and a dummy element, which
I will represent by a dot.
S O R T I N G .
The games S-O, R-T and so on are played. O S R T I N G .
The game O-R is a win for O, so the array is
unchanged. However, the game I-G requires
the _pairs_ IN and G. to be swapped so as to
avoid disturbing the results of previous
games. O S R T G . I N
The game O-G requires OSRT to be swapped
with G.IN. G . I N O S R T
The overall winner is G, so it is now eliminated and all games
involving the first element of the array have to be replayed.
The game .-. is a no-op . . I N O S R T
The game .-I is a win for I I N . . O S R T
The game I-O is a win for I. I N . . O S R T
The second place now goes to I, and it is eliminated.
The game .-N is a win for N N . . . O S R T
The games N-. and N-O are wins for N. N . . . O S R T
Third place goes to N. . . . . O S R T
The game .-O is a win for O O S R T . . . .
Fourth place goes to O. . S R T . . . .
The game .-S is a win for S S . R T . . . .
The game S-R is a win for R R T S . . . . .
The game R-. is a win for R.
Fifth place goes to R. . T S . . . . .
The game .-T is a win for T T . S . . . . .
The game T-S is a win for S S . T . . . . .
Sixth place goes to S.
So clearly last place goes to T.
I am not going to implement this in Rexx because it involves a fair
amount of unnecessary moving of elements.
You can find a Rexx heap-sort by searching on Google. The first one I
found was quite informative: <http://www.os2ezine.com/v3n01/rexx.htm>.
If you read the description you'll see that it turns out to be quite
similar in structure to the above, but has the advantage that you only
ever have to swap individual elements, not whole chunks of elements
as I was doing above. It's not identical to your algorithm, but it
incorporates similar ideas. It too has two steps: firstly, arranging
the elements into a tree structure, and secondly, repeatedly eliminating
the top element and shuffling up the other elements to maintain the
tree.
--
---- Ian Collier : i...@comlab.ox.ac.uk : WWW page (including REXX section):
------ http://users.comlab.ox.ac.uk/ian.collier/imc.shtml
New to this group? Answers to frequently-asked questions can be had from
http://rexx.hursley.ibm.com/rexx/ .
Jaime A. Cruz, Jr.
hobbes for a REXX program I wrote some time ago called "HELLO"
It's a little time/date and reminder program I use in my boot up
sequence to remind me of upcoming dates. There is a REXX-written
function in that package called "JCSort" that does a linear sort of the
REXX stack...
M1
> would have required more than just this one game to find the second
> best. In fact you need about log2(N) games to find the second best
> of N competitors.
200 elements on a very slow PC), but the results below do show some
obvious increases in sorting time.
> What you have here seems to be somewhat similar to a heap-sort. It
> is actually nowhere near linear
True. The sort results I remembered (and the graph that wents with it)
is most likely from the XT era, with the comment that "each 10 elements
added increases the sorting time by about 4 seconds". Some results:
Elements Seconds
10 2 (2/10=0.2)
20 6
30 9
100 41
110 45
120 49
130 60
180 82
190 86
200 90 (90/200=0.45)
The biggest increases obviously occur when a power of 2 is exceeded,
e.g. 10->20 (>16) and 120->130 (>128). Nowadays, 200 elements is not
really worth mentioning... :-)
> Your algorithm can be viewed as two steps: firstly, playing all the
> initial games to determine the winner; secondly, eliminating the
> winner and replaying all the games in which it took part to determine
> which one comes next. This step is repeated until all the players have
> been eliminated in order.
Just for the fun of it, I'ld include the BASIC source below. As far as
my BASIC knowledge goes (it's a while ago since I typed in BASIC code)
is not fully optimized, since it looks like it is starting new matches
all the time (finding numbers 1 and 2, not using the knowlegde to find
the number 3).
> The problem is that representing the games played and the winner
> of each is fairly difficult.
I did like the property of finding the second best one. And it is not
linear, but sorting will always take the same amount of time.
> For a rather naïve representation
> <cut>
That indeed was the idea.
> You can find a Rexx heap-sort by searching on Google. The first
> one I found was quite informative:
> <http://www.os2ezine.com/v3n01/rexx.htm>.
I will take a look at it!
Finally the original implementation in BASIC. On an OS/2 system, one
can run it (in a DOS box) with "QBASIC /RUN <SAVENAME.BAS>". It has
10 elements included (line numbers 30, and 70-90), so it just can
be useful to show how it is done.
It looks somehow like REXX, but don't ask me what "OPTION BASE 1"
actually means! :-)
----- <cut here> -----
10 OPTION BASE 1
11 REM ** Translations not embedded: AANTAL=number (of), NIVO=level,
12 REM HULP=help (/temp)
20 REM ** Initialize
30 MAX% = 10: HULP$ = CHR$(255)' high value
33 REM ** Because the number of elements must be even, it is possible
34 REM that the table by each step must be increased by 1. The maximum
35 REM number of steps is equal to the power of 2 required to minimal
36 REM match the number of elements. With 10 elements this is 4, since
37 REM 2^4=16 and 16>10.
38 REM ** English words are shorter than Dutch words, so I just will add
39 REM two meaningless lines to keep up with the line numbers
40 M2 = INT((LOG(MAX%) / LOG(2)) + 1)' determine power of 2
50 REM ** Z$ contains the elements
56 REM Y contains the indices of the winners
57 REM START contains the start of each new step
58 REM AANTAL contains the number of elements per step
60 DIM Z$(MAX% + M2), Y(MAX% + M2), START(M2 + 1), AANTAL(M2 + 1)
65 REM ** Fill table with to be sorted elements
70 FOR I = 1 TO MAX%
80 Z$(I) = STR$(MAX% - I)
90 NEXT I
100 REM ** Sort ascending **
110 NR% = 0' shows number of sorted elements
115 REM ** Stop if there are no more elements left
120 IF MAX% = 0 THEN STOP
125 REM ** Compare the elements for the first time
126 REM Yet another meaningless line (one may GOTO here)
130 NIVO = 1' first step
135 REM ** The number of winners is half
140 AANTAL(NIVO) = INT(MAX% / 2)
145 REM ** The first step begins with element 1
150 START(NIVO) = 1
155 REM ** If the number of elements is odd, the table Z$ will be
156 REM extended with one element, with the "high value"
157 REM Yet another meaningless line
158 REM Yet another meaningless line
160 IF MAX% = AANTAL(NIVO) * 2 THEN GOTO 200
170 MAX% = MAX% + 1' extension of the number of elements
180 Z$(MAX%) = HULP$' assignment of the "high value"
190 AANTAL(NIVO) = AANTAL(NIVO) + 1' number of elements first step+1
195 REM ** X0 increases by 2, and tus compares element 1 with
196 REM element 2, 3 with 4, 5 with 6, et cetera
200 X0 = 1: X1 = 1
205 REM ** Comparization of the 2 elements, remember the smallest
206 REM Yet another meaningless line
210 IF Z$(X0) < Z$(X0 + 1) THEN Y(X1) = X0 ELSE Y(X1) = X0 + 1
220 X0 = X0 + 2
230 X1 = X1 + 1
235 REM ** The loop stops after all elements are compared
236 REM Yet another meaningless line
240 IF X0 < MAX% THEN GOTO 210
245 REM ** After the first round the winners go to the next round. This
246 REM goes on until there is one winner left.
247 REM Yet another meaningless line
250 IF AANTAL(NIVO) = 1 THEN GOTO 390
260 NIVO = NIVO + 1' next round
265 REM ** Determination of the number of "matches" in the next round
270 AANTAL(NIVO) = INT(AANTAL(NIVO - 1) / 2)
275 REM ** Determine starting point in table Y
280 START(NIVO) = START(NIVO - 1) + AANTAL(NIVO - 1)
285 REM ** Check if the number of competitors is even
290 IF AANTAL(NIVO - 1) = AANTAL(NIVO) * 2 THEN GOTO 340
295 REM ** The number of competitors is made even
296 REM Number of competitios of the previous round is increased by 1
297 REM Yet another meaningless line
300 AANTAL(NIVO - 1) = AANTAL(NIVO - 1) + 1
305 REM ** The last competitor of the previous round plays against
306 REM itself
310 Y(START(NIVO)) = Y(START(NIVO) - 1)
315 REM ** Increase the number of matches by 1
320 AANTAL(NIVO) = AANTAL(NIVO) + 1
325 REM ** The starting point in table Y is increased by 1
330 START(NIVO) = START(NIVO) + 1
335 REM ** The first two competitors from the previous round are
336 REM compared with each other
340 X0 = START(NIVO - 1): X1 = START(NIVO)
350 IF Z$(Y(X0)) < Z$(Y(X0 + 1)) THEN Y(X1) = Y(X0) ELSE Y(X1) = Y(X0 + 1)
360 X0 = X0 + 2: X1 = X1 + 1
365 REM ** Have all competitors played?
370 IF X0 < START(NIVO) THEN GOTO 350
375 REM ** Next round
380 GOTO 250
385 REM ** The winner
390 W = Y(START(NIVO))
395 REM ** Check if the winner is the high value
396 REM If so, we are done
400 IF Z$(W) = HULP$ THEN GOTO 550
405 REM ** Print ranking and winner
410 NR% = NR% + 1: PRINT NR%; Z$(W)
415 REM ** The high value is assigned to the winner
420 Z$(W) = HULP$
425 REM ** Start again with round 1
430 NIVO = 1
435 REM ** Determine the place of the inner in the table Y
440 X1 = INT(W / 2)
445 REM ** X1 must be a whole number
450 IF W <> X1 * 2 THEN X1 = X1 + 1: W = W + 1
455 REM ** Determine the new winner
460 IF Z$(W - 1) < Z$(W) THEN Y(X1) = W - 1 ELSE Y(X1) = W
470 IF AANTAL(NIVO) = 1 THEN GOTO 390
475 REM ** Next round
480 NIVO = NIVO + 1: X0 = X1
490 X1 = INT(X0 / 2)
495 REM ** X0 must be a whole number
500 IF X0 <> X1 * 2 THEN X0 = X0 + 1: X1 = X1 + 1
510 X2 = START(NIVO - 1) + X0 - 1
520 X3 = START(NIVO) + X1 - 1
525 REM ** Determine new winner
530 IF Z$(Y(X2 - 1)) < Z$(Y(X2)) THEN Y(X3) = Y(X2 - 1) ELSE Y(X3) = Y(X2)
540 GOTO 470
550 REM ** End ascending sort
M1
> hobbes for a REXX program I wrote some time ago called "HELLO"
M1
> hobbes for a REXX program I wrote some time ago called "HELLO"
I'll check if your thoughts were right!
M1
Ian Collier
>If you guys are asking for what I THINK you're asking for, check on
>hobbes for a REXX program I wrote some time ago called "HELLO"
I checked... didn't find it. However, I suspect that what you mean by
"linear sort" isn't the same as what M1 means.
Ian Collier
>Just for the fun of it, I'ld include the BASIC source below. As far as
>my BASIC knowledge goes (it's a while ago since I typed in BASIC code)
>is not fully optimized, since it looks like it is starting new matches
>all the time (finding numbers 1 and 2, not using the knowlegde to find
>the number 3).
No, it's actually doing what I outlined previously; that is, eliminating
the winner and replaying just the games in which the winner took part.
However, instead of physically swapping the array elements it stores
the winners of all the games in the Y array. This saves time at the
expense of storage.
The two stages in the BASIC program are lines 200-380 (setting up all
the initial games) and 460-540 (replaying the winner's games).
Jaime A. Cruz, Jr.
Hash: SHA1
From: "Jaime A. Cruz, Jr." <Spam...@Bite.Me>
Message-ID: <wnvzrpehmanffnhjvat...@news-server.optonline.net>
References: <y82e+I0F...@uni-one.nl> <26298-ex...@comlab.ox.ac.uk> <b5nqq0$fl2$1...@ausnews.austin.ibm.com> <26299-b...@comlab.ox.ac.uk>
Date: Tue, 25 Mar 2003 07:13:04 -0500 (EST)
Reply-To: "Jaime A. Cruz, Jr." <Spam...@Bite.Me>
X-Newsreader: PMINews 2.00.1205 For OS/2
Organization: Nassau Wings Motorcycle Club
MIME-Version: 1.0
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
Subject: Re: Linear sort
/******************************* REXX *********************************/
/* REXX subroutine to sort items in the stack. */
/* This simple sort algorithm is based on a "3-index sort" I */
/* learned way back in school at the Grumman Data Systems */
/* Institute. The table will be sorted in one complete pass. All */
/* items to be sorted should be placed into the REXX stack. The */
/* first item in the stack to be read should contain the number of */
/* elements in the stack. Upon return to the calling routine, all */
/* items in the stack will be sorted in ascending sequence. This */
/* code is released to the public domain by the author. */
/**********************************************************************/
/* Load items in the stack into a table. */
/**********************************************************************/
Parse Pull table.0
Do x = 1 To table.0
Parse Pull table.x
End
/**********************************************************************/
/* If there is more than one element in the stack, sort them. */
/**********************************************************************/
If table.0 > 1 Then
Do x = 1 To table.0
y = x
Do z = (x + 1) To table.0
If table.y > table.z Then
y = z
End
If x <> y Then
Do
Push table.x
table.x = table.y
Parse Pull table.y
End
End
/**********************************************************************/
/* Dump the sorted elements back on to the stack FIFO */
/**********************************************************************/
Do x = 0 To table.0
Queue table.x
End
Return 0
Jaime A. Cruz, Jr.
o&o_o&o_o&o_o&o_o&o_o&o_o&o_o&o_o&o_o&o_o&o_o&o_o&o
o o
o Visit the Nassau Wings Motorcycle Club at: o
o http://www.nassauwings.org/ o
o A Charter Member of the Motorcycle Web Ring! o
o o
o&o_o&o_o&o_o&o_o&o_o&o_o&o_o&o_o&o_o&o_o&o_o&o_o&o
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.0 OS/2 for non-commercial use
Comment: PGP 5.0 for OS/2
Charset: cp850
wj8DBQE+gDnAgvzYfxgMc34RAuqVAKCUXjx5nKyCD6UUHiA1HQPK41MpjgCgwRUm
KXIrBSwVQPOTIgCNHdtCe8c=
=ApdV
-----END PGP SIGNATURE-----
Jim Mehl
> in Vladimir Zabrodsky book:
> Album of Algorithms and Techniques for Standard Rexx.
I can find no mention of this book on Amazon or Bookpool.
Could you tell us a little more about it?
Jim
Mark V
M1
>> as my BASIC knowledge goes (it's a while ago since I typed in BASIC
>> code) is not fully optimized, since it looks like it is starting new
>> matches all the time (finding numbers 1 and 2, not using the
> No, it's actually doing what I outlined previously; that is, eliminating
> the winner and replaying just the games in which the winner took part.
That's what the (not included) comments say too. But where is the
following logic happening?
Round 1: 1-3, ..., 2-4, ..., 127-128
Round ...:
Final: 1-2
The winner is 1. Given the above matches, the next item is the winner
of the game 2-3: the (new) winner is 2. Number 3 was beaten by 1 OR 2
and cannot be found by replaying the games of item 1 XOR 2. Maybe I'm
just overlooking this part, BTW... :-/
And I guess I found why the porting to REXX may have failed before. I
now did solve a tiny bug in the original BASIC source. I very well may
have missed that one during the first attempt.
> However, instead of physically swapping the array elements it stores
> the winners of all the games in the Y array. This saves time at the
> expense of storage.
As an aside: swapping variables with calculations is slower than using
a temporarly variable, most likely due to the calculations. I checked
that with the heap sort article you refered too earlier (without looking
at possible precision problems related to the calculations):
/* Fast swap, but it costs Gerard a few bytes of storage :-( */
a=7
b=1
temp=a
a=b
b=temp
/* Slow swap, but it may save Gerard a few bytes of storage :-) */
a=7
b=1
a=a+b
b=a-b
a=a-b
GerardS
The "slow" swap won't work, of course, with alpahbetic data. It can also
"fail", depending open NUMERIC DIGITS. Also, doing arithmetic on the values
may change it in ways that change the list of numbers into different
format(s).
Consider adding: 4.00 04 4 .4e1 +4 +04 00004 .4E1 .4E+1 __+_4_ where the
underbar is a blank, and 3.999999999999999999999999999999999999999999999999
or even 123456789012345678901234567890 with NUMERIC digits (say) set to the
default.
In REXX, you can swap two variables via: parse value a b with b a
which is probably the fastest swap (in REXX). _____________________Gerard S.
Wolfgang Riedel
It's online via
http://www.geocities.com/SiliconValley/Garage/3323/
(homepage) at
http://www.geocities.com/SiliconValley/Garage/3323/aat/index.html
Wolfgang
Ian Collier
wrote:
>The "slow" swap won't work, of course, with alpahbetic data. It can also
>"fail", depending open NUMERIC DIGITS. Also, doing arithmetic on the values
>may change it in ways that change the list of numbers into different
>format(s).
True.
>In REXX, you can swap two variables via: parse value a b with b a
>which is probably the fastest swap (in REXX). _____________________Gerard S.
However, if the data is alphabetic then it could quite easily contain
spaces too, which means the above won't work (in fact, one of your
numeric examples that I snipped contained spaces).
parse value a || '0'x || b with b '0'x a
would work (unless your data was seriously strange) but is on the ugly
side and probably no longer has a speed advantage.
Ian Collier
say:
> Do x = 1 To table.0
> y = x
> Do z = (x + 1) To table.0
> If table.y > table.z Then
> y = z
> End
> If x <> y Then
> Do
> Push table.x
> table.x = table.y
> Parse Pull table.y
> End
> End
Classic selection sort. As I suspected, though, it isn't "linear" in
the sense that M1 meant: it's O(n^2) and so is only good for small
values of n.
Ian Collier
scribbled some words to post to comp.lang.rexx:
[I said]
> > No, it's actually doing what I outlined previously; that is, eliminating
> > the winner and replaying just the games in which the winner took part.
>That's what the (not included) comments say too. But where is the
>following logic happening?
>
> Round 1: 1-3, ..., 2-4, ..., 127-128
> Round ...:
> Final: 1-2
>The winner is 1. Given the above matches, the next item is the winner
>of the game 2-3: the (new) winner is 2. Number 3 was beaten by 1 OR 2
>and cannot be found by replaying the games of item 1 XOR 2. Maybe I'm
>just overlooking this part, BTW... :-/
I'm not sure I understand what you are saying in this paragraph...
The first round is played in lines 200-240, which plays Z1 vs Z2, Z3 vs Z4
and so on, storing the winners in the Y array. The second round (and
all subsequent ones) is played in lines 250-380. If Z1 beats Z2 and
Z4 beats Z3 then obviously the first game played here is Z1 vs Z4.
If Z1 is the eventual winner then (in line 420) Z1 is eliminated.
The game Z1 vs Z2 will be replayed in line 460, obviously being won
by Z2 this time. Next, Z2 is played against Z4 (remembering that
Z4 beat Z3 in the first round); this takes place in lines 470-540.
In a similar manner, all the games that were originally won by Z1
will be replayed.
Now if Z2 is the second best overall then it will win all its games
and come out in second place. But if Z4 is the second best overall
then it will win its game against Z2 and it will be Z4 that comes out
the eventual winner. On the other hand, if Z127 is the second best
and Z4 is third best then Z4 will be promoted all the way to the final
but will lose out to Z127 in the last game.
M1
>> Round ...:
>> Final: 1-2
>> The winner is 1. Given the above matches, the next item is the winner
>> of the game 2-3: the (new) winner is 2. Number 3 was beaten by 1 OR 2
>> and cannot be found by replaying the games of item 1 XOR 2. Maybe I'm
>> just overlooking this part, BTW... :-/
> I'm not sure I understand what you are saying in this paragraph...
> On the other hand, if Z127 is the second best and Z4 is third best
> then Z4 will be promoted all the way to the final but will lose out
> to Z127 in the last game.
I was kind of thinking about the elimination of that promotion by using
(more memory and) a result tree to avoid replaying some matches. The
second lost always of the winner and the third best always is beaten
by the winner OR the second best.
If 1-2 was an original quarter-final, and there are 128 competitors, it takes
127 matches to find the winner. Number 2 can occur in any of the 7 matches
that 1 has won. Number 3 then occurs in any of those 7 (won by 1) and 4
(won by 2) matches. That way, you may be excluding branches of the tree
until it becomes more effective to replay matches with (let's say) the
remaining 125 competitors (4-128)?
Jaime A. Cruz, Jr.
Hash: SHA1
From: "Jaime A. Cruz, Jr." <Spam...@Bite.Me>
Message-ID: <wnvzrpehmanffnhjvat...@news-server.optonline.net>
References: <y82e+I0F...@uni-one.nl> <b5nqq0$fl2$1...@ausnews.austin.ibm.com> <26299-b...@comlab.ox.ac.uk> <wnvzrpehmanffnhjvat...@news-server.optonline.net> <26302-nob...@comlab.ox.ac.uk>
Date: Wed, 26 Mar 2003 17:57:51 -0500 (EST)
Reply-To: "Jaime A. Cruz, Jr." <Spam...@Bite.Me>
X-Newsreader: PMINews 2.00.1205 For OS/2
Organization: Nassau Wings Motorcycle Club
MIME-Version: 1.0
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
Subject: Re: Linear sort
Okay, then I'm not sure what he meant. In the algorithm below, the outer
loop only makes one pass through the data, each succeeding iteration being
smaller and smaller. I haven't seen anything faster...
Jaime A. Cruz, Jr.
o&o_o&o_o&o_o&o_o&o_o&o_o&o_o&o_o&o_o&o_o&o_o&o_o&o
o o
o Visit the Nassau Wings Motorcycle Club at: o
o http://www.nassauwings.org/ o
o A Charter Member of the Motorcycle Web Ring! o
o o
o&o_o&o_o&o_o&o_o&o_o&o_o&o_o&o_o&o_o&o_o&o_o&o_o&o
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.0 OS/2 for non-commercial use
Comment: PGP 5.0 for OS/2
Charset: cp850
wj8DBQE+giJfgvzYfxgMc34RAuxzAKDwkSqD96nR271pnTsR+TI5HG+ZHgCaAvj2
JcHUtxF+2+rYofnla69TEWc=
=2nAs
-----END PGP SIGNATURE-----
GerardS
| Okay, then I'm not sure what he meant. In the algorithm below, the outer
| loop only makes one pass through the data, each succeeding iteration being
| smaller and smaller. I haven't seen anything faster...
|> Ian Collier wrote:
|>> Jaime A. Cruz, Jr. wrote:
|>> Do x = 1 To table.0
|>> y = x
|>> Do z = (x + 1) To table.0
|>> If table.y > table.z Then
|>> y = z
|>> End
|>> If x <> y Then
|>> Do
|>> Push table.x
|>> table.x = table.y
|>> Parse Pull table.y
|>> End
|>> End
|> Classic selection sort. As I suspected, though, it isn't "linear" in
|> the sense that M1 meant: it's O(n^2) and so is only good for small
|> values of n.
Just for curosity's sake, why use the "stack" to hold a temporary variable?
I would think that (pushing/pulling):
do
push table.x
table.x=table.y
parse pull table.y
end
would be somewhat slower than"
do
temp=table.x
table.x=table.y
table.y=temp
end
_________________________________________________________________Gerard S.
Ian Collier
>I was kind of thinking about the elimination of that promotion by using
>(more memory and) a result tree to avoid replaying some matches. The
>second lost always of the winner and the third best always is beaten
>by the winner OR the second best.
It is already as efficient as it can be. The result tree is already
held in the array Y.
>If 1-2 was an original quarter-final, and there are 128 competitors, it takes
>127 matches to find the winner. Number 2 can occur in any of the 7 matches
>that 1 has won. Number 3 then occurs in any of those 7 (won by 1) and 4
>(won by 2) matches.
Not sure where you are getting that 4 from. Certainly you have to
examine 7 matches in order to find number 2, as it could have been
beaten by 1 in any round from the first to the final. If number 2
went all the way to the final then number 3 could have been beaten
by 2 in any round from the first to the semi-final, so that's 6 matches
you have to examine, together with the 6 matches in which number 1 won,
*if* you are still looking at the original result tree.
The point of the program is that while you re-examine the games played
by number 1 (in order to find number 2) you re-write the results table
for those games so that you don't have to re-examine them when looking
for number 3. Thus the program replays exactly 7 games for every winner
other than the first.
> That way, you may be excluding branches of the tree
>until it becomes more effective to replay matches with (let's say) the
>remaining 125 competitors (4-128)?
By keeping the results table up to date it never becomes necessary to
replay all the matches (if it did then the algorithm would be no more
efficient than any of the other O(N^2) sorting algorithms we know and
love, and would be more complicated into the bargain).
Jaime A. Cruz, Jr.
stack is a standard REXX construct that didn't need creating, whereas a
temporary variable would need to be created and initialized by the REXX
runtime...
Don Hills
"Jaime A. Cruz, Jr." <jaim...@us.ibm.com> wrote:
>Honestly, I don't know. I've never done any timings, but I figure the
>stack is a standard REXX construct that didn't need creating, whereas a
>temporary variable would need to be created and initialized by the REXX
>runtime...
Sigh... lots of earnest and learned conjecture, but no-one has taken 5
minutes to actually try it <grin>. In the case of temp variable versus
push/pull, the temp variable method is much faster. This makes sense,
because the stack isn't a simple stack - it is a complex queue / pipe
mechanism. On the other hand, assigning a value to a variable is one of the
most common operations performed in REXX so it would hopefully have been
carefully optimised.
Note that the parse method is even faster, but as pointed out earlier it is
not a general purpose method because it doesn't work with embedded spaces.
/**/
x = 1
y = 2
table.x = 'abcdefghijklmnopqrstuvwxyz'
table.y = table.x
iterations = 10000
call time 'R'
do iterations;
temp = table.x
table.x = table.y
table.y = temp
end;
say 'Temp variable:' time('E')
call time 'R'
do iterations;
push table.x
table.x = table.y
parse pull table.y
end;
say 'Push/Pull:' time('E')
call time 'R'
do iterations;
parse value a b with b a
end;
say 'Parse swap:' time('E')
--
Don Hills (dmhills at attglobaldotnet) Wellington, New Zealand
"I don't use Linux. I prefer to use an OS supported by a large multi-
national vendor, with a good office suite, excellent network/internet
software and decent hardware support."
M1
>> it takes 127 matches to find the winner. Number 2 can occur in any
>> of the 7 matches that 1 has won. Number 3 then occurs in any of those
>> 7 (won by 1) and 4 (won by 2) matches.
> Not sure where you are getting that 4 from.
It may not even be worth the trouble, but if number 1 beat number 2 in
the fifth round, number 3 can be found in the matches that 1 won (other
than the game 1-2), or in the (4) matches that 2 won, before number 2
was beaten by number 1.
Ian Collier
wrote:
>Okay, then I'm not sure what he meant. In the algorithm below, the outer
>loop only makes one pass through the data, each succeeding iteration being
>smaller and smaller. I haven't seen anything faster...
I'll be posting more on this in a few days. However, the method you
refer to (that is, "selection sort") is the third slowest method I know
for sorting a fair number of items [tested at n=250].
The thing is, your inner loop isn't actually that small. It starts
off at size n and decreases by 1 each time; so the average size of
this loop is about n/2. This means that with the outer loop, your
algorithm performs about n*n/2 operations. On the other hand, the
heap-sort algorithm whose url was posted earlier in this thread performs
about n/2*log2(n) operations while creating the heap and then at most a
further log2(n) operations to move each element to its final position in
the array - so about 3n/2*log2(n) in total.
With n=250, log2(n) is 8 so if the above is correct then selection
sort takes about 31250 operations while heap sort takes about 3000.
Of course, the operations for heap sort are more complex, but they
are nowhere near ten times as complex.
Ian Collier
>On Wed, 26 Mar 2003 22:57:49 GMT, Jaime A. Cruz, Jr. <Spam...@Bite.Me>
>wrote:
>>Okay, then I'm not sure what he meant. In the algorithm below, the outer
>>loop only makes one pass through the data, each succeeding iteration being
>>smaller and smaller. I haven't seen anything faster...
>I'll be posting more on this in a few days.
Well, Easter and various other things got in the way so it turned out to
be slightly more than a few days. However, I can now present 16 sorting
algorithms in Rexx and their timing tests over 100 to 50000 data elements:
http://users.comlab.ox.ac.uk/ian.collier/rexxla/sorting/
I'm afraid that Jaime's algorithm still turned out to be the third slowest
(with only the two bubblesorts being slower). I also implemented M1's
tournament method, but it fared a lot less well than expected.
As a taster, here is the first table of timing results (in seconds)
based on sorting random 7-digit fixed-point numbers.
100 200 500 1000 2000 5000 10000 20000 50000
bubble 0.331 1.40 9.57 41.9 190 - - - -
bubble2 0.279 1.15 8.36 35.7 166 - - - -
selection 0.213 0.863 5.92 27.3 118 - - - -
shaker 0.160 0.659 4.55 20.9 92.4 822 - - -
insertion 0.135 0.595 4.04 16.9 76.1 664 - - -
sshell 0.138 0.393 1.35 3.79 10.9 52.9 160 544 -
tournament 0.120 0.298 0.928 2.39 6.38 27.4 82.5 294 1625
comb 0.066 0.196 0.583 1.59 4.26 16.2 46.1 121 713
shell 0.060 0.150 0.490 1.23 3.42 14.0 39.5 121 651
lmerge 0.072 0.175 0.529 1.25 3.07 11.4 29.9 84.2 390
smerge 0.060 0.143 0.403 0.950 2.36 9.40 27.6 99.0 572
merge 0.065 0.157 0.457 1.08 2.55 8.84 21.8 57.3 243
quick 0.045 0.115 0.349 0.844 2.10 7.33 19.1 52.6 253
heap 0.068 0.166 0.490 1.11 2.60 8.09 18.8 46.4 162
radix 0.040 0.108 0.515 0.654 1.85 9.71 15.7 47.8 325
iradix 0.039 0.100 0.268 0.595 1.64 4.66 12.0 38.1 130
Jaime A. Cruz, Jr.
I'll check your page when I have more time. Thanks.
Jaime A. Cruz, Jr.
M1
> to be slightly more than a few days.
> http://users.comlab.ox.ac.uk/ian.collier/rexxla/sorting/
I'll check it out tomorrow; thanks anyway for your both helpfull and
interesting efforts!
> I also implemented M1's tournament method, but it fared a lot less
> well than expected.
> sshell 0.138 0.393 1.35 3.79 10.9 52.9 160 544 -
> tournament 0.120 0.298 0.928 2.39 6.38 27.4 82.5 294 1625
Looks like it was the next one to be excluded from publishing results. :-|
Maybe it has something to do with the way REXX is executed (regarding
optimization, et cetera), but OTOH one cannot really write a REXX
sorting routine without using REXX as is.
---
Tim White
...
>
> 100 200 500 1000 2000 5000 10000 20000 50000
.
> radix 0.040 0.108 0.515 0.654 1.85 9.71 15.7 47.8 325
> iradix 0.039 0.100 0.268 0.595 1.64 4.66 12.0 38.1 130
If the value of the variable "small" is 30 (instead of 70) in the
"radixsort" procedure (as it is in "iradixsort") then the results
for both procedures don't diverge as much for the 500, 5000 and
50000 data points???
Tim White
Ian Collier
You appear to be correct. Note that the optimum value of this constant
is heavily dependent on the interpreter and the type of data being
sorted. The number 70 seemed about right for sorting character strings,
but a smaller value would probably have been better for numerics.
With the value 30, the results from the above table would have looked
like this:
radix 0.041 0.108 0.303 0.666 1.83 6.20 15.7 49.2 280
As you have noted, this differs chiefly in the columns 500, 5000 and 50000.
Why might that be?
Well, we are sorting random numbers. So when dividing the data into
piles, there will usually be ten roughly equal piles. If we start with
50,000 elements then we will have 10 piles of about 5000 elements each.
Each of those will be divided into piles of about 500 elements, and
yet again into piles of about 50 elements. This is where the "small"
constant kicks in. If it is 70 then these piles will be considered
small enough to go to insertion sort, but if it is 30 then the piles
will usually be radix-sorted one more time into piles of 5 elements.
It turns out that the latter is quicker when we are sorting numbers
(but probably not when sorting character strings, because there are
more piles to deal with).
If we start with 10,000 or 20,000 elements and perform the
above analysis then it turns out that small=70 and small=30 give
indistinguishable results. That's why the timing data for these
cases don't show much difference between the two values of "small".
Tim White
...An excellent explanation of the interaction of the value of the
constant "small" with the type of data sorted (numeric/string) and
the size of the data set. (See Ian's previous message)
Thanks Ian. I was about to go to sleep when I sent the question,
and my brain was already going into power-down. I guessed you would
reason it out in short order (and probably wouldn't be able to resist
the 'challenge').
Your Sorting in Rexx page at
http://users.comlab.ox.ac.uk/ian.collier/rexxla/sorting/
is a most worthwhile addition to my references on Rexx stuff - and I
recommend it highly. Bet you had much fun doing it too!
Tim White