Re. RippleSort

[Brad D Byrne]

Wayne, I believe the RippleSort proc. is also called BubbleSort, B

------------------
mailto:[email protected][email protected]</A>

[Wayne Diamond]

Brad, not according to my Pascal book!

A method which is often used to sort the data stored in arrays is called a ripple-sort, a form of the bubble sort.

Unfortunately it doesn't state the differences between a bubble-sort and ripple-sort, but seems to clearly state that the two are at least slightly different.. ?? I'm not sure, I'd like to know though I like sorting algorithms!

Cheers,
Wayne



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

[Tom Hanlin]

...after the inventor, "Bubbles". It's not a member of the set of efficient sorting algorithms.

------------------
Tom Hanlin
PowerBASIC Staff

[Wayne Diamond]

Does anybody here know what sorting algorithms are best used under which circumstances? There are so many different ways to sort different types of data that I don't really know where to begin
If anybody reading this thread has any preference towards any sorting algorithms, I'd like to know when and why you choose to use such algorithms... it'd be nice to know when to use which sorting algorithm!


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

[Brad D Byrne]

I was taught (in the 60's) that the best way to sort data, is to
Store it Pre-Sorted,

However I think "QuickSort" is still the fastest, there are different
versions which optimize for certain data structs----
B

------------------
mailto:[email protected][email protected]</A>

[This message has been edited by Brad D Byrne (edited January 15, 2002).]

[Tom Hanlin]

Any general book on algorithms will have at least a chapter on sorting. For the definitive work, see Knuth's Sorting and Searching.

Bubble-sort variants are increasingly inefficient for larger amounts of data, but have a low base overhead, and may be useful for sorting small data sets (say, in the dozens of items).

QuickSort is the usual winner for general-purpose in-memory sorts.

For sorting data too large to fit in memory, there are merge-sorting algorithms. Basically, the data gets divided into smaller, more convenient lots, each of which is sorted, and then the parts are efficiently recombined into one sorted file.


------------------
Tom Hanlin
PowerBASIC Staff

[Mark Hunter]

Shell Sort uses far fewer compares, though
more swaps, than QuickSort, a little known
fact.

If your data items cost a lot to compare,
shell sort is the way to go, using an index
into your array.

Create an array of subscripts, index(),
initially 1,2,3,4,... into these arrays
so that you always consider a(index()).
Then you can sort a() by sorting just
index(), using a() for comparisons.

In the example below a() is numbers, but
the code could be modified for any kind
of array.

Another advantage of shell sort is that
it's very fast if the data is only a
little out of order. This is not the
case with QuickSort.

' a() is a random array, index() is an array of
' subscripts into a().  This code sorts index()
' so that a(index()) is in order; it leaves a()
' itself alone.  It compares only elements of a()
' and swaps the index array instead.

' Tested on PBDOS and PBCC.  I don't have PBDLL
' but changing print to messagebox should fix it.


function pbmain
 %N = 20                 'a(0 to %N-1)
 %M = %N - 1
 
 dim a(%N) as long       'given array
 dim v     as long       'same type as a()
 dim index(%N) as long   'an array of subscripts 1,2,3,...
 dim i as long, j as long, k as long


'CREATE INITIAL INDEX()
 for i = 0 to %N - 1
  index(i) = i           'could be in any order just so
 next                    'numbers are unique, 0 to %N - 1


'CREATE A RANDOM ARRAY a() AND PRINT IT
 randomize timer
 for i = 0 to %N - 1
  a(i) = rnd*%N
  print a(i);
 next
 print


'SHELL SORT
 K = 1                   'initialize K
 do
   K = 2*K + 1           'contrary to some literature,
 loop until K > %N       '2* is better than 3*


 do
   K = K\2
   for i = K to %M
     v = a(index(i))
     j = i
     do while a(index(j - K)) > v
       swap index(j), index(j - K)
       j = j - K
     loop until j < K
   next i
 loop until K <= 1


'PRINT SORTED ARRAY
 for i = 0 to %N - 1
  print a(index(i));
 next


 waitkey$
end function

Mark

[co. name removed]

[This message has been edited by Mark Hunter (edited July 25, 2005).]

[Borje Hagsten]

Always interesting to see different algo's, but the real challenge
is to beat ARRAY SORT..


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

[Wayne Diamond]

When would you use ARRAY SORT and when would you implement your own algo, such as bubblesort etc... ? ARRAY SORT has pretty much always suited my needs, but I do like the various different algorithms


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

[John Petty]

Wayne
Writing sorts in practice is a very complicated issue due to a lot of factors
1. is the time it takes to write the code worth the time it saves in execution.
2. How accurately can you predict the number of items to be sorted. ie if you design your program such that it is optimised for sorting 20 items and someone sends it 1000000 to sort they will be very annoyed by the time taken whereas if you optimise for 1000000 and they only send it 20 they usually wont notice the difference.
3. How and how fast the data is presented for the sort, which is I think what Brad is referring when he says "store it presorted" or indexed which normally uses some inserion sort algorithem.
4. What type of data you are sorting.
After many years of studying and writing sorts the following are my own personal guidelines.

Taking in account point 1 if it is a simple data type, integer, long or short string and cannot be more than a few hundred thousand items then Array Sort.
else
< 10, bubble sort
< 20, optimised bubble - ie each loop only goes up to the last swap
From here on there is a general rule that if the data type is anything other than an integer or long I start off by making a pointer array to the data and only swapping pointers.
< few thousand, Shell sort (I can't totally agree with Mark here as my own tests shows that with random data this only holds true up to a certain size) after which shellsort becomes dramatically slower than the next option.
< few hundred thousand and not simple data, assembler optimised quick sort.
Sort work area < available physical memory, combined quick and shell ie when quick breaks data block down below a specified size then the block is sorted with a shell sort and returned to the quick sort (Steve Hutchison gave a reference in another forum to some math which uses radix sorting as the second level, havn't had time to test it yet). This combination results in a sort approx 10% faster than straight quick sort (and array sort) with simple data types and with proper data preperation techniques twice as fast as array sort for long strings and UDT's. Again written in assembler.
Bigger! this is when the fun starts. First sort blocks that fit criteria of previous and then it becomes very hardware dependant ie number of disk controllers, number of disks and there relative speeds for some optimised merge sort. For most cases a simple binary merge where a sections of each of two sorted blocks is read in in portions equal in size up to 1/4 of the available physical memory at a time and outputed when the merged block is equal to 1/2 available physical memory. The process is repeated merging pairs of sorted blocks into a block of twice the size until only one block remains.
Hope this helps
John


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

[Brad D Byrne]

John,
Wow!!!, I'm going to need a week to "Sort out" what you said

------------------
mailto:[email protected][email protected]</A>

[Wayne Diamond]

Yes, thankyou John! actually that answers my next five questions too


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

[Mark Hunter]

Borje Hagsten asks for a sort faster than PB's
ARRAY SORT.

The following assembler shell sort takes less
than half the time of PB's array sort. For PBDOS.

' Comparison of PB ARRAY SORT
' with          ASSEMBLER INDEXED SHELL SORT.
' For PBDOS (16 bit word).


defint a-z


%N = 16000          'number of elements in a (0 to %N - 1)

                    'it must be less than half of 32767
dim a(%N)           'a given array of random numbers
dim savea(%N)       'to save between sorts
dim index(%N)       'an array of subscripts 1,2,3,...
N = %N              


segIndex%  = varseg(index(0))		'varptr is 0
segA%      = varseg(a(0))		'varptr is 0
cls


'CREATE ARRAY
randomize timer     'make a random array a(), print it
for i = 0 to N - 1
  a(i) = rnd*N
  savea(i) = a(i)
'  print a(i);	    'optional printout
next
print


'PB ARRAY SORT
mtimer              'start microsecond timer
array sort a(0) for N
x& = mtimer
print "PB array sort: ";x&;" microseconds
'for i=0 to N-1     'optional printout
'  print a(i);
'next

'RESTORE ARRAY
for i=0 to N - 1
 a(i)=savea(i)
next


'SHELL SORT
mtimer               'start microsecond timer
! push ds            ;save registers for BASIC
! push es            ;  These, and the pops at the end,
! push si            ;  are the only push-pops used.
! push di
! push bp


! mov dx,N           ;get N


! mov ax,segIndex%   ;get segments
! mov bx,segA%
! mov ds,bx          ;es is segment of index()
! mov es,ax          ;ds is segment of a()


! xor ax,ax          ;initialize index()
! xor di,di          ;  Note: this needs to be done only once
! mov cx,dx          ;  for repeated sorts, if N does not change.
indexloop:           '  between sorts.  All that is needed are
! stosw              ;  unique integers 0 to N - 1 in any order.
! inc ax
! loopnz indexloop   ;could switch es and ds for rest of code


! mov cx,1           ;compute initial compare gap
initK:
! add cx,cx
! inc cx
! cmp cx,dx
! jle initK


! dec dx             ;dx = N - 1, never changes
! add dx,dx          ;since we double every pointer into integer
                     '  arrays and dx will be compared with pointers

doloop:
 !shr cx,1           ;new cx = old cx\2
 !add cx,cx          ;double it
 !mov di,cx          ;di points into index
forloop:             'for di = cx to N - 1
  !mov bx,es:[di]    ;index(i)
  !add bx,bx         ;double it
  !mov bp,ds:[bx]    ;bp = a(index(di))
  !mov bx,di         ;bx = di,  bx points into index
innerloop:
   !mov si,bx
   !sub si,cx        ;bx-cx,         si points into index
   !mov si,es:[si]   ;index(bx-cx)
   !add si,si        ;double it
   !cmp ds:[si],bp   ;if a(index(bx-cx))<=bp then endloop
   !jle endinnerloop
   !mov si,bx        ;swap index(bx),index(bx-cx)
   !sub si,cx        ;bx-cx
   !mov bx,es:[bx]   ;will need to restore bx later,
   !mov ax,es:[si]   ;  use bx to avoid push pop of another reg
   !mov es:[si],bx   ;
   !mov bx,si        ;restore bx
   !add bx,cx        ;
   !mov es:[bx],ax   ;
   !mov bx,si        ;decr bx,cx
   !cmp bx,cx
   !jge innerloop    ;loop if bx >= cx
endinnerloop:
  !add di,2          ;next di,  double increment
  !cmp di,dx
  !jle forloop       ;loop if di<=N-1
 !shr cx,1           ;undouble cx
 !cmp cx,1
 !jg doloop          ;loop until cx<=1


 ! pop bp            ;restore registers for PowerBASIC
 ! pop di
 ! pop si
 ! pop es
 ! pop ds


x& = mtimer          'print microsecond timer
print "Assember sort: ";x&;" microseconds


'CHECK THAT A() IS REALLY SORTED
b = a(index(0))      'print a() using sorted index()
'print b;            'first -- optional printout
for i = 1 to N - 1   'second to end
  bb = a(index(i))
  if bb < b then print "It's not sorted."
'  print bb;         'optional printout
  b = bb
next

[co. name removed]

[This message has been edited by Mark Hunter (edited September 19, 2005).]

[Scott Smith]

Originally posted by Tom Hanlin:
Bubble-sort variants are increasingly inefficient for larger amounts of data...

A long, long time ago in a publication now defunct...

PC Tech Journal published a modified bubble-sort, which they called a comb sort. In testing against shell, quick, and recursive quick sorts using long integer keys, I found the comb sort was faster than shell and almost as fast as quick/rquick sorts for up to 25,000 keys. That was for random lists. For partially or already ordered lists, it was kick-booty fast. As a general purpose in-memory sort for a few thousand items, it served me well for years. Until ARRAY SORT came along, which is a bit faster, not to mention easier. I suppose if comb were implemented in assembly...?

Scott

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

[mark smit]

Hello Guys,

Here is an example of a custom quick sort. With this quick sort you can track a given row number, prevent same value swapping and it is also non recursive. Oh... this is also kid tested and mother approved

FUNCTION SortArrayData(OPTIONAL BYVAL lRow AS LONG) EXPORT AS LONG
    DIM lCount AS LONG
    DIM lTop AS LONG
    DIM lBot AS LONG
    DIM lMin AS LONG
    DIM lMid AS LONG
    DIM lMax AS LONG
    DIM lValue AS LONG
 
 
    lBot = UBOUND(ArrayData)
 
 
    ASM mov     edx,lBot
    ASM and     edx,edx
    ASM jz      DoneSorting ;check for zero element
    ASM js      DoneSorting ;check for sign
    ASM mov     eax,1
    ASM push    eax
    ASM push    edx
    ASM inc     lCount
 
 
    WHILE lCount
        ASM pop     eax
        ASM mov     lBot,eax
        ASM mov     lMax,eax
        ASM pop     edx
        ASM mov     lTop,edx
        ASM mov     lMin,edx
        ASM add     eax,edx
        ASM shr     eax,1
        ASM mov     lMid,eax
        ASM dec     lCount
 
 
        lValue = ArrayData(lMid)
 
 
        WHILE (lMin <= lMax)
 
 
            REM scan for minimum value
            WHILE (ArrayData(lMin) < lValue) AND (lMin < lBot)
                ASM inc lMin
            WEND
 
 
            REM scan for maximum value
            WHILE (ArrayData(lMax) > lValue) AND (lMax > lTop)
                ASM dec lMax
            WEND
 
 
            REM swap array data
            IF (lMin <= lMax) THEN
                IF ISFALSE(ArrayData(lMin).lValue = ArrayData(lMax).lValue) THEN
                    SWAP ArrayData(lMin),ArrayData(lMax)
 
                    REM track row number
                    IF (lRow = lMin) THEN lRow = lMax:EXIT IF
                    IF (lRow = lMax) THEN lRow = lMin:EXIT IF
                END IF
 
                ASM inc lMin
                ASM dec lMax
            END IF
        WEND
 
 
        REM add bottom range
        IF (lMin < lBot) THEN
            ASM mov     eax,lMin
            ASM push    eax
            ASM mov     eax,lBot
            ASM push    eax
            ASM inc     lCount
        END IF
 
 
        REM add top range
        IF (lMax > lTop) THEN
            ASM mov     eax,lTop
            ASM push    eax
            ASM mov     eax,lMax
            ASM push    eax
            ASM inc     lCount
        END IF
    WEND
 
 
DoneSorting:
    FUNCTION = lRow
END FUNCTION

------------------
Cheers!

[Mark Hunter]

Here's the quicksort Mark Smit posted above, part assembly
and part basic, converted to 16 bit and PBDOS, so we can
compare it to the assembler indexed sort posted above.

The shell sort tests ten times faster than the quicksort.

Two reasons: The shell sort algorithm is faster than
quicksort. The quicksort implementation considered here
uses many pushes and pops, and accesses to RAM rather
than registers.

(Note: even in PBCC the ".lValue" needs to be removed
from the quicksort code above inorder to compile.)

(Note: one minor difference in the algorithms here
implemented is that the shell sort array index goes
from 0 to N - 1, the quicksort from 1 to N.)

 Declare sub sortarraydata()


 %N = 16000
 Dim arraydata(%N) As integer   'non-negative integers
 shared arraydata()

 randomize timer
 For i = 1 To %N
  arraydata(i) = Rnd*%N
'  print arraydata(i);          'optional printout
 Next
 Print
 mtimer
 sortarraydata
' For i = 1 To %N               'optional printout
'  Print arraydata(i);
' Next
 Print
 x& = mTimer
 Print x&
stop


sub SortArrayData
 Dim lCount As word
 Dim lTop As word
 Dim lBot As word
 Dim lMin As word
 Dim lMid As word
 Dim lMax As word
 Dim lValue As word
 Dim lrow As word


 lBot = UBound(ArrayData)        'assume > 0


 ! mov dx,lBot
 ! and dx,dx
 ! mov ax,1
 ! push ax
 ! push dx
 ! inc lCount


 While lCount
  ! pop ax
  ! mov lBot,ax
  ! mov lMax,ax
  ! pop dx
  ! mov lTop,dx
  ! mov lMin,dx
  ! add ax,dx
  ! shr ax,1
  ! mov lMid,ax
  ! dec lCount


  lValue = ArrayData(lMid)


  While lMin <= lMax


  ' scan for minimum value
   While ArrayData(lMin) < lValue And lMin < lBot
    ! inc lMin
   Wend


  ' scan for maximum value
   While ArrayData(lMax) > lValue And lMax > lTop
    ! dec lMax
   Wend


 ' swap array data
   If lMin <= lMax Then
    If ArrayData(lMin) <> ArrayData(lMax) Then
     Swap ArrayData(lMin),ArrayData(lMax)
     ' track row number
     If lRow = lMin Then lRow = lMax :Exit If
     If lRow = lMax Then lRow = lMin :Exit If
    End If


    ! inc lMin
    ! dec lMax
   End If


  Wend


' add bottom range
  If lMin < lBot Then
   ! mov ax,lMin
   ! push ax
   ! mov ax,lBot
   ! push ax
   ! inc lCount
  End If


 ' add top range
  If lMax > lTop Then
   ! mov ax,lTop
   ! push ax
   ! mov ax,lMax
   ! push ax
   ! inc lCount
  End If


 Wend
End sub

[This message has been edited by Mark Hunter (edited January 19, 2002).]