C言語の研究・演習編3

第3章　ソートとサーチ

データの並べ替えつまりソートやデータ検索つまりサーチについては、現在は市販のアプリケーションが簡単に処理してくれるので助かる。

ここでは、その原理について研究してみよう。

1　選択法

私はこの方法が一番信頼のおけるソート方法と考えているが、手順は以下のとおりである。

左から順番に、a(0), a(1), a(2),・・・・・・・,a(n-1), a(n) という具合にデータがならんでいるとして、

まず、a(0)に対して、a(1)からa(n)までを順に比較してa0より小さいものがあれば、a0とそれを入れ換える。

今度は、a(1)と、a(2)〜a(n)までを比較してa1より小さいものがあればa1とそれを入れ換える。

これをa(n-1)になるまで繰り返す処理である。

さっそくテストしてみよう。char型配列のソートを選択法で行ってみよう。

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

char *sort(char *, int);
void main()
{
    char a[20];
    char *pa;
    int n;

    pa=a;

    printf("ソートする文字列を入力してください(20文字以下) :");
    scanf("%s",pa);

    n = strlen(pa);

    printf("-----Result-----\n");
   
    printf("%s\n",sort(pa,n));
}

char *sort(char *pa, int n)
{
    int i, a;
    char temp;

    for(i=0; i<n-1; i++){
        for(a=i+1; a<n; a++){
            if( *(pa+a) < *(pa+i) ){
                            temp = *(pa+a);
                            *(pa+a)=*(pa+i);
                            *(pa+i)= temp;
            }
        }
    }
    return pa;
}

どうだろうか、配列の頭から1文字づつ、残りの文字と比較して、小さいものがあれば、一時領域にコピーしてから小さいものと入れ換える。この入れ換えをスワップと呼んでいる。

では次に、文字配列を5個入力させて、選択法によりstrcmp関数で比較してソートさせてみよう。

レッツノート、いやレッツビギン。

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

#define KOSU 5

char **sort(char **, int);
void main()
{
    char a[KOSU][21];
    char *pa[KOSU];
    char **p_pa;
    int i;

    for(i = 0; i < KOSU; i++)    pa[i] = a[i];
    p_pa = &pa[0];

    printf("ソートする文字配列を%d個入力してください(20文字以下)\n",KOSU);

    for(i=0; i < KOSU; i++){
        printf("文字配列%d :",i+1);
        scanf("%s",*(p_pa+i));
    }

    printf("-----Result-----\n");

    sort(p_pa, KOSU);
   
    for(i=0; i < KOSU; i++)
        printf("%d     %s\n",i+1 , *(p_pa+i));
}

char **sort(char **p, int n)
{
    int i, j;
    char *temp;

    for(i=0; i<n-1; i++){
        for(j = i+1; j<n; j++){
            if( strcmp(*(p+i) , *(p+j )) > 0 ){
                            temp = *(p+j );
                            *(p+j ) = *(p+i);
                            *(p+i) = temp;
            }
        }
    }
    return p;
}

どうだろうか。文字配列にはポインタ型を指すポインタを使用すれば便利だね。

ただし、実体とポインタの設定はしっかりやっておこう。これがポインタを使う際の基本だったね。

2　クイックソート

私はこの方法をあまり信頼のおけないソート方法と考えているが、基本書に掲載されているので紹介する。

手順は以下のとおりである。

a(0),a(1),a(2),・・・・,a(n-1),a(n)　というデータの並びがあった場合、

中央付近のデータ、この場合なら、n/2=tとすると、a(t)を基準値とする。

基本的なアルゴリズムは後で説明するが、tより左はa(t)以下のデータ、tより右はa(t)以上のデータが並ぶことを目的とする。

そこで、a(t)より左のデータについても、中央付近の基準値を決めて、基準値から左は基準値以下のデータ、右は基準値以上のデータが並ぶようにする。これを繰り返して要素数が2以下になるようにする。2つになれば大小比較して、逆なら交換する。1つなら終わりということになる。

a(t)より右のデータについても同様のことをする。

それでは、基準値a(t)以下のデータは左に、基準値a(t)以上のデータが右に来るように並べ替える手順を見て行こう。

