shakerSort関数

本ページには広告が含まれています。

引数に指定された配列をシェーカーソートで並び替えます。

構文
shakerSort( array, optimazed )
引数
array 必須
ソートする数値を格納した配列。参照引数。
optimazed 省略可
最適化フラグ
戻り値

プログラム

UWSC

解説

    2行目
    UWSC
    並べ替えの範囲の「先頭(左端)」を管理する変数topIndexを宣言し、最初は0で初期化しています。ソートが進むにつれて、確定した左端の要素を避けるためにこの位置は右(後ろ)へずれていきます。
    3行目
    UWSC
    並べ替えの範囲の末尾(右端)を管理する変数bottomIndexを宣言しています。UBound(array) で配列の要素数を取得し、隣り合う要素(nとn+1)を比較するために「最大インデックスより1つ手前」の位置を初期値として設定しています。
    4-30行目
    UWSC
    ソートが完了して途中でBREAK(脱出)されるまで、処理を無限に繰り返すループを開始します。
    5行目
    UWSC
    要素の交換(スワップ)が最後に発生した位置を記録する変数lastSwapIndexを宣言し、現在の先頭位置で初期化します。この変数は、最適化(optimized = True)のときに次の探索範囲を決定するために使われます。
    6-11行目
    UWSC
    ソート範囲の左端(topIndex)から右端(bottomIndex)に向かって、要素を1つずつ順番に走査(スキャン)するループを開始します(往路)。
    7-10行目
    UWSC
    もし現在の要素(array[n])の要素が右隣の要素(array[n+1])より大きかったらこの2つの要素を入れ替え、要素を交換したインデックスをlastSwapIndex記録します。
    12-16行目
    UWSC
    【最適化ありの場合】右端の境界(bottomIndex)を、最後に交換が発生した位置(lastSwapIndex)に一気に狭めます。これより右側はすでに完全に並べ替えが終わっていることが保証されるため、無駄な比較を省けます。【最適化なしの場合】右端の境界を機械的に「1つだけ」左にずらします。(シェーカーソートの標準的な挙動です)。
    17行目
    UWSC
    先頭の境界と末尾の境界が重なった、あるいは逆転した場合、すべての並べ替えが完了したとみなして全体のループ(WHILE)を抜けます(終了)。
    18-23行目
    UWSC
    ソート範囲の左端(bottomIndex)から右端(topIndex)に向かって、要素を1つずつ順番に走査(スキャン)するループを開始します(復路)。
    19-22行目
    UWSC
    もし現在の要素(array[n])の要素が左隣の要素(array[n-1])より小さかったら、この2つの要素を入れ替え、要素を交換したインデックスをlastSwapIndex記録します。
    24-28行目
    UWSC
    最適化ありの場合、左端の境界(topIndex)を、最後に交換が発生した位置(lastSwapIndex)に一気に狭めます。これより左側はすでに完全に並べ替えが終わっています。
    29行目
    UWSC
    往路の後と同様に、境界が重なるか逆転していれば全体のループ(WHILE)を抜けます。

使い方

UWSC
結果
プレーンテキスト

シェーカーソート

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

バブルソートでは、配列の要素を1つずつ比較していくため、逆に整列された配列の場合には非常に遅いという問題があります。シェーカーソートは、配列を前から順番に比較するだけでなく、後ろからも比較することで、配列の整列をより効率的に行います。

アルゴリズム

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

最悪計算時間 \(O(n^{2})\)
  1. 最初に、カレントポインタを配列の先頭、終端ポインタを配列の末尾に設定します。
  2. カレントポインタが終端ポインタに到達するまで、以下の処理を繰り返します。
    1. カレントポインタとその次の要素を比較し、大小関係が逆ならば、交換します。
    2. カレントポインタを1つ進めます。
    3. 終端ポインタとその前の要素を比較し、大小関係が逆ならば、交換します。
    4. 終端ポインタを1つ戻します。
  3. カレントポインタが終端ポインタに到達したら、ソートが完了です。
アルゴリズムを選択して「開始」を押してください。
比較交換/代入基準整列済処理中のグループ処理対象外(薄く表示)
比較回数: 0
交換/代入回数: 0

関連記事

small関数 (自作関数)
配列の中で小さい方から数えた順位の値を求めます。
shearSort関数 (自作関数)
引数に指定された配列を シェアソート で並び替えます。
quickSort関数 (自作関数)
引数に指定された配列を クイックソート で並び替えます。
heapSort関数 (自作関数)
引数に指定された配列を ヒープソート で並び替えます。
shellSort関数 (自作関数)
引数に指定された配列を シェルソート で並び替えます。
insertionSort関数 (自作関数)
引数に指定された配列を 挿入ソート で並び替えます。
gnomeSort関数 (自作関数)
引数に指定された配列を ノームソート で並び替えます。
bubbleSort関数 (自作関数)
引数に指定された配列を バブルソート で並び替えます。
QSORT関数 (スクリプト関数)
配列の中身をソートします。
arrayRand関数 (自作関数)
一次元配列から一つの値をランダムに取得します。