|
|
PUBLIC NUMERIC N,KMAX
LET N=100
LET KMAX=100
DIM X(N)
SET WINDOW 1,N+1,0,KMAX
FOR MODE=1 TO 16
CALL DATASET(N,X)
SELECT CASE MODE
CASE 1
PRINT "バブルソート"
CALL BUBBLESORT(N,X)
CASE 2
PRINT "双方向バブルソート"
CALL BIDIRECTIONALBUBBLESORT(N,X)
CASE 3
PRINT "選択法"
CALL SELECTIONSORT(N,X)
CASE 4
PRINT "基数ソート"
CALL RADIXSORT(N,X)
CASE 5
PRINT "シェルソート"
CALL SHELLSORT(N,X)
CASE 6
PRINT "マージソート"
CALL MERGESORT(1,N,X)
CASE 7
PRINT "ヒープソート"
CALL HEAPSORT(N,X)
CASE 8
PRINT "選択ソート"
CALL SELECTSORT(N,X)
CASE 9
PRINT "挿入ソート"
CALL INSERTSORT(N,X)
CASE 10
PRINT "コムソート"
CALL COMBSORT(N,X)
CASE 11
PRINT "ストゥージソート"
CALL STOOGESORT(1,N,X)
CASE 12
PRINT "ノームソート"
CALL GNOMESORT(N,X)
CASE 13
PRINT "バケットソート"
CALL BUCKETSORT(N,X)
CASE 14
PRINT "分布数えソート"
CALL DISTRIBUTIONSORT(N,X)
CASE 15
PRINT "奇遇転置ソート"
CALL ODDEVEN(N,X)
CASE 16
PRINT "クイックソート"
CALL QUICKSORT(1,N,X)
END SELECT
IF MODE<16 THEN PAUSE
NEXT MODE
END
EXTERNAL SUB DATASET(N,X())
RANDOMIZE
FOR I=1 TO N
LET X(I)=INT(RND*KMAX)
CALL DRAWBAR(X)
NEXT I
END SUB
EXTERNAL SUB DRAWBAR(X())
SET DRAW MODE HIDDEN
CLEAR
FOR I=1 TO N
PLOT AREA:I,0;I+.5,0;I+.5,X(I);I,X(I)
NEXT I
SET DRAW MODE EXPLICIT
END SUB
EXTERNAL SUB BUBBLESORT(N,X())
FOR I=1 TO N
FOR J=1 TO N-I
IF X(J)>X(J+1) THEN
SWAP X(J),X(J+1)
CALL DRAWBAR(X)
END IF
NEXT J
NEXT I
END SUB
EXTERNAL SUB BIDIRECTIONALBUBBLESORT(N,A())
LET ST=0
LET EN=N
DO WHILE ST<EN
LET ST=ST+1
LET EN=EN-1
FOR I=ST TO EN
IF A(I)>A(I+1) THEN
SWAP A(I),A(I+1)
CALL DRAWBAR(A)
LET FL=1
END IF
NEXT I
IF FL=0 THEN EXIT DO
LET FL=0
FOR I=EN TO ST STEP-1
IF A(I)>A(I+1) THEN
SWAP A(I),A(I+1)
CALL DRAWBAR(A)
LET FL=1
END IF
NEXT I
IF FL=0 THEN EXIT DO
LET FL=0
LOOP
END SUB
EXTERNAL SUB SELECTIONSORT(N,X())
FOR I=1 TO N-1
FOR J=I+1 TO N
IF X(I)>X(J) THEN
SWAP X(I),X(J)
CALL DRAWBAR(X)
END IF
NEXT J
NEXT I
END SUB
EXTERNAL SUB RADIXSORT(N,A())
DIM B(N)
FOR I=1 TO N
LET KETA=MAX(KETA,LOG10(A(I)+1))
NEXT I
FOR J=0 TO INT(KETA)
LET M=1
FOR K=0 TO 9
FOR I=1 TO N
IF MOD(INT(A(I)/10^J),10)=K THEN
LET B(M)=A(I)
CALL DRAWBAR(B)
LET M=M+1
END IF
NEXT I
NEXT K
MAT A=B
NEXT J
END SUB
EXTERNAL SUB SHELLSORT(N,A())
LET H=1
DO WHILE H<=N
LET H=H*3+1
LOOP
LET H=INT(H/9)
DO WHILE H>=1
FOR I=H TO N
LET X=A(I)
LET J=I-H
DO WHILE J>0 AND A(J)>X
LET A(J+H)=A(J)
LET J=J-H
IF J<1 THEN EXIT DO
LOOP
LET A(J+H)=X
CALL DRAWBAR(A)
NEXT I
LET H=INT(H/3)
LOOP
END SUB
EXTERNAL SUB MERGESORT(FI,LA,X())
IF FI>=LA THEN EXIT SUB
DIM W(LA-FI+1)
LET MI=INT((FI+LA)/2)
CALL MERGESORT(FI,MI,X)
CALL MERGESORT(MI+1,LA,X)
LET P=1
FOR I=FI TO MI
LET W(P)=X(I)
LET P=P+1
NEXT I
LET I=MI+1
LET J=1
LET K=FI
DO WHILE I <= LA AND J < P
IF W(J) <= X(I) THEN
LET X(K)=W(J)
LET K=K+1
LET J=J+1
CALL DRAWBAR(X)
ELSE
LET X(K)=X(I)
LET K=K+1
LET I=I+1
CALL DRAWBAR(X)
END IF
LOOP
DO WHILE J < P
LET X(K)=W(J)
CALL DRAWBAR(X)
LET K=K+1
LET J=J+1
LOOP
END SUB
EXTERNAL SUB SELECTSORT(N,A())
FOR I=1 TO N-1
LET MIN=A(I)
LET K=I
FOR J=I+1 TO N
IF A(J)<MIN THEN
LET MIN=A(J)
LET K=J
END IF
NEXT J
LET A(K)=A(I)
LET A(I)=MIN
CALL DRAWBAR(A)
NEXT I
END SUB
EXTERNAL SUB INSERTSORT(N,A())
FOR I=N TO 1 STEP-1
LET X=A(I)
LET J=I+1
DO WHILE J<=N AND A(J)<X
LET A(J-1)=A(J)
CALL DRAWBAR(A)
LET J=J+1
LOOP
LET A(J-1)=X
CALL DRAWBAR(A)
NEXT I
END SUB
EXTERNAL SUB COMBSORT(SIZE,ARRAY())
LET H = SIZE
DO WHILE H > 1 OR IS_SWAPPED=1
LET H = INT((H*10)/13)
IF H<1 THEN LET H=1
IF H=9 OR H=10 THEN LET H=11
LET IS_SWAPPED = 0
FOR I = 1 TO SIZE-H
IF ARRAY(I) > ARRAY(I+H) THEN
SWAP ARRAY(I),ARRAY(I+H)
LET IS_SWAPPED = 1
CALL DRAWBAR(ARRAY)
END IF
NEXT I
LOOP
END SUB
EXTERNAL SUB STOOGESORT(I,J,L())
IF L(J) < L(I) THEN
SWAP L(I) , L(J)
CALL DRAWBAR(L)
END IF
IF J - I + 1 >= 3 THEN
LET T = INT((J - I + 1) / 3)
CALL STOOGESORT(I , J-T,L)
CALL STOOGESORT(I+T, J ,L)
CALL STOOGESORT(I , J-T,L)
END IF
END SUB
EXTERNAL SUB GNOMESORT(SIZE,A())
LET I = 1
DO WHILE I < SIZE
IF A(I) <= A(I+1) THEN
LET I = I + 1
ELSE
SWAP A(I), A(I+1)
CALL DRAWBAR(A)
LET I = I - 1
IF I = 0 THEN
LET I = I + 1
END IF
END IF
LOOP
END SUB
EXTERNAL SUB BUCKETSORT(N,A())
LET MIN=999999999
LET MAX=-MIN
FOR I=1 TO N
IF MIN>A(I) THEN LET MIN=A(I)
IF MAX<A(I) THEN LET MAX=A(I)
NEXT I
DIM BUFF(MIN TO MAX)
FOR I=1 TO N
LET BUFF(A(I))=BUFF(A(I))+1
NEXT I
FOR I=MIN TO MAX
FOR J=1 TO BUFF(I)
LET COUNT=COUNT+1
LET A(COUNT)=I
CALL DRAWBAR(A)
NEXT J
NEXT I
END SUB
EXTERNAL SUB DISTRIBUTIONSORT(N,A())
LET MIN=999999999
LET MAX=-MIN
FOR I=1 TO N
IF MIN>A(I) THEN LET MIN=A(I)
IF MAX<A(I) THEN LET MAX=A(I)
NEXT I
DIM C(MIN TO MAX),B(N)
FOR I=1 TO N
LET C(A(I))=C(A(I))+1
NEXT I
FOR I=MIN TO MAX-1
LET C(I+1)=C(I+1)+C(I)
NEXT I
FOR I=N TO 1 STEP-1
LET X=A(I)
LET B(C(X))=X
CALL DRAWBAR(B)
LET C(X)=C(X)-1
NEXT I
MAT A=B
END SUB
EXTERNAL SUB ODDEVEN(N,D())
DO
LET FLAG = 0
FOR I = 2 TO N-1 STEP 2
IF D(I) > D(I+1) THEN
SWAP D(I), D(I+1)
CALL DRAWBAR(D)
LET FLAG = 1
END IF
NEXT I
FOR I = 1 TO N-1 STEP 2
IF D(I) > D(I+1) THEN
SWAP D(I), D(I+1)
CALL DRAWBAR(D)
LET FLAG = 1
END IF
NEXT I
LOOP WHILE FLAG=1
END SUB
EXTERNAL SUB QUICKSORT(FI,LA,A())
LET X=A((FI+LA)/2)
LET I=FI
LET J=LA
DO
DO WHILE A(I)<X
LET I=I+1
LOOP
DO WHILE X<A(J)
LET J=J-1
LOOP
IF I>=J THEN EXIT DO
SWAP A(I),A(J)
CALL DRAWBAR(A)
LET I=I+1
LET J=J-1
LOOP
IF FI<I-1 THEN CALL QUICKSORT(FI,I-1,A)
IF J+1<LA THEN CALL QUICKSORT(J+1,LA,A)
END SUB
|
|