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%)
Limit% = EndSort%
DO
Switch% = 0
FOR I% = StartSort% TO Limit% - 1
IF Work%(I%) > Work%(I% + 1) THEN
CALL Swapper(I%, I% + 1)
Switch% = I%
END IF
NEXT I%
Limit% = Switch%
LOOP WHILE Switch% > StartSort%
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)
