shakerSort

タグ: ,
構文
shakerSort( Var array )
引数
array
ソートする数値を格納した配列。参照引数。
戻値

プログラム

//////////////////////////////////////////////////
// 【引数】
//   array : ソートする数値を格納した配列。参照引数。 
// 【戻値】
// 
//////////////////////////////////////////////////
PROCEDURE shakerSort(Var array[])
	DIM topIndex = 0
	DIM bottomIndex = UBound(array) - 1
	WHILE TRUE
		DIM lastSwapIndex = topIndex
		FOR n = topIndex TO bottomIndex
			IFB array[n] > array[n+1] THEN
				swap(array[n], array[n+1])
				lastSwapIndex = n
			ENDIF
		NEXT
		bottomIndex = lastSwapIndex
		IF topIndex = bottomIndex THEN BREAK
		FOR n = bottomIndex TO topIndex + 1 STEP -1
			IFB array[n] < array[n-1] THEN
				swap(array[n], array[n-1])
				lastSwapIndex = n
			ENDIF
		NEXT
		topIndex = lastSwapIndex
		IF topIndex = bottomIndex THEN BREAK
	WEND
FEND

//////////////////////////////////////////////////
// 【引数】
//   a : 変数bと交換する値。参照引数。 
//   b : 変数aと交換する値。参照引数。 
// 【戻値】
// 
//////////////////////////////////////////////////
PROCEDURE swap(Var a, Var b)
	DIM tmp = a
	a = b
	b = tmp
FEND

//////////////////////////////////////////////////
// 【引数】
//   配列 : 上限値を求める配列 
// 【戻値】
//   配列の上限値 
//////////////////////////////////////////////////
FUNCTION UBound(array[])
	RESULT = RESIZE(array)
FEND

解説

  1. 2-3行目
    	DIM topIndex = 0
    	DIM bottomIndex = UBound(array) - 1
    
  2. 4行目
    	WHILE TRUE
    
    無限ループ。
  3. 5行目
    		DIM lastSwapIndex = topIndex
    
  4. 6行目
    		FOR n = topIndex TO bottomIndex
    
    n=topIndexからbottomIndexまで繰り返す。
  5. 7-10行目
    			IFB array[n] > array[n+1] THEN
    				swap(array[n], array[n+1])
    				lastSwapIndex = n
    			ENDIF
    
    配列のn番目がn+1番目より大きかったら、その2つを入れ替える。
  6. 12行目
    		bottomIndex = lastSwapIndex
    
  7. 13行目
    		IF topIndex = bottomIndex THEN BREAK
    
    topIndexとbottomIndexが等しかったらループを抜ける。
  8. 14行目
    		FOR n = bottomIndex TO topIndex + 1 STEP -1
    
  9. 15-18行目
    			IFB array[n] < array[n-1] THEN
    				swap(array[n], array[n-1])
    				lastSwapIndex = n
    			ENDIF
    
  10. 20行目
    		topIndex = lastSwapIndex
    
  11. 21行目
    		IF topIndex = bottomIndex THEN BREAK
    

シェーカーソート

シェーカーソートは、ソートのアルゴリズムの一つです。バブルソートを改良もの。した双方向バブルソート、改良交換法とも言われます。

バブルソートではスキャンを一方向にしか行わないのに対し、シェーカーソートでは交互に二方向に行います。

アルゴリズム

バブルソートで1回スキャンを行うと最後の要素1個がスキャン範囲中最大であることがわかり、次回のスキャン範囲を1狭めることができます。さらに、このスキャンの最後で連続してm個の要素の交換が行われていなければそのm個についてはソート済みであることが分かるので、次回のスキャン範囲をm狭めることができます。この工夫で、後半が殆ど整列済みのデータに対してバブルソートが高速に行えるようになります。