Announcement

Collapse
No announcement yet.

Re. RippleSort

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

  • Re. RippleSort

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

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

  • #2
    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



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

    Comment


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

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

      Comment


      • #4
        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!


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

        Comment


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

          Comment


          • #6
            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

            Comment


            • #7
              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.
              Code:
              ' 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).]
              Politically incorrect signatures about immigration patriots are forbidden. Searching “immigration patriots” is forbidden. Thinking about searching ... well, don’t even think about it.

              Comment


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


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

                Comment


                • #9
                  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


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

                  Comment


                  • #10
                    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


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

                    Comment


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

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

                      Comment


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


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

                        Comment


                        • #13
                          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.
                          Code:
                          ' 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).]
                          Politically incorrect signatures about immigration patriots are forbidden. Searching “immigration patriots” is forbidden. Thinking about searching ... well, don’t even think about it.

                          Comment


                          • #14
                            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

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

                            Comment


                            • #15
                              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

                              Code:
                              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!

                              Comment


                              • #16
                                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.)
                                Code:
                                 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).]
                                Politically incorrect signatures about immigration patriots are forbidden. Searching “immigration patriots” is forbidden. Thinking about searching ... well, don’t even think about it.

                                Comment

                                Working...
                                X