Announcement

Collapse
No announcement yet.

Non recursive Quick Sort

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Non recursive Quick Sort

    I have managed to convert Ethan Winer's 1992 QB quick sort to
    PowerBASIC inline assembler. Ethan's original algorithm was fast
    as it was ported to PowerBASIC code but with the reduction of
    instructions written in assembler, its speed has increased by a
    reasonable amount.

    On my own box, a 600 PIII, it sorts a million randomly generated
    LONG integers in about 560 milliseconds which is starting to become
    competitive in speed terms. It is about 5 times faster on this type
    of data than the Comb Sort I posted before.

    The encoding is reasonably efficient, it could probably be tweaked here
    and there but there are no real speed gains left in it, there was some
    gain in the loop code but the real gains in speed were in the capacity
    to handle the array data directly in assembler. This algo is destined
    for MASM as it does not have PowerBASIC's built in array support.

    The low level power of PowerBASIC has made porting high level code to assembler
    a far simpler task than some toothless OOP terror and its capacity to
    prototype code for MASM would make it a compiler with an unusually
    powerful capacity.

    It is easy enough to use, the first parameter is the address of the first
    element in the array that needs to be sorted, the second parameter is
    the number of elements that are to be sorted.
    Code:
    Prototypes
    ~~~~~~~~~~
        DECLARE FUNCTION SysAllocStringByteLen LIB "oleaut32.dll" _
                         alias "SysAllocStringByteLen" _
                         (ByVal cpyString as LONG,ByVal bytelen as LONG) as LONG
      
        DECLARE FUNCTION SysFreeString LIB "oleaut32.dll" _
                         alias "SysFreeString" _
                         (ByVal strhandle as LONG) as LONG
      
    Code
    ~~~~
        nrQsort VarPtr(MyArray(0)),1000
      
    Algorithm
    ~~~~~~~~~
      ' #########################################################################
      
      SUB nrQsort (ByVal Arr as LONG,ByVal count as LONG)
      
          #REGISTER NONE
      
          LOCAL First as LONG
          LOCAL Last  as LONG
          LOCAL cntr  as LONG
          LOCAL bLen  as LONG
          LOCAL hMem  as LONG
          LOCAL temp  as LONG
      
          ! mov esi, Arr              ; source address in ESI
      
        ' --------------------------
        ' allocate temporary buffer
        ' --------------------------
          ! mov eax, count
          ! add eax, 40
          ! mov bLen, eax
          SysAllocStringByteLen 0, bLen
          ! mov hMem, eax
          ! mov edi, hMem             ; buffer address in EDI
      
        ' ------------------------------------
        ' set First and Last reference values
        ' ------------------------------------
          ! mov First, 0
          ! mov eax, count
          ! dec eax
          ! mov Last, eax             ; Last = count - 1
      
        outer_loop:
        ' -------------------
        ' calculate midpoint
        ' -------------------
          ! mov eax, Last
          ! add eax, First
          ! shr eax, 1
          ' =========================
          ! mov ebx, [esi+eax*4]      ; midpoint in EBX
          ! mov temp, ebx
          ' =========================
          ! mov ecx, First
          ! mov edx, Last
        ' ---------------------------------------------------------
        inner_loop:
          ! cmp [esi+ecx*4], ebx
          ! jge wl2                   ; JLE for descending sort
          ! inc ecx
          ! jmp inner_loop
        wl2:
          ! cmp [esi+edx*4], ebx
          ! jle wl2Out                ; JGE for descending sort
          ! dec edx
          ! jmp wl2
        wl2Out:
          ! cmp ecx, edx              ; If ecx > edx, exit inner loop
          ! jg exit_innerx
          ' =========================
          ! mov eax, [esi+ecx*4]
          ! mov ebx, [esi+edx*4]      ; swap elements
          ! mov [esi+ecx*4], ebx
          ! mov [esi+edx*4], eax
          ' =========================
          ! mov ebx, temp             ; restore EBX
          ! inc ecx
          ! dec edx
          ! cmp ecx, edx
          ! jle inner_loop
        exit_innerx:
        ' ---------------------------------------------------------
          ! cmp ecx, Last             ; If ecx < Last jump over
          ! jg iNxt
          ' =========================
          ! mov eax, cntr
          ! mov [edi+eax*4], ecx
          ! mov ebx, Last
          ! mov [edi+eax*4+4], ebx
          ' =========================
          ! add cntr, 2
        iNxt:
          ! mov ebx, temp             ; restore EBX
          ! mov Last, edx             ; Last  = EDX
          ! cmp edx, First            ; compare Last & First
          ! jg outer_loop
      
          ! cmp cntr, 0
          ! jz qsOut
          ! sub cntr, 2
          ' =========================
          ! mov eax, cntr
          ! mov ebx, [edi+eax*4]
          ! mov First, ebx
          ! mov ebx, [edi+eax*4+4]
          ! mov Last, ebx
          ' =========================
          ! mov ebx, temp             ; restore EBX
          ! jmp outer_loop
      
          qsOut:
      
          SysFreeString hMem
      
      END SUB
      
      ' #########################################################################
    Regards,

    [email protected]


    [This message has been edited by Steve Hutchesson (edited September 19, 2001).]
    hutch at movsd dot com
    The MASM Forum

    www.masm32.com

  • #2
    Steve , is this sort just for long integers ? I tried it with a string array and the results are all over the place.
    In the following program I would have expected a line of '@' on the first few lines but I get lines starting with 'A' before lines starting with '@' etc.

    Regards

    Adrian

    Code:
    global MyArray() as string
    
    ...
    your sort routine
    ...
    FUNCTION PBMAIN()
        DIM i AS DOUBLE
        REDIM MyArray(1000000)
        FOR i=0 TO 1000000
            MyArray(i) = CHR$((RND(i) AND 31) +64) + CHR$((RND(i) AND 31) +64) + CHR$((RND(i) AND 31) +64) + CHR$((RND(i) AND 31) +64) + CHR$((RND(i) AND 31) +64) + CHR$((RND(i) AND 31) +64) + CHR$((RND(i) AND 31) +64)
        NEXT
        MSGBOX "ready ?"
        nrQsort VARPTR(MyArray(0)),1000000
        MSGBOX "done"
        OPEN "c:\output.txt" FOR OUTPUT AS #1
        FOR i=0 TO 100
            PRINT #1,Myarray(i)
        NEXT
        CLOSE
       
    END FUNCTION
    ------------------

    Comment


    • #3
      In this circumstance, a string buffer would be sorted in "blocks" of 4 characters, since LONG integers are 4 bytes wide.

      ------------------
      Lance
      PowerBASIC Support
      mailto:[email protected][email protected]</A>
      Lance
      mailto:[email protected]

      Comment


      • #4
        Adrian,

        This sort routine is specifically for LONG integer arrays.

        You would be very hard pressed to improve on Bob's code for sorting
        string arrays and string sorts are a very different animal.

        I am using PowerBASIC to prototype sorting algorithms for MASM as
        MASM does not have the built in sorting support that PowerBASIC does.

        This version is competitively fast in the LONG arrays it is written
        to sort but to make the point, the sorting capacity in PowerBASIC is
        very fast anyway so unless you specifically need to target a LONG
        integer array in a sub range of its dimension, the standard one would
        be preferred.

        Regards,

        [email protected]

        ------------------
        hutch at movsd dot com
        The MASM Forum

        www.masm32.com

        Comment


        • #5
          Anyone care to post an example with COMPLETE code?
          I am having difficulty making this work......

          Steve Geisler

          ------------------

          Comment


          • #6
            Steve,

            This is the simplest of the test code that I was using to develop this algo
            once it was ported to PowerBASIC from the old Quick Basic.

            Code:
                redim a(1 to 20) as LONG
              
                a(1)  = 9
                a(2)  = 3
                a(3)  = 11
                a(4)  = 7
                a(5)  = 16
                a(6)  = 6
                a(7)  = 12
                a(8)  = 13
                a(9)  = 14
                a(10) = 18
                a(11) = 1
                a(12) = 20
                a(13) = 8
                a(14) = 5
                a(15) = 15
                a(16) = 17
                a(17) = 4
                a(18) = 19
                a(19) = 2
                a(20) = 10
              
                nrQsort VarPtr(a(1)),20
            The two parameters are the address of the first element to be sorted, the
            second is the count of the number of elements to be sorted. If you are doing
            general purpose array work, I would strongly advise using the standard
            PowerBASIC sorting functions, they are both fast and reliable.

            A friend of mine has found a problem that appears to be in the original
            algorithm and it can be reproduced with data in the following form.

            123456-123456 in an array is a theoretical worst case for a quick sort but
            when the data is constructed exactly in this form, the algorithm crashes and
            I have not had time to track it down yet. I am probably stuck with having to
            redesign the algo from scratch to avoid problems of this type.

            Regards,

            [email protected]

            ------------------
            hutch at movsd dot com
            The MASM Forum

            www.masm32.com

            Comment

            Working...
            X