C/C++ qsort(QuickSort)
C/C++ ソート
あちこち弄って(修正して)いる間に、動作しない関数が出てくる。(例えば、比較関数名の重複による修正などは致命的)
フォローしきれないので動作保証なし...と言うことで...。または、エラーが出たら自分で気づいて修正してくらはい。
分割コンパイルと言えども、最終的に1つの実行ファイルを作成するため、シグネチャの一致する同一名称関数は使えない。クラスにすると出来ると思うが、クラスに深く首を突っ込みたくない。
qsort(QuickSort)
qsort は C言語用関数、C++ でも動くが推奨されない。また、STL std::sort() と比べ初期から取っ付き難い面がある。
関数テンプレート:
void qsort(void* base, size_t nmemb, size_t size, int(*compar)(const void *, const void *)); // 1). void* base - 配列アドレス // 2). size_t nmemb - 並び替えサイズ // 3). size_t size - sizeof(type) 配列要素の型サイズ::bytes // 4). int(*compare)(… - よく判らないが、比較関数の準備が要る※4) 並び替え比較文字の大小を、(x>y)=正の整数、(x<y)=負の整数、(x==y)=0 で戻り値を返す関数を別途準備する。
▲上へ [ 編集 ]
ソートテストで使用した関数サンプル
※このサンプルは、main_sort.cpp をメインとして分割(分割コンパイル)された一部。メイン、ヘッダー、共通関数等は、分割コンパイルの頁を参照。
sub_sort_qst.cpp
//#include <iostream> //#include <time.h> //#include <string> #include <vector> #include <algorithm> //using namespace std; #include "main_sort.h" // ----------------------------------------- // ソート関数・比較関数 // ----------------------------------------- // qsort 用比較関数 int qasc_cmp(const void* a, const void* b) { return *(int *)a - *(int *)b; } int qdes_cmp(const void* a, const void* b) { return *(int *)b - *(int *)a; } /***************************** qsort *****************************/ void cqsort(vector < int > & v) { int size = (int)v.size(); // dsp_arr(&v[0], size); // ----------------------------------------- // 参考:0.0400 qsort(&v[0], size, sizeof(&v[0]), qasc_cmp); // 昇順ソート // qsort(&v[0], size, sizeof(&v[0]), qdes_cmp); // 降順ソート // ------------------------------------------------------ // dsp_arr(&v[0], size); }※qsort のみ 同じファイルへ比較関数を記述。stl algolithm の比較は原則共通で別ソースとしている。
※qsort も 比較関数呼出にバリエーションがある。
※とにかく早い。C++ で非推奨だが、速度を追及するなら一考の価値がある。要素数を2桁上げで、3.4250程度である。
▲上へ [ 編集 ]
sample qsort.cpp
sample qsort.cpp
#include <iostream> #include <time.h> // time() #include <process.h> // getpid() <- 非推奨 _getpid()使用 using namespace std;
int cmp_type(const int* x, const int* y); bool testArrData(int* arr_tbl, int arr_elm);
void main() { const int iArrEle = 10; // 配列要素数 int iaTbl[iArrEle]; // 配列の作成 // □テストデータ代入(関数呼出) testArrData(iaTbl, iArrEle); // □配列要素を表示 cout << "ソート前:"; for (int i=0; i<iArrEle; i++) { printf("%d ", iaTbl[i]); } cout << endl; // ■ソートの実行 qsort(iaTbl, iArrEle, sizeof(int), (int (*)(const void*, const void*))cmp_type); // □ソート後の配列要素を表示 cout << "ソート後:"; for(int i=0; i<iArrEle; i++) { printf("%d ", iaTbl[i]); } cout << endl; }
// qsort用比較関数 int cmp_type(const int* x, const int* y) { int *a, *b; a = (int*)x; b = (int*)y; return (*a)-(*b); }
// テストデータの作成 bool testArrData(int* arr_tbl, int arr_elm) { srand( (unsigned)(time(NULL) + getpid() ) ); // 毎回異なる乱数を発生 for (int i=0; i<arr_elm; i++) { arr_tbl[i] = rand() * rand(); // 〜 1,073,676,289 arr_tbl[i] = (int)(arr_tbl[i]) // 0〜100 擬似乱数取得 % (((EXPECTED_MAX - EXPECTED_MIN) * RND_N_DEV) + 1) + (EXPECTED_MIN * RND_N_DEV); } // 取り合えず 成否に関係なく true を返す。 return true; }※これを叩き台に qsort() のテストが可能。
表示サンプル
ソート前:54 23 14 50 65 73 5 0 78 34 ソート後:0 5 14 23 34 50 54 65 73 78 続行するには何かキーを押してください . . .
sample qsort.c
.cpp では推奨されないが、テストするにも .cpp の方が便利。sample qsort.c
※ .c のみ動作確認。
※比較対照変数の型置換えで int 以外(char,int,long,double など)も利用可。
※文字列の並べ替えはこれでは出来ない。(C言語の文字列扱の仕様)
※cmp_type は、関数の先頭アドレスを渡すのみでも動いてる。
#include <stdio.h> #include <stdlib.h> int cmp_type(const int* x, const int* y);
void main() { int i; int iaTbl[10] = {126,123,130,256,232,10,100,23,900,40}; qsort(iaTbl, 10, sizeof(int), cmp_type); for(i=0; i<10; i++) { printf("%d ", iaTbl[i]); } printf("\n"); }
int cmp_type(const int* x, const int* y) { int *a, *b; a = (int*)x; b = (int*)y; return (*a)-(*b); }※.c のみコンパイル可。
▲上へ [ 編集 ]
sample2 qsort.cpp
sample qsort.c を qsort.cpp へ直した例qsort.cpp 修正版
※.cpp では、qsort 第4pr を厳密に記述にないとエラー(チェック厳?)
※(int (*)(const void*, const void*)) とするとエラーを回避する例。
#include <iostream> using namespace std; int cmp_type(const int* x, const int* y);
void main() { int iaTbl[10] = {126,123,130,256,232,10,100,23,900,40}; qsort( iaTbl, 10, sizeof(int), (int (*)(const void*, const void*))cmp_type ); for(int i=0; i<10; i++) { printf("%d ", iaTbl[i]); } cout << endl; }※注:重複割愛
※変更点:(int (*)(const void*, const void*)) によるキャスト。
※再確認:.cpp では qsort関数の使用が推奨されない。
▲上へ [ 編集 ]
リンク
内部リンク
- C/C++ C++/CLI C# 関連
- VC++ 2005 Express のインストール
- C/C++ の簡単なプログラム例
- C/C++ ソート(並べ替え)
- C/C++ テストの実行
- C/C++ STL(Standard Template Library)
- 変数・定数
- プログラムの分割/ダイナミックリンクライブラリ など
- その他
- C/C++ その他::書式文字/ESC code など
- VB2005リファレンス(覚え書き)
- SQL文:SQLステートメント
- VBA(VisualBasic for Applications)
外部リンク
- 現在ありません
▲上へ
2008年07月21日(月) 14:15:52 Modified by cafeboy1