最近更新したページ
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++ ソート(並べ替え)


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) も思うほどややこしくないのも一安心。

ソートの種類


ソートの種類一覧
sortcomment
STLw32/.netC++ std::sort() <algorithm> stl版qsort 非安定
STLw32/ ? C++ stable_sort() <algorithm> MergeSort 安定
STLw32/ ? C++ partial_sort() <algorithm> 部分sort 非安定
STLw32/ ? C++ partial_sort_copy() <algorithm> 部分sort -> copy
STLw32/ ? C++ nth_element() <algorithm> 分類 : sort も可能?
- w32/ ? C/C++ qsort() <stdlib.h> C言語提供ライブラリ。
C++でも使えるが非推奨。
- 何でもOK 自分で作った関数 自由自在・・・
STLw32/.netC++ list<>::sort() <list> コンテナ listコンテナ+sort()メソッド
ランダムアクセスイテレータ使用のソートアルゴリズムは使用不可
STLw32/.netC++ set / multiset ツリー構造・データ追加でソートされ格納(操作不可)
STLw32/.netC++ map / multimap ツリー構造・データ追加でソートされ格納(操作不可)
STLw32/ ? C++ rotate() sort 可?
STLw32/ ? C++ random_shuffle() sort 不可だが、テストデータの簡易作成に有用 
データをバラバラにするのでソートと真逆。
STLw32/ ? 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 関数を自分で用意する

 以下、順時ソートを行う一般的なソート。但し 1万〜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 で戻り値を返す関数を準備する。


▲上へ [ 編集 ]


リンク


内部リンク


外部リンク


  • 現在ありません

▲上へ

その他


テストデータの準備 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: 実行時間計測 1
#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; 実行時間の計測 2
#include <time.h>

clock_t tc_start, tc_end;
tc_start = clock();
// … 計測対象処理 …
tc_end   = clock();
※精度を求めないならこの方が簡単。

※外にも多数計測の定石あり。上記の2方法の何れかで実用上問題無いと思われる。

▲上へ

覚書


 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




スマートフォン版で見る

×

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