クイックソート
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
案の定ほぼ同じ実装でいけましたね。
一応中央値を算出するコードもついでに書いてみたんですが、あってるのかどうか、またこれによりパフォーマンスがあがってるのかどうかがいまいち実感できないのでよくわからないですね。
何か検証できるコードがあればよいのですが・・・。