マージソート（１）
下のマージソートのプログラムは、はっきり言って良くないです (//△//)。
「先ず配列を分割する」の意味と、「再帰的な処理」の扱い方があいまいなまま作業に入ったのが良くなかったです。
無駄の多いプログラムを書いているうちに、それらのことが少し理解できたので、次回にもう少しマシなプログラムを作りたいと思っています。
だだ、無駄は多いのですが、ソートしていく手順としてはマージソートになっているので、一応下記しておきます。
最後に掲載してある実行結果の画面コピーで、数字の並びがマージソートされる過程を確認できるのではないかと思います。
// ------------------------------------
#include <iostream>
int main() {
int a[]
= { 25, 21, 16, 12, 17, 11, 23, 19, 28, 17, 13,
22, 24, 11, 18, 26, 19, 10, 21, 17, 19, 16, 14};
int nmemb = sizeof(a) / sizeof(a[0]);
for (int i = 0; i < nmemb; i++)
std::cout << a[i] << " ";
std::cout << '\n';
int nmem = nmemb;
int p = 0;
while (nmem /= 2) p++;
if (nmemb > (int)pow(2, p))
nmem = (int)pow(2, p + 1);
int* f = new int[nmem];
int* g = new int[nmem];
for (int i = nmemb; i < nmem; i++)
f[i] = INT_MAX;
for (int i = 0; i < nmemb; i++)
f[i] = a[i];
for (int i = 0; ; i++) {
for (int j = 0; j < nmem / pow(2, i + 1); j++) {
// pow(2, i + 1) … 2 の i + 1 乗
// 操作対象範囲の要素数
// pow(2, i + 1) = 2, 4, 8, ･･･
int nl = (int)pow(2, i);
// pow(2, i) は操作対象範囲の左側要素数
// pow(2, i) = 1, 2, 4 ･･･
if (nl >= nmem) goto END;
// 操作対象範囲の左側要素数が、配列 f の要素数以上に
// なったら作業終了。
int nr = nl;
// 操作対象範囲の右側要素数
int xleft = (int)pow(2, i + 1) * j;
// 操作対象範囲左側の左端要素の添字
int xrght = xleft + nl;
// 操作対象範囲右側の左端要素の添字
int xl = xleft;
int xr = xrght;
for (int k = 0; k < nl + nr; k++) {
// 操作対象範囲内の要素の個数と同じ回数だけの繰返し
if (
f[xl] <= f[xr] && xl < xleft + nl
|| xr >= xrght + nr
)
// ｢ f[xl] <= f[xr]
// かつ xl が操作対象範囲左側に収まっている ｣
// または ｢ xr が操作対象範囲右側を超えている ｣
g[xleft + k] = f[xl++];
// f[xl] の値を臨時の配列 g に収容し、xl++ する。
else if (xr < xrght + nr) {
// そうではない場合
g[xleft + k] = f[xr++];
// a[xr] の値を臨時の配列 g に収容し、xr++ する。
}
}
} // j{ }
for (int i = 0; i < nmemb; i++) {
a[i] = f[i] = g[i];
}
for (int i = 0; i < nmemb; i++)
std::cout << a[i] << " ";
std::cout << '\n';
} // i{ }
delete[] f;
delete[] g;
END:
;
}
// ------------------------------------
|
新品価格 |
|
新品価格 |
