シェーカーソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）

このページでは、ソートアルゴリズムの１つである「シェーカーソート」について解説します。

まずシェーカーソートの解説を行い、その次にシェーカーソートを行うC言語のサンプルプログラムの紹介を行います。

シェーカーソートは、要は「バブルソートを改良したソートアルゴリズム」です。

ですので、シェーカーソートについて理解する前には、まずバブルソートを理解していただく必要があります。

バブルソートについては下記ページで解説しています。まだバブルソートをご存知ない方は下記ページを読んでおいていただけると、今後の解説が理解しやすくなると思います。

バブルソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）

シェーカーソートとは

まずは、シェーカーソートがどのようなアルゴリズムであるかを解説します。

シェーカーソートの特徴

シェーカーソートには下記のような特徴があります。

• バブルソートの改良版
  • バブルソートに比べるとソート速度は速い
  • バブルソートを理解していればシェーカーソートの理解も簡単
• 使用メモリが少ない（配列一つ分でソートできる）

シェーカーソートはバブルソートの改良版です。

改良版になったことでソート速度も向上しますが、計算量のオーダーが下がるわけではないので、劇的に速度が速くなるというわけではないです。

スポンサーリンク

シェーカーソートの考え方

では、シェーカーソートではどのような考え方でデータをソートするのかについて解説していきたいと思います。

バブルソートの特徴のおさらい

シェーカーソートは前述の通りバブルソートを改良したソートアルゴリズムです。

より具体的には、シェーカーソートはバブルソートの下記の特徴を利用してソートを効率よく行うソートアルゴリズムになります。

• 先頭から最後尾までの隣り合うデータの交換により、後ろ側の１つ以上のデータの位置が確定する

以降では、「先頭から最後尾までの隣り合うデータの交換」のようにソート範囲に対して隣り合うデータを交換する処理を “一連のデータ交換” と呼ばせていただきます。

バブルソートでは、この「一連のデータ交換」を繰り返すことでソートを行うソートアルゴリズムです。データの交換は「隣り合うデータの “大小関係が逆” の場合」のみ行います。

また、前述の通り、バブルソートでは「一連のデータ交換」が完了した際に、後ろ側の “１つ以上” のデータの位置が確定します。

位置が確定したデータに関していうと、すでにソートが完了していることになるため、もうソートを行う必要はありません。ですので、次は最後尾を “位置が確定していないデータの最後尾” として「一連のデータ交換」を行えば良いことになります（つまり位置が確定しているデータをソート範囲から省きます）。

つまり、ソート範囲を狭めながらソートを進めていくことが可能です。ソート範囲が狭まるので、処理の効率が上がります。

この辺りは、下記ページのソート範囲を考慮して効率アップさせると最後に交換したデータまでを次のソート範囲とするで説明していますので、詳しく知りたい方は読んでみてください。

バブルソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）

データの走査方向を逆にしながらソートするのがシェーカーソート

では、本題のシェーカーソートの解説に移ります。

前述の通り、バブルソートでは下記の特徴があります。

• 先頭から最後尾までの隣り合うデータの交換により、後ろ側の１つ以上のデータの位置が確定する

上記はデータの走査方向が “先頭から最後尾”  の場合の特徴です。位置が確定するのが “後ろ側のデータ” のみであるところがポイントです。

一方で、データの走査方向を逆にした場合の特徴、つまりデータの走査方向を “最後尾から先頭” とした場合の特徴は下記のようになります。

• 最後尾から先頭までの隣り合うデータの交換により、前側の１つ以上のデータの位置が確定する

“前側のデータ” の位置を確定することができるところがポイントです。

シェーカーソートはこれらの特徴を利用したソートアルゴリズムです。

要は、「一連のデータ交換」をデータの走査方向を入れ替えながら行います。そして「一連のデータ交換」が終了するたびに「一連のデータ交換」を行う範囲（つまりソート範囲）を狭めながら処理を行うことで、効率的にソートを行います。

例えば下の図のようなデータをソートするとしましょう。

