トップC-Tips > データの並び替え(ソート)

データの並び替え(ソート)

1.単一項目についてのソート

下のプログラムに示すように、 文字列型と整数型の要素からなる構造体Funcの配列についての並び替えについて述べる。

まず、文字列型の要素について、アルファベット順に並び替えるプログラムが sort01.c である。 コールバック関数 cmp の引数は、比較する二つのレコードの先頭アドレスを表す。 したがって、アロー演算子を使って、比較要素を指定すればよい。

sort01.c
#include <stdio.h> 
#include <string.h>
#include <stdlib.h>

typedef struct _Func {
    char *name;
    int  len;
} Func;

Func func[] = {
   { "strcpy", 6 },
   { "atoi", 4 },
   { "qsort", 5 },
   { "put", 3 },
   { "itoa", 4 },
   { "printf", 6 },
   { "puts", 4 },
};

int cmp(const void *p, const void *q) {
    return strcmp(((Func *)p)->name, ((Func *)q)->name);
}

int main() {
    int n;
    qsort(func, sizeof(func)/sizeof(Func), sizeof(Func), cmp);
    for (n = 0; n < sizeof(func)/sizeof(Func); n++) {
        printf("%s\t %d\n", func[n].name, func[n].len);
    }
}

実行結果を下に示す。正しく、アルファベット順に並び替えられたことを確認できる。

c:\MH\www\c-tips\data-structure>sort01
atoi     4
itoa     4
printf   6
put      3
puts     4
qsort    5
strcpy   6

2.複数項目についてのソート

複数項目についての並び替えは、比較関数を少し変えるだけでよい。 例えば、まず、整数型データ len について、小さい順に並び替え、 値が同じ場合については、文字列型データ name について、 アルファベット順に並び替えるプログラムを下に示す。

sort02.c
#include <stdio.h> 
#include <string.h>
#include <stdlib.h>

typedef struct _Func {
    char *name;
    int  len;
} Func;

Func func[] = {
   { "strcpy", 6 },
   { "atoi", 4 },
   { "qsort", 5 },
   { "put", 3 },
   { "itoa", 4 },
   { "printf", 6 },
   { "puts", 4 },
};

int cmp(const void *p, const void *q) {
    int r = ((Func *)p)->len - ((Func *)q)->len;
    if (r != 0) return r;
    return strcmp(((Func *)p)->name, ((Func *)q)->name);
}

int main() {
    int n;
    qsort(func, sizeof(func)/sizeof(Func), sizeof(Func), cmp);
    for (n = 0; n < sizeof(func)/sizeof(Func); n++) {
        printf("%s\t %d\n", func[n].name, func[n].len);
    }
}

実行結果を下に示す。正しく並び替えられたことを確認できる。

put      3
atoi     4
itoa     4
puts     4
qsort    5
printf   6
strcpy   6