Re: Sort Speed

 BBS: Inland Empire Archive
Date: 05-07-92 (01:24)             Number: 170
From: MIKE AVERY                   Refer#: NONE
  To: MILES HUFFORD                 Recvd: NO  
Subj: Re: Sort Speed                 Conf: (2) Quik_Bas
MA>> In general, a Shell sort is much faster than a bubble sort, however
MA>> when a "nearly sorted" or "completely sorted" list is sorted, a
MA>> bubble sort will blow the doors off of just about any other sort as
MA>> it _should_ only make one pass over the data.

MA>> Which sort is "the best" is often a matter of understanding how it
MA>> will be used - if the data will often be nearly or completely sorted,
MA>> a bubble sort may be a good choice.  If you are writing the sort, it
MA>> may be a good idea to make a single pass over the data, check how out
MA>> of sorts it it is and then select the sort based on the first scans
MA>> results.

 MH> A bubble sort tends to make too many swaps..  It swaps the same
 MH> item many times,  I tried the bubble sort on a completly sorted
 MH> array and then used the shell sort...again...the shell sort was
 MH> much faster. Its because the bubble sort makes many more loops
 MH> than the shell sort.

A bubble sort will only swap data if the data is out of order.  And it
should only make 1 pass over data that is already sorted.  As a result, if
the data is already sorted no swaps and only 1 pass.  The bubble sort code
in the MicroSoft sort demo included with QuickBasic does this.  In case
you only have the QBASIC provided with DOS 5.0, I have included a bubble
sort I wrote modelled after the Microsoft bubble sort.

Again, if the data is not in sorted or nearly sorted order, the bubble
sort stinks.

SUB BubbleSort (WorkSpace$, StartSort%, EndSort%)
' Do a bubble sort in the workspace, sorting the items from StartSort%
' to EndSort%.

Limit% = EndSort%

DO
   Switch% = 0
   FOR I% = StartSort% TO Limit% - 1
       IF Work%(I%) > Work%(I% + 1) THEN 'if data out of order
   CALL Swapper(I%, I% + 1)       'swap it
   Switch% = I%                   'point to last swap done
       END IF
   NEXT I%
   ' sort only to the point where the last switch was made...
   Limit% = Switch%
LOOP WHILE Switch% > StartSort%          'and sort until no swaps are done

END SUB

A LOT of code has been removed as it dealt with profiling the sort and is
not relevant to the discussion at hand.  Hopefully I have not removed
anything important.  The Swapper routine swaps the elements in Work% that
the arguments point to.  The routine was put in place as part of profiling
the sort.  In short, it counts the number of swaps.  Also, it displays the
data on screen so as to amuse people interested in sorts.  Since I am
comparing about 17 various sorts, it made sense to use a routine to swap
and count.  Less debugging and all that.  The comments to the right of
each line were added as I edited this message.  I mention this so if the
syntax is wrong, people won't feel that the code was never run under QB45.

A final note - here are the results from a recent sort test on pre-sorted
data, nearly sorted, and unsorted data.  The sorts were run in the
environment, on a 386DX-25 no-name clone slowed down to 8mhz so that there
would be a difference between some of the sorts.  (It ran a LOT slower on
my old XT!!!!)  The nearly sorted data has about 10% of the data items out
of order, with data needing to be moved throughout the data array.  There
are 368 data items to be sorted.


                                  Sort Demo
                            Using Pre-Sorted Data
 旼컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴캠
                                                                           
        Sort Name          Sort Results                                    
                           Compares     Exchanges    Elapsed Time          
           Bubble               367             0               0          
         Exchange            67,528             0              43          
       Hybrid q-e             9,126            18               7          
        Insertion               367           367               1          
            Quick             2,929           372              14          
            Radix             3,307             0               5          
            Shell             1,661             0               1          
          baTcher             6,463             0              22          
             heAp            13,272         5,602              35          
           shaKer               367             0               0          
 突袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴暠

                                  Sort Demo
                           Using Nearly Sorted Data
 旼컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴캠
                                                                           
        Sort Name          Sort Results                                    
                           Compares     Exchanges    Elapsed Time          
           Bubble            67,162         6,240              75          
         Exchange            67,528           363              45          
       Hybrid q-e            20,902           472              17          
        Insertion             6,607         6,607              22          
            Quick            15,309           790              25          
            Radix             3,301           576               8          
            Shell             5,353           777               7          
          baTcher             6,463           620              25          
             heAp            13,694         5,556              35          
           shaKer            12,045         6,240              39          
 突袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴暠

                                 Sort Demo
                             Using Unsorted Data
 旼컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴캠
                                                                           
        Sort Name          Sort Results                                    
                           Compares     Exchanges    Elapsed Time          
           Bubble            66,556        33,742             212          
         Exchange            67,528           364              45          
       Hybrid q-e            38,504           588              29          
        Insertion            34,104        34,109             115          
            Quick            34,755           891              38          
            Radix             3,307           774               9          
            Shell            11,518         2,408              20          
          baTcher             6,463         1,992              33          
             heAp            11,589         3,414              24          
           shaKer            45,545        33,742             198          
 突袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴暠

Hope this answers some questions for you,
Mike

--- via Silver Xpress V3.00
 * Origin: Silver Xpress Mail System (1:382/10@fidonet)
Outer Court
Echo Basic Postings

Books at Amazon:

Back to BASIC: The History, Corruption, and Future of the Language

Hackers: Heroes of the Computer Revolution (including Tiny BASIC)

Go to: The Story of the Math Majors, Bridge Players, Engineers, Chess Wizards, Scientists and Iconoclasts who were the Hero Programmers of the Software Revolution

The Advent of the Algorithm: The Idea that Rules the World

Moths in the Machine: The Power and Perils of Programming

Mastering Visual Basic .NET