Announcement

Collapse
No announcement yet.

Writing a bubble sort in PowerBASIC

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

  • Writing a bubble sort in PowerBASIC

    I had the time today to play with a very simple bubble sort algorithm. I
    had a rather badly coded Pascal version so I converted it to PowerBASIC
    without some of the "structured" irritations and it ran OK so I recoded
    it from scratch in PowerBASIC inline assembler and got it a lot smaller
    and somewhat faster.

    Comparing bubble sorts is like watching snails race down a garden path
    as there are others that are much better designs but it is useful when
    only doing small simple single dimension arrays. In my own case, MASM
    does not have the high speed sorting that come with PowerBASIC so I am
    stuck with having to develop a few to do basic stuff.

    The format of both is "ascending" on DWORD/LONG size data in an array.

    Regards,

    [email protected]

    Code:
    Test Code
    ~~~~~~~~~
    
                redim a(1 to 20) as LONG
      
                a(1)  = 95
                a(2)  = 84
                a(3)  = 100
                a(4)  = 99
                a(5)  = 91
                a(6)  = 98
                a(7)  = 94
                a(8)  = 92
                a(9)  = 96
                a(10) = 93
                a(11) = 90
                a(12) = 81
                a(13) = 88
                a(14) = 83
                a(15) = 97
                a(16) = 85
                a(17) = 87
                a(18) = 86
                a(19) = 82
                a(20) = 89
      
                ' bubblesort 1,20,a()   ' PB high level version
    
                bSort 1,20,VarPtr(a(1))  ' PB assembler version
      
                lf$ = chr$(13,10)
      
                tst$ = str$(a(1))+lf$ + _
                       str$(a(2))+lf$ + _
                       str$(a(3))+lf$ + _
                       str$(a(4))+lf$ + _
                       str$(a(5))+lf$ + _
                       str$(a(6))+lf$ + _
                       str$(a(7))+lf$ + _
                       str$(a(8))+lf$ + _
                       str$(a(9))+lf$ + _
                       str$(a(10))+lf$ + _
                       str$(a(11))+lf$ + _
                       str$(a(12))+lf$ + _
                       str$(a(13))+lf$ + _
                       str$(a(14))+lf$ + _
                       str$(a(15))+lf$ + _
                       str$(a(16))+lf$ + _
                       str$(a(17))+lf$ + _
                       str$(a(18))+lf$ + _
                       str$(a(19))+lf$ + _
                       str$(a(20))
      
                MessageBox hWin,ByCopy tst$,"Sorted", _
                           %MB_OK or %MB_ICONINFORMATION
    
    2 Bubble sort algorithms
    ~~~~~~~~~~~~~~~~~~~~~~~~
      
    '##########################################################################
      
    FUNCTION bubblesort(ByVal st as LONG, _         ' array start
                        ByVal nd as LONG, _         ' array end
                        Arr() as LONG) as LONG      ' array
      
        LOCAL i as LONG
        LOCAL j as LONG
        LOCAL dmy as LONG
      
          For j = st to nd
            i = j
            While Arr(st) and Arr(i) < Arr(i-1)
              dmy = Arr(i)
              Arr(i) = Arr(i-1)
              Arr(i-1) = dmy
              ! dec i
            Wend
          Next
      
        FUNCTION = 0
      
    END FUNCTION
      
    '##########################################################################
      
    FUNCTION bSort(ByVal st  as LONG, _             ' array start
                   ByVal nd  as LONG, _             ' array end
                   ByVal Arr as LONG) as LONG       ' array address
      
        #REGISTER NONE
      
        ! mov esi, Arr
        ! sub esi, 4
        ! mov ebx, nd
        ! sub ebx, st
        ! inc ebx               ; EBX holds element count
        ! xor ecx, ecx          ; set outer loop counter to 0
      
      lbSt:
        ! mov edx, ecx
      lbNxt:
      ' -----------------
      ' compare elements
      ' -----------------
        ! mov eax, [esi+edx*4]
        ! cmp eax, [esi+edx*4+4]
        ! jl lbOut
      ' --------------
      ' swap elements
      ' --------------
        ! mov edi, [esi+edx*4]
        ! mov eax, [esi+edx*4+4]
        ! mov [esi+edx*4], eax
        ! mov [esi+edx*4+4], edi
        ! dec edx
        ! jmp lbNxt
      lbOut:
        ! inc ecx
        ! cmp ecx, ebx
        ! jne lbSt
      
        FUNCTION = 0
      
    END FUNCTION
      
    '##########################################################################
    ------------------
    hutch at movsd dot com
    The MASM Forum

    www.masm32.com

  • #2
    Hutch

    Talking of simple sorting routines, have you ever come across
    "combsort". I've used it with success in Fortran codes.

    Code:
          SUBROUTINE CombSort (array, rank, maxRow)
            INTEGER rank(1: *), maxRow, i, j, gap, temp
            REAL array(1: *)
            LOGICAL switch
     
            gap = maxRow
    10      CONTINUE
              gap = (gap * 10) / 13     !Much faster than INT(REAL(gap) / 1.3)
              IF (gap .EQ. 0) THEN
                gap = 1
              ELSEIF ((gap .EQ. 9) .OR. (gap .EQ. 10)) THEN
                gap = 11
              ENDIF
     
              switch = .FALSE.
              DO 20 i = 1, maxRow - gap
                j = i + gap
                IF ( array(rank(i)) .GT. array(rank(j)) ) THEN
                  temp = rank(i)
                  rank(i) = rank(j)
                  rank(j) = temp
                  switch = .TRUE.
                ENDIF
    20        CONTINUE
            IF (switch .OR. (gap .GT. 1)) GOTO 10
     
          END
    Regards,
    Keith

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

    Comment


    • #3
      Keith,

      Yes, I have used CombSort a lot in both Access and VB/VBA. It was published in the
      April 1991 edition of Byte magazine, by Stephen Lacey and Richard Box - a fascinating
      article. As you probably know - but for the benefit of others reading this - it
      succeeds over bubble sorts principally by addressing the problem of 'turtles'
      (grossly out-of-place elements in the sort), which in a bubble sort, take a long time
      to 'bubble up' into place.

      I've only ever used it on small data sets, but it runs in a blink (technical term ).
      Not yet found a need to port it to PowerBASIC.

      Regards,

      Paul


      ------------------
      http://www.zippety.net
      mailto[email protected][email protected]</A>
      Zippety Software, Home of the Lynx Project Explorer
      http://www.zippety.net
      My e-mail

      Comment


      • #4
        Quite a few years ago I was trying to get a faster way of sorting
        data and tried a routine in GWBASIC then in TURBO BASIC. The 1,000
        lines of data sorted in something like six minutes in GWBASIC and
        around two minutes in TURBO BASIC.

        I was telling a friend of my experiment and he said I should try
        POWER BASIC which was the fastest DOS programming he'd ever seen.

        I bought POWER BASIC and tried out Array Sort. It was so fast,
        virtually instantaneous, that I didn't believe it had sorted until,
        after a number of runs I decided to check the data output and
        found it really was instantaneous. Of course, systems weren't as
        fast those days.

        I've never bothered trying to find a faster way to sort since.

        Brian.


        ------------------
        Brian.

        Comment


        • #5
          Karl,

          Actually it does mean 'comb', the reason being that as the sort proceeds, it uses a
          progressively narrowing gap (the 'gap' variable in Keith's code), to divide up the
          domain being sorted. This is likened to the action of a comb, and is literally the
          key to its success.

          Others may possibly refer to it as a combinatorial sort - I couldn't comment on that.
          One thing I forgot to mention previously was that in 10 years, this is the first
          time I have ever seen any mention of CombSort. Maybe I should get out more

          Regards,

          Paul


          ------------------
          http://www.zippety.net
          mailto[email protected][email protected]</A>
          Zippety Software, Home of the Lynx Project Explorer
          http://www.zippety.net
          My e-mail

          Comment


          • #6
            Keith,

            Thanks for posting this version, I have at least some chance of
            reading fortran so I get the general idea of what it is doing.

            Funny enough I am working on a test version of a sort algo that
            appears to have much the same logic, I am trying to do 2 swaps
            for each scan and then swap the lowest in the scan with the
            lowest position and the highest in the scan with the highest
            position. Inc and Dec the two ends and do it again until all of
            the members have been placed.

            Edited here !

            Here is a a simplified version, its technically a Selection Sort,
            a fair bit faster than a bubble sort but a very long way off the
            pace to be competitive. It repeatedly scans the array to finds the
            shortest member and swaps it with the first member, then increments
            the first position. Its swap count is OK but it pays a big penalty
            with the number of scans it does.

            Code:
              '##########################################################################
              
              FUNCTION SelSort(ByVal cnt as LONG, _           ' array count
                               ByVal Arr as LONG) as LONG     ' array address
              
                ' ---------------
                ' Selection Sort
                ' ---------------
              
                  #REGISTER NONE
              
                  LOCAL lcnt as LONG
              
                  ! mov esi, Arr
                  ! xor ecx, ecx
                  ! mov lcnt, ecx
              
                cSt:
                  ! mov ecx, lcnt
                  ! mov edi, &H6FFFFFFF       ; LONG range
                clbl:
                  ! cmp edi, [esi+ecx*4]      ; cmp lowest value holder to current member
                  ! jl cnxt1
                  ! mov edi, [esi+ecx*4]      ; store value in EDI if smaller
                  ! mov edx, ecx              ; store the index
                cnxt1:
                  ! inc ecx
                  ! cmp ecx, cnt
                  ! jne clbl
              
                  ! mov ebx, lcnt
                  ! mov eax, [esi+edx*4]      ; do the swap
                  ! mov ecx, [esi+ebx*4]
                  ! mov [esi+edx*4], ecx
                  ! mov [esi+ebx*4], eax
              
                  ! inc lcnt
                  ! mov ecx, cnt
                  ! cmp lcnt, ecx
                  ! jne cSt
              
                  FUNCTION = 0
              
              END FUNCTION
              
              '##########################################################################
            Regards,

            [email protected]

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


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

            www.masm32.com

            Comment

            Working...
            X