まずは “先頭から最後尾” の方向で「一連のデータ交換」を行います。これにより “後ろ側の１つ以上のデータ” の位置が確定します。

この “位置が確定したデータ” をソート範囲から取り除き、次は “最後尾から先頭” の方向で「一連のデータ交換」を行います。これにより “前側の１つ以上のデータ” の位置が確定します。

さらに、位置が確定したデータをソート範囲から取り除き、次は “先頭から最後尾” の方向で「一連のデータ交換」を行います。これにより、また新たに後ろ側の１つ以上のデータの位置が確定します。

後はこれを繰り返していけば、いずれはソート範囲のデータ個数が１つになります。

ソート範囲のデータ個数が１つということは、１つ以外のデータが位置が確定したことになりますので、残りの１つも位置が確定していることになります。

なので、ソート範囲が１つになった際には、データ全体のソートが完了したと考えてソート処理を終了することができます。

今回は最初の１回目が “先頭から最後尾” の方向での「一連のデータ交換」として解説しましたが、逆の方向から開始しても良いです。重要なのは、この方向を交互に入れ替えながら「一連のデータ交換」を行なっていくことです。

ソート範囲の狭め方

では、「一連のデータ交換」によって、具体的にどのデータの位置が確定するのかについて解説していきたいと思います。

結論をいうと、「一連のデータ交換」を行うと下記のデータの位置が確定します。

• “先頭から最後尾” の方向で行なった場合：
  • 最後に交換を行なった “後ろ側” のデータの位置 〜 最後尾
    
• “最後尾から先頭” の方向で行なった場合：
  • 先頭 〜 最後に交換を行なった “前側” のデータの位置
    

次は上記のデータの位置が確定する理由を、”先頭から最後尾” の方向で「一連のデータ交換」を行った場合を例にして解説していきたいと思います。

この理由は、最後のデータ交換後のソート範囲のデータに対して下記の２つのことが言えるためです。

1. ソート範囲の「先頭のデータ 〜 最後にデータ交換を行なった “後ろ側” のデータ」の中で “最後にデータ交換を行なった後ろ側のデータ” が必ず一番大きいデータとなる
2. 最後にデータ交換を行なった “後ろ側” のデータ以降は大小関係が逆ではない

隣り合うデータが「大小関係が逆」の場合にデータを交換するということは、その隣り合うデータの中で “一番大きいデータ” を、その隣り合うデータの “後ろ側” に移動させることと考えることができます。

さらに、ある範囲の中でこの隣り合うデータを１つずつずらしながら交換を行うということは、その範囲の中で “一番大きいデータ” をその範囲の最後尾に移動させることと考えることができます。

つまり、1. で述べたように、最後に交換が行われた隣り合うデータの  “後ろ側” には、ソート範囲の「先頭から最後に交換が行われたデータ」の範囲の中で “一番大きいデータ” であるということができます。

また、最後にデータ交換が行われた “後ろ側” 以降のデータに注目すると、これらはデータ交換が行われなかったことになります。

データ交換は、隣り合うデータの「大小関係が逆」の場合に必ず行われるので、データ交換が行われなかったということは、2. で述べたように、最後にデータ交換を行なった “後ろ側” のデータ以降はすでに大小関係が整っていたということになります。

さらに、1. も加えて考えると、最後にデータ交換を行なった “後ろ側” のデータ以降は全て、「交換が行われた範囲の中の “一番大きいデータ以上” のデータ」と言えるので、大小関係が整っているだけでなく、最終的なデータの位置としても確定していると考えることができます。

“最後尾から先頭” の方向で「一連のデータ交換」を行った場合も、同様のことが言えるので、結局この節の最初に述べた「一連のデータ交換」を行うと下記のデータの位置が確定することになります。

• “先頭から最後尾” の方向で行なった場合：
  • 最後に交換を行なった “後ろ側” のデータの位置 〜 最後尾
    
• “最後尾から先頭” の方向で行なった場合：
  • 先頭 〜 最後に交換を行なった “前側” のデータの位置
    

