|
|
> No.303[元記事へ]
!クイック・ソートのアニメーション
!
!写像ソートが使用できない場合、依然、最高速なクイック・ソートの手順。
!概略
! データーが、左(Ｌ)から右(Ｒ)に並んでいて、右(Ｒ)へ向かって昇順に、
! 並び替えたいとする。
!１）データー列 順番の中央位置の値を「基準値」に選ぶ。この値は、
! 全データー値の平均とも限らず、不遇にも一番大きな値や、一番小さな値に
! 選ばれる場合も含まれている。
!２）この「基準値」以上の値のデーターは、Ｒ側に、
! この「基準値」以下の値のデーターは、Ｌ側に、２つの領域に分ける。
! 「基準値」は、１）の条件なので、分割の境界が、
! どちらかの端に寄っていき、不均衡になる事もある。
! 各々の領域は、降順や昇順にする必要は無く、以上と以下に、分ければ良い。
!３）分割された２領域、それぞれは、新たなデーター列として、
! 上の１）２）の操作を同様に行なう。それも又、２つずつに分かれていく。
! ・・・この繰り返しを、分割領域１つの長さが、１以下になって、
! 分割出来なくなるまで、進めると、全体のソートが終了している。
DIM VA$(100)
SUB div1time(i,j)
!---------- 以上の分割を１回行なうブログラム。i=L,j=R で開始。
LET v$=VA$((i+j)/2)
DO
DO WHILE VA$(i)< v$
LET i=i+1
LOOP
DO WHILE v$< VA$(j)
LET j=j-1
LOOP
IF j< i THEN EXIT DO ! 等号付 j<=i は、不良。連続の再帰で暴走する。
SWAP VA$(i),VA$(j)
LET i=i+1
LET j=j-1
LOOP UNTIL j< i ! 等号付 j<=i は、不適。連続の再帰で低速。
!----------
END SUB
!上の結果のi,j (L … j)(i … R) を、
! ↓ ↓ ↓ ↓
! 次のL,R (L … R)(L … R) として、上記の処理を行い、
! 両区間のデーター数が、各々１以下( <=1 )になるまで繰返す。
!===================
SUB QuickSort(L,R) ! 上を、連続に行なうブログラム。
local i,j
LET i=L
LET j=R
!----------
! 上のプログラム("---"の内側)を、ココに置いて、
! 再帰的に、繰返し使用。
!----------
CALL div1time(i,j) !これでも良い。…再帰文の分離は、local 変数に用心!
!----------
IF L< j THEN CALL QuickSort(L,j) !データー数１個以下( L>=j) になるまで。
IF i< R THEN CALL QuickSort(i,R) !データー数１個以下( i>=R) になるまで。
END SUB
!========================== 上記の動作の、図解アニメーション ============
!LET samp$="079427856083621"
LET samp$="0794278069836215794278560836215806083"
LET L=1
LET R=LEN(samp$)
FOR k=L TO R
LET VA$(k)=samp$(k:k)
NEXT k
!
SET TEXT background "Opaque"
SET TEXT font "ＭＳ ゴシック",11
SET WINDOW -1,40, 30,0
SET LINE width 2
PLOT TEXT,AT 1,1.5:"** クイック・ソートの手順 **"
LET s=26
PLOT TEXT,AT 1,s :"下線の付いた文字は、L~ R 中央位置で選ばれた「基準値」"
PLOT TEXT,AT 1,s+1 :"その「基準値」で、分割された下の段の色分、"
SET COLOR MIX(0) 0,1,1
PLOT TEXT,AT 1,s+2 :"青は「基準値」以下"
SET COLOR MIX(0) 1,1,0
PLOT TEXT,AT 13,s+2 :"黄は「基準値」以上"
SET COLOR MIX(0) 1,1,1
PLOT TEXT,AT 25,s+2 :"(無色：分割不要、確定)"
PLOT TEXT,AT 1,s+3 :"描画の順序は、再帰文としての、実行順序そのまま。"
LET s=3
!
CALL plotVA(L,R,s,L,R)
CALL GraphQS(L,R)
CALL plotVA(L,R,m+1,L,R)
SUB GraphQS(L,R) ! 分割繰返しの構造を、グラフィックに表示。
local i,j
LET i=L
LET j=R
LET s=s+1
SET COLOR MIX(0) 1,1,1
PLOT TEXT,AT L,s :"L"
PLOT TEXT,AT R,s :"R"
LET s=s+1
!----------
CALL div1time(i,j) !← 冒頭の（分割を１回行なう・・）文を、実際に使用。
CALL plotVA(L,R,s,i,j)
IF m< s THEN LET m=s
WAIT DELAY .1 ! 描画の速さの調整。
!----------
IF L< j THEN CALL GraphQS(L,j)
IF i< R THEN CALL GraphQS(i,R)
LET s=s-2
END SUB
SUB plotVA(L,R,y,i,j)
FOR x=L TO R
IF L=i AND R=j THEN
SET COLOR MIX(0) .8,.8,.8
!SET COLOR MIX(0) 1,1,1
ELSEIF x<=j THEN
SET COLOR MIX(0) 0,1,1
ELSEIF i<=x THEN
SET COLOR MIX(0) 1,1,0
ELSE
SET COLOR MIX(0) 1,1,1
END IF
PLOT TEXT,AT x,y :VA$(x)
IF L<>j AND ROUND((L+j)/2)=x OR i<>R AND ROUND((i+R)/2)=x THEN
PLOT LINES:x+.2,y;x+.6,y
END IF
NEXT x
END SUB
END
! 付録： ※冒頭説明～付録含めて、全文をコピー貼り付け、実行する。
!-------------------------------------
! Swapの直後に、分割終了する場合で、
! 時々、どちらにも属さないデーターが、すき間を、開ける時がある。
! ※下は i=J で、swap 不要の終了ですが、iJ は、進めないと、次のＬ～Ｒが、
! １つ長くなって、速度が落ちる。if~then swap より、無条件 swap が速い。
! このケースは、基準のv$ の位置が、次の分割から除かれており、又、v$ 自体、
! その位置が、移動していない、即ちソート後の位置として、確定している。
! Ｌ iJ Ｒ
! ▽▽▽▽▽▽▽▽●△△△△△△△△
! VA$()= v$ =VA$()
! swap
! Ｌ Ｊ ｉ Ｒ
! ▽▽▽▽▽▽▽▽●△△△△△△△△
! v$
!次のＬ－－－－－－Ｒ Ｌ－－－－－－Ｒ
|
|