C/C++ ソート（並べ替え）
2008.07.15:三度の脱線より再度戻る。(何となく sort が見えて来た？？？ような...)
2008.06.28:再度脱線の後、この頁へ戻る。
2008.05.26:「STL」->「実行時間測定」->「テストデータ作成」と脱線、この頁へ戻る。
ソート（並べ替え処理）
C/C++ のソートの種類
C/C++ で並び替え（その他も...）と言っても、Win32API / CLR(C++/CLI) では使える関数が異なったり、MS拡張(****_s()...とか)があったりと全く面倒である。list, set, map, のソート、qsort()、algorithm の std::sort() 実用的には、vector の動的配列を使用した構造体メンバでソートとか...。当初動的配列は、new, delete を使ったメモリ管理におびえながら如何と思っていたが、STL 使えば必要無いし･･･。
C++ の string(実は STL) も思うほどややこしくないのも一安心。
ソートの種類
ソートの種類一覧
| sort | comment | |||
|---|---|---|---|---|
| STL | w32/.net | C++ | std::sort() | <algorithm> stl版qsort 非安定 |
| STL | w32/ ? | C++ | stable_sort() | <algorithm> MergeSort 安定 |
| STL | w32/ ? | C++ | partial_sort() | <algorithm> 部分sort 非安定 |
| STL | w32/ ? | C++ | partial_sort_copy() | <algorithm> 部分sort -> copy |
| STL | w32/ ? | C++ | nth_element() | <algorithm> 分類 : sort も可能？ |
| - | w32/ ? | C/C++ | qsort() | <stdlib.h> C言語提供ライブラリ。 C++でも使えるが非推奨。 |
| - | 何でもOK | 自分で作った関数 | 自由自在･･･ | |
| STL | w32/.net | C++ | list<>::sort() | <list> コンテナ listコンテナ+sort()メソッド ランダムアクセスイテレータ使用のソートアルゴリズムは使用不可 |
| STL | w32/.net | C++ | set / multiset | ツリー構造・データ追加でソートされ格納(操作不可) |
| STL | w32/.net | C++ | map / multimap | ツリー構造・データ追加でソートされ格納(操作不可) |
| STL | w32/ ? | C++ | rotate() | sort 可? |
| STL | w32/ ? | C++ | random_shuffle() | sort 不可だが、テストデータの簡易作成に有用 データをバラバラにするのでソートと真逆。 |
| STL | w32/ ? | C++ | reverse() | sort 不可(と思う)。ソート済データ反転。 昇(降)順→降(昇)順 |
各ソートの特徴
C++ のソートでは、STL(Standard Template Library) の知識が有用。
STL を使えば、動的配列もメモリ管理を意識する必要が無い。
また、クラス(Class)ほどのボリュームも多分無いと思われる...が、使いこなすには案外敷居(現状operaterが壁)も高い。
operater は、C++ で案外重要視されるらしく、これもまた避けて通れそうに無いため再度脇道へそれないと先に(構造体メンバでソートする)進めないようである。
▲上へ [ 編集 ]
C++ のソート
algorithm std::sort()
C/C++ STL sort へ分項。単純な昇順、逆順程度なら非常に簡単。構造体メンバで並べ替えしようとすると突如ハイレベルになる？
（operator 何チャラの習得も必要：現在意味不明でちんぷんかんぷん！）
また、何気なく無視していた「テンプレート:template」の知識も必要。
（template は、突っ込まなければ案外判り易い）
ソートのアルゴリズムとしては、クイックソートになるらしいので、ソート後の並び順は安定とはならない。また、クイックソート利用の割に、qsort() と速度を比較すると劇的に遅いようでもある。（確認に使用したプログラムに問題があるのかも知れない ... が ...）
sort() は、STL #include <algorithm> で利用可能。Win32 でも問題なく利用可能。
<vector> などの STL 専用と思い込んでたがそうではないらしく、普通の配列でも利用できるようである。
※注：<list> では使用できない。<list> メンバ関数を利用する。
▲上へ [ 編集 ]
C言語でのソート
sort 関数を自分で用意する
以下、順時ソートを行う一般的なソート。但し １万〜6万件ソートさせると若干待たされるほど実行が遅い。sample sort
※.cpp で作成。
#include <iostream> // 手直後 stdio.h も可 #include "testArrData.h" using namespace std;
void swap(int* x, int* y); void sort(int* p, int n);
int main(void) {
cout << "■1. --- 開始 ---" << endl;
const int arr_elm = 25;
int arr_tbl[arr_elm];
cout << "■2. テストデータ代入" << endl;
testArrData(arr_tbl, arr_elm);
cout << "■3. ソート前データ表示" << endl;
for(int i=0; i < arr_elm; i++) {
printf("%3i ", arr_tbl[i]);
}
cout << endl;
cout << "■4. ソート実行" << endl;
sort(arr_tbl, arr_elm);
cout << "■5. ソート後データ表示" << endl;
for(int i=0; i < arr_elm; i++) {
printf("%3i ", arr_tbl[i]);
}
cout << endl;
cout << "■6. --- 終了 ---" << endl;
}
// sort関数
void sort(int* p, const int n) {
int k = n-1;
while(k>=0) {
int i=1, j=-1;
for(; i<=k; i++) {
if( *(p+i-1) > *(p+i) ) {
j = i-1;
swap(p+i, p+j); // 値の入替
/* ------------------
int temp = *(p+i); // 埋込なら実行step減
*(p+i) = *(p+j);
*(p+j) = temp;
------------------ */
}
}
k = j;
}
}
// swap関数
void swap(int* x, int* y) {
int temp = *x;
*x = *y;
*y = temp;
}
※65000件ほどのデータソートを想定している。この件数では実用性に難あり。※処理件数が多い程、要する時間が（指数的？）増えるかも。
表示サンプル
■1. --- 開始 --- ■2. テストデータ代入 ■3. ソート前データ表示 48 20 73 17 95 90 55 31 56 35 46 12 37 12 68 ■4. ソート実行 ■5. ソート後データ表示 12 12 17 20 31 35 37 46 48 55 56 68 73 90 95 ■6. --- 終了 --- 続行するには何かキーを押してください . . .
▲上へ [ 編集 ]
qsort
C/C++ 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 で戻り値を返す関数を準備する。▲上へ [ 編集 ]
リンク
内部リンク
- 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)
外部リンク
- 現在ありません
▲上へ
その他
テストデータの準備 2
C/C++ テストの実行 のテストデータ作成関数を修正。※テンプレートで汎用性を持たせたい関数・・・である。
※2008/06/30 テンプレートを使用し、若干汎用性持たせたサンプルを作成。
sample 1-1
#include <iostream> #include <stdlib.h> // srand() rand() #include <time.h> // time() #include <process.h> // getpid() #include <math.h> // double floor(double n) (切捨て処理) bool testArrData(double* arr_tbl, int arr_elm); // test data の作成
void main() {
const int arr_elements = 200; // 配列要素数
double arr_tbl[arr_elements]; // 配列の作成
// □テストデータ代入（関数呼出）
testArrData(arr_tbl, arr_elements);
// □配列要素を表示
for (int i=0; i<arr_elements; i++) {
printf("arr_tbl[%05d] = %9.2f \n",
i,
arr_tbl[i]
);
}
}
// ********************************
// テストデータ作成関数(汎用版)
// ********************************
// 取得したい乱数範囲のパラメータ指定
#define RND_N_DEV 1 // digit指定：100/.00 10/.0 1/0
#define EXPECTED_MIN 0 // 最小値
#define EXPECTED_MAX 100 // 最大値
// 渡された配列(参照渡し)へ乱数データを格納するだけの関数。
// arr_tbl：配列の値渡しアドレスを受取る。
// arr_elm：Number of elements 要するに要素数を受取る。
bool testArrData(double* arr_tbl, int arr_elm) {
// srand((unsigned)(time(NULL)+getpid())); // 毎回異なる乱数を発生
srand(1); // 乱数初期値セット
for (int i=0; i<arr_elm; i++) {
arr_tbl[i] = rand() * rand(); // 〜 1,073,676,289
arr_tbl[i] = floor(arr_tbl[i]/10); // 桁落し(intなら不要）
arr_tbl[i] = (int)(arr_tbl[i]) // 0〜100 擬似乱数取得
% (((EXPECTED_MAX - EXPECTED_MIN) * RND_N_DEV) + 1)
+ (EXPECTED_MIN * RND_N_DEV);
arr_tbl[i] = arr_tbl[i] / (RND_N_DEV); // 桁調整(intなら不要)
}
// 取り合えず 成否に関係なく true を返す。
return true;
}
※最小値？最大値？出現頻度に問題有った様におもう。（詳細忘れ、切上げ、切捨ての関係？）※桁上げすると min の出現頻度減少、切り捨てると max の出現頻度減少？の問題点有り？
▲上へ [ 編集 ]
テストデータの作成 1
※C/C++ テストの実行 へ移動。簡略したサンプルのみ残し、冗長部分削除乱数(擬似乱数)の基本
sample1:rand(),srand() 乱数の取得
〜 #include <stdlib.h> // srand() rand() #include <time.h> // time() #include <unistd.h> // getpid() win→ <process.h> // ---- 乱数の初期値設定：種(seed) srand(1); // 3).同一乱数発生初期値(系列 3) srand((unsigned)time(NULL)); // 1).乱数初期値(系列 1) srand((unsigned)(time(NULL)+getpid())); // 2).乱数初期値(系列 2) // ---- 乱数取得 ---- iRnd = rand(); // 4).（取得値）0~RAND_MAX iRnd = rand() % (100+1); // 5).（取得値）0~100 iRnd = rand() % (140-60+1)+60; // 6).（取得値）60~140 iRnd = rand() * rand(); // 7).大きな乱数を取得する場合
▲上へ
「STL」の覚書。
※STL は、専用頁へ移動しました。以下、STL の簡単な概要のみ。STL(Standard Template Library)とは？
データ構造やアルゴリズムを扱うための C++ ライブラリ。特に「動的な配列」「リスト」「キュー」「スタック」「マップ」「セット」と言った、複雑なデータ構造を統一された利用方法で簡単に利用できる（･･･そういう目的で作成されている･･･らしい。）ので、覚えない手は無い。- コンテナ
- 簡単に言えば、複雑なデータ構造そのものに、その機能を与えたオブジェクト？（実態はクラスで作られた型に依存しない C++ のテンプレートと言うことらしい。）
vector（動的な配列）,list（双方向リスト）,queue（キュー）,stack（スタック）,multimap（マルチマップ）,multiset（マルチセット）,bitset（ビッドセット）など（一部割愛）が有り、データの種類、取扱、処理方法によりこれらのコンテナから選択して使用する。
※deque, priority_queue といったコンテナもある。 - 共通アルゴリズム
- sort など、コンテナのアルゴリズムが豊富にある。
- イテレータ
- コンテナの別名らしいが、コンテナパラメータなど、ほぼ共通化されているようで、こうした STL のコンテナ仕様の総称をイテレータと呼ぶらしい。（正誤不明、内容非保証）
- 関数オブジェクト
- 共通仕様により、共用できる関数オブジェクトが揃っているらしい。（内容非保証）
※STL を使うとコード短縮が可能となるようだが、C言語とかけ離れた文体のため、使い始めると、クラス同様切りが無い感じである。sort 使うためだけの知識を詰め込んで「終了〜！」としたいところである。
Standard Template Library Samples
▲上へ
実行速度の計測
※C/C++ テストの実行 へ移動。簡略したサンプルのみ残し、冗長部分削除時間の取得
sample1.cpp: 実行時間計測 １
#include <windows.h> // mmsystem.h <- UINT で使用
#include <mmsystem.h> // timeGetTime()
#pragma comment(lib,"winmm.lib") // timeGetTime()
timeBeginPeriod(1); // 精度 1ms
unsigned long tc_start = timeGetTime(); // 計測開始
// … 計測対象処理を記述 …
unsigned long tc_end = timeGetTime(); // 計測終了
printf("Time = %d\t \n\n", tc_end - tc_start);
timeEndPeriod(1); // 精度復元
sample2.c/.cpp; 実行時間の計測 ２
#include <time.h> clock_t tc_start, tc_end; tc_start = clock(); // … 計測対象処理 … tc_end = clock();※精度を求めないならこの方が簡単。
※外にも多数計測の定石あり。上記の２方法の何れかで実用上問題無いと思われる。
▲上へ
覚書
STL(Standard Template Library)
.NET .NET Framework
C++/CLI
CLR
STL/CLR
・・・ ややこしい ・・・
▲上へ [ 編集 ]
その他覚書
独自ソートの動作チェック
std::sort, qsort を使用しない独自ソートの動作確認。sample sort
#include <iostream> #include "testArrData.h" using namespace std;
void swap(int* x, int* y); void sort(int* p, int* pi, int n); // 修正あり
int main(void) {
const int arr_elm = 100;
int idx[arr_elm]; // idx[] 追加
int arr_tbl[arr_elm];
testArrData(arr_tbl, arr_elm);
sort(arr_tbl, idx, arr_elm); // sort 実行
for(int i=0; i < arr_elm; i++) { // 結果表示
printf("idx[%3i]:%3i \n",idx[i], arr_tbl[i]);
}
}
// sort
void sort(int* p, int* pi, const int n) { // *pi を追加
int k = n-1;
while(k>=0) {
int i=1, j=-1;
for(; i<=k; i++) {
if( *(p+i-1) > *(p+i) ) {
j = i-1;
swap(p+i, p+j); // 対象データ
swap(pi+i,pi+j); // 並び順も合せて入替える
}
}
k = j;
}
}
// swap // 変更なし
void swap(int* x, int* y) {
int temp = *x;
*x = *y;
*y = temp;
}
※初期の index を idx へ構造体を使用せず保持し、ソート後の状態が確認可能に修正。表示サンプル
※修正、省略あり
index data --------------- idx[ 42]: 0 idx[ 57]: 0 idx[ 84]: 2 idx[ 31]: 3 idx[ 22]: 4 idx[ 47]: 5 idx[ 12]: 7 idx[ 39]: 7 idx[ 59]: 7 〜 省略 〜 idx[ 36]: 58 idx[ 65]: 58 idx[ 41]: 59 idx[ 1]: 60 idx[ 61]: 60 idx[ 7]: 62 〜 省略 〜 idx[ 10]: 95 idx[ 46]: 97 idx[ 29]: 98 idx[ 50]: 98 idx[ 90]: 99 // --- end ---※idx の並び順が維持されている理想的なソートだが、処理件数が多いと速度が遅い。
▲上へ [ 編集 ]
2008年07月21日(月) 21:30:36 Modified by cafeboy1