ソートアニメ

 投稿者：しばっち  投稿日：2019年 1月 1日(火)19時46分19秒
  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
 		 

Re: ソートアニメ

 投稿者：hayashi  投稿日：2019年 1月23日(水)14時36分38秒
  > No.4611[元記事へ]

ヒープソートのところで止まってしまうのですが？

> 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
> 		 

Re: ソートアニメ

 投稿者：しばっち  投稿日：2019年 1月24日(木)21時23分26秒
  > No.4624[元記事へ]

hayashiさんへのお返事です。

> ヒープソートのところで止まってしまうのですが？
>

ご報告ありがとうございます。投稿前に確認していたのですが
ソースの一部が欠けていたのを修正した時に抜けてしまっていたようです。大変失礼致しました。
下記プログラムを最後に追加してください。


EXTERNAL SUB HEAPSORT(N,A())
LET NN=N
FOR K=INT(NN/2) TO 1 STEP -1
   LET I=K
   LET X=A(I)
   DO WHILE 2*I<=NN
      LET J=2*I
      IF J<NN THEN
         IF A(J)<A(J+1) THEN LET J=J+1
      END IF
      IF X>=A(J) THEN EXIT DO
      LET A(I)=A(J)
      CALL DRAWBAR(A)
      LET I=J
   LOOP
   LET A(I)=X
   CALL DRAWBAR(A)
NEXT K
DO WHILE NN>1
   LET X=A(NN)
   LET A(NN)=A(1)
   CALL DRAWBAR(A)
   LET NN=NN-1
   LET I=1
   DO WHILE 2*I<=NN
      LET J=2*I
      IF J<NN AND A(J)<A(J+1) THEN LET J=J+1
      IF X>=A(J) THEN EXIT DO
      LET A(I)=A(J)
      CALL DRAWBAR(A)
      LET I=J
   LOOP
   LET A(I)=X
   CALL DRAWBAR(A)
LOOP
END SUB
 		 

戻る