アルゴリズムとデータ構造：ソート、サーチの数値以外への応用

C/C++ アルゴリズム

ここまでに出て来たソート、サーチのプログラムは全て数値のみを対象として
操作されていたが、もちろん配列でも同じように書けるよ的な応用。
本の検索がお題。

[book_seach.c]

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

#define N 5

typedef struct {
    char *title;
    char *author;
    int bookID;
    int available;
} book;

book *bookarray[N];

void initdata(void){
    int n;
    for(n = 0; n < N; n++){
         bookarray[n] = (book*)malloc(sizeof(book));
    }

    bookarray[0]->title = "book0";
    bookarray[1]->title = "book1";
    bookarray[2]->title = "book2";
    bookarray[3]->title = "book3";
    bookarray[4]->title = "book4";
    bookarray[0]->author = "author0";
    bookarray[1]->author = "author1";
    bookarray[2]->author = "author2";
    bookarray[3]->author = "author3";
    bookarray[4]->author = "author4";
    bookarray[0]->bookID = 1000;
    bookarray[1]->bookID = 502;
    bookarray[2]->bookID = 731;
    bookarray[3]->bookID = 628;
    bookarray[4]->bookID = 1;
    bookarray[0]->available = 1;
    bookarray[1]->available = 0;
    bookarray[2]->available = 0;
    bookarray[3]->available = 1;
    bookarray[4]->available = 1;
}

void cleanupdata(void){
   int n; 
   for (n = 0; n < N; n++) {
        free(bookarray[n]); 
   }
}

void sortbook(int bottom, int top){
    int lower, upper, div;
    book *temp;

    if (bottom >= top) {
        return; 
    }

    div = bookarray[bottom]->bookID;
    for (lower = bottom, upper = top; lower < upper;) {
        while (/*lower < upper && */ bookarray[lower]->bookID < div) {
            lower++; 
        }
        while (/*lower < upper && */ bookarray[upper]->bookID > div) {
            upper--; 
        }
        if (lower < upper) {
            temp = bookarray[lower]; 
            bookarray[lower] = bookarray[upper];
            bookarray[upper] = temp;
            lower++;
            upper--;
        }
        sortbook(bottom, upper);
        sortbook(upper + 1, top);
    }
}

int searchbook(book *books[],int size, int key){
    int left, mid, right;
    left = 0;
    right = size;
    while (left < right) {
        mid = (left + right)  / 2;
        if (books[mid]->bookID < key){
            left = mid + 1; 
        }
        else {
            right = mid; 
        }
    }
    if (books[left]->bookID == key) {
        return left; 
    }

    return -1;
}

int main(void) {
    int key, position;

    initdata();
    sortbook(0, N - 1);

    while (1) {
        printf("検索する本の番号を入力"
        "(0で終了)："); 
        scanf("%d", &key);
        if (key == 0) break;

        position = searchbook(bookarray, N - 1, key);
        if (position != -1) {
            printf("-- 次の本が見つかりました --\n"
                    "[タイトル]%s [著者]%s [管理番号]%d \n", 
                    bookarray[position]->title,
                    bookarray[position]->author,
                    bookarray[position]->bookID
                    ); 
            if (bookarray[position]->available != 0) {
                puts("この本は貸し出し可能です\n"); 
            }
            else {
                puts("この本は貸し出し中です\n"); 
            }
        }
        else {
            puts("お探しの本は見つかりませんでした\n"); 
        }
    }
    cleanupdata();
    return 0;
}

ちょっとしか変わらないけどC++版。
C++に全くわかりませんが演算子のオーバーロードってよくあるの？
個人的には好きじゃないけど、世間では当たり前でしょ、って感じだったら慣れようか。
[book_seach.cpp]

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

class CBook {
public:
    char *title;
    char *author;
    int bookID;
    int available;

    bool operator<(CBook& book) {
        return bookID < book.bookID; 
    }
    bool operator>(CBook& book) {
        return bookID > book.bookID; 
    }
    operator int() {
        return bookID; 
    }
};

#define N 5

CBook *bookarray[N];

