「並び替え」がつくるあみだくじ

ソート（並べ替え、整列）過程を視覚化することで実現できる。
特に、隣接要素の交換の場合があみだくじになる。
隣接しない場合は、縦線をまたぐあみだくじと考えればよい。

参照　SAMPLEフォルダ内AMIDA3.BAS

また、「置換は（隣接する／しない）互換の積で表される」の補足としてのプログラムでもある。

!「並び替え」がつくるあみだくじ

LET N=10 !本数

DIM A(N) !対象データ（あみだくじの結果）
!DATA 5,2,4,1,3
DATA 9,1,6,10,2,7,8,3,4,5
MAT READ A

SUB ConnectLine(b1,b2) !b1とb2との間に横棒を描く
LET dy=y/INT(SQR(N))+1 !間隔
PLOT LINES: b1,dy; b2,dy !結線
DRAW disk WITH SCALE(0.05)*SHIFT(b1,dy) !端
DRAW disk WITH SCALE(0.05)*SHIFT(b2,dy)
LET y=y+1 !次へ
END SUB

SET WINDOW 0,N+1,0,N+1 !表示領域

FOR i=1 TO N !番号、縦棒を表示する
PLOT TEXT, AT i,N: STR$(i)
PLOT LINES: i,1; i,N
NEXT i

LET y=1 !横棒　※本数に制限あり。間隔を詰めれば可能。

CALL Sort(A)
!CALL Sort2(A)
!CALL Sort3(A)
!CALL Sort4(A)
!CALL Sort5(A,1,UBOUND(A))
MAT PRINT A

!隣接する要素の交換
SUB Sort(A()) !基本交換法、隣接交換法、バブルソート
FOR i=1 TO UBOUND(A)-1
FOR j=UBOUND(A) TO i+1 STEP -1
IF A(j)<A(j-1) THEN
swap A(j),A(j-1)

CALL ConnectLine(j-1,j) !横棒を描く
END IF
NEXT j
NEXT i
END SUB

SUB Sort2(A()) !基本挿入法　※Tutorialフォルダ内ex44.bas参照
FOR i=2 TO UBOUND(A)
FOR j=i TO 2 STEP -1
IF A(j)<A(j-1) THEN
swap A(j),A(j-1)

CALL ConnectLine(j-1,j)
ELSE
EXIT FOR
END IF
NEXT j
NEXT i
END SUB

SUB Sort3(A()) !シェーカーソート
LET L=1
LET R=UBOUND(A)
DO WHILE L<R
FOR i=L TO R-1
IF A(i)>A(i+1) THEN
swap A(i),A(i+1)
LET SHIFT=i

CALL ConnectLine(i,i+1)
END IF
NEXT i
LET R=SHIFT

FOR i=R TO L+1 STEP -1
IF A(i)<A(i-1) THEN
swap A(i),A(i-1)
LET SHIFT=i

CALL ConnectLine(i-1,i)
END IF
NEXT i
LET L=SHIFT
LOOP
END SUB

「並び替え」がつくるあみだくじ	返事を書くノートメニュー
山中和義 <drdlxujciw> 2007/11/07 14:03:04
ソート（並べ替え、整列）過程を視覚化することで実現できる。特に、隣接要素の交換の場合があみだくじになる。隣接しない場合は、縦線をまたぐあみだくじと考えればよい。参照　SAMPLEフォルダ内AMIDA3.BAS また、「置換は（隣接する／しない）互換の積で表される」の補足としてのプログラムでもある。 !「並び替え」がつくるあみだくじ LET N=10 !本数 DIM A(N) !対象データ（あみだくじの結果） !DATA 5,2,4,1,3 DATA 9,1,6,10,2,7,8,3,4,5 MAT READ A SUB ConnectLine(b1,b2) !b1とb2との間に横棒を描く LET dy=y/INT(SQR(N))+1 !間隔 PLOT LINES: b1,dy; b2,dy !結線 DRAW disk WITH SCALE(0.05)SHIFT(b1,dy) !端 DRAW disk WITH SCALE(0.05)SHIFT(b2,dy) LET y=y+1 !次へ END SUB SET WINDOW 0,N+1,0,N+1 !表示領域 FOR i=1 TO N !番号、縦棒を表示する PLOT TEXT, AT i,N: STR$(i) PLOT LINES: i,1; i,N NEXT i LET y=1 !横棒　※本数に制限あり。間隔を詰めれば可能。 CALL Sort(A) !CALL Sort2(A) !CALL Sort3(A) !CALL Sort4(A) !CALL Sort5(A,1,UBOUND(A)) MAT PRINT A !隣接する要素の交換 SUB Sort(A()) !基本交換法、隣接交換法、バブルソート FOR i=1 TO UBOUND(A)-1 FOR j=UBOUND(A) TO i+1 STEP -1 IF A(j)<A(j-1) THEN swap A(j),A(j-1) CALL ConnectLine(j-1,j) !横棒を描く END IF NEXT j NEXT i END SUB SUB Sort2(A()) !基本挿入法　※Tutorialフォルダ内ex44.bas参照 FOR i=2 TO UBOUND(A) FOR j=i TO 2 STEP -1 IF A(j)<A(j-1) THEN swap A(j),A(j-1) CALL ConnectLine(j-1,j) ELSE EXIT FOR END IF NEXT j NEXT i END SUB SUB Sort3(A()) !シェーカーソート LET L=1 LET R=UBOUND(A) DO WHILE L<R FOR i=L TO R-1 IF A(i)>A(i+1) THEN swap A(i),A(i+1) LET SHIFT=i CALL ConnectLine(i,i+1) END IF NEXT i LET R=SHIFT FOR i=R TO L+1 STEP -1 IF A(i)<A(i-1) THEN swap A(i),A(i-1) LET SHIFT=i CALL ConnectLine(i-1,i) END IF NEXT i LET L=SHIFT LOOP END SUB

Re: 「並び替え」がつくるあみだくじ	返事を書くノートメニュー
山中和義 <drdlxujciw> 2007/11/07 14:03:37
つづき !隣接しない要素の交換 SUB Sort4(A()) !基本選択法　※Tutorialフォルダ内ex43.bas参照 FOR i=1 TO UBOUND(A)-1 LET k=i !左端 FOR j=i+1 TO UBOUND(A) !最小の位置を見つける IF A(j)<A(k) THEN LET k=j NEXT j IF i<k THEN !交換が必要なら swap A(i),A(k) CALL ConnectLine(i,k) END IF NEXT i END SUB SUB Sort5(A(),L,R) !クイックソート　※Libraryフォルダ内sort1.lib参照 IF L<R THEN LET s=A(INT((L+R)/2)) !中央を軸にする LET i=L-1 !軸より小さいグループと大きいグループに分ける LET j=R+1 DO DO LET i=i+1 LOOP WHILE A(i)<s !軸以上の位置i DO LET j=j-1 LOOP WHILE A(j)>s !軸以下の位置j IF i>=j THEN EXIT DO swap A(i),A(j) CALL ConnectLine(i,j) LOOP CALL Sort5(A, L,i-1) !左部分 CALL Sort5(A, j+1,R) !右部分 END IF END SUB END