OpenEuphoria

allsorts.ex

• Posted by Steve Baxter <candotec at hotmail.com> Sep 22, 2006
• 489 views

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!