void initdata(void){
    int n;
    for(n = 0; n < N; n++){
         //bookarray[n] = (book*)malloc(sizeof(book));
         bookarray[n] = new CBook;
    }

    bookarray[0]->title = "book0";
    bookarray[1]->title = "book1";
    bookarray[2]->title = "book2";
    bookarray[3]->title = "book3";
    bookarray[4]->title = "book4";
    bookarray[0]->author = "author0";
    bookarray[1]->author = "author1";
    bookarray[2]->author = "author2";
    bookarray[3]->author = "author3";
    bookarray[4]->author = "author4";
    bookarray[0]->bookID = 1000;
    bookarray[1]->bookID = 502;
    bookarray[2]->bookID = 731;
    bookarray[3]->bookID = 628;
    bookarray[4]->bookID = 1;
    bookarray[0]->available = 1;
    bookarray[1]->available = 0;
    bookarray[2]->available = 0;
    bookarray[3]->available = 1;
    bookarray[4]->available = 1;
}

void cleanupdata(void){
   int n; 
   for (n = 0; n < N; n++) {
        delete bookarray[n]; 
   }
}

void sortbook(int bottom, int top){
    int lower, upper;
    CBook *div, *temp;

    if (bottom >= top) {
        return; 
    }

    div = bookarray[bottom];
    for (lower = bottom, upper = top; lower < upper;) {
        while (*bookarray[lower] < *div) {
            lower++; 
        }
        while (*bookarray[upper] > *div) {
            upper--; 
        }
        if (lower < upper) {
            temp = bookarray[lower]; 
            bookarray[lower] = bookarray[upper];
            bookarray[upper] = temp;
            lower++;
            upper--;
        }
        sortbook(bottom, upper);
        sortbook(upper + 1, top);
    }
}

int searchbook(CBook *books[],int size, int key){
    int left, mid, right;
    left = 0;
    right = size;
    while (left < right) {
        mid = (left + right)  / 2;
        if (*books[mid] < key){
            left = mid + 1; 
        }
        else {
            right = mid; 
        }
    }
    if (*books[left] == key) {
        return left; 
    }

    return -1;
}

int main(void) {
    int key, position;

    initdata();
    sortbook(0, N - 1);

    while (1) {
        printf("検索する本の番号を入力"
        "(0で終了)："); 
        scanf("%d", &key);
        if (key == 0) break;

        position = searchbook(bookarray, N - 1, key);
        if (position != -1) {
            printf("-- 次の本が見つかりました --\n"
                    "[タイトル]%s [著者]%s [管理番号]%d \n", 
                    bookarray[position]->title,
                    bookarray[position]->author,
                    bookarray[position]->bookID
                    ); 
            if (bookarray[position]->available != 0) {
                puts("この本は貸し出し可能です\n"); 
            }
            else {
                puts("この本は貸し出し中です\n"); 
            }
        }
        else {
            puts("お探しの本は見つかりませんでした\n"); 
        }
    }
    cleanupdata();
    return 0;
}

アルゴリズムとデータ構造：バイナリサーチ

C/C++ アルゴリズム

ニ分探索。
配列の真ん中の値と探している値を比較、それを繰り返すことでターゲットを絞って行く。
対象となる配列がソートされている必要がある。
データ量が少なかったり、ソートする時間がない場合はリニアサーチにしましょう。


[計算量]
O(log N)


[binary_seach.c]

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

#define NOT_FOUND (-1)
#define N (10)

int binary_search(int x, int *a, int left, int right) ;

int binary_search(int x, int *a, int left, int right) {
    int mid = 0;

    while (left <= right) {
        mid = (left + right) / 2;
        if (a[mid] == x) {
            return mid; 
        }
        printf("a[mid]:%d < x:%d=>%d\n", a[mid] ,x ,a[mid] < x);
        if (a[mid] < x) {
            left = mid + 1;
        }
        else {
            right = mid - 1; 
        }
    }

    return NOT_FOUND;
}

int main(void){
    int i,r,array[N];
    
    srand((unsigned int) time(NULL));
    printf("array...\n");
    for(i = 0; i <  N; i++){
        array[i]  = array[i-1] + rand() % 3;
        printf("[%d]:%d",i,array[i]);
    }

    printf("\n何をさがしますか:");
    scanf("%d", &i);

    r = binary_search(i, array, 0, N - 1);

    if (r == NOT_FOUND) {
        printf("%dはみつかりませんでした\n", i); 
    }
    else {
        printf("%dは%d番目です\n", i, r); 
    }

    return EXIT_SUCCESS;
}