まず、左端a(0)からa(t)までについて、a(i) > =a(t)のデータを探すと同時に、右端のa(n)からa(t)までについては、a(j) <= a(t)のデータを探す。

i < j　の状態で上記赤色のデータが見つかった場合、a(i)とa(j)を交換し、i を右へ、 j を左とそれぞれ1ずつ進めて、赤色の処理を繰り返す。

i = j のときは、両者ともt の位置にあるから、a(0)からa(t-1)を左側の範囲とし、a(t+1)からa(n)までを右側の範囲として処理を終了する。このときa(t)の位置が確定したことになる。

i > j のときは、既にa(t)以下のデータは左に、a(t)以上のデータは右にあることになり、a(0)からa(j)を左側の範囲とし、a(i)からa(n)を右側の範囲として処理を終了する。

なお、赤字の処理は要素数が2以下になるまで繰り返すので再帰呼び出しを利用しよう。

それでは例をみていただこう。

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

char *qsort(char *, int);
void swap(char *, char *);
void main()
{
    char a[21];
    char *pa;
    int n;

    pa=a;

    printf("クイックソートする文字列をいれてください(20文字以下) :");
    scanf("%s",pa);
    n = strlen(pa);

    printf("-----Result-----\n");
   
    printf("%s\n",qsort(pa,n));
}

char *qsort(char *pa, int n)
{
    int i, a;
    char t;

    if(n==2){ /*データが2個の場合*/
        if(*(pa) > *(pa+1)) swap(pa,(pa+1));
    }
    else if(n>2){ /*データが2個以上の場合*/
        t = *(pa+n/2); /*基準値を設定*/
        i = -1;
        a = n;

        while(i < a){
            while(*(pa+(++i)) < t);
            while(*(pa+(--a)) > t);

            if(i < a)
                swap(pa+i, pa+a);
            else if(i == a){
                qsort(pa, i); /*paからpa+i-1まで再帰呼び出し*/
                qsort(pa+i+1, n-(i+1)); /*pa+i+1からpa+nまで再帰呼び出し*/
            }
            else{
                qsort(pa, a+1); /*paからpa+aまで再帰呼び出し*/
                qsort(pa+i, n-i); /*pa+iからpa+nまで再帰呼び出し*/
            }
        }
    }
    return pa;
}

void swap(char *pa, char *pb)
{
    char temp;
    temp=*pa;
    *pa=*pb;
    *pb=temp;
}

どうだろうか。ポインタを使ったから私もかなり混乱してしまったが、注釈を見れば納得するだろう。

なお、クイックソートはデータの並びによってはソートできないことがあるので使用しない方がいいだろう。

できるだけソートには選択法を利用しよう。

3　マージ

マージとは「併合」というほどの意味だろう。よく2つのデータファイルをマージするとかいうが、マージするための前提条件としては、マージするデータ列がいずれも既にソートされていなければならないことだ。

方法は極めて簡単だ。

a(0),a(1),・・・・,a(n-1),a(n) という昇順にソートされたデータ列と、

b(0),b(1),・・・・,b(n-1),b(n) という昇順にソートされたデータ列の2つがあったとして、

これをマージしてc というデータ列を作成する場合を考えてみよう。

まず、a(0)とb(0)を比較して小さい方をc(0)にコピーする。

aの添字i をひとつ進めてa(1)として、b(0)と比較する。そして小さい方をcにコピーして添字を1つ進める。

これを繰り返し行い、片方のデータ列が終わりに達したら、他の残っているデータ列を全てcにコピーする。

こんな方法だ。さっそく見てみよう。

2つの文字列をscanf関数により入力させて、これをソートした上で、2つの文字列をマージして出力するようにしてみた。

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

void sort(char *, int);
char *merge(char *, char *, char *, int ,int);

void main()
{
    char a[21];
    char b[21];
    char c[41];
    int n;
    int m;

    char *pa = a;
    char *pb = b;
    char *pc = c;


    printf("マージする文字列a[]を入力してください(20字以内) :");
    scanf("%s",pa);
    n = strlen(pa);
    sort(pa, n);

    printf("マージする文字列b[]を入力してください(20字以内) :");
    scanf("%s",pb);
    m = strlen(pb);
    sort(pb, m);

    printf("-----Result-----\n");
    printf("%s\n",merge(pa, pb, pc, n, m));
}

