Ｃ言語によるアルゴリズムとデータ構造

演習6-5の解答

　以下に示すデータの並びをソートすることを考えよう。
　　9 1 3 4 6 7 8
　ほぼソート済みであるにも関わらず、最大の要素9が先頭に位置しているために、第3版のアルゴリズムでも、ソート作業を早期に打ち切ることはできない。というのも、最大の要素は、各パスにおいて、一つずつしか後ろに移動しないためである。
　そこで、奇数パスでは最小要素を先頭側に移動させ、偶数パスでは最大要素を末尾側に移動するというように、パスを交互に行えば、このような並びを高速にソートできるはずである。バブルソートを改良したこのアルゴリズムは、双方向バブルソート（bidirection bubble sort ）あるいはシェーカーソート（shaker sort ）という名称で知られている。
　第3版を改良して、双方向バブルソートを行うプログラムを作成せよ。

/*
    演習6-5
    シェーカーソート
*/

#include  <stdio.h>

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

void shakersort(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;
    int  x[7];
    int  nx = sizeof(x) / sizeof(x[0]);
    
    printf("%d個の整数を入力せよ。\n", nx);
    for (i = 0; i < nx; i++) {
        printf("x[%d] : ", i);
        scanf("%d", &x[i]);
    }

    shakersort(x, nx);                          /* 配列xをシェーカーソート */

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

    return (0);
}

戻る