Writing a bubble sort in PowerBASIC

[Steve Hutchesson]

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.

  '##########################################################################
  
  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).]

[Paul Noble]

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>

[Brian Reynolds]

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.


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

[Paul Noble]

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>

[Keith Waters]

Hutch

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

      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

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

[Steve Hutchesson]

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]

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
  
'##########################################################################

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