改良版。配列内に同じ値が存在する場合、真ん中に近いものしか取得できないのを左よせで検索。ちょっとコード変えると右よせでも検索できる。
[binary_seach_plus.c]

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

#define NOT_FOUND (-1)
#define N (10)

int binary_search(int x, int *a, int left, int right) ;

int binary_search(int x, int *a, int left, int right) {
    int mid;

    while (left < right) {
        mid = (left + right) / 2;
        if (a[mid] < x) {
            left = mid + 1;
        }
        else {
            right = mid; 
        }
    }
    if (a[left] == x) {
        return left; 
    }

    return NOT_FOUND;
}

int main(void){
    int i,r,array[N];
    
    srand((unsigned int) time(NULL));
    printf("array...\n");
    for(i = 0; i <  N; i++){
        array[i]  = array[i - 1] + rand() % 3;
        printf("[%d]:%d",i,array[i]);
    }

    printf("\n何をさがしますか:");
    scanf("%d", &i);

    r = binary_search(i, array, 0, N - 1);

    if (r == NOT_FOUND) {
        printf("%dはみつかりませんでした\n", i); 
    }
    else {
        printf("%dは%d番目です\n", i, r); 
    }

    return EXIT_SUCCESS;
}

C言語にはbsearch()、C++にはbinary_seach()という関数でバイナリーサーチができる。

アルゴリズムとデータ構造：リニアサーチ

C/C++ アルゴリズム

リニアサーチは配列の先頭から順番に調べて行って探している数字と同じであればキーを返す。
単純挿入ソートで使った方法。逐次探索、線形探索とも言う。C++標準ライブラリのfind()が相当する。


[計算量]
O(N)


[linear_search.c]

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

#define NOT_FOUND (-1)
#define N (10)

int linear_search(int x, int *a, int num) ;

int linear_search(int x, int *a, int num) {
    int n = 0;

    while (n < num && a[n] != x) {
        ++n; 
    }
    if (n < num){
        return n; 
    }

    return NOT_FOUND;
}

int main(void){
    int i,r,array[N];
    
    srand((unsigned int) time(NULL));
    printf("array...\n");
    for(i = 0; i <  N; i++){
        array[i]  = rand() % 10;
        printf("[%d]:%d",i,array[i]);
    }

    printf("\n何をさがしますか:");
    scanf("%d", &i);

    r = linear_search(i, array, N);

    if (r == NOT_FOUND) {
        printf("%dはみつかりませんでした\n", i); 
    }
    else {
        printf("%dは%d番目です\n", i, r); 
    }

    return EXIT_SUCCESS;
}

改良版。whileの条件が1つ減った。このやり方は覚えておいたらいいかも。10%くらい速くなるそうです。
[linear_search_plus.c]

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

#define NOT_FOUND (-1)
#define N (10)

int linear_search(int x, int *a, int num) ;

int linear_search(int x, int *a, int num) {
    int n = 0, t;

    t = a[num - 1];
    a[num - 1] = x;
    while (a[n] != x) {
        ++n; 
    }

    a[num - 1] = t;
    if (n < num - 1){
        return n; 
    }
    if (x == t){
        return n; 
    }

    return NOT_FOUND;
}

int main(void){
    int i,r,array[N];
    
    srand((unsigned int) time(NULL));
    printf("array...\n");
    for(i = 0; i <  N; i++){
        array[i]  = rand() % 10;
        printf("[%d]:%d",i,array[i]);
    }

    printf("\n何をさがしますか:");
    scanf("%d", &i);

    r = linear_search(i, array, N);

    if (r == NOT_FOUND) {
        printf("%dはみつかりませんでした\n", i); 
    }
    else {
        printf("%dは%d番目です\n", i, r); 
    }

    return EXIT_SUCCESS;
}

スリープソート

C/C++ アルゴリズム

時間を使ったソート。
今年ちょっと話題になって初めてブログで見たときは、お〜なるほど〜って感じだった。
いつ使うの？と聞かれると、まだわからないとしか言えないけど、何かに使えるはず。
WindowsだったらSleepはミリ秒でスレッド実行できるようなので実用性++か？


[sleep_sort.c]

#include <assert.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include <wait.h>

#define N 10 /* データ件数 */

