Compare sorting algorithms' performance: Difference between revisions
Content added Content deleted
m ({{omit from|GUISS}}) |
(Added BBC BASIC) |
||
Line 331: | Line 331: | ||
Return var |
Return var |
||
}</lang> |
}</lang> |
||
=={{header|BBC BASIC}}== |
|||
{{works with|BBC BASIC for Windows}} |
|||
<lang bbcbasic> HIMEM = PAGE + 2000000 |
|||
INSTALL @lib$+"SORTLIB" |
|||
INSTALL @lib$+"TIMERLIB" |
|||
Sort% = FN_sortinit(0,0) |
|||
Timer% = FN_ontimer(1000, PROCtimer, 1) |
|||
PRINT "Array size:", 1000, 10000, 100000 |
|||
@% = &2020A |
|||
FOR patt% = 1 TO 4 |
|||
CASE patt% OF |
|||
WHEN 1: PRINT '"Data set to all ones:" |
|||
WHEN 2: PRINT '"Data ascending sequence:" |
|||
WHEN 3: PRINT '"Data randomly shuffled:" |
|||
WHEN 4: PRINT '"Data descending sequence:" |
|||
ENDCASE |
|||
FOR type% = 1 TO 6 |
|||
CASE type% OF |
|||
WHEN 1: PRINT "Internal (lib)"; |
|||
WHEN 2: PRINT "Quicksort "; |
|||
WHEN 3: PRINT "Radix sort "; |
|||
WHEN 4: PRINT "Shellsort "; |
|||
WHEN 5: PRINT "Bubblesort "; |
|||
WHEN 6: PRINT "Insertion sort"; |
|||
ENDCASE |
|||
FOR power% = 3 TO 5 |
|||
PROCsorttest(patt%, type%, 10^power%) |
|||
NEXT |
|||
PRINT |
|||
NEXT type% |
|||
NEXT patt% |
|||
END |
|||
DEF PROCsorttest(patt%, type%, size%) |
|||
LOCAL a%(), C%, I% |
|||
DIM a%(size%-1) |
|||
CASE patt% OF |
|||
WHEN 1: a%() = 1 : a%() = 1 |
|||
WHEN 2: FOR I% = 0 TO size%-1 : a%(I%) = I% : NEXT |
|||
WHEN 3: FOR I% = 0 TO size%-1 : a%(I%) = I% : NEXT |
|||
C% = RND(-123456) : REM Seed |
|||
FOR I% = size% TO 2 STEP -1 : SWAP a%(I%-1),a%(RND(I%)-1) : NEXT |
|||
WHEN 4: FOR I% = 0 TO size%-1 : a%(I%) = size%-1-I% : NEXT |
|||
ENDCASE |
|||
Start% = TIME |
|||
ON ERROR LOCAL IF ERR=111 PRINT , " >100.00" ; : ENDPROC |
|||
CASE type% OF |
|||
WHEN 1: C% = size% : CALL Sort%, a%(0) |
|||
WHEN 2: PROCquicksort(a%(), 0, size%) |
|||
WHEN 3: PROCradixsort(a%(), size%, 10) |
|||
WHEN 4: PROCshellsort(a%(), size%) |
|||
WHEN 5: PROCbubblesort(a%(), size%) |
|||
WHEN 6: PROCinsertionsort(a%(), size%) |
|||
ENDCASE |
|||
PRINT , (TIME - Start%)/100; |
|||
FOR I% = 0 TO size%-2 |
|||
IF a%(I%) > a%(I%+1) ERROR 100, "Sort failed!" |
|||
NEXT |
|||
ENDPROC |
|||
DEF PROCtimer |
|||
Start% += 0 |
|||
IF (TIME - Start%) > 10000 ERROR 111, "" |
|||
ENDPROC |
|||
DEF PROCbubblesort(a%(), n%) |
|||
LOCAL i%, l% |
|||
REPEAT |
|||
l% = 0 |
|||
FOR i% = 1 TO n%-1 |
|||
IF a%(i%-1) > a%(i%) THEN |
|||
SWAP a%(i%-1),a%(i%) |
|||
l% = i% |
|||
ENDIF |
|||
NEXT |
|||
n% = l% |
|||
UNTIL l% = 0 |
|||
ENDPROC |
|||
DEF PROCinsertionsort(a%(), n%) |
|||
LOCAL i%, j%, t% |
|||
FOR i% = 1 TO n%-1 |
|||
t% = a%(i%) |
|||
j% = i% |
|||
WHILE j%>0 AND t%<a%(ABS(j%-1)) |
|||
a%(j%) = a%(j%-1) |
|||
j% -= 1 |
|||
ENDWHILE |
|||
a%(j%) = t% |
|||
NEXT |
|||
ENDPROC |
|||
DEF PROCquicksort(a%(), s%, n%) |
|||
LOCAL l%, p%, r%, t% |
|||
IF n% < 2 THEN ENDPROC |
|||
t% = s% + n% - 1 |
|||
l% = s% |
|||
r% = t% |
|||
p% = a%((l% + r%) DIV 2) |
|||
REPEAT |
|||
WHILE a%(l%) < p% l% += 1 : ENDWHILE |
|||
WHILE a%(r%) > p% r% -= 1 : ENDWHILE |
|||
IF l% <= r% THEN |
|||
SWAP a%(l%), a%(r%) |
|||
l% += 1 |
|||
r% -= 1 |
|||
ENDIF |
|||
UNTIL l% > r% |
|||
IF s% < r% PROCquicksort(a%(), s%, r% - s% + 1) |
|||
IF l% < t% PROCquicksort(a%(), l%, t% - l% + 1 ) |
|||
ENDPROC |
|||
DEF PROCshellsort(a%(), n%) |
|||
LOCAL h%, i%, j%, k% |
|||
h% = n% |
|||
WHILE h% |
|||
IF h% = 2 h% = 1 ELSE h% DIV= 2.2 |
|||
FOR i% = h% TO n% - 1 |
|||
k% = a%(i%) |
|||
j% = i% |
|||
WHILE j% >= h% AND k% < a%(ABS(j% - h%)) |
|||
a%(j%) = a%(j% - h%) |
|||
j% -= h% |
|||
ENDWHILE |
|||
a%(j%) = k% |
|||
NEXT |
|||
ENDWHILE |
|||
ENDPROC |
|||
DEF PROCradixsort(a%(), n%, r%) |
|||
LOCAL d%, e%, i%, l%, m%, b%(), bucket%() |
|||
DIM b%(DIM(a%(),1)), bucket%(r%-1) |
|||
FOR i% = 0 TO n%-1 |
|||
IF a%(i%) < l% l% = a%(i%) |
|||
IF a%(i%) > m% m% = a%(i%) |
|||
NEXT |
|||
a%() -= l% |
|||
m% -= l% |
|||
e% = 1 |
|||
WHILE m% DIV e% |
|||
bucket%() = 0 |
|||
FOR i% = 0 TO n%-1 |
|||
bucket%(a%(i%) DIV e% MOD r%) += 1 |
|||
NEXT |
|||
FOR i% = 1 TO r%-1 |
|||
bucket%(i%) += bucket%(i% - 1) |
|||
NEXT |
|||
FOR i% = n%-1 TO 0 STEP -1 |
|||
d% = a%(i%) DIV e% MOD r% |
|||
bucket%(d%) -= 1 |
|||
b%(bucket%(d%)) = a%(i%) |
|||
NEXT |
|||
a%() = b%() |
|||
e% *= r% |
|||
ENDWHILE |
|||
a%() += l% |
|||
ENDPROC</lang> |
|||
'''Output:''' |
|||
<pre> |
|||
Array size: 1000 10000 100000 |
|||
Data set to all ones: |
|||
Internal (lib) 0.00 0.01 0.03 |
|||
Quicksort 0.02 0.27 3.18 |
|||
Radix sort 0.01 0.05 0.53 |
|||
Shellsort 0.03 0.36 4.44 |
|||
Bubblesort 0.00 0.01 0.09 |
|||
Insertion sort 0.00 0.02 0.26 |
|||
Data ascending sequence: |
|||
Internal (lib) 0.00 0.00 0.02 |
|||
Quicksort 0.02 0.15 1.82 |
|||
Radix sort 0.02 0.18 2.10 |
|||
Shellsort 0.03 0.37 4.44 |
|||
Bubblesort 0.00 0.01 0.09 |
|||
Insertion sort 0.01 0.03 0.27 |
|||
Data randomly shuffled: |
|||
Internal (lib) 0.00 0.02 0.44 |
|||
Quicksort 0.02 0.26 3.17 |
|||
Radix sort 0.02 0.17 2.08 |
|||
Shellsort 0.04 0.73 11.57 |
|||
Bubblesort 0.69 69.70 >100.00 |
|||
Insertion sort 0.55 55.54 >100.00 |
|||
Data descending sequence: |
|||
Internal (lib) 0.00 0.01 0.10 |
|||
Quicksort 0.01 0.15 1.90 |
|||
Radix sort 0.02 0.17 2.06 |
|||
Shellsort 0.03 0.50 6.39 |
|||
Bubblesort 0.95 94.77 >100.00 |
|||
Insertion sort 1.11 >100.00 >100.00 |
|||
</pre> |
|||
=={{header|C}}== |
=={{header|C}}== |