テクメモ このページをアンテナに追加 RSSフィード Twitter

2009-06-21

C言語で文字列のクイックソート

コマンドライン引数で受け取った文字列をstrcmpで比較してソートする。


#include <stdio.h>
#include <string.h>

void quicksort(char *array[], int left, int right) {
    if (left >= right) return;

    int l = left;
    int r = right;
    char *pivot = array[(left + right) / 2];  // 中央からピボットを選択
    char *buf;

    while (1) {
        while (strcmp(array[l], pivot) < 0) l++;
        while (strcmp(array[r], pivot) > 0) r--;

        if (l > r) break;

        // pivotより小さい値を左、大きい値を右に入れ替え
        buf = array[l];
        array[l] = array[r];
        array[r] = buf;

        l++, r--;
    }

    // pivotより小さい領域と大きい領域をそれぞれ再帰的にソート
    quicksort(array, left, r);
    quicksort(array, l, right);
}

int main(int argc, char *argv[]) {
    int i;

    if (argc < 2) {
        fprintf(stderr, "Usage; %s ...\n", argv[0]);
        return 1;
    }

    quicksort(argv, 1, argc - 1);

    for (i = 1; i < argc; i++) {
        printf("%s\n", argv[i]);
    }

    return 0;
}

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/lagos_on/20090621/1245606917
リンク元