　あちこち弄って（修正して）いる間に、動作しない関数が出てくる。
　（例えば、比較関数名の重複による修正などは致命的）
　フォローしきれないので動作保証なし...と言うことで...。または、エラーが出たら自分で気づいて修正してくらはい。

　分割コンパイルと言えども、最終的に１つの実行ファイルを作成するため、シグネチャの一致する同一名称関数は使えない。クラスにすると出来ると思うが、クラスに深く首を突っ込みたくない。

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

▲上へ [ 編集 ]