シェーカーソートのプログラム

では、ここまで解説してきたシェーカーソートを実装したサンプルプログラムを紹介していきます。

ソースコード

シェーカーソートを行うC言語プログラムのサンプルのソースコードは下記のようになります。具体的には shakerSort 関数でシェーカーソートを実行しています。

#include <stdio.h>

/* データの数 */
#define NUM 10

/* 配列のデータを表示する関数 */
void printArray(int a[], int num){
    int i;
    for (i = 0; i < num; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

/*
 * シェーカーソートを行う関数
 * a：ソートしたいデータを格納した配列
 * num：ソートしたいデータの個数
 */
void shakerSort(int a[], int num) {

    int i;
    int tmp;
    int last_exchange; /* 交換したデータの後ろ側の位置*/
    int head, tail; /* ソート範囲の先頭と最後尾の位置 */

    /* データ全体をソート範囲とするように先頭と最後尾を設定 */
    head = 0;
    tail = num - 1;
    
    while (1) {

        last_exchange = head;

        /* 先頭から最後尾の方向にデータを走査 */
        for (i = head; i <= tail - 1; i++) {

            /* 隣り合うデータの大小関係を確認 */
            if (a[i] > a[i + 1]) {
                /* 大小関係が逆なら２つのデータを交換 */
                tmp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = tmp;

                /* 交換時の後ろ側のデータの位置を記憶 */
                last_exchange = i + 1;

            }
        }

        /* last_exchange位置以降はソート範囲から省く */
        tail = last_exchange - 1;

        if (tail == head) {
            /* 先頭と最後尾が一緒になったらソート完了 */
            return;
        }

        last_exchange = tail;

        /* 最後尾から先頭の方向にデータを走査 */
        for (i = tail - 1; i >= head; i--) {

            /* 隣り合うデータの大小関係を確認 */
            if (a[i] > a[i + 1]) {
                /* 大小関係が逆なら２つのデータを交換 */
                tmp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = tmp;

                /* 交換時の前側のデータの位置を記憶 */
                last_exchange = i + 1;

            }
        }

        /* last_changeの１つ前まではソート範囲から省く */
        head = last_exchange;

        if (tail == head) {
            /* 先頭と最後尾が一緒になったらソート完了 */
            return;
        }
    }
}


/* 配列を初期化する関数 */
void initArray(int a[]) {

    a[0] = 5;
    a[1] = 0;
    a[2] = 9;
    a[3] = 7;
    a[4] = 1;
    a[5] = 6;
    a[6] = 3;
    a[7] = 8;
    a[8] = 4;
    a[9] = 2;

}

int main(void) {
    int array[NUM];

    /* 配列を初期化 */
    initArray(array);

    /* ソート前の配列の表示 */
    printArray(array, NUM);

    /* シェーカーソート */
    shakerSort(array, NUM);

    /* ソート後の配列の表示 */
    printArray(array, NUM);

    return 0;

}

スポンサーリンク

ソースコードの解説

shakerSort 関数でポイントになるのは下記の３つの変数だと思います（”位置” とは、要は配列の要素番号のことです）。

• head：ソート範囲の先頭の位置
• tail：ソート範囲の最後尾の位置
• last_exchange：最後に交換を行なったデータの位置（隣り合うデータの “後ろ側” の位置）

head と tail がソート範囲を表しています。

 「一連のデータ交換」が完了するたびに、last_exchange（最後に交換を行なったデータの位置）に基づいて head や tail を変更してソート範囲を狭めていくところがポイントになります。

ソート範囲に対するループ

ソートを実際に行っているのは while ループの中です。

前半では、ソート範囲の “先頭から最後尾” の方向で「一連のデータ交換」を行っています。

/* 先頭から最後尾の方向にデータを走査 */
for (i = head; i <= tail - 1; i++) {
    /* 略 */
}

後半では、ソート範囲の “最後尾から先頭” の方向で「一連のデータ交換」を行っています。

/* 最後尾から先頭の方向にデータを走査 */
for (i = tail - 1; i >= head; i--) {
    /* 略 */
}

データの交換

実際にデータの交換を行なっているのは下記の部分になります。このデータ交換の処理は “先頭から最後尾” の方向の場合も “最後尾から先頭” の方向の場合も同様です。

/* 隣り合うデータの大小関係を確認 */
if (a[i] > a[i + 1]) {
    /* 大小関係が逆なら２つのデータを交換 */
    tmp = a[i];
    a[i] = a[i + 1];
    a[i + 1] = tmp;

    /* 交換時の前側のデータの位置を記憶 */
    last_exchange = i + 1;

}

前述の２つの for 文においては、 i  が取りうる値は head から tail - 1 までとなりますが、上記の通りデータの交換は a[i] と a[i + 1]とで行うため、head から tail までの範囲のデータ交換が行われることになります。

また、データの交換が行われるのは隣り合うデータの「大小関係が逆」の場合のみなので、a[i] > a[i + 1] の場合のみデータ交換を行うようにしています。

ソート範囲を狭める制御

交換時にシェーカーソートを行う上でポイントになるのは、下記の最後に交換した位置の記憶です。

last_exchange = i + 1;

last_exchange には、for ループの中で交換が実行されるたびに i + 1 が格納されるため、 for 文を抜けた際には最後に交換を行なった隣り合うデータの “後ろ側” の位置が格納されていることになります。

シェーカーソートでは、この last_exchange に基づいて head と tail の位置を変更していくことでソート範囲を狭めながら効率的にソートを行っていきます。

より具体的にいうと、”先頭から最後尾” の方向への「一連のデータ交換」が完了した際には、下記のように tail を last_exchange - 1 に更新することでソート範囲を狭めます。

/* last_exchange位置以降はソート範囲から省く */
tail = last_exchange - 1;

これは、”先頭から最後尾” の方向への「一連のデータ交換」が完了した際には、最後に交換を行なった隣り合うデータの “後ろ側”（つまり last_exchange の位置）以降のデータの位置が確定するためです。

逆に “最後尾から先頭” の方向への「一連のデータ交換」が完了した際には、下記のように head を last_exchange に更新することでソート範囲を狭めます。

/* last_changeの１つ前まではソート範囲から省く */
head = last_exchange;

これは、”最後尾から先頭” の方向への「一連のデータ交換」が完了した際には、最後に交換を行なった隣り合うデータの “前側”（つまり last_exchange - 1 の位置）までのデータの位置が確定するためです。

ソートの終了

この head と tail の更新によって head と tail が同じ位置になった時（つまりソート範囲のデータ数が１になった時）はソートが完了したことになります。ですので、この場合は下記のように return して関数を終了するようにしています。

if (tail == head) {
    /* 先頭と最後尾が一緒になったらソート完了 */
    return;
}

まとめ

このページではソートアルゴリズムの１つである「シェーカーソート」について解説しました！

シェーカーソートは、要はバブルソートを行う方向を交互に変化させながらソートを行うアルゴリズムになります。

このシェーカーソートのように、他のアルゴリズムを改良することで生まれたアルゴリズムもたくさんあります。その１つの例としてシェーカーソートの存在を知っておくと良いと思います！

ポイントはソートする範囲を狭めていくところだと思います。

最後にデータの交換を行なった位置が、どのように次のソート範囲の決め方に影響するかを考えながら実装すれば、バブルソートさえ理解していれば割と簡単に実装できると思います！

ソートアルゴリズムにはこのシェーカーソート以外にも様々なものが存在し、本サイトでは、シェーカーソート以外にも下記のソートについても解説しています。

• クイックソート
• マージソート
• 選択ソート
• 挿入ソート
• ヒープソート
• バブルソート

下記リンク先でそれぞれについて解説していますので、他のソートアルゴリズムにも興味のある方は是非こちらも読んでみてください！

クイックソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）

マージソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）

選択ソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）

挿入ソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）

ヒープソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）

バブルソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）