Subject: ソート(1) Date: Sat, 10 Feb 2001 11:31:16 +0900 (JST) From: si9746@si.hirosaki-u.ac.jp (Mizuno Katuyosi) To: s-tatsuo@msf.biglobe.ne.jp Cc: si9746@si.hirosaki-u.ac.jp 始めまして、浜工処理部OBの銀の星です。 早速ですが、あなたがHPに掲載されているソートアルゴリズムに ついて私なりの提案を示したいと思います。 C++が使える環境にあるなら、テンプレート関数を有効利用する。 ポインタの演算を多用しない。 主な物は以上2つでしょうか。以下にこの提案に沿った修正リスト を示します。何かの参考にでもなれば良いのですが。 なお、テスト環境はWin9x + Borland C++ Compiler 5.5.1です。 以上 Written by 銀の星☆ミ e-mail si9746@si.hirosaki-u.ac.jp --------------------------------------------------- /* ソート(1) - 選択法、バブルソート、挿入ソート */ /* * 現在の問題点(?): * ・swap() 内でのメモリの動的確保を何となく止めたい * ・メモリ確保失敗時のエラー処理をもう少しスマートにしたい * ・memmove() の処理速度が、memcpy() と比べてどうなのか判ってない(苦笑 * ・bubblesort()がまだ一寸汚い */ /* * ご意見・ご感想、お待ちしております。 * WebSite : http://www2s.biglobe.ne.jp/~nuts/ * 掲示板 : http://www.tcup2.com/232/nuts.htm * E-mail : s-tatsuo@msf.biglobe.ne.jp * ICQ UIN : 9365951 */ /* * edit by 銀の星 ☆ミ * * C にこだわらなければ,この方がスマート! * また,下手にポインタを使わない分だけバグが入りにくい。 * * ユーザ定義クラスでは最低限operator<()とoperator==()の * 2つを定義をしておくこと。 * (理由1 : そのほかはこの2つから簡単に派生できる。) * (理由2 : 今回のソートではoperator<()しか使っていない。) */ /* * memmove()とmemcpy()の違いは,オーバラップしている領域が * あっても正常にコピーできるかどうか。 * memmove()の方はオーバーラップしている領域があっても大丈夫 * * stdoutとstderrの違いは,リダイレクトやパイプによって * 出力先を変更できるのがstdout,それらに関係なくコンソール * に出力するのがstderr。 * したがってプログラムの異常終了などに関するメッセージを * 出力する時はstderrの方が望ましい。 */ #include // cout, endl #include // setw(), setprecision(), fixed #include // rand(), srand(), size_t, EXIT_SUCCESS using namespace std; /* 値の入れ替え */ template void swap(T& x, T& y) { T t; t = x; x = y; y = t; } /* another 選択法。こっちのが効率は良いと思う * * ってかこう書いてあるモノのが多い……。 */ template void selectsort2(T *const array, size_t nel) { size_t i, j, min; for(i=0; i void bubblesort(T *const array, size_t nel) { size_t i, j; bool check; for(i=nel-1; i>0; i--) { check = false; for(j=0; j void insertsort(T *const array, size_t nel) { size_t i, j; for(i=1; ij; k--) array[k] = array[k-1]; array[j] = t; /* どうしてもスピードが気になるなら * * 上の挿入部分を次のようにしても良い */ /* memcpy(&t, array+i, sizeof(T)); memmove(array+j+1, array+j, sizeof(T)*(i-j)); memcpy(array+j, &t, sizeof(T)); */ break; } } } } /************************************************/ #define DAT_NUM 20 /* データ数 */ #define MOD 10 /* 「適当な値で割る」の割る数 */ #define SEED 128 /* 乱数を初期化する種 */ /* intの関数 */ void init(int *value, size_t nel) { for(size_t i=0; i(const pair_t& rhs) { return !(*this<=rhs); } bool operator>=(const pair_t& rhs) { return !(*this void test(size_t nel, void (*sort)(T* const array, size_t nel)) { T *value = new T[nel]; srand(SEED); /* 初期化 */ init(value, nel); /* ソート前の配列を表示 */ cout << "original" << endl; print(value, nel); cout << endl; /* ソート */ sort(value, nel); /* ソート後の配列を表示 */ cout << "sorted" << endl; print(value, nel); cout << endl; delete value; } int main(void) { /* int型によるテスト */ cout << "int\t: "; test(DAT_NUM, insertsort); /* float型によるテスト */ cout << "float\t: "; test(DAT_NUM, insertsort); /* pair_t型によるテスト */ cout << "pair_t\t: "; test(DAT_NUM, insertsort); return EXIT_SUCCESS; }