本ページには広告が含まれています。
引数に指定された配列をシェーカーソートで並び替えます。
- 構文
- shakerSort( 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
//////////////////////////////////////////////////
// 【引数】
// inputs : 繰り返す文字列
// multiplier : inputsを繰り返す回数
// 【戻り値】
// inputsをmultiplier回を繰り返した文字列を返します
//////////////////////////////////////////////////
FUNCTION strRepeat(inputs, multiplier)
DIM res = ""
FOR n = 1 TO multiplier
res = res + inputs
NEXT
RESULT = res
FEND
//////////////////////////////////////////////////
// 【引数】
// a : bと交換する値。参照引数。
// b : aと交換する値。参照引数。
// 【戻り値】
//
//////////////////////////////////////////////////
PROCEDURE swap(Var a, Var b)
DIM tmp = a
a = b
b = tmp
FEND
//////////////////////////////////////////////////
// 【引数】
// arrayname : 上限値を求める配列の名前
// dimension : 返す次元を示す整数
// 【戻り値】
// 配列の上限値
//////////////////////////////////////////////////
FUNCTION UBound(arrayname[], dimension = 1)
RESULT = EVAL("RESIZE(arrayname" + strRepeat("[0]", dimension - 1) + ")")
FEND解説
- 2-3行目
DIM topIndex = 0 DIM bottomIndex = UBound(array) - 1
- 4,22行目
- 無限ループ。
WHILE TRUE … WEND
- 5行目
- lastSwapIndexにtopIndexを代入。
DIM lastSwapIndex = topIndex
- 6,11行目
- topIndexがbottomIndexになるまで繰り返す。
FOR n = topIndex TO bottomIndex … NEXT
- 7-10行目
- 配列のn番目がn+1番目より大きかったら、その2つを入れ替える。lastIndexにnを代入する。
IFB array[n] > array[n+1] THEN swap(array[n], array[n+1]) lastSwapIndex = n ENDIF
- 12行目
- bottomIndexにlastSwapIndexを代入。
bottomIndex = lastSwapIndex
- 13行目
- topIndexとbottomIndexが等しかったらループを抜ける。
IF topIndex = bottomIndex THEN BREAK
- 14,19行目
- bottomIndexからtopIndex+1まで繰り返す。
FOR n = bottomIndex TO topIndex + 1 STEP -1 … NEXT
- 15-18行目
- 配列のn番目がn-1番目より小さかったら、その2つを入れ替える。lastIndexにnを代入する。
IFB array[n] < array[n-1] THEN swap(array[n], array[n-1]) lastSwapIndex = n ENDIF
- 20行目
- bottomIndexにlastSwapIndexを代入。
topIndex = lastSwapIndex
- 21行目
- topIndexとbottomIndexが等しかったらループを抜ける。
IF topIndex = bottomIndex THEN BREAK
使い方
DIM array[] = 8, 20, 2, 22, 17, 30, 14, 4, 25, 5
shakerSort(array)
FOR item IN array
PRINT item
NEXT- 結果
2 4 5 8 14 17 20 22 25 30
シェーカーソート
シェーカーソートは、ソートのアルゴリズムの一つです。バブルソートを改良したもの。双方向バブルソート、改良交換法とも言われます。
バブルソートでは、配列の要素を1つずつ比較していくため、逆に整列された配列の場合には非常に遅いという問題があります。シェーカーソートは、配列を前から順番に比較するだけでなく、後ろからも比較することで、配列の整列をより効率的に行います。
アルゴリズム
バブルソートで1回スキャンを行うと最後の要素1個がスキャン範囲中最大であることがわかり、次回のスキャン範囲を1狭めることができます。さらに、このスキャンの最後で連続してm個の要素の交換が行われていなければそのm個についてはソート済みであることが分かるので、次回のスキャン範囲をm狭めることができます。この工夫で、後半が殆ど整列済みのデータに対してバブルソートが高速に行えるようになります。
| 最悪計算時間 | \(O(n^{2})\) |
|---|
- 最初に、カレントポインタを配列の先頭、終端ポインタを配列の末尾に設定します。
- カレントポインタが終端ポインタに到達するまで、以下の処理を繰り返します。
- カレントポインタとその次の要素を比較し、大小関係が逆ならば、交換します。
- カレントポインタを1つ進めます。
- 終端ポインタとその前の要素を比較し、大小関係が逆ならば、交換します。
- 終端ポインタを1つ戻します。
- カレントポインタが終端ポインタに到達したら、ソートが完了です。
関連記事
- QSORT関数 (スクリプト関数)
- QSORT関数は、配列の中身をソートする関数です。戻値はありません。昇順・降順・UNICODE文字比較 昇順・UNICODE文字比較 降順・自然順ソート 昇順・自然順ソート 降順のいずれかを指定することができます。
- small関数 (自作関数)
- 配列の中で小さい方から数えた順位の値を求めます。
- bubbleSort関数 (自作関数)
- 引数に指定された配列を バブルソート で並び替えます。
- gnomeSort関数 (自作関数)
- 引数に指定された配列を ノームソート で並び替えます。
- insertionSort関数 (自作関数)
- 引数に指定された配列を 挿入ソート で並び替えます。
- shellSort関数 (自作関数)
- 引数に指定された配列を シェルソート で並び替えます。
- heapSort関数 (自作関数)
- 引数に指定された配列を ヒープソート で並び替えます。
- quickSort関数 (自作関数)
- 引数に指定された配列を クイックソート で並び替えます。
- shearSort関数 (自作関数)
- 引数に指定された配列を シェアソート で並び替えます。
- Sort.Header プロパティ (Excel)
- 最初の行にヘッダー情報が含まれるかどうかを指定します。