int sort[N];
int count;
void SleepSort(void);
void output(void);

void SleepSort(void) {
    int i;
    for (i = 0; i < N; i++) {
        switch (fork()) {
            case -1:
                assert(0);
                break;
            case 0:
                /* child process */
                sleep(sort[i]);
                printf("%d\n", sort[i]);
                exit(0);
                break;
            default:
                break;
        }   
    }
    for (i = 0; i < N; i++) {
        while (wait(NULL) <= 0)
            assert(errno == EINTR);
    }
}
                                                                                          

int main(void) {
    int i;
    
    srand((unsigned int) time(NULL));
    for (i = 0; i < N; i++) {
        sort[i]  = rand() % 10;
    }

    printf("Stundy...\n");
    output();

    printf("Start...\n");
    SleepSort();
    printf("End...\n");

    return EXIT_SUCCESS;
}


void output(void){
    int i = 0;
    printf("sort => [");
    while(1){
        printf("%d", sort[i]); 
        if (i != N - 1) {
            printf(","); 
        }
        else{
            printf("]\n"); 
            break;
        }
        ++i;
    }
}

cでも、もっとカンタンな実装があるし
シェルでも簡単に書ける。
こっちの方が実用性があるかも。

[sleep_sort.bash]

#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

実行サンプル

/bin/bash sleep_sort.bash 7 4 1 3 2 6 8 0 9 5
0
1
2
3
4
5
6
7
8
9

バケットソート

C/C++ アルゴリズム

鳩の巣ソート(pigeonhole sort)なんていうのがあるらあしいですよ。
でもバケットソートの方が一般的だし、効率も良いよ。


[計算時間]
O(n)

高速、安定ソート


[bucket_sort.c]

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

#define N 10 /* データ件数 */

int sort[N];
int list[N];
void BucketSort(void);
void output(int data[],char *name);

void BucketSort(void){
    int i,j,key=0;
    int counter[N] = {0};
    for(i = 0; i < N; i++){
        counter[list[i]] += 1;
    }
    for(i = 0; i < N; i++){
        for(j = 0; j < counter[i]; j++){
           sort[key++] = i; 
        }
    }
}

int main(void){
    int i;
    clock_t start,end;
    
    srand((unsigned int) time(NULL));
    for(i=0; i< N; i++){
        list[i]  = (int) rand() % 10 ;
    }

    printf("Stundy...\n");
    output(list,"before");

    printf("Start...\n");
    start = clock();

    BucketSort();

    end = clock();
    printf("End...\n");
    output(sort,"after");
    printf("Time:%.2f\n",(double)(end-start)/CLOCKS_PER_SEC);

    return EXIT_SUCCESS;
}


void output(int data[],char *name){
    int i=0;
    printf("%s => [",name);
    while(1){
        printf("%d",data[i]); 
        if (i != N - 1) {
            printf(",");
        }
        else{
            printf("]\n"); break;
        }
        ++i;
    }
}


データ10件の実行結果

Stundy...
before => [2,9,5,5,6,1,4,8,8]
Start...
End...
after => [0,1,2,4,5,5,6,8,8]
Time:0.00

データ100万件の実行結果

Stundy...
Start...
End...
Time:0.05

これまでのソートの中で最速。

なんでバケツソート？と思いますが
週末スリープソートに挫折したのと（特にpthredが上手く使えなくて）
日頃よく似た様なことやっている気がしたから。
スリープソートはバケットソートのバケツをメモリ空間の代わりに時間に置き換えたもの。
次回はスリープソート。実用性は低そうだけどね！

アルゴリズムとデータ構造：最適なソート

C/C++ アルゴリズム

何個かソートの実装例を書いてきたけど
その中で最適なソートとはどれなのか。
安定ソート、不安定ソート、内部ソート、外部ソート、O(n2)、O(n log n)。
判断基準は状況によるが、処理するデータ量で考えると
大量のデータの場合はO(n log n)のクイックソート、マージソート、
数十個程度のデータなら単純挿入ソートやバブルソートが効率的。しかし場合によるらしい。
何を使うか迷う場合は、クイックソートかマージソートにしとけだそうです。乱暴ですが、とりあえず。
他にも色んなソートアルゴリズムがあるので週末書いてみたいと思います。
バケットソート、ボゴソート、シェーカーソート、ヒープソートなどなど。