改良交換法とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > デジタル大辞泉 > 改良交換法の意味・解説 

かいりょう‐こうかんほう〔カイリヤウカウクワンハフ〕【改良交換法】

読み方:かいりょうこうかんほう

シェーカーソート


シェーカーソート

(改良交換法 から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/10/07 16:31 UTC 版)

シェーカーソート
クラス ソート
データ構造 配列
最悪計算時間 О(n²)

シェーカーソート (: shaker sort) は、ソートアルゴリズムの一つ。バブルソートを、効率がよくなるように改良したもの。別名は、双方向バブルソート改良交換法[1]

バブルソートではスキャンを一方向にしか行わないのに対し、シェーカーソートでは交互に二方向に行う。バブルソートと同じく安定な内部ソートで、最悪の場合の時間計算量O(n2)である。

アルゴリズム

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

シェーカーソートはこれに加え、スキャン方向を毎回反転することにより、スキャン範囲を後方からだけではなく前方からも狭めるようにしたものである。挿入ソートのように、殆ど整列済みのデータに対しては高速に行うことができる。

実装例

C++言語による実装例を示す。

#include <algorithm> // std::swap

template<typename T> void shaker_sort(T data[], int num_elements)
{
    int top_index = 0;
    int bot_index = num_elements - 1;

    while (true)
    {
        int last_swap_index;

        /* 順方向のスキャン */
        last_swap_index = top_index;

        for (int i = top_index; i < bot_index; i++)
        {
            if (data[i] > data[i+1])
            {
                std::swap(data[i], data[i+1]);
                last_swap_index = i;
            }
        }
        bot_index = last_swap_index; /* 後方のスキャン範囲を狭める */

        if (top_index == bot_index)
            break;

        /* 逆方向のスキャン */
        last_swap_index = bot_index;

        for (int i = bot_index; i > top_index; i--)
        {
            if (data[i] < data[i-1])
            {
                std::swap(data[i], data[i-1]);
                last_swap_index = i;
            }
        }
        top_index = last_swap_index; /* 前方のスキャン範囲を狭める */

        if (top_index == bot_index)
            break;
    }
}

動作例

t はスキャン範囲の先頭、b は末尾を表す。

初期データ: 8 4 3 7 6 5 2 1

1回目のスキャン終了後: (交換回数:7)

4 3 7 6 5 2 1 8
t           b

2回目のスキャン終了後: (交換回数:6)

1 4 3 7 6 5 2 8
  t         b

3回目のスキャン終了後: (交換回数:4)

1 3 4 6 5 2 7 8
  t       b

4回目のスキャン終了後: (交換回数:4)

1 2 3 4 6 5 7 8
    t     b

5回目のスキャン終了後: (交換回数:1)

1 2 3 4 5 6 7 8
    t   b

6回目のスキャン終了後: (交換回数:0)

1 2 3 4 5 6 7 8

合計交換回数:7+6+4+4+1+0=22 (バブルソートの場合22)

脚注

出典

  1. ^ シェーカーソートの意味(出典:デジタル大辞泉) - goo辞書

関連項目



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「改良交換法」の関連用語

1
シェーカー‐ソート デジタル大辞泉
70% |||||


改良交換法のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



改良交換法のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
デジタル大辞泉デジタル大辞泉
(C)Shogakukan Inc.
株式会社 小学館
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのシェーカーソート (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS