Sorting Arrays

[Moneo]

Aga,

Here's a copy of your slightly modified code as is appears in my test version of SortDemo.

Code:

SUB AgaSort (a.max%)

DIM g2(1 TO a.max%) AS INTEGER, h2(1 TO a.max%) AS INTEGER
DIM i AS INTEGER, j AS INTEGER, r AS INTEGER
DIM E AS INTEGER, g AS INTEGER, h AS INTEGER
rem DIM k AS LONGINT
DIM k as integer

E = 1: g2(1) = 1: h2(1) = a.max%
f1: g = g2(E): h = h2(E)
f2: i = g: j = h: r = (g + h) \ 2: k = Sortarray(r).length
f3: IF Sortarray(i).length < k THEN i = i + 1: GOTO f3
f4: IF Sortarray(j).length > k THEN j = j - 1: GOTO f4
IF i <= j THEN SWAP Sortarray(i),Sortarray(j): SwapBars i,j:i = i + 1: j = j - 1: IF i <= j THEN GOTO f3
IF j - g + i < h THEN
IF i < h THEN g2(E) = i: h2(E) = h: E = E + 1
h = j
ELSE
IF g < j THEN g2(E) = g: h2(E) = j: E = E + 1
g = i
END IF
IF g < h THEN GOTO f2 ELSE E = E - 1: IF E THEN GOTO f1
ERASE g2, h2
END SUB

*****

[Agamemnus]

Can you just give me a link to the file you tested? That would be nice..

[Moneo]

Can you just give me a link to the file you tested? That would be nice..

Aga, sent you the entire program file in an email.

EDIT: Since I got a copy of the mail, I noticed that on the mail, some of the original lines in your code are missing a carriage-return and line feed at the end of the line. I don't understand why.
*****

[Agamemnus]

thanks.

you probably used notepad to save it at some point.

notepad usually creates carriage returns whenever the text starts at a new line in the window, when you save the file. :|

Ok, I figured it out. One of the code pieces was slightly slower than his. I had used an earlier version of his code to create mine, I think..

This runs at the same speed as his:

Code:

SUB AgaSort (amax AS INTEGER)

DIM g2(1 TO 32) AS INTEGER, h2(1 TO 32) AS INTEGER
DIM i AS INTEGER, j AS INTEGER, r AS INTEGER
DIM e AS INTEGER, g AS INTEGER, h AS INTEGER
REM DIM k AS INTEGER
DIM k AS INTEGER

e = 1
g2(1) = 1
h2(1) = amax
f1: g = g2(e): h = h2(e)
f2: i = g: j = h: r = (g + h) \ 2: k = Sortarray(r).length
f3: IF Sortarray(i).length < k THEN i = i + 1: GOTO f3
f4: IF Sortarray(j).length > k THEN j = j - 1: GOTO f4

IF i <= j THEN
IF i < j THEN SWAP Sortarray(i), Sortarray(j): SwapBars i, j
i = i + 1: j = j - 1
IF i <= j GOTO f3
END IF

IF j - g + i < h THEN
IF i < h THEN g2(e) = i: h2(e) = h: e = e + 1
h = j
ELSE
IF g < j THEN g2(e) = g: h2(e) = j: e = e + 1
g = i
END IF

IF g < h THEN GOTO f2
e = e - 1
IF e THEN GOTO f1
ERASE g2, h2
END SUB

[Moneo]

Aga,

Congratulations! I tested it, and like you said, your sort algorithm runs just as fast as Ethan Winer's version of the Quicksort.

That puts your algorithm into the elite class of the best sort algorithms ever developed, and perhaps the best overall. :bounce:

You need to give your algorithm a name so it can be easily identified and distinguished from all the other slower solutions.

I'm happy too. Now I can say I know the man who wrote the fastest sort algorithm.
*****

[Agamemnus]

The Ethan Weiner Duplicate :|

[Moneo]

The Ethan Weiner Duplicate :|

Aga,

Don't sell your implementation short. Granted, yours and Ethan Winer's implementation are fundamentally a Quicksort approach.

However, I compared your code to Winer's, and they are quite different. There's no way you could say that yours was modelled after his. The similarities are only in design; that is, they basically do a form of Quicksort, replace the original Quicksort recursion by handling a proprietary stack, and do not compute a random pivot position, using a simple half-way point instead.

So, I think your sort algorithm deserves a name. Meanwhile, here at QBN, we can refer to it as the AgaSort.
*****

[Dr_Davenstein]

Awesome!

Hey, why don't you call it a GotoSort?

[Agamemnus]

Thanks,

But again I say that my code was made from GOTOing his previous code, converting the one array to two arrays, and reducing the variable length.

GOTOsort.

I like it.

[relsoft]

Fruitysort?