クイックソート

http://www.geocities.jp/ky_webid/algorithm/020.html

クイックソートの話です。

もの凄いアルゴリズムですね。コレ。

これを考え付いた人凄いです。普通こんなの思いつかないって。

分割したデータは、中央に向かって探索、交換していき、再帰でそれを最後の要素になるまで繰り返すというものです。

実装がわからなかったので解答例を先にみました。

折角なのでコレを参考に文字列のクイックソートを実装してみます。殆ど変わらないとは思いますが。

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

char *median(char **array,int begin,int end) {
    char *a = array[begin];
    char *b = array[(begin + end) / 2];
    char *c = array[end];
    
    if( strcmp(a,b) < 0 ){
        if( strcmp(b,c) < 0 ){ return b; }
        if( strcmp(a,c) < 0 ){ return c; }
        return a;
    }
    else if( strcmp(a,c) < 0 ){ return a; }
    else if( strcmp(b,c) < 0 ){ return c; }
    
    return b;
}

void quick_sort (char **array,int begin,int end) {
    int i,j;
    char *data;
    char *work;
    
    data = median(array,begin,end);
    i = begin;
    j = end;
    
    while (1) {
        while( strcmp(array[i],data) < 0 ){ ++i; }
        while( strcmp(array[j],data) > 0 ){ --j; }
        if( i >= j ){ break; }
        
        work = array[i];
        array[i] = array[j];
        array[j] = work;
    }
    if ( begin < i - 1 ) { quick_sort(array,begin,i-1); }
    if ( end > j + 1 )   { quick_sort(array,j+1,end); }
}

int main (void) {
    char *str[]= {
        "ppppp",
        "aaaaba",
        "aaaaa",
        "asdfe",
        "ffrty",
        "ytfyy",
        "iiu87",
        "gffre",
        "cdsww",
        "zkpoi",
        "ekpoia",
    };
    
    quick_sort(str,0,ARRAY_NUM(str)-1);
    printf_array_cpp("%s\n",str,ARRAY_NUM(str));
    
    return 0;
}
$ main
aaaaa
aaaaba
asdfe
cdsww
ekpoia
ffrty
gffre
iiu87
ppppp
ytfyy
zkpoi

mylib.h

案の定ほぼ同じ実装でいけましたね。

一応中央値を算出するコードもついでに書いてみたんですが、あってるのかどうか、またこれによりパフォーマンスがあがってるのかどうかがいまいち実感できないのでよくわからないですね。

何か検証できるコードがあればよいのですが・・・。