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

シェーカーソートの解説ページアイキャッチ

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

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

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

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

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

バブルソートの解説ページアイキャッチバブルソートを図を使って分かりやすく解説(C言語サンプルプログラム付き)

シェーカーソートとは

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

シェーカーソートの特徴

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

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

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

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

スポンサーリンク

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

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

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

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

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

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

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

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

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

バブルソートで先頭から最後尾までのデータの交換で後ろ側のデータの位置が確定する様子

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

2回目の一連のデータ交換時にはソート範囲が狭められる様子

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

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

バブルソートの解説ページアイキャッチバブルソートを図を使って分かりやすく解説(C言語サンプルプログラム付き)

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

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

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

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

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

バブルソートで先頭から最後尾までのデータの交換で後ろ側のデータの位置が確定する様子

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

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

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

バブルソートで最後尾から先頭までのデータの交換で後ろ側のデータの位置が確定する様子

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

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

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

ソートするデータの例

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

先頭から最後尾の方向の一連のデータで後ろ側のデータの位置が確定する様子

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

最後尾から先頭の方向の一連のデータで今度は後ろ側のデータの位置が確定する様子

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

先頭から最後尾の方向の一連のデータでさらに後ろ側のデータの位置が確定する様子

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

ソート範囲を狭めていくことでやがてソート範囲が1つになる様子

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

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

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

ソート範囲の狭め方

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

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

  • “先頭から最後尾” の方向で行なった場合:
    • 最後に交換を行なった “後ろ側” のデータの位置 〜 最後尾
      最後の交換を行なったデータの後ろ側以降のデータの位置が確定する様子
  • “最後尾から先頭” の方向で行なった場合:
    • 先頭 〜 最後に交換を行なった “前側” のデータの位置
      最後の交換を行なったデータの前側以前のデータの位置が確定する様子

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

MEMO

昇順にソートする場合を例に説明していきます

降順にソートする場合は大きい小さいを逆に考えて読んでいただければ話が合うと思います

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

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

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

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

最後に交換を行なったデータの後ろ側にそこまで交換を行なってきた範囲の中で1番大きいデータがくる様子

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

最後の交換を行なったデータの後ろ側にそこまで交換を行なった範囲の中で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]) {
                /* 大小関係が逆なら2つのデータを交換 */
                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]) {
                /* 大小関係が逆なら2つのデータを交換 */
                tmp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = tmp;

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

            }
        }

        /* last_changeの1つ前まではソート範囲から省く */
        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 関数でポイントになるのは下記の3つの変数だと思います(”位置” とは、要は配列の要素番号のことです)。

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

headtail がソート範囲を表しています。

headとtailがソート範囲を示す様子

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

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

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

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

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

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

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

データの交換

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

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

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

}

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

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

MEMO

a[i] > a[i + 1] は昇順ソート時のデータの交換を行う条件文になります

降順ソートの場合は、この条件文を a[i] < a[i + 1] に置き換えてやれば良いです 

ソート範囲を狭める制御

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

最後に交換した位置の記憶
last_exchange = i + 1;

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

last_exchangeが最後に交換されたデータの後ろ側の位置を示す様子

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

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

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

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

last_exchangeからtailのデータの位置が確定する様子

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

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

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

headからlast_exchange-1データの位置が確定する様子

ソートの終了

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

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

まとめ

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

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

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

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

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

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

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

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

クイックソート解説ページのアイキャッチクイックソートを図を使って分かりやすく解説(C言語サンプルプログラム付き) マージソート解説ページのアイキャッチマージソートを図を使って分かりやすく解説(C言語サンプルプログラム付き) 選択ソート解説ページのアイキャッチ選択ソートを図を使って分かりやすく解説(C言語サンプルプログラム付き) 挿入ソートの解説ページアイキャッチ挿入ソートを図を使って分かりやすく解説(C言語サンプルプログラム付き) ヒープソートの解説ページアイキャッチヒープソートを図を使って分かりやすく解説(C言語サンプルプログラム付き) バブルソートの解説ページアイキャッチバブルソートを図を使って分かりやすく解説(C言語サンプルプログラム付き)

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です