char *merge(char *pa, char *pb, char *pc, int t1, int t2)
{
    int i = 0;
    int j = 0;
    int k = 0;

    while(i < (t1) && j < t2){
        if(*(pa+i) < *(pb+j )) *(pc+k++) = *(pa+i++);
        else *(pc+k++) = *(pb+j++);
    }
    if(i == t1){
        while(j < t2) *(pc+k++) = *(pb+j++);
    }
    else *(pc+k++) = *(pa+i++);
   
    *(pc+k) = NULL;
    return pc;
}

void sort(char *p, int n)
{
    int i, a;
    char temp;

    for(i=0; i<n-1; i++){
        for(a = i+1; a < n; a++){
            if( *(p+a) < *(p+i) ){
                            temp = *(p+a);
                            *(p+a)=*(p+i);
                            *(p+i)= temp;
            }
        }
    }
}

どうだろうか、特にコメントを付すほどの必要はないだろう。

このように、ユーザがわざわざソートしたデータを入力することなく、できるだけ簡単に好きな文字列を入力できるようにしてやること、これがプログラミングの基本と言えるね。

4　二分探索法

二分探索法とは、データが昇順に並んでいることが前提のデータ検索方法で、基本的には、目的のデータが前半にあるか後半にあるかを見て、徐々に範囲を絞って行くやり方だ。　

具体的には以下の要領でやる。

a(0),a(1),・・・・,a(n-1),a(n) という昇順に並んでいるデータ列があったとして、目的のデータsを探索する場合、

最初のデータa(0)と、最後のa(n)を見ると、目的のsがこれらのデータ範囲にあるかないかが判明する。

あった場合、クイックソートと同じ要領で、範囲の中央のデータ a(m) = (a(0) + a(n))/2を求める。

a(m)とsを比較し、

s = a(m) の場合、見つかったということだが、複数個存在する場合もあるので、1つずつ前にさかのぼり、先頭のデータを目的のデータとする。

s < a(m) の場合、a(m-1)を最終データとし、a(0)〜a(m-1)を範囲とする。

s > a(m) の場合、a(m+1)を最初のデータとし、a(m+1)〜a(n)を範囲とする。

これを繰り返して行き、s = a(m)となったら発見となっていいが、最終データ < 最初のデータ となった場合は見つからなかった、つまり該当なしということである。  

さっそく例題で確認してみよう。

学生データとして学生番号、名前へのポインタ、年齢が年齢順に格納されている構造体配列に対して、年齢を入力させて、該当する年齢の学生データを全部表示させるプログラムである。

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

#define KOSU 10

typedef struct nenrei_hyo{
    int no;
    char *name;
    int age;
}DATA;

DATA *search(DATA *,int, int);

void main()
{
    DATA age_jun[10]={
        {1001,"pell", 17},
        {1002,"Akira",17},
        {1003,"Bruce",18},
        {1004,"Friend",18},
        {1005,"Tomato",19},
        {1006,"Pineapple",19},
        {1007,"Masked",20},
        {1008,"Tongarashi",20},
        {1009,"Onion",21},
        {1010,"Charly",22}
    };

    DATA    *pa;
    DATA    *pn;
    int age;
    char buff[80];
    int i;

    pa = age_jun;

    printf("年齢を入れてください : ");
    while(gets(buff) != NULL){
        age = atoi(buff);
        pn = search(pa,KOSU,age);
       
        if(pn != NULL){
            printf("     ��    名前    年齢\n");
            for(i=0; (pn+i)->age == age; i++){
                printf("%2d     %4.4d    %s    %2d\n"
                    ,i+1, (pn+i)->no, (pn+i)->name, (pn+i)->age);
            }
        }
        else{
            printf("該当なし\n");
        }
        printf("\n年齢を入れてください : ");
    }
}

