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

シェーカーソート

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

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

アルゴリズム

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

最悪計算時間 \(O(n^{2})\)

関連記事

QSORT (スクリプト関数)
QSORT関数は、配列の中身をソートする関数です。戻値はありません。昇順・降順・UNICODE文字比較 昇順・UNICODE文字比較 降順・自然順ソート 昇順・自然順ソート 降順のいずれかを指定することができます。
gnomeSort
ノームソートはソートアルゴリズムの一つです。挿入ソートに似ているが、要素の移動は挿入ではなくバブルソートのような一連の交換で行います。
heapSort
引数に指定された配列をヒープソートで並び替えます。
bubbleSort
引数に指定した配列をバブルソートで並び替えます。
combSort
コムソートではソートの初期段階では離れた要素を比較交換します。そして徐々に2つの要素間の距離を縮めて、最後に直接隣接している要素どうしの比較交換を行います。
selectionSort
選択ソートは、ソートのアルゴリズムの一つ。配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えを行うことでソートします。
insertionSort
挿入ソートは、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入します。
oddEvenSort
奇偶転置ソートは、ソートのアルゴリズムの一つで、バブルソートを改良したもの。バブルソートではスキャンを一方向に順次行うのに対し、奇偶転置ソートでは組ごとに行います。
shearSort
シェアソートはソートアルゴリズムの一つで、データを長方形に並べた上で各行・各列ごとにソートを行ないます。
shellSort
シェルソートは挿入ソートが改良された整列アルゴリズムです。リストにおいてあらかじめ離れている要素を交換しておき、最終的に挿入ソートを実行します。
mergeSort
マージソートは整列されていないリストを2つのリストに分割して、それぞれを整列させた後、それらをマージして整列済みのひとつのリストを作ります。
quickSort
問題を小さな部分問題に分割していく分割統治法を利用した手法で、データから適当に基準値を決めこれより大きいグループと小さいグループに分けるという手順を、分けた小さなグループに対しても再帰的に繰り返していきます。
bogoSort
要素をランダムに並べ替えることで偶発的な一致を試みる整列アルゴリズムです。
Sort オブジェクト (Excel)
データの並べ替えを表します。
CALCARRAY (スクリプト関数)
配列の合計値・最小値・最大値・平均値を求めます。
GETALLWIN (スクリプト関数)
全ウィンドウのIDを取得します。
JOIN (スクリプト関数)
引数に指定した配列を結合し文字列を返します。
POPUPMENU (スクリプト関数)
ポップアップメニューを表示し、引数に指定した配列の中から選択された項目の要素番号を取得します。選択された項目を取得したい場合は、POPUPMENUの戻値を引数に指定した配列の要素番号として指定します。
RESIZE (スクリプト関数)
配列のサイズを変更します。第二引数を省略した場合はサイズを取得します。
SETCLEAR (スクリプト関数)
配列のすべての要素を任意の値で埋めます。
SHIFTARRAY (スクリプト関数)
配列を指定した値だけシフトします。プラス値で後方、マイナス値で前方にシフトします。
SPLIT (スクリプト関数)
SPLIT関数は、引数に指定された文字列を区切文字列で区切り配列に格納します。区切文字列を省略した場合、スペースが区切文字列となります。戻値は配列でsafearray型です。
UBound
配列の最大インデックスを返します。
連想配列
連想配列とは、自動的に割り当てられる数字をキーとして持つかわりに、自由に任意の文字列を割り振ることができる配列のことです。添え字に番号の変わりに名前をつけることでわかりやすく管理することができます。
inArray
divisors
引数に指定した数値の約数をリストを配列で返します。
arraySearch
配列の中から指定した要素が見つかった場合、その要素がある最初のインデックスを返します。
SLICE (スクリプト関数)
SLICE関数は、配列の中を指定範囲の配列で返す関数です。第一引数に配列を指定し、第二引数に開始位置、第三引数に終了位置を指定します。第二・第三引数は省略可能で、省略した場合は配列全体を返します。戻値はsafearray型です。
FOR-IN-NEXT
配列やコレクションなどのグループの各要素に対して繰り返し処理を行います。
arrayReverse
引数に指定した配列を逆順にして返します。