C言語によるシェーカーソート

はじめに

今回はC言語でシェーカーソート（双方向バブルソート）を作成したので解説記事を書きます。 ある程度C言語が読める人向けの記事なので基本から説明しません。 予めご了承ください。

シェーカーソート

#include <stdio.h>
#include <stdlib.h>

#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)

void shaker(int a[], int n)
{
int left = 0;
int right = n -1;
int last = right;

while (left < right) {
int j;
for (j = right; j > left; j--) {
if (a[j - 1] > a[j]) {
swap(int, a[j - 1], a[j]);
last = j;
}
}
left = last;

for (j = left; j < right; j++) {
if (a[j] > a[j + 1]) {
swap(int, a[j], a[j + 1]);
last = j;
}
}
right = last;
}
}

int main(void) {
int i, nx;
int *x;

puts("単純交換ソート");
printf("要素数：");
scanf("%d", &nx);

x = (int *)malloc(sizeof(int)*nx);

for (i = 0; i < nx; i++) {
printf("x[%d]:", i);
scanf("%d", &x[i]);
}

shaker(x, nx);

puts("昇順にソートしました。");
for (i = 0; i < nx; i++) {
printf("x[%d] = %d\n", i , x[i]);
}

free(x);

return 0;
}

Mainクラスの解説はスッキプしてshakeクラスの説明をしていきます。

読み込まれるてソートされる値は下記値とします。

9 1 3 4 6 7 8

まずshake関数内に入ると左端と右端の値、最後に交換した位置を代入します。

int left = 0;
int right = n -1; //6
int last = right; //6

while (left < right) { がループを続ける条件式です。 1回目のループ時は、left=0とright=6で0<6となり条件を満たしているのでループをします。

for (j = right; j > left; j--) ではj=6でj>0になるまでデクリメントしていきループを続けます。（ここでは5回 ループします）

続いてif (a[j - 1] > a[j]) の条件分岐です。 配列の5番目と6番目を比較すると7 > 8 なのでfalseです。

まだループが続いているので再度条件式を評価します。(ここから簡略します。)

1. j=5の時、6 > 7はfalse
2. j=4の時、4 > 6はfalse
3. j=3の時、3 > 4はfalse
4. j=2の時、1 > 3はfalse
5. j=1の時、9 > 1はtrue

j=1の比較でtrueがswap関数が実行されます（9と1を交換する処理）。

現代のデータ下記のようになっています。

1 9 3 4 6 7 8

lastには1が代入されます。

for文を一回抜けて変数leftに1(last=1)を代入します。

for (j = left; j < right; j++) のfor文の条件は j=1が初期値で、j<6になるまでインクリメントします。

if (a[j] > a[j + 1]) の条件式なので下記簡略したループのイメージです。

1. j=1の時、9 > 3はtrue 交換後データは「1 3 9 4 6 7 8」
2. j=2の時、9 > 4はtrue 交換後データは「1 3 4 9 6 7 8」
3. j=3の時、9 > 6はtrue 交換後データは「1 3 4 6 9 7 8」
4. j=4の時、9 > 7はtrue 交換後データは「1 3 4 6 7 9 8」
5. j=5の時、9 > 8はtrue 交換後データは「1 3 4 6 7 8 9」

最終的に「1 3 4 6 7 8 9」になって昇順のソート完了です。

シェーカーソートにより大幅にループ回数を抑えることができました。

今日はこれぐらいで終わりにしたいと思います。 最後まで読んでいただいてありがとうございました。

もしよろしければtwitterアカウント（@piklus100yen）もフォローしていただけると幸いです！