DATA *search(DATA *pt, int n, int age)
{
    DATA *pm;
    DATA *ps;
    DATA *pe;
    DATA *pr = NULL;

    if( pt->age <= age && (pt+n-1)->age >= age){
        ps=pt;
        pe=pt+n-1;

        while(ps <= pe){
            pm = ps+(pe-ps)/2;
            if (pm->age > age) pe = pm-1;
            else if (pm->age < age) ps = pm+1;
            else break;
        }

        if(pm->age == age){
            pr = pm;
            while( pr > pt && (pr-1)->age == age) pr--;
        }
    }
    return pr;
}

いかがだろうか。学生データはあらかじめ作成しておいたが、これをscanf関数で入力させるプログラムに変えてみても面白いだろう。ただし、ユーザ側は入力の手間がかかる。

では、この章の最後に恒例の情報処理技術者試験の問題を研究してみよう。

n人の学生の試験成績が高い順に並んでいるとき、ある得点の学生の順位を調べるプログラムである。

成績は構造体配列で、得点順にそれぞれ、学生番号、名前へのポインタ、得点を格納している。得点が同点の場合は学生番号の若い順となっている。学生番号に重複はないものとする。

得点をscanf関数で入力させて、構造体配列から同得点のデータを検索する。同得点の学生が存在しない場合は、それより低い最も近い得点の学生の順位を表示する。ただし、最低点より低い得点の場合はn+1番とする。

データの検索方法は次のとおり二分探索である。

入力された得点(tenとする)が最低点より低い場合はn+1番であり、最高点より高い場合は1番とする。

構造体配列へのポインタ配列をp[]とするならば、p[0]をstart、p[n-1]をendとし、範囲の中央のデータ、つまり、p[m] (m = (start + end) / 2)を求める。

p[m]の得点と入力された得点tenとを比較し、以下の処理を行う。

�@ ten = p[m] のとき、下記の同点処理を行う

�A ten > p[m] のとき、p[m-1]をendとする

�B ten < p[m] のとき、p[m+1]をsrartとする

�A�Bを繰り返し、end < start となったとき、入力された得点は、p[end]とp[start]の間にあることがわかり、求める順位はp[start]の学生の順位である。

同点の学生がp[m]に存在する場合、同点の学生の中で先頭の学生の位置を求める順位とする。

長い問題の説明だが、降順データの場合の二分探索法で、ほとんどアルゴリズムが問題中にあるので、あとはプログラムをそのまま見て行けばいいだけだ。

さて、見てみよう。

#include <stdio.h>

#define NINZU 10

typedef struct seiseki{
    int no;
    char *namae;
    int ten;
}DATA;

int juni(DATA *, int, int);

void main(int argc, char **argv)
{
    DATA z[10]={
        {1001, "pell" ,100},
        {1002, "Akira" ,99},
        {1003, "Brue" ,87},
        {1004, "Red" ,75},
        {1005, "Pink" ,66},
        {1006, "White" ,52},
        {1007, "Yellow" ,43},
        {1008, "Green" ,36},
        {1009, "Brown" ,25},
        {1010, "Black" ,9}
    };

    int ten;
    int x;
    DATA *pa;
    pa = z;

    printf("得点を入力してください :");
    scanf("%d",&ten);
    x = juni(pa, NINZU, ten);
    printf("-----Result-----\n");
    printf("順位は%2d位です\n",x);
}

int juni(DATA *p, int n, int ten)
{
    int m;
    int s;
    int e;
    int x;
   
    if(ten > p->ten) x = 1;
    else if(ten < (p+n-1)->ten) x = n+1;
    else{
        s = 0;
        e = n-1;
        while(s <= e){
            m = (s + e) / 2;
            if((p+m)->ten < ten) e = m-1;
            else if((p+m)->ten > ten) s = m+1;
            else break;
        }

        if((p+m)->ten == ten){
                x = m+1;

                while(x > 1 && (p+x-2)->ten == ten) x--;
        }
        else x = s+1;
    }
    return x;
}

どうだろうか、例によって赤色部分の穴埋め式だ。

二分探索は知っているぜと問題をよく読みもせずに解答にとりかかってしまうと、私のように降順に並んでいるのを見落として失敗してしまう。

落ち着いて行こう。この問題のように答えが説明の中に書かれている場合もあるからね。

HOME