この間書いた「無駄話」で「【Visual Studio探検記】の準備が整いました」と書き、現実にそのブログインスタンス（ブログクラスの実体－要すればネタ）を作っていますが、ネタ的にC++やC#のプログラムが要るので、先ずは先般Embarcaderoの32bitネイティブコンパイラーで作ったC++用の「各種ソートの比較」をベンチマークプログラム的に使おうかと考えました。
"Comparison_Sort.cpp"というプログラムなんですが、まだ覚えておられるでしょうか？
となると、
矢張りC#用にも欲しいですよね？と、いうことでこのプログラムをC#に移植（末尾参照）し、実行してみました。
解説：一番遅いBubbleソートはC++よりも遅いが、アルゴリズム的に速いHeap、Quick、Shellソートでは（テストプログラムのデータセットの違いを考えても）早くなっていることがわかります。なお、.NETは.Netはコンパイラーとインタープリターの両方の特性を組み合わせたような実行環境をとっており、「遅い」とか「速い」とかいろいろと言われますが、実際に計測すると面白いですね。
ウ～ン、.NET、速いですね。恐るべし。
アルゴリズムの勝利、恐るべし。
【Compare_Sort.cs】
解説：以下のプログラムは、C++用のComparison_Sort.cppのアルゴリズム、構成をなるべく忠実にC#に移したものですが、両言語の違いにより変更したところがあります。
///////////////////////
// C# Sort Comparison
///////////////////////
using System;
using System.Diagnostics; //Stopwatchを使う為
namespace Comparison_Sort
{
class comparison_sort
{
///////////
//定数定義
///////////
const int MAX = 10000; //取り敢えず10,000がお勧め
////////////////////
// 共通テスト用配列
////////////////////
int[] original = new int[MAX];
double[,] results = new double[4, MAX];
///////////////
//Mainメソッド
///////////////
public static void Main()
{
comparison_sort cs = new comparison_sort();
Stopwatch sw = new Stopwatch();
sw.Start();
for(int i = 0; i < MAX; i++) {
cs.comparison(i);
}
for(int i = 0; i < 4; i++) {
cs.print_result(i);
}
sw.Stop();
TimeSpan ts = sw.Elapsed; //時間ts.Hours, 分ts.Minutes, 秒ts.Seconds, ミリ秒ts.Milliseconds
string elapsed = String.Format("Total time consumed for the above processing is: {0:00.000000}", ts.Milliseconds);
Console.WriteLine(elapsed);
Console.WriteLine("Push CR key ..." + Environment.NewLine);
Console.Read(); //コンソールを閉じない為
}
///////////////
// Comparison
///////////////
void comparison(int n)
{
//乱数の初期化
Random rand = new Random((int) DateTime.Now.Ticks & 0x0000FFFF);
//テスト用の配列の作成
//解説：C#では引数に配列を渡す場合、参照渡しになる－https://water2litter.net/rye/post/c_array_ref/
int[] test_array = new int[MAX]; //テスト用ローカル変数
for(int i = 0; i < MAX; i++)
{
test_array[i] = //originalを保存し、テストはこれで行う
original[i] = rand.Next(); //0から32,767の整数で初期化する
}
//時間計測の準備
Stopwatch sw = new Stopwatch();
//ソート比較
sw.Start();
bubblesort(test_array);
sw.Stop();
TimeSpan ts = sw.Elapsed; //時間ts.Hours, 分ts.Minutes, 秒ts.Seconds, ミリ秒ts.Milliseconds
results[0, n] = (double)ts.Milliseconds;
for(int i = 0; i < MAX; i++)
test_array[i] = original[i];
sw.Reset();
sw.Start();
heapsort(test_array);
sw.Stop();
ts = sw.Elapsed; //時間ts.Hours, 分ts.Minutes, 秒ts.Seconds, ミリ秒ts.Milliseconds
results[1, n] = (double)ts.Milliseconds;
for(int i = 0; i < MAX; i++)
test_array[i] = original[i];
sw.Reset();
sw.Start();
quicksort(test_array, 0, MAX - 1); //配列、開始添字、終了添字
sw.Stop();
ts = sw.Elapsed; //時間ts.Hours, 分ts.Minutes, 秒ts.Seconds, ミリ秒ts.Milliseconds
results[2, n] = (double)ts.Milliseconds;
for(int i = 0; i < MAX; i++)
test_array[i] = original[i];
sw.Reset();
sw.Start();
shellsort(test_array);
sw.Stop();
ts = sw.Elapsed; //時間ts.Hours, 分ts.Minutes, 秒ts.Seconds, ミリ秒ts.Milliseconds
results[3, n] = (double)ts.Milliseconds;
}
////////////////
// Bubble Sort
////////////////
/*
n個の整数配列dataを総て順に比較、交換し、配列の最後から大きい順に並べる
通称「馬鹿ソート」
*/
void bubblesort(int[] data)
{
int i, j, temp, n = data.Length;
for(i = n - 1; i > 0; i--) { //配列の末尾から先頭へ
for(j = 0; j < i; j++) { //配列の先頭から末尾へ
if(data[j] > data[j + 1]) { //次の配列要素の方が小さければ交換する
temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}
} //その結果iに最大の要素が置かれる
}
}
//////////////
// Heap Sort
//////////////
/*
ヒープソートは次のようなヒープ（二分木）の「親－子」関係を用いる
Parent(0)
／＼
ChildL(1) ChildR(2)
この二分木を用いて配列を表現すると以下のようになる（数字は添字）
0
／ ＼
1 2
／ ＼ ／ ＼
3 4 5 6
／ ＼
7 8 ...
*/
void exchange(int top, int[] data, int n)
{
int temp = data[top]; //開始時の二分木の親の値をtempに退避
//子のある二分木の左の子供を指定し、（交換があればやり直す為）末尾迄子孫を辿る
for(int i = top * 2 + 1; i < n; top = i, i = top * 2 + 1) {
if(i < n - 1 && data[i] < data[i + 1]) //右の子供が左の子供より大きければ
i++; //右の子供を指定する
if(temp >= data[i]) //開始時の親と大きい方の子供を比較
break; //親が大きければループを抜ける（topは変化しない）
data[top] = data[i]; //二分木の親に大きい子の値を代入する
} //大きい子（data[i]）はループのi = topで
data[top] = temp; //data[top]となり、退避した親の値を代入
}
void heapsort(int[] data)
{
int top, i, n = data.Length;
for(top = n / 2 - 1; top >= 0; top--) //最初に「子がある最後の二分木」から
exchange(top, data, n); //「親が最大値を持つ」ように頂点まで継続する
for(i = n - 1; i > 0; i--) { //次に配列の最後と頂点（最大値）の値を交換し
int temp;
temp = data[i];
data[i] = data[0];
data[0] = temp;
exchange(0, data, i);
} //配列の最後を切り離し、その前の要素から頂点まで継続する
}
//////////////
// Quick Sort
//////////////
//検索範囲（startとend）で、基準値（key）を定め、それよりも多いものと少ないものを分割し、更にkeyの前後で同じ処理を再帰呼び出しする。
void quicksort(int[] data, int start, int end) //配列、開始添字、終了添字
{
if(start < end) //開始位置が終了位置以上で終了（最後の再帰呼び出し参照）
{
int left, right, key, kp; //順に右進行添字、左進行添字、「分水嶺」値、その添字
//右端乃至左端に到達し、breakで抜けるまでループする
for(left = start, right = end, key = data[right];;) {
while(key >= data[left])
{
left++; //keyを超える値迄右に進む
if(left == right) //配列添字が範囲を超えないよう追加
break;
}
if(left < right) //rightの位置迄は
data[right] = data[left]; //leftの値をrightの位置に書き込む
else //leftがright位置を過ぎたなら
{
kp = right; //keyの位置をrightの位置としてループを抜ける
break;
}
while(key <= data[right])
{
right--; //key未満の値迄右に進む
if(right == 0) //配列添字が範囲を超えないよう追加
break;
}
if(left < right) //leftの位置迄は
data[left] = data[right]; //rightの値をleftの位置に書き込む
else //rightがleft位置を過ぎたなら
{
kp = left; //keyの位置をleftの位置としてループを抜ける
break;
}
}
data[kp] = key; //keyポインターの位置にkeyの値を代入する
quicksort(data, start, kp - 1); //開始位置からkeyポインター迄で再帰呼び出しする
quicksort(data, kp + 1, end); //keyポインターから終了位置迄で再帰呼び出しする
}
}
//////////////
// Shell Sort
//////////////
//シェルソートは配列要素を一定の距離を置いたグループに分けて比較、交換を行いソートする方法
void shellsort(int[] data)
{
int gap, i, j, temp, n = data.Length; //gapは比較、交換する要素間の距離
for(gap = n / 2; gap > 0; gap /= 2) { //初期的な距離は配列サイズの1/2とする
for(i = gap; i < n; i++) { //距離は徐々に狭まってゆく
for(j = i - gap; j >= 0 && data[j] > data[j + gap]; j -= gap) {
//v[j]とv[j + gap]を交換する
temp = data[j];
data[j] = data[j + gap];
data[j + gap] = temp;
}
}
}
}
/////////////////
// Print results
/////////////////
void print_result(int n)
{
double[] array = new double[MAX]; //n行の配列のコピー用
string[] title = new string[4] {">>> Bubble Sort <<<", ">>> Heap Sort <<<", ">>> Quick Sort <<<", ">>> Shell Sort <<<"};
double max = 0.0, min = (double)MAX, med = 0, ave = 0;
for(int i = 0; i < MAX; i++)
{
if(results[n, i] > max) //n番目のソートの結果の最大値を求める
max = results[n, i];
if(results[n, i] < min) //n番目のソートの結果の最小値を求める
min = results[n, i];
ave += results[n, i]; //n番目のソートの結果を合計する
array[i] = results[n, i]; //n番目の配列をコピーする
}
Array.Sort(array); //コピー配列をソートする （注）
med = array[(MAX % 2 != 0) ? MAX / 2 : MAX / 2 - 1];
Console.WriteLine(title[n]);
Console.WriteLine("最大値 ：{0:00.000000}", max);
Console.WriteLine("最小値 ：{0:00.000000}", min);
Console.WriteLine("平均値 ：{0:00.000000}", ave / MAX);
Console.WriteLine("中央値 ：{0:00.000000}", med);
Console.WriteLine("総所要時間：{0:00.000000}", ave);
Console.WriteLine();
}
}
}
注：以下はCopilotのアドバイスです。
「.NETのArray.Sort()メソッドは、状況に応じて**イントロソート (Introsort)**という複合アルゴリズムを使用しています。
具体的には、以下の3つのソートアルゴリズムを組み合わせて、効率的なソートを実現しています。
- クイックソート (Quicksort): 一般的なケースで使用されます。平均的な時間計算量はO(n log n)と高速です。
- 挿入ソート (Insertion Sort): 配列の要素数が非常に少ない場合（通常16要素以下）に使用されます。オーバーヘッドが少なく、小さな配列では効率的です。
- ヒープソート (Heapsort): クイックソートの再帰が深くなりすぎた場合（最悪ケースに陥りそうな場合）に切り替わります。これにより、最悪ケースでの時間計算量がO(n^2)になるのを防ぎ、常にO(n log n)のパフォーマンスを保証します。
これにより、どのようなデータに対しても高いパフォーマンスと安定した時間計算量を実現しています。
なお、.NET Frameworkのバージョン4.5より前では、デフォルトのアルゴリズムは単純なクイックソートでした。 」
こういう「遊び」って、面白くありません？
