Sorting algorithms/Merge sort: Difference between revisions
Added Chipmunk Basic, Minimal BASIC and Quite BASIC
Not a robot (talk | contribs) (Add Miranda) |
(Added Chipmunk Basic, Minimal BASIC and Quite BASIC) |
||
Line 1,935:
END</syntaxhighlight>
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
{{trans|Quite BASIC}}
<syntaxhighlight lang="qbasic">100 REM Sorting algorithms/Merge sort
110 CLS
120 LET N = 10
130 LET C = 0
140 OPTION BASE 1
150 DIM A(10)
160 DIM B(10)
170 RANDOMIZE TIMER
180 GOSUB 810
190 REM Print the random array
200 PRINT "unsort ";
210 GOSUB 860
220 REM Sort the array
230 GOSUB 300
240 PRINT " sort ";
250 REM Print the sorted array
260 GOSUB 860
270 PRINT "Number of iterations: ";C
290 END
300 REM Merge sort the list A of length N
310 REM Using the array B for temporary storage
320 REM
330 REM === Split phase ===
340 REM C counts the number of split/merge iterations
350 LET C = C+1
360 LET X = 1
370 LET Y = 1
380 LET Z = N
390 GOTO 410
400 IF A(X) < A(X-1) THEN GOTO 470
410 LET B(Y) = A(X)
420 LET Y = Y+1
430 LET X = X+1
440 IF Z < Y THEN GOTO 500
450 GOTO 400
460 IF A(X) < A(X-1) THEN GOTO 410
470 LET B(Z) = A(X)
480 LET Z = Z-1
490 LET X = X+1
500 IF Z < Y THEN GOTO 530
510 GOTO 460
520 REM
530 REM === Merge Phase ===
540 REM Q means "we're done" (or "quit")
550 REM Q is 1 until we know that this is _not_ the last iteration
560 LET Q = 1
570 LET X = 1
580 LET Y = 1
590 LET Z = N
600 REM First select the smaller item
610 IF B(Y) < B(Z) THEN GOTO 710 ELSE GOTO 750
620 REM Check if the loop is done
630 IF Z < Y THEN GOTO 790
640 REM If both items are smaller then start over with the smallest
650 IF B(Y) >= A(X-1) OR B(Z) >= A(X-1) THEN GOTO 680
660 LET Q = 0
670 GOTO 600
680 REM Pick the smallest item that represents an increase
690 IF B(Z) < B(Y) AND B(Z) >= A(X-1) THEN GOTO 750
700 IF B(Z) > B(Y) AND B(Y) < A(X-1) THEN GOTO 750
710 LET A(X) = B(Y)
720 LET Y = Y+1
730 LET X = X+1
740 GOTO 620
750 LET A(X) = B(Z)
760 LET Z = Z-1
770 LET X = X+1
780 GOTO 620
790 IF Q = 0 THEN GOTO 330
800 RETURN
810 REM Create a random list of N integers
820 FOR I = 1 TO N
830 LET A(I) = FLOOR(RND(100))
840 NEXT I
850 RETURN
860 REM PRINT the list A
870 FOR I = 1 TO N
880 PRINT A(I);" ";
890 NEXT I
900 PRINT
910 RETURN</syntaxhighlight>
==={{header|Minimal BASIC}}===
{{trans|Quite BASIC}}
<syntaxhighlight lang="qbasic">120 LET N = 10
130 LET C = 0
140 OPTION BASE 1
150 DIM A(10)
160 DIM B(10)
170 RANDOMIZE
180 GOSUB 810
190 REM Print the random array
200 PRINT "unsort ";
210 GOSUB 860
220 REM Sort the array
230 GOSUB 300
240 PRINT " sort ";
250 REM Print the sorted array
260 GOSUB 860
270 PRINT "Number of iterations: "; C
290 GOTO 950
300 REM Merge sort the list A of length N
310 REM Using the array B for temporary storage
320 REM
330 REM === Split phase ===
340 REM C counts the number of split/merge iterations
350 LET C = C+1
360 LET X = 1
370 LET Y = 1
380 LET Z = N
390 GOTO 410
400 IF A(X) < A(X-1) THEN 470
410 LET B(Y) = A(X)
420 LET Y = Y+1
430 LET X = X+1
440 IF Z < Y THEN 500
450 GOTO 400
460 IF A(X) < A(X-1) THEN 410
470 LET B(Z) = A(X)
480 LET Z = Z-1
490 LET X = X+1
500 IF Z < Y THEN 530
510 GOTO 460
520 REM
530 REM === Merge Phase ===
540 REM Q means "we're done" (or "quit")
550 REM Q is 1 until we know that this is _not_ the last iteration
560 LET Q = 1
570 LET X = 1
580 LET Y = 1
590 LET Z = N
600 REM First select the smaller item
610 IF B(Y) < B(Z) THEN 710
615 IF B(Y) > B(Z) THEN 750
620 REM Check if the loop is done
630 IF Z < Y THEN 790
640 REM If both items are smaller then start over with the smallest
650 IF B(Y) >= A(X-1) THEN 680
655 IF B(Z) >= A(X-1) THEN 680
660 LET Q = 0
670 GOTO 600
680 REM Pick the smallest item that represents an increase
690 IF B(Z) < B(Y) THEN 695
692 IF B(Z) > B(Y) THEN 700
695 IF B(Z) >= A(X-1) THEN 750
700 IF B(Z) > B(Y) THEN 705
705 IF B(Y) < A(X-1) THEN 750
710 LET A(X) = B(Y)
720 LET Y = Y+1
730 LET X = X+1
740 GOTO 620
750 LET A(X) = B(Z)
760 LET Z = Z-1
770 LET X = X+1
780 GOTO 620
790 IF Q = 0 THEN 330
800 RETURN
810 REM Create a random list of N integers
820 FOR I = 1 TO N
830 LET A(I) = INT((RND * 100) + .5)
840 NEXT I
850 RETURN
860 REM PRINT the list A
870 FOR I = 1 TO N
880 PRINT A(I); " ";
890 NEXT I
900 PRINT
910 RETURN
950 END</syntaxhighlight>
==={{header|Quite BASIC}}===
<syntaxhighlight lang="qbasic">100 REM Sorting algorithms/Merge sort
110 CLS
120 LET N = 10
130 LET C = 0
150 ARRAY A
160 ARRAY B
180 GOSUB 810
190 REM Print the random array
200 PRINT "unsort ";
210 GOSUB 860
220 REM Sort the array
230 GOSUB 300
240 PRINT " sort ";
250 REM Print the sorted array
260 GOSUB 860
270 PRINT "Number of iterations: "; C
290 END
300 REM Merge sort the list A of length N
310 REM Using the array B for temporary storage
320 REM
330 REM === Split phase ===
340 REM C counts the number of split/merge iterations
350 LET C = C+1
360 LET X = 1
370 LET Y = 1
380 LET Z = N
390 GOTO 410
400 IF A(X) < A(X-1) THEN GOTO 470
410 LET B(Y) = A(X)
420 LET Y = Y+1
430 LET X = X+1
440 IF Z < Y THEN GOTO 500
450 GOTO 400
460 IF A(X) < A(X-1) THEN GOTO 410
470 LET B(Z) = A(X)
480 LET Z = Z-1
490 LET X = X+1
500 IF Z < Y THEN GOTO 530
510 GOTO 460
520 REM
530 REM === Merge Phase ===
540 REM Q means "we're done" (or "quit")
550 REM Q is 1 until we know that this is _not_ the last iteration
560 LET Q = 1
570 LET X = 1
580 LET Y = 1
590 LET Z = N
600 REM First select the smaller item
610 IF B(Y) < B(Z) THEN GOTO 710 ELSE GOTO 750
620 REM Check if the loop is done
630 IF Z < Y THEN GOTO 790
640 REM If both items are smaller then start over with the smallest
650 IF B(Y) >= A(X-1) OR B(Z) >= A(X-1) THEN GOTO 680
660 LET Q = 0
670 GOTO 600
680 REM Pick the smallest item that represents an increase
690 IF B(Z) < B(Y) AND B(Z) >= A(X-1) THEN GOTO 750
700 IF B(Z) > B(Y) AND B(Y) < A(X-1) THEN GOTO 750
710 LET A(X) = B(Y)
720 LET Y = Y+1
730 LET X = X+1
740 GOTO 620
750 LET A(X) = B(Z)
760 LET Z = Z-1
770 LET X = X+1
780 GOTO 620
790 IF Q = 0 THEN GOTO 330
800 RETURN
810 REM Create a random list of N integers
820 FOR I = 1 TO N
830 LET A(I) = FLOOR(RND(100))
840 NEXT I
850 RETURN
860 REM PRINT the list A
870 FOR I = 1 TO N
880 PRINT A(I); " ";
890 NEXT I
900 PRINT
910 RETURN</syntaxhighlight>
=={{header|BCPL}}==
| |||