最近更新したページ
2013-10-20
2013-09-29
2013-09-23
2012-01-07
2011-11-09
2011-10-23
2011-10-09
2011-10-01
2011-09-29
2011-09-03
2011-08-07
2011-08-02
2011-07-29
2011-07-10
2011-05-05
2011-05-04
2011-04-24
2011-04-13
2011-04-05
2011-03-26
2011-02-18
2011-02-15
2010-12-26
2010-12-07
2010-12-05
2010-11-23
2010-09-28
2010-09-23
2010-08-26
2010-08-22
2010-07-16
2010-01-17
2010-01-11
2009-10-04
2009-08-21
2009-08-13
2009-06-18
2009-06-01
2009-04-29
2009-02-16
2009-02-11
2009-02-03
2008-07-22
2008-07-21
2008-07-15
2008-07-14
2008-07-13
2008-07-12
2008-07-08
2008-07-05
2008-06-28
2008-06-17
2008-06-05
2008-06-02
2008-06-01
2008-05-29
2008-05-26
2008-05-21
2008-05-19
2008-05-18
2007-10-31
2007-10-27
2007-09-28
2007-09-23
2007-09-17
2007-09-16
2007-09-14
2007-09-11
2007-06-18
2007-04-15
2006-12-21
2006-11-30
2006-11-22
2006-08-17
2006-03-29
2006-03-28
2006-03-27

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関数の使用が推奨されない。

▲上へ [ 編集 ]


リンク


内部リンク


外部リンク


  • 現在ありません

▲上へ
2008年07月21日(月) 14:15:52 Modified by cafeboy1




スマートフォン版で見る

×

この広告は60日間更新がないwikiに表示されております。