1. allsorts.ex
First, amazing news about the new direction for Euphoria. Just amazing.
Now, the allsorts.ex demo program included with the standard installation
of Euphoria is a delight because it compares different famous sort alorithms
dynamically under various conditions. But the shell sort has consistently
outperformed the quicksort. This runs counter to theory and experience.
I replaced the algorithm with one I use with a marked improvement that is
line with my past experience. The quicksort algorithm was translated to
Euphoria from code written by Ethan Winer for QuickBASIC.
Most quicksort algorithms rely on recursion, but recursion is not necessary
and better performsnce is possible without it. I have included the routine
routine that avoides recursion.
function quick_sort(sequence Array)
sequence QStack
integer First, Last, StackPtr, I, J, tmp, Temp
QStack = repeat(0,floor((length(Array)/5) + 10)) -- create a stack
First = 1
Last = length(Array)
StackPtr = 0
while 1 do
while 1 do
Temp = Array[floor(Last + First) / 2]
I = First
J = Last
while 1 do
while Array[I] < Temp do
I += 1
end while
while Array[J] > Temp do
J -= 1
end while
if I > J then exit end if
if I < J then
tmp = Array[I] Array[I] = Array[J] Array[J] = tmp
end if
I += 1
J -= 1
if I > J then
exit
end if
end while
if I < Last then
QStack[StackPtr + 1] = I
QStack[StackPtr + 2] = Last
StackPtr += 2
end if
Last = J
if First >= Last then
exit
end if
end while
if StackPtr = 0 then
exit
end if
StackPtr -= 2
First = QStack[StackPtr + 1]
Last = QStack[StackPtr + 2]
end while
return Array
end function
>>> Thanks!
