IchigoJam でソートの可視化をしてみた。
今回はバブルソートとクイックソートでの昇順ソートを扱う。
※IchigoJamはjig.jpの登録商標です。
バブルソート
今回行うバブルソートは、以下のアルゴリズムである。
- ソートする配列全体を対象とする。
- 対象の前から順に、隣り合う要素の大小関係をチェックし、前の要素の方が大きい場合は入れ替える。
- 対象の最後の組までチェックしたら、対象の一番最後の要素を対象から外し、2から繰り返す。対象が無くなった場合は終了する。
以下が、今回作成したこれを行うプログラムである。
10 ' ｲﾁｺﾞ ｿｰﾄ (ﾊﾞﾌﾞﾙ)
20 FOR I=0 TO 19:[I]=I+1:NEXT
30 FOR I=0 TO 19:P=RND(20-I):T=[I]:[I]=[I+P]:[I+P]=T:NEXT
40 CLS:FOR P=0 TO 19:GOSUB 50:NEXT:GOTO 80
50 FOR K=0 TO 19:LOCATE 6+P,K
60 IF [P]>=20-K ?CHR$(#FF); ELSE ?CHR$(0);
70 NEXT:RETURN
80 FOR I=18 TO 0 STEP -1
90 LOCATE 6,20:?CHR$(#E2);:FOR J=0 TO I
100 LOCATE 7+J,20:?CHR$(#E2);
110 WAIT 5
120 IF [J]<=[J+1] GOTO 140
130 T=[J]:[J]=[J+1]:[J+1]=T:P=J:GOSUB 50:P=J+1:GOSUB 50
140 LOCATE 6+J,20:?CHR$(0);
150 NEXT:LOCATE 7+I,20:?CHR$(0);
160 NEXT
170 LOCATE 0,21:END
クイックソート
今回行うクイックソートは、以下のアルゴリズムである。
- ソートする配列全体を対象とする。
- 対象に要素が1個しか無い場合、この対象についての処理を終える。
- 対象の一番左の要素を基準とし、左位置を対象の左から2番目の位置に、右位置を対象の最後の位置とする。
- 左位置が右位置よりも左にあり、かつ左位置の要素が基準以下の間、左位置を右に進める。
- 右位置が左位置よりも右にあり、かつ右位置の要素が基準以上の間、右位置を左に進める。
- 左位置が右位置よりも左にあるならば、左位置の要素と右位置の要素を交換し、4に戻る。
- 左位置(=右位置)の要素が基準より小さいならば、基準の要素と左位置の要素を交換する。
(これにより、対象の最初から左位置までの部分は基準以下の要素のみ、左位置から最後までの部分は基準以上の要素のみになる) - 「対象の最初から左位置の1個左の部分」「対象の左位置から最後の部分」それぞれを新しい対象とし、2以降の処理を行う。
以下が、今回作成したこれを行うプログラムである。
10 ' ｲﾁｺﾞ ｿｰﾄ (ｸｲｯｸ)
20 FOR I=0 TO 19:[I]=I+1:NEXT
30 FOR I=0 TO 19:P=RND(20-I):T=[I]:[I]=[I+P]:[I+P]=T:NEXT
40 CLS:FOR P=0 TO 19:GOSUB 50:NEXT:GOTO 90
50 FOR K=0 TO 19:LOCATE 6+P,K
60 IF [P]>=20-K ?CHR$(#FF); ELSE ?CHR$(0);
70 NEXT:RETURN
80 WAIT 5:RETURN
90 S=20:LET[S],0,19
100 IF S<20 GOTO 240
110 X=[S]:Y=[S+1]:S=S-2:IF X<Y LOCATE 6+X,20:?CHR$(#E5); ELSE GOTO 100
120 L=X+1:R=Y:LOCATE 6+L,20:?CHR$(#E2);:LOCATE 6+R,20:?CHR$(#E2);
130 IF L>=R OR [L]>[X] GOTO 150
140 LOCATE 6+L,20:?CHR$(0,#E2);:L=L+1:GOSUB 80:GOTO 130
150 IF R<=L OR [R]<[X] GOTO 170
160 R=R-1:LOCATE 6+R,20:?CHR$(#E2,0);:GOSUB 80:GOTO 150
170 IF R<=L GOTO 200
180 T=[L]:[L]=[R]:[R]=T:P=L:GOSUB 50:P=R:GOSUB 50
190 GOSUB 80:GOTO 130
200 IF [X]>[L] T=[X]:[X]=[L]:[L]=T:P=X:GOSUB 50:P=L:GOSUB 50:GOSUB 80
210 LOCATE 6+X,20:?CHR$(0);:LOCATE 6+L,20:?CHR$(0);
220 S=S+4:IF L-X>Y-L+1 LET[S-2],X,L-1,L,Y ELSE LET[S-2],L,Y,X,L-1
230 GOTO 100
240 LOCATE 0,21:END
実行結果
以下は、これらのプログラムを GIGA IchigoDake で実行した様子である。