勢いだけで
ポチッ
としてしまった買い物（【無駄話】ブラックフライデー）。現在その「つけ」で結構苦しんでいます。又webに書いてあったことが現在では必ずしも正しくない、ということも学びました。
苦境を脱しましたならば、その顛末を報告しましょう。
＜注意＞文中にリンクを入れましたが、一部のリンク（特定不能）に対してabema amebaが許可を出さなかったので、リンクではなく、"http(s)://"を除いたパスだけ表示します。
突然ですが、2022年に買い替えた今のmini PC（CHUWI製 RZBox - Ryzen 7 5800H、16MGメモリー、500GB SSD）、
最近頓に立ち上がり時にフリーズしたり、落ちたりするので若干不安に感じており、Micro SDとHDにバックアップを取っていたのですが、昨日一旦立ち上がってからフリーズし、その後認証画面で落ちたので、「潮時かな」ということで本日、
ポチッ
とやってしまいました。
といっても、今度も中国製 mini PC（注）で性能は3年の差があるスペック（Intel Core i9-13900HK、32MGメモリー、1TB SSD）だとおもいます。
注：trigkey.com/products/trigkey-key-r8-mini-pc-amd-ryzen-7-8745hs-8c-16t-up-to-4-9ghz-32gb-lpddr5-5600mhz-1tb-pcie-4-0-ssd-gaming-pc-radeon-780m-graphics-wifi-6-bt5-2-2-5g-lan-dp-hdmi-usb4-triple-display-%E5%89%AF%E6%9C%AC
しかし、「まぁ、Amazonに出品されているんだからよいだろう」と余り調べずに買ってしまってからチェックする、という悪い癖が出ましたが、このサイト（注１）をみて少し安心しました。値段も楽天（￥78,639）よりAmazon（注２￥66,999）の方が15%程安かったですし、メーカーTrigKey（注３）のHPを見ても$439.0なので、本日のレートで計算すると$439.0 x ￥156.41（TTS） x 1.1 = ￥75 - 6,000程度になるかと思いますので、矢張り11- 2%程度安くなっていますね。
注１： //kunitohyouban.com/2024/08/20/trigkey%E3%81%AF%E3%81%A9%E3%81%93%E3%81%AE%E5%9B%BD%EF%BC%9F%E3%83%9F%E3%83%8Bpc%E3%81%AE%E8%A9%95%E5%88%A4%E3%81%A8%E3%80%81%E3%83%90%E3%83%83%E3%82%AF%E3%83%89%E3%82%A2%E3%82%84%E5%AE%89%E5%85%A8/
後、これも。
wwl.sakura.ne.jp/trigkey/
注２：www.amazon.co.jp/TRIGKEY-i9-13900HK%EF%BC%8814%E3%82%B3%E3%82%A2-20%E3%82%B9%E3%83%AC%E3%83%83%E3%83%89%E3%80%81%E6%9C%80%E5%A4%A75-4GHz%EF%BC%89%E3%80%8132GB-SSD%E6%90%AD%E8%BC%89%E3%80%81%E5%B0%8F%E5%9E%8B%E3%83%91%E3%82%BD%E3%82%B3%E3%83%B3%E3%80%814K%E3%83%88%E3%83%AA%E3%83%97%E3%83%AB%E3%83%87%E3%82%A3%E3%82%B9%E3%83%97%E3%83%AC%E3%82%A4%E5%AF%BE%E5%BF%9C%EF%BC%88HDMI-BT5-2%E3%80%81%E3%82%AA%E3%83%95%E3%82%A3%E3%82%B9%E3%83%BB%E3%83%93%E3%82%B8%E3%83%8D%E3%82%B9%E5%90%91%E3%81%91/dp/B0FJ1V6PBW/ref=asc_df_B0FJ1V6PBW?mcid=844a725bc6223dacb3463ed2d2f17d07&tag=jpgo-22&linkCode=df0&hvadid=707549940410&hvpos=&hvnetw=g&hvrand=7134540100200192200&hvpone=&hvptwo=&hvqmt=&hvdev=c&hvdvcmdl=&hvlocint=&hvlocphy=1009318&hvtargid=pla-2440526183969&hvocijid=7134540100200192200-B0FJ1V6PBW-&hvexpln=0&th=1
注３：trigkey.com/
このマシン、YouTube（注１）での紹介もされていましたが、矢張り問題があるとすればOSのライセンス認証の点でしょうか？あまり詳しくなかったので、このサイト（注２）で勉強しました。これ（注３）とか、このサイト（注４）や、このサイト（注５）も詳しいです。現物が届いたら認証状況をチェックして、必要ならクリーンインストール（注６）をしておこうか、と思います。ここら辺は又ブログでご報告させていたこうかと思います。
注１：www.youtube.com/watch?v=GfHlF5SyXw4
注２：www.pasoble.jp/windows/11/how-to-clean-install.html#:~:text=%E3%81%9F%E3%81%84%E8%A8%AD%E5%AE%9A%E7%A2%BA%E8%AA%8D-,Windows11%20%E3%82%AF%E3%83%AA%E3%83%BC%E3%83%B3%E3%82%A4%E3%83%B3%E3%82%B9%E3%83%88%E3%83%BC%E3%83%AB%E3%81%AB%E3%82%88%E3%82%8B%E3%83%A9%E3%82%A4%E3%82%BB%E3%83%B3%E3%82%B9%E8%AA%8D%E8%A8%BC%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6,%E8%AA%8D%E8%A8%BC%E3%81%8C%E5%AE%9F%E6%96%BD%E3%81%95%E3%82%8C%E3%81%BE%E3%81%99%E3%80%82
「初期設定でOEMライセンス化する」
注３：mtalic.com/trigkey-g4/
「<ライセンス種類の確認>
①”スタートボタン”右クリックターミナル(管理者)またはPowerShell(管理者)を開きます。
②”slmgr /dli”+”ENT”で認証情報が表示される。
説明の欄に”VOLUME_MAK”や”OEM_DM”、”RETAIL”などが表示される
(G4の場合初期時は”VOLUME_MAK”、再インストールライセンス認証を行うと”RETAIL”になった)
<プロダクトキーの確認>
①”スタートボタン”右クリック、”ファイル名を指定して実行”に”regedit”と入力時実行。
②ユーザーアカウント制御が出たら”はい”
③メニューバー下の検索ボックスに下記を入力し実行。
”コンピューター\HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows NT\CurrentVersion\SoftwareProtectionPlatform”
④”BackupProductKeyDefault”という項目にプロダクトキーがあるので25桁控える。(クリーンインストール後必要)」
注４：zenn.dev/tttttttttt/articles/5e1ac892697531
「・windowsのライセンスにはOEM版とretail版があり、OEM版のPCにMicrosoft公式のOSをインストールするとライセンス認証がされない。
・OSやドライバはメーカーからダウンロードできる。ない場合問い合わせれば行けるハズ」
注５：hobbyjinsei.com/blog081/
注６：zenn.dev/km100/articles/7f13605224c44a
後は、
現在のRZBoxをどうするか、ですが、単に廃棄するにはもったいないとも思いますので、旧いWindowsとか、違うOSを入れて遊ぶ、という可能性を検討してみます。
【ソート】シリーズもBubble Sort、Heap Sort、Quick Sort、Shell Sort迄消化し、どのようなやり方で並べ替えをしているのかを紹介しましたが、本当にwikiに書かれているような速度の差があるのかどうか、確かめてみたくなりませんか？
最初に紹介した「整数10,000個の要素を使った4つのアルゴリズムの比較用プログラム」（注）を実行すると、例えば↓のイメージの様に「それっぽく」時間差が出るものもありますが、
途中から使っているイメージの様に、Bubble Sortを除く3つは全て「0 ミリセコンド」という現実もあります。
これは偏に乱数を使って作られる「整数10,000個の配列の初期的な並び方」によるものであり、このように差がついてしまうと「本当に速いの？」という疑心が生じてしまうのも仕方がありません。
と、いうことで
一回の結果で判断してはいけないな！
という戒めを持って↑のサンプルプログラムを改造し、
「整数10,000個の要素を使った4つのアルゴリズムの比較用プログラムを一万回実行し、その結果の最大値、最小値、平均値と中央値」
を表示するプログラムを作りました。（初期化等の準備や結果の計算等、純粋にソート処理だけではないのでそんな単純ではないですが、「規模感」としては、ソート10,000回 X テスト10,000回 X 4アルゴリズム = 400,000,000回の処理という、決して64bit CPUにも簡単ではないモノになっていると思います。）
その結果は？
単位：各ソートテストの結果は1/1,000秒、初期化や結果計算等を含む総テスト時間は秒
先ずこのテストの総所要時間（↑のイメージの最後の英文）は「971秒」、即ち「16.2分」。
長いっ！
その内4つのアルゴリズムのソートに掛った時間は、
Bubble Sort - 941.68 sec
Heap Sort - 8.53 sec
Quick Sort - 5.55 sec
Shell Sort - 15.62 sec
ということで、初期化や準備などのを含む総時間の96.98%がバブルソートに要した時間で、クイックソート、ヒープソート、シェルソートの順に速い、ということが確認されて、
やっと腑に落ちました。
これにてソートは一件落着！
【↑の写真の改造サンプルプログラム（前とほぼ同じなので、変更点を除き解説無し）】
///////////////////////
// C++ Sort Comparison
///////////////////////
#include <stdio.h> //C言語の最小限のシステムヘッダー
#include <conio.h> //getch()を使う為
#include <iostream> //C++言語の入出力システムヘッダー
#include <chrono> //C++の時間計測用ライブラリー
//定数定義
#define MAX 10000 //取り敢えず10,000がお勧め
using namespace std;
////////////////////////
// 関数プロトタイプ宣言
////////////////////////
// Comparison
void comparison(int);
// Bubble Sort
void bubblesort(int*, int);
// Heap Sort
void heapsort(int*, int);
void exchange(int, int*, int);
// Quick Sort
void quicksort(int*, int*);
// Shell Sort
void shellsort(int*, int);
// Print result
void print_result(int);
// Comparison function
int compare(const void*, const void*);
////////////////////
// 共通テスト用配列
////////////////////
static int original[MAX];
static double results[4][MAX];
/////////////
// main関数
/////////////
int main(int argc, char** argv) {
chrono::system_clock::time_point begining = chrono::system_clock::now();
for(int i = 0; i < MAX; i++) {
comparison(i);
}
for(int i = 0; i < 4; i++) {
print_result(i);
}
chrono::system_clock::time_point ending = chrono::system_clock::now();
解説：元main関数に書いていた処理をcomparison関数に外出ししてループで使用しています。又、全体処理も時間計測（秒）しました。
double t = static_cast<double>(chrono::duration_cast<chrono::seconds>(ending - begining).count());
printf("Total time consumed for the above processing is: %lf[s]\r\n", t);
cout << endl << "Push CR key ..." << endl;
getchar();
return 0;
}
///////////////
// Comparison
///////////////
void comparison(int n) { 解説：外出ししただけ。（時間計測は1/1000秒）
//テスト用の配列の作成
srand((unsigned)time(NULL)); //現在時刻を元に種を生成
static int test_array[MAX]; //テスト用ローカル変数
for(int i = 0; i < MAX; i++) {
test_array[i] = //originalを保存し、テストはこれで行う
original[i] = rand(); //0から32,767の整数で初期化する
}
//時間計測の準備
chrono::system_clock::time_point start, end;
//ソート比較
start = chrono::system_clock::now();
bubblesort(test_array, MAX);
end = chrono::system_clock::now();
results[0][n] = static_cast<double>(chrono::duration_cast<chrono::microseconds>(end - start).count() / 1000.0);
for(int i = 0; i < MAX; i++)
test_array[i] = original[i];
start = chrono::system_clock::now();
heapsort(test_array, MAX);
end = chrono::system_clock::now();
results[1][n] = static_cast<double>(chrono::duration_cast<chrono::microseconds>(end - start).count() / 1000.0);
for(int i = 0; i < MAX; i++)
test_array[i] = original[i];
start = chrono::system_clock::now();
quicksort(test_array, &test_array[MAX - 1]);
end = chrono::system_clock::now();
results[2][n] = static_cast<double>(chrono::duration_cast<chrono::microseconds>(end - start).count() / 1000.0);
for(int i = 0; i < MAX; i++)
test_array[i] = original[i];
start = chrono::system_clock::now();
shellsort(test_array, MAX);
end = chrono::system_clock::now();
results[3][n] = static_cast<double>(chrono::duration_cast<chrono::microseconds>(end - start).count() / 1000.0);
}
////////////////
// Bubble Sort
////////////////
/*
n個の整数配列dataを総て順に比較、交換し、配列の最後から大きい順に並べる
通称「馬鹿ソート」
*/
void bubblesort(int* data, int n) {
int i, j, temp;
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 n) {
int top, i;
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* start, int* end) {
if(start < end) { //開始位置が終了位置以上で終了（最後の再帰呼び出し参照）
int *left, *right, key, *kp; //順に右進行位置、左進行位置、「分水嶺」値、その位置
//右端乃至左端に到達し、breakで抜けるまでループする
for(left = start, right = end, key = *right;;) {
while(key >= *left)
left++; //keyを超える値迄右に進む
if(left < right) //rightの位置迄は
*right = *left; //leftの値をrightの位置に書き込む
else { //leftがright位置を過ぎたなら
kp = right; //keyの位置をrightの位置としてループを抜ける
break;
}
while(key <= *right)
right--; //key未満の値迄右に進む
if(left < right) //leftの位置迄は
*left = *right; //rightの値をleftの位置に書き込む
else { //rightがleft位置を過ぎたなら
kp = left; //keyの位置をleftの位置としてループを抜ける
break;
}
}
*kp = key; //keyポインターの位置にkeyの値を代入する
quicksort(start, kp - 1); //開始位置からkeyポインター迄で再帰呼び出しする
quicksort(kp + 1, end); //keyポインターから終了位置迄で再帰呼び出しする
}
}
//////////////
// Shell Sort
//////////////
//シェルソートは配列要素を一定の距離を置いたグループに分けて比較、交換を行いソートする方法
void shellsort(int *v, int n) {
int gap, i, j, temp; //gapは比較、交換する要素間の距離
for(gap = n / 2; gap > 0; gap /= 2) { //初期的な距離は配列サイズの1/2とする
for(i = gap; i < n; i++) { //距離は徐々に狭まってゆく
for(j = i - gap; j >= 0 && v[j] > v[j + gap]; j -= gap) {
//v[j]とv[j + gap]を交換する
temp = v[j];
v[j] = v[j + gap];
v[j + gap] = temp;
}
}
}
}
/////////////////
// Print results 解説：1万階のテストの結果計測表示関数です。
/////////////////
void print_result(int n) {
char* title[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番目のソートの結果を合計する
}
qsort(results[n], MAX, sizeof(double), compare); //解説：時間計測値の並び替えは標準ライブラリーのqsortを使っています。
med = results[n][MAX % 2 ? MAX / 2 : MAX / 2 - 1]; //解説：↑は中央値算出の為でした。
cout << title[n] << endl;
cout <<"最大値 ：" << max << endl;
cout <<"最小値 ：" << min << endl;
cout <<"平均値 ：" << ave / MAX << endl;
cout <<"中央値 ：" << med << endl;
cout <<"総所要時間：" << ave << endl << endl;
}
//////////////////////////////////////////////////
//Comparison function
//解説：qsortの為の比較関数を作りました。
//////////////////////////////////////////////////
int compare(const void *elem1, const void *elem2) {
return (int)(*(double*)elem1 - *(double*)elem2);
//解説：この一行でvoidポインター→intポインターにキャストし、それが指す値はdoubleのポインターのelem1|2にしています。
//戻り値 負－elem1がelem2より小さい
// 0 －elem1がelem2と等しい
// 正－elem1がelem2より大きい
}
この間、お昼に麺が食べたくなって「フム、野菜タンメンを、普通の中華麺でなく、中国の麺に似ているうどん（注）で作ったらどうだろう？」ということで、作ってみました。
注：1999年にシンガポールに駐在した時に、即上海（今の上海とは別世界でしたが．．．）で仕事が入り、上海出張で最初に食べた麺が（日本のかん水の入った黄色い麺ではなく）真っ白だったので。これに関しては後記参照。
うん、所謂讃岐うどんの乾麺で十分行けますね。あっさりとした塩味で結構好きです。（注）
注：写真の上に見えるのは「胡椒」、多すぎますよね？スープは清湯の鶏ガラ、トッピングは野菜炒めです。尚、この後、「所謂海苔や志那竹の載った、しょうゆ味の東京ラーメンではどうかしら？」と試してみましたが、✖。お勧めしません。
それはそれとして、「中国の麺」って皆このようにうどんみたいなのか、と言うとそうではなく、（前にも書きましたが）香港麺（ホンコンミェン、ホンコンミー）は日本の中華麺の様に黄色い細麺です。では、
中華麺ってどのくらいの種類があるのかな？
ということで、軽くググってみました。（麺好きには写真を見ているだけで楽しい！）
【中華麺一般】
中国の麺類(wiki)
中国のラーメン事情、麺の種類がそんなに多いの？（深圳大学東京校）
色々ありますね。「北は小麦、南は米」も頷けます。東南アジア迄範囲を広げるとまだ当分私の麺喰い人生は充実しそうです。
所で、最後の記事の「香港ワンタンメン」が私のfavoriteなので、香港麺を少し深堀りしました。
【香港麺】
（香港の）麺の種類
序に私のFavoriteの竹昇麺の海老雲吞麺（Shrimp Dumpling noodle）の写真もどーぞ。
何気なく始めた【ソート】シリーズ、Bubble Sort、Heap Sort、Quick Sortと進めましたが、今回がアルゴリズム紹介の最後で「シェルソート（Shell Sort）」をやります。（今回も詳しく調べられる方の為にwikiの参照を載せます。）
”Shell”というのが最初「貝」を連想させましたが、全く関係なくて、アルゴリズムを開発した方の名前なんですね。アルゴリズムは「（一定の距離をおいた）飛び飛びの列を（距離を縮めながら）繰り返しソートして、配列を大まかに整列された状態に近づけていく」（↑のwiki記事参照）というものです。
ではコードを見てゆきます。
//////////////
// Shell Sort
//////////////
//シェルソートは配列要素を一定の距離を置いたグループに分けて比較、交換を行いソートする方法
void shellsort(int *v, int n) {
int gap, i, j, temp; //gapは比較、交換する要素間の距離
for(gap = n / 2; gap > 0; gap /= 2) { //初期的な距離は配列サイズの1/2とする
for(i = gap; i < n; i++) { //距離は徐々に狭まってゆく
for(j = i - gap; j >= 0 && v[j] > v[j + gap]; j -= gap) {
//v[j]とv[j + gap]を交換する（解説：if文が無いのはforの条件に反映しているから）
temp = v[j];
v[j] = v[j + gap];
v[j + gap] = temp;
}
}
}
今回も実際に処理の動きを見て行きましょう。
配列 = {2, 7, 3, 5, 8, 0, 6, 1, 4};
要素数 9
１．３つのforループ
解説：距離（gap）を要素数の半分(4)にし、第2のforループでgapから末尾迄進め、第3のforループでgap間の2要素を比較、交換する。
配列 = {2, 7, 3, 5, 8, 0, 6, 1, 4};
↑ ↑
比較対象 > gap → 交換
配列 = {2, 0, 3, 5, 8, 7, 6, 1, 4};
配列 = {2, 0, 3, 5, 8, 7, 6, 1, 4};
↑ ↑
比較対象 > gap → 交換
配列 = {2, 0, 3, 1, 8, 7, 6, 5, 4};
配列 = {2, 0, 3, 1, 8, 7, 6, 5, 4}; //第3のループ2回目
↑ ↑
比較対象 > gap → 交換なし
配列 = {2, 0, 3, 1, 4, 7, 6, 5, 8}; //第3のループ2回目
解説：第2ループのカウンターiがnになったので第2ループを抜ける。
２．再度３つのforループ
解説：第1のループで距離（gap）を半分(2)にし、同様に第2、第3のforループでgap間の2要素を比較、交換する。
配列 = {2, 0, 3, 1, 4, 7, 6, 5, 8};
↑ ↑
比較対象>gap → 交換
配列 = {2, 0, 3, 1, 4, 5, 6, 7, 8};
解説：第2ループのカウンターiがnになったので第2ループを抜ける。
３．再々度３つのforループ
解説：第1のループで距離（gap）を半分(1)にし、同様に第2、第3のforループでgap間の2要素を比較、交換する。
配列 = {2, 0, 3, 1, 4, 5, 6, 7, 8};
↑ ↑
｜ gap
比較対象 → 交換
配列 = {0, 2, 3, 1, 4, 5, 6, 7, 8};
配列 = {0, 2, 3, 1, 4, 5, 6, 7, 8};
↑ ↑
｜ gap
比較対象 → 交換
配列 = {0, 2, 1, 3, 4, 5, 6, 7, 8};
配列 = {0, 2, 1, 3, 4, 5, 6, 7, 8};
↑ ↑
｜ gap
比較対象 → 交換
配列 = {0, 1, 2, 3, 4, 5, 6, 7, 8};
如何でしたでしょうか？あっさりとソートされた、という感じですかね？
これで主たるソートアルゴリズムの紹介を終えますが、（ドラゴンボールみたいに）【ソート】シリーズはもうちょっと続きます。
【ご参考】（解説：↑の例のshellsortソート実行中の配列変化の出力）
>>> オリジナルデータ <<<
2, 7, 3, 5, 8, 0, 6, 1, 4
>>> Shell Sort started ... <<<
>>> 第0回目の交換 <<<
2, 0, 3, 5, 8, 7, 6, 1, 4
>>> 第1回目の交換 <<<
2, 0, 3, 1, 8, 7, 6, 5, 4
>>> 第2回目の交換 <<<
2, 0, 3, 1, 4, 7, 6, 5, 8
>>> 第3回目の交換 <<<
2, 0, 3, 1, 4, 5, 6, 7, 8
>>> 第4回目の交換 <<<
0, 2, 3, 1, 4, 5, 6, 7, 8
>>> 第5回目の交換 <<<
0, 2, 1, 3, 4, 5, 6, 7, 8
>>> 第6回目の交換 <<<
0, 1, 2, 3, 4, 5, 6, 7, 8
>>> Shell Sort completed! <<<
0, 1, 2, 3, 4, 5, 6, 7, 8
Push CR key ...
Babble Sort、Heap Sortとみてきましたが、次は（おそらく様々なライブラリー等で最も利用されているアルゴリズムだと思いますが）Quick Sortをリビューしましょう。（今回も詳しく調べられる方の為にwikiの参照を載せます。）
処理時間が速いので「クイック」と言われたのでしょうが、このソートの基本は「基準値（注）」を設けて、それよりも大きなものと、小さなものに仕分けし、その仕分けをそれぞれの仕分け結果に対して再帰的に繰り返す方式です。（このソートは直観的に理解しやすいですよね？）但し、上記wikiの記事に書いてある通り、配列の要素の並びによっては遅いこともあり得ます。
注：wikiの記事では「ピボット"pivot"－「回転軸」のことですが、「転回点」の意味を持たせているのでしょうか？」、以下のプログラムでは"key"という閾値です。配列の要素の中央値が最も早くソートできるといわれています。コードでは暫定的にソート範囲の右端の値にしています。
ではコードを見てゆきます。
//////////////
// Quick Sort
//////////////
//検索範囲（startとend）で、基準値（key）を定め、それよりも多いものと少ないものを分割し、更にkeyの前後で同じ処理を再帰呼び出しする。
void quicksort(int* start, int* end) {
if(start < end) { //開始位置が終了位置以上で終了（最後の再帰呼び出し参照）
int *left, *right, key, *kp; //順に右進行位置、左進行位置、「分水嶺」値、その位置
//右端乃至左端に到達し、breakで抜けるまでループする
for(left = start, right = end, key = *right;;) {
while(key >= *left)
left++; //keyを超える値迄右に進む
if(left < right) //rightの位置迄は
*right = *left; //leftの値をrightの位置に書き込む
else { //leftがright位置を過ぎたなら
kp = right; //keyの位置をrightの位置としてループを抜ける
break;
}
while(key <= *right)
right--; //key未満の値迄右に進む
if(left < right) //leftの位置迄は
*left = *right; //rightの値をleftの位置に書き込む
else { //rightがleft位置を過ぎたなら
kp = left; //keyの位置をleftの位置としてループを抜ける
break;
}
}
*kp = key; //keyポインターの位置にkeyの値を代入する
quicksort(start, kp - 1); //開始位置からkeyポインター迄で再帰呼び出しする
quicksort(kp + 1, end); //keyポインターから終了位置迄で再帰呼び出しする
}
}
今回も実際に処理の動きを見て行きましょう。なお、今まで使っていたサンプルは最大値が偶々最後にあり、Quick Sortのサンプルとしては余りおもしろくないので、今回からちょっと変更し、
配列 = {2, 7, 3, 5, 8, 0, 6, 1, 4};
要素数 9
を想定して実際の処理につき、変更された値は橙で以下に解説します。
１．forループ（keyの設定と右進行）と最初のwhileループ
解説：forループで、（仮に）右端のdata[8]の値(4)をkeyに設定し、開始位置を左端、終了位置を右端とします。leftは開始位置から右に進行するポインター、rightは終了位置から左に進行するポインターです。
配列 = {2, 7, 3, 5, 8, 0, 6, 1, 4}; //key(4)と比較しながらleftは左に進む
↑left ↑right
解説：そして最初のwhileループでkeyよりも大きな値の要素(7)で、右端以前なので右端にその値を代入します。
配列 = {2, 7, 3, 5, 8, 0, 6, 1, 7}; //右端に7が代入される
↑left ↑right
２．次のwhileループで反転
解説：次のwhileループに入り、rightは左へ進み、key未満となる位置で7のあった位置にその値を代入します。
配列 = {2, 1, 3, 5, 8, 0, 6, 1, 7}; //7のあった位置に1が代入される
↑left ↑right
３．forループを続ける
解説：再度forループに戻り、最初のwhileループでkeyよりも大きな値(5)をrightの位置に代入します。
配列 = {2, 1, 3, 5, 8, 0, 6, 5, 7}; //次のkeyよりも大きな値(5)を1があった位置（right）に代入します。
↑left ↑right
４．次のwhileループで反転
解説：次のwhileループに入り、rightは左へ進み、key未満となる0の所で、1のあった位置（left）にその値を代入します。
配列 = {2, 1, 3, 0, 8, 0, 6, 5, 7}; //5のあった位置に0が代入される
↑left↑right
５．forループを続ける
解説：再度forループに戻り、最初のwhileループでkeyよりも大きな値(8)をrightの位置に代入します。
配列 = {2, 1, 3, 0, 8, 8, 6, 5, 7}; //0のあった位置に8が代入される
↑left
↑right
６．次のwhileループで反転、forループを抜ける
解説：次のwhileループに入り、rightは左へ進み、key未満となる3の所でleftよりも左（left > right）になった為、key未満となる3の所で、8のあった位置（left）がkpに設定されます。
配列 = {2, 1, 3, 0, 8, 8, 6, 5, 7}; //*right < keyとなった時点で、left > rightとなりkpがleftの位置に設定される
↑left(kpとなる)
↑right
７．kpで配列を2分割して継続
解説：forループを抜けた所でkpの値がkeyに設定され、
配列 = {2, 1, 3, 0, 4, 8, 6, 5, 7}; //解説：key(4)の左右にkey未満グループとkey(超グループが仕分けされました。
解説：今度は
【key未満グループ】
配列 = {2, 1, 3, 0}; //quicksort(start, kp - 1)で再帰呼び出し
と
【key超グループ】
配列 = {8, 6, 5, 7}; //quicksort(kp + 1, end)で再帰呼び出し
の二つに分割され、１～６までの処理を夫々繰り返します。
【key未満グループ】
配列 = {2, 1, 3, 0}; //keyは0
配列 = {0, 1, 3, 2}; //2が右端へ、rightは左端まで行くので2が0へ
＜再分割＞
【key超グループ2】
配列 = {1, 3, 2}; //keyは2となり、3の位置に2が代入されて終了
配列 = {1, 2, 3}; //終了
【key超グループ】
配列 = {8, 6, 5, 7}; //keyは7
配列 = {5, 6, 7, 8}; //8が右端、5が左端で再分割（元の5の位置にkey((7)を代入）
＜再分割＞
【key未満グループ2】
配列 = {5, 6}; //終了
【key超グループ2】
配列 = {8}; //終了
如何でしたでしょうか？確かに効率的なソートアルゴリズムだと思いますね。
【ご参考】（解説：↑の例のquicksortソート実行中の配列変化の出力）
>>> オリジナルデータ <<<
2, 7, 3, 5, 8, 0, 6, 1, 4
>>> Quick Sort started ... <<<
オリジナル処理（key = 4）
2, 7, 3, 5, 8, 0, 6, 1, 7
オリジナル処理（key = 4）
2, 1, 3, 5, 8, 0, 6, 1, 7
オリジナル処理（key = 4）
2, 1, 3, 5, 8, 0, 6, 5, 7
オリジナル処理（key = 4）
2, 1, 3, 0, 8, 0, 6, 5, 7
オリジナル処理（key = 4）
2, 1, 3, 0, 8, 8, 6, 5, 7
オリジナル処理（key = 4）
2, 1, 3, 0, 8, 8, 6, 5, 7
再帰処理（key = 0）
2, 1, 3, 2, 4, 8, 6, 5, 7
再帰処理（key = 0）
2, 1, 3, 2, 4, 8, 6, 5, 7
再帰処理（key = 2）
0, 1, 3, 3, 4, 8, 6, 5, 7
再帰処理（key = 2）
0, 1, 3, 3, 4, 8, 6, 5, 7
再帰処理（key = 7）
0, 1, 2, 3, 4, 8, 6, 5, 8
再帰処理（key = 7）
0, 1, 2, 3, 4, 5, 6, 5, 8
再帰処理（key = 7）
0, 1, 2, 3, 4, 5, 6, 5, 8
再帰処理（key = 6）
0, 1, 2, 3, 4, 5, 6, 7, 8
>>> Quick Sort completed! <<<
0, 1, 2, 3, 4, 5, 6, 7, 8
Push CR key ...
↑のタイトル（「毎朝私が好きで欠かさないもの」）はウケを狙ったもので、そのオリジナルはコレ（What You Won't Do for Love－注）です。
注：Bobby Caldwellの1978年リリースの曲。私が就職した年でもあり、内容も適齢期の多感な私にピッタリの曲で好きでした。どうでしょう？お耳にあいますでしょうか？
閑話休題。
私は所謂ベジタリアンではないですが、大の野菜好きなので毎朝野菜を食べます。それもメインディッシュ用の大きい皿で、（時々キャベツベースのコールスローやツナサラダにしますが）殆どがこの（↓）サラダ。
選手たちはレタス（玉レタス、サニーレタス、フリルレタス等）、水菜、キャベツ、オニオンスライス、ピーマン/パプリカ、人参、胡瓜、トマト（大玉、中玉、ミニ）と（何故か）竹輪、ハム、ソーセージ等
ドレッシングの種類も、
（１）自製洋風オイルアンドヴィネガー（バージンオリーブオイル、調理酢１：穀物酢１とブラックペパー）
（２）自製和風オイルアンドビネガー（ごま油とポン酢醤油）
（３）自製和風マヨポン酢（まんまで、マヨネーズとポン酢醤油）
（４）その他（イタリアン、フレンチ<透明と白>、シーザー、コブ、黒酢玉葱、深炒り胡麻、etc etc＋追い穀物酢）
と結構多彩で、毎日食べても飽きが来ません。（注）
注：毎朝、神様にも作るのですが、「量が多すぎる」ということで小さなお皿にし、「毎日よく飽きないね～笑」とからかわれます。
私って変でしょうか？（不安;）
ps. 今朝ウォーキングをしている時に掛ったのが Everything must change （注）、矛盾しています？
注：これはDavid Sanbornのカバー。オリジナルは又しても1978年の Everything Must Change （1978 - Johnny Lytle ）のようで、これも私の大好きな曲です。→と思っていたら1976年にリリースされたEverything Must Change （Randy Crawford）がオリジナルのようです。同じ曲ですが、それも趣が異なりますね？→と思ったら、作曲はBenard Ighnerさんで、リリースは1974年だそうです。
"Ighner became a session singer in Hollywood. In 1974, he sang his own composition "Everything Must Change", a track on Quincy Jones' best-selling album Body Heat. Though not issued as a single, it is claimed that "the haunting masterwork went a long way toward selling the full-length album.." The song was later recorded as the title track of a 1976 album by Randy Crawford, as well as by Barbra Streisand, Peggy Lee, George Benson, Nina Simone, Nancy Wilson, Judy Collins, June Christy, Jean Carn, Oleta Adams, David Sanborn, and others."（何と錚々たるJazz singers or playersでしょうか？勉強になりました。）
ソート（並び替え）のアルゴリズムのリビューとして始めたこのシリーズ、バブルソートに続く第2弾です。
今回取り上げるのは「ヒープソート（Heap Sort）」と呼ばれるものです。(今回も詳しく調べられる方の為にwikiの参照を載せます。）
何故"Heap（「積み重ね、かたまり、山」）"と言い始めたのかは分かりませんが、以下のように二分木を使った並び替え方法（アルゴリズム）です。
//////////////
// 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 n) {
int top, i;
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); //解説：ヒープソートのから呼び出すサブ関数
} //配列の最後を切り離し、その前の要素から頂点まで継続する
}
これだけではどのように並び替えが行われるのかよく分かりませんよね？
ヒープソートは直観的に理解するのが少し難しいので、今回も具体的に
配列 = {2, 7, 3, 5, 4, 0, 6, 1, 8};
要素数 9
を想定して実際の処理につき、変更された値は橙、最大値は赤で以下に解説します。
１．原型
2 解説：data[0]
／ ＼
7 3 解説：data[1]とdata[2]
／ ＼ ／ ＼
5 4 0 6 解説：data[3] ～ data[6]
／ ＼
1 8 ... 解説：data[7]からdata[8]
配列 = {2, 7, 3, 5, 4, 0, 6, 1, 8};
２．HeapSortの第1ループとexchange
(1) top == 3 解説：forループの初期化がtop = n / 2 - 1なので。（これは子のある最後の二分木を指す。）
2
／ ＼
7 3
／ ＼ ／ ＼
5 4 0 6 解説：このdata[3]（5）が
／ ＼
1 8 ... 解説：data[8]（8）（> data[7]（1））と比較され、交換される
解説：世代の最後である第3世代から始めますが、8 > 1なので、（top * 2 + 1で7であった）iはインクリメント（i++;）され8となる為、親の5と右の子8の比較となり、交換が生じます。交換は
data[top] = data[i]; //二分木の親に大きい子の値を代入する
と、forループの事後処理の
top = i, i = top * 2 + 1
により、元の親の値（temp（5））がdata[top]、即ち元のi（8）に代入される
data[top] = temp;
ことで成立します。又この段階で新しいiが17（8 * 2 + 1）となり、forループを抜けます。
配列 = {2, 7, 3, 8, 4, 0, 6, 1, 5};
(2) top == 2 解説：forループの事後処理がtop--なので。
2
／ ＼
7 3 解説：この3が
／ ＼ ／ ＼
8 4 0 6 解説：この6（> 0）と比較され、交換される
／ ＼
1 5 ...
解説：同様にtopが2となり、親が3、子が0と6の二分木を処理します。右の子（6）が左の子（0）より大きいので、親の3と右の子（6）が比較され、交換されます。ここでもiは事後処理で13となり、ループを抜けます。
配列 = {2, 7, 6, 8, 4, 0, 3, 1, 5};
(3) top == 1 解説：forループの事後処理がtop--なので。
2
／ ＼
7 6 解説：この7が
／ ＼ ／ ＼
8 4 0 3 解説：この8と比較され、交換される
／ ＼
1 5 ...
解説：同様にtopが1となり、親が7、子が8と4の二分木で、親の7と左の子（8）が比較され、交換されます。ここではiが事後処理で7となり、親が8、子が1と5の二分木についても比較が行われ、親が大きいので（break;）交換は行われません。
配列 = {2, 8, 6, 7, 4, 0, 3, 1, 5};
(4) top == 0 解説：forループの事後処理がtop--なので。（条件式：top >= 0）
2 解説：この（tempに保存される）2が
／ ＼
8 6 解説：この8と比較され、親（2）に8が代入される
／ ＼ ／ ＼
7 4 0 3
／ ＼
1 5 ...
解説：最後にtopが0、i が1となり、親が2、子が8と6の二分木で、親の2と左の子（8）が比較され2のあった場所（data[0]）に8が代入されます。
8
／ ＼
8 6
／ ＼ ／ ＼
7 4 0 3
／ ＼
1 5 ...
解説：ここでも事後処理
top = i, i = top * 2 + 1
でtopにi（1）が代入され、iが3（top * 2 + 1）となり、親が8、子が7と4の二分木についても「最初の親の値（temp（2））」と比較が行われ、data[3]の7が大きいので交換は行われます。
8
／ ＼
7 6
／ ＼ ／ ＼
7 4 0 3
／ ＼
1 5 ...
解説：更に事後処理
top = i, i = top * 2 + 1
でtopにi（3）が代入され、iが7（top * 2 + 1）となり、親が7、子が1と5の二分木についても「最初の親の値（temp - 2）」と比較が行われ、左の子より右の子が大きいのでiはインクリメントされて8となり、data[8]の5が大きいので交換7のあったdata[[3]に5が代入され、
8
／ ＼
7 6
／ ＼ ／ ＼
5 4 0 3
／ ＼
1 5 ...
解説：iが17（top * 2 + 1）となったのでループを抜けて、5があったdata[8]に2が代入されて交換が完了します。
8
／ ＼
7 6
／ ＼ ／ ＼
5 4 0 3
／ ＼
1 2 ...
解説：最終的に次のような配列となります。
配列 = {8, 7, 6, 5, 4, 0, 3, 1, 2};
３．HeapSortの第2ループとexchange
解説：HeapSortの第1ループのtopの値が"top--;"により-1になったので、第1ループを抜けます。第2ループでは最大値を最後尾にと交換し、最大値の8を除外し、要素数を1減らされた8にして二分木の頂点から下に向かって同じ処理を繰り返し（for(i = n - 1; i > 0; i--)、exchange(0, data, i);）行います。
2
／ ＼
7 6
／ ＼ ／ ＼
5 4 0 3
／ ＼
1 8 ...
解説：先ずは最大値8を除外して要素数iが8の配列の変化を示します。
2
／ ＼
7 6
／ ＼ ／ ＼
5 4 0 3
／
1 ...
7
／ ＼
7 6
／ ＼ ／ ＼
5 4 0 3
／
1 ...
7
／ ＼
5 6
／ ＼ ／ ＼
5 4 0 3
／
1 ...
7
／ ＼
5 6
／ ＼ ／ ＼
2 4 0 3
／
1 ...
配列 = {7, 5, 6, 2, 4, 0, 3, 1, 8};
解説：次に最大値7を除外した新しい二分木を要素数7で同様の処理を続けます。
5
／ ＼
6 2
／ ＼ ／ ＼
4 0 3 1...
| |
＼ ／
配列 = {5, 6, 2, 4, 0, 3, 1, 7, 8};
6
／ ＼
5 3
／ ＼ ／ ＼
2 4 0 1...
| |
＼ ／
配列 = {5, 3, 2, 4, 0, 1, 6, 7, 8};
解説：更に最大値6を除外した新しい二分木を要素数6で同様の処理を続けます。
5
／ ＼
3 2
／ ＼ ／
4 0 1...
| |
＼ ／
配列 = {4, 3, 2, 1, 0, 5, 6, 7, 8};
解説：このようにして同じ処理を繰り返してゆき、末尾から8、7、6、5 ...と第2ループの最大値が並んでゆき、並び替えが完了して最後に配列は次のようになります。
配列 = {0, 1, 2, 3, 4, 5, 6, 7, 8};
如何でしたか？ちょっととっつきにくかったかもしれませんが、wikiの記事と共にご確認ください。
【ご参考】（解説：↑の例のヒープソート実行中のexchange関数における配列変化の出力）
>>> オリジナルデータ <<<
2, 7, 3, 5, 4, 0, 6, 1, 8
>>> Heap Sort <<<
--- top = 3 and i = 8 ---
2, 7, 3, 8, 4, 0, 6, 1, 8
--- top = 8 ---
2, 7, 3, 8, 4, 0, 6, 1, 5
--- top = 2 and i = 6 ---
2, 7, 6, 8, 4, 0, 6, 1, 5
--- top = 6 ---
2, 7, 6, 8, 4, 0, 3, 1, 5
--- top = 1 and i = 3 ---
2, 8, 6, 8, 4, 0, 3, 1, 5
--- top = 3 ---
2, 8, 6, 7, 4, 0, 3, 1, 5
--- top = 0 and i = 1 ---
8, 8, 6, 7, 4, 0, 3, 1, 5
--- top = 1 and i = 3 ---
8, 7, 6, 7, 4, 0, 3, 1, 5
--- top = 3 and i = 8 ---
8, 7, 6, 5, 4, 0, 3, 1, 5
--- top = 8 ---
8, 7, 6, 5, 4, 0, 3, 1, 2
--- top = 0 and i = 1 ---
7, 7, 6, 5, 4, 0, 3, 1, 8
--- top = 1 and i = 3 ---
7, 5, 6, 5, 4, 0, 3, 1, 8
--- top = 3 ---
7, 5, 6, 2, 4, 0, 3, 1, 8
--- top = 0 and i = 2 ---
6, 5, 6, 2, 4, 0, 3, 7, 8
--- top = 2 and i = 6 ---
6, 5, 3, 2, 4, 0, 3, 7, 8
--- top = 6 ---
6, 5, 3, 2, 4, 0, 1, 7, 8
--- top = 0 and i = 1 ---
5, 5, 3, 2, 4, 0, 6, 7, 8
--- top = 1 and i = 4 ---
5, 4, 3, 2, 4, 0, 6, 7, 8
--- top = 4 ---
5, 4, 3, 2, 1, 0, 6, 7, 8
--- top = 0 and i = 1 ---
4, 4, 3, 2, 1, 5, 6, 7, 8
--- top = 1 and i = 3 ---
4, 2, 3, 2, 1, 5, 6, 7, 8
--- top = 3 ---
4, 2, 3, 0, 1, 5, 6, 7, 8
--- top = 0 and i = 2 ---
3, 2, 3, 0, 4, 5, 6, 7, 8
--- top = 2 ---
3, 2, 1, 0, 4, 5, 6, 7, 8
--- top = 0 and i = 1 ---
2, 2, 1, 3, 4, 5, 6, 7, 8
--- top = 1 ---
2, 0, 1, 3, 4, 5, 6, 7, 8
--- top = 0 ---
1, 0, 2, 3, 4, 5, 6, 7, 8
--- top = 0 ---
0, 1, 2, 3, 4, 5, 6, 7, 8
Push CR key ...
一口に「焼きそば」と言っても色々とあります。先ず「日本の焼きそば」があれば、アジア中華圏の「炒麺」、「世界に伝播した焼きそば」等など。
更に「麺喰い」の私にとっては、麺の範囲をミーフン、ミーゴレンや「暗殺者のパスタ」等の焼きスパゲッティに広げれば、私の中では立派な「焼きそば」です。従って国内出張はもとより、海外駐在2回、海外旅行などでは積極的にローカス「焼きそば」にトライしてきました。
自分でも結構作ります。記録に残っているだけでも、
2020年04月03日香港焼そば
2020年12月07日広東風海鮮焼きそば
2022年10月13日スープ焼きそば
（殆ど野菜タンメンですね？）
2023年11月20日ガパオ焼きそば
2025年06月11日海鮮餡かけ焼きそば
等があります。
先日の旅行で、「出雲大社の出先」にお参りに行ったのですが、近所のチャイナタウンに"LegendSeafoodRestrant"という飲茶の店があり、出雲大社祭礼時には必ず立ち寄り、いくつかDumplingを頂いた後、〆（締め）に海鮮焼きそばを頂きます。
（喰いかけでスミマセン！！！）
これが私の
Favorite!
でした。
では、前に開示しましたコードを使って4つのソートアルゴリズムを確認してゆきましょう。
矢張り最初に登場願うのは最もストレートなソートアルゴリズムである「バブルソート」でしょう。詳しくお知りになりたい方はリンクのwikiの説明もご覧ください。
////////////////
// Bubble Sort
////////////////
/*
n個の整数配列dataを総て順に比較、交換し、配列の最後から大きい順に並べる
通称「馬鹿ソート」
*/
void bubblesort(int* data, int n) {
int i, j, temp;
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に最大の要素が置かれる
}
}
上のコードを使って簡単に説明するとすれば、この方法は「dataという場所に並んでいる、n人の選手（整数）の勝ち抜き戦をn - 1回（最後は一人になるので相手がいない為）行う」方法と言えます。
より具体的に見てみましょう。簡単な例として
配列 = {2, 7, 3, 5, 4, 0, 6, 1, 8};
要素数 9
を想定します。
１．外側のループ
先ずインデックスiの初期値はn - 1（= 8）で、0から始まる配列の最後（data[n - 1]、値は8） を指します。
２．内側のループ
インデックスjが0からiの指す最後の手前まで、即ち配列data[0]（値は2）から始め、順に次の配列（data[j + 1]）の値と比較し、手前が大きければ次と交換して行きます。
配列 = {2, 3, 5, 4, 0, 6, 1, 7, 8}; （解説：交換で移動させられた値は橙、最後の最大値は赤で表します。）
偶々最後のdata[8]が8だったので、交換はされませんでしたが、一番大きな値の8が最後に置かれました。
３．外側のループ
インデックスiは配列最後の8の手前の7を指します。
４．内側のループ
インデックスjが又0からiの指す最後の手前まで、即ち配列data[0]（値は2）から始めて比較と必要に応じて交換を行います。
配列 = {2, 3, 4, 0, 5, 1, 6, 7, 8}; （解説：↑の通り。なお確定値は青で示します。）
５．外側のループ
インデックスiは配列最後の二つ手前の6を指します。
６．内側のループ
インデックスjが又0からiの指す最後の手前まで比較と必要に応じて交換を行います。
配列 = {2, 3, 0, 4, 1, 5, 6, 7, 8};
７．外側のループ
インデックスiは配列最後の三つ手前の5を指します。
８．内側のループ
インデックスjが2から始めて
配列 = {2, 0, 3, 1, 4, 5, 6, 7, 8};
９．外側のループ
インデックスiは配列最後の四つ手前の4を指します。
10．内側のループ
インデックスjが2から始めて比較と必要に応じて交換を行います。
配列 = {0, 2, 1, 3, 4, 5, 6, 7, 8};
11．外側のループ
インデックスiは配列最後の五つ手前の3を指します。
12．内側のループ
インデックスjが2から始めて同様に処理します。
配列 = {0, 1, 2, 3, 4, 5, 6, 7, 8};
13．外側のループ
外側のインデックスがdata[2]（値は2）、data[1]（値は1）を指しますが、交換無しで終了します。
配列 = {0, 1, 2, 3, 4, 5, 6, 7, 8};
いかがでしょうか？具体的な例でプログラムが何をやっているかをトレースしてみるとよくその動作が分かるかと思います。（解説：デバッガーがやることをハンドでバッギングしている、ということです。）
この方法がバブルソートと呼ばれるのは、配列中の大きな値が最後の方へ運ばれる様子が「泡が上がってくる様子」と似ているからと言われます。しかし、この方法は比較や交換の回数が多くなり、他のソートアルゴリズム（解法）よりも遅いという難点があります。次の前に開示したコードの実行例は他のソートアルゴリズムが1万個の整数配列のソートに殆ど時間を要していないのに、バブルソートだけは95/10,000秒時間がかかったことを示しています。
次回はより速いソートアルゴリズムであるヒープソートを見て行きましょう。