本ページには広告が含まれています。
引数に指定された配列をシェーカーソートで並び替えます。
- 構文
- shakerSort( array, optimazed )
- 引数
- array 必須
- ソートする数値を格納した配列。参照引数。
- optimazed 省略可
- 最適化フラグ
- 戻り値
プログラム
解説
- 2行目
- 3行目
- 4-30行目
- 5行目
- 6-11行目
- 7-10行目
- 12-16行目
- 17行目
- 18-23行目
- 19-22行目
- 24-28行目
- 29行目
使い方
- 結果
シェーカーソート
シェーカーソートは、ソートのアルゴリズムの一つです。バブルソートを改良したもの。双方向バブルソート、改良交換法とも言われます。
バブルソートでは、配列の要素を1つずつ比較していくため、逆に整列された配列の場合には非常に遅いという問題があります。シェーカーソートは、配列を前から順番に比較するだけでなく、後ろからも比較することで、配列の整列をより効率的に行います。
アルゴリズム
バブルソートで1回スキャンを行うと最後の要素1個がスキャン範囲中最大であることがわかり、次回のスキャン範囲を1狭めることができます。さらに、このスキャンの最後で連続してm個の要素の交換が行われていなければそのm個についてはソート済みであることが分かるので、次回のスキャン範囲をm狭めることができます。この工夫で、後半が殆ど整列済みのデータに対してバブルソートが高速に行えるようになります。
| 最悪計算時間 | \(O(n^{2})\) |
|---|
- 最初に、カレントポインタを配列の先頭、終端ポインタを配列の末尾に設定します。
- カレントポインタが終端ポインタに到達するまで、以下の処理を繰り返します。
- カレントポインタとその次の要素を比較し、大小関係が逆ならば、交換します。
- カレントポインタを1つ進めます。
- 終端ポインタとその前の要素を比較し、大小関係が逆ならば、交換します。
- 終端ポインタを1つ戻します。
- カレントポインタが終端ポインタに到達したら、ソートが完了です。
アルゴリズムを選択して「開始」を押してください。
比較交換/代入基準整列済処理中のグループ処理対象外(薄く表示)
比較回数: 0
交換/代入回数: 0
公開日:
更新日:
関連記事
- small関数 (自作関数)
- 配列の中で小さい方から数えた順位の値を求めます。
- shearSort関数 (自作関数)
- 引数に指定された配列を シェアソート で並び替えます。
- quickSort関数 (自作関数)
- 引数に指定された配列を クイックソート で並び替えます。
- heapSort関数 (自作関数)
- 引数に指定された配列を ヒープソート で並び替えます。
- shellSort関数 (自作関数)
- 引数に指定された配列を シェルソート で並び替えます。
- insertionSort関数 (自作関数)
- 引数に指定された配列を 挿入ソート で並び替えます。
- gnomeSort関数 (自作関数)
- 引数に指定された配列を ノームソート で並び替えます。
- bubbleSort関数 (自作関数)
- 引数に指定された配列を バブルソート で並び替えます。
- QSORT関数 (スクリプト関数)
- 配列の中身をソートします。
- arrayRand関数 (自作関数)
- 一次元配列から一つの値をランダムに取得します。
