ソート (2)
ソート の続きです。今回はヒープソートとマージソートという高速なソートアルゴリズムを説明します。それから、連結リストのソートについて説明します。
●ヒープソート
ヒープ (heap) は 前回 説明したデータ構造です。実は、このヒープを使ったソートも優秀なアルゴリズムの一つです。実行時間は N * log2 N に比例しますが、平均するとクイックソートよりも遅くなります。しかし、クイックソートとは違って、データの種類によって性能が劣化することはありません。
プログラムは次のようになります。
リスト : ヒープソート
void heap_sort(double *buff, int size)
{
for (int i = size / 2 - 1; i >= 0; i--) {
int c, n = i;
double x = buff[n];
while ((c = 2 * n + 1) < size) {
if (c + 1 < size && buff[c] < buff[c + 1]) c++;
if (x >= buff[c]) break;
buff[n] = buff[c];
n = c;
}
buff[n] = x;
}
for (int i = size - 1; i >= 0; i--) {
int c, n = 0;
double x = buff[i];
buff[i] = buff[0];
while ((c = 2 * n + 1) < i) {
if (c + 1 < i && buff[c] < buff[c + 1]) c++;
if (x >= buff[c]) break;
buff[n] = buff[c];
n = c;
}
buff[n] = x;
}
}
前半部分でヒープを構築します。親子関係が 前回 の説明と逆になっていることに注意してください。つまり、親が子より大きいという関係を満たすようにヒープを構築します。したがって、配列の先頭 (buff[0]) が最大値になります。
後半部分で、最大値を取り出してヒープを再構築します。配列の先頭には最大値がセットされているので、これを配列の最後尾のデータと交換します。あとは、そのデータを除いた範囲でヒープを再構築すれば、その次に大きいデータを求めることができます。これを繰り返すことで、大きいデータが配列の後ろから整列していくことになります。
最初の for ループで、配列の前半部分のデータを後ろから順番に取り出します。次の while ループで、親子関係を満たすように修正します。変数 n が親の位置を、変数 c が子の位置を示します。次に、後半の for ループで、最大値 buff[0] と最後尾のデータ buff[i] を交換します。そして、while ループでヒープの再構築を行います。あとはヒープのプログラムとほとんど同じですが、ヒープを再構築する範囲が変数 i で管理されていて、その値は一つずつ減っていくことに注意してください。
●実行結果 (1)
それでは実行結果を示します。
表 : heap sort の結果 (単位 : 秒) 個数 : 乱数 : 昇順 : 逆順 : 山型 --------+-------+-------+-------+------- 1000000 : 0.201 : 0.090 : 0.094 : 0.104 2000000 : 0.470 : 0.189 : 0.196 : 0.220 4000000 : 1.100 : 0.374 : 0.405 : 0.466 8000000 : 2.528 : 0.771 : 0.829 : 0.967 実行環境 : clang version 14.0.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz 最適化オプション : -O2
このように、ヒープソートはどのデータに対しても、そこそこの速度でソートすることができます。ただし、実行時間はクイックソートだけではなくシェルソートやコムソートよりも遅くなってしまいました。ヒープソートの処理内容は他のソートアルゴリズムよりも複雑なので、時間がかかるのは仕方がないのかもしれません。また、M.Hiroi のコーディングに何か問題があるのかもしれません。お気づきの点がありましたら、ご教示お願いいたします。
●マージとは？
「マージ (併合 : merge)」とはソート済みの複数の列を一つの列にまとめる操作のことです。このマージを使ったソートを「マージソート (merge sort)」といいます。最初にマージについて簡単に説明します。次の図を見てください。
図 : マージの考え方
2 つのリスト a と b があります。これらのリストはソート済みとしましょう。これらのリストをソート済みのリストにまとめることを考えます。 a と b はソート済みなので先頭のデータがいちばん小さな値です。したがって、上図のように先頭のデータを比較し、小さい方のデータを取り出して順番に並べていけば、ソート済みのリストにまとめることができます。途中でどちらかのリストが空になったら、残ったリストのデータをそのまま追加します。
●マージソートの原理
当たり前だと思われるでしょうが、これが「マージソート (merge sort)」の原理です。次の図を見てください。
9 5 3 7 6 4 2 8 最初の状態
|5 9|3 7|4 6|2 8| 長さ２の列に併合
|3 5 7 9|2 4 6 8| 長さ４の列に併合
2 3 4 5 6 7 8 9 ソート終了
図 : マージソート
マージをソートに応用する場合、最初は各要素をソート済みの配列として考えます。この状態で隣の配列とマージを行い、長さ 2 の配列を作ります。次に、この配列に対して再度マージを行い、長さ 4 の配列を作ります。このように順番にマージしていくと、最後には一つの配列にマージされソートが完了します。
●マージソートのプログラム
それではプログラムを作りましょう。配列の長さを 1, 2, 4, 8, ... と増やしていくよりも、再帰的に考えた方が簡単です。マージは 2 つの列を一つの列にまとめる操作です。そこで、まずソートする配列を 2 つに分けて、前半部分をソートします。次に後半部分をソートして、その結果をマージすればいいわけです。
では、どうやってソートするのかというと、再帰呼び出しするのです。そうすると、どんどん配列を 2 つに割っていくことになり、最後にデータが一つとなります。それはソート済みの配列と考えることができるので、再帰呼び出しを終了してマージ処理に移ることができます。あとはデータを順番にマージしていってソートが完了します。
プログラムは次のようになります。
リスト : マージソート
// 挿入ソート
void insert_sort(double *buff, int low, int high)
{
for (int i = low + 1; i <= high; i++) {
int j;
double temp = buff[i];
for (j = i - 1; j >= low && temp < buff[j]; j--) {
buff[j + 1] = buff[j];
}
buff[j + 1] = temp;
}
}
// マージソート
#define LIMIT 32
void merge_sort_sub(double *buff, int low, int high)
{
if (high - low <= LIMIT) {
insert_sort(buff, low, high);
} else {
int mid = low + (high - low) / 2;
merge_sort_sub(buff, low, mid);
merge_sort_sub(buff, mid + 1, high);
int p = 0;
int i = low;
while (i <= mid) work[p++] = buff[i++];
i = mid + 1;
int j = 0;
int k = low;
while (i <= high && j < p) {
if (work[j] <= buff[i]) {
buff[k++] = work[j++];
} else {
buff[k++] = buff[i++];
}
}
while (j < p) buff[k++] = work[j++];
}
}
void merge_sort(double *buff, int size)
{
merge_sort_sub(buff, 0, size - 1);
}
最初に区間の幅が LIMIT 以下になったかチェックします。そうであれば、挿入ソート (insert_sort) に切り替えてソートします。この方が少しですが速くなります。これが再帰呼び出しの停止条件になります。区間の幅が LIMIT よりも大きい場合はマージソートを行います。
まず列の中央を求めて変数 mid にセットします。最初に前半部、それから後半部をマージソートします。これは merge_sort を再帰呼び出しするだけです。再帰呼び出しから戻ってくると、配列の前半部分と後半部分はソートされているのでマージ処理を行います。
まず前半部分を作業領域 work に退避します。work はグローバル変数として定義します。work の大きさはソートする配列の半分で十分です。たとえば、前半部分のデータよりも後半部分のデータがすべて小さいとします。この場合、後半部分のデータが先頭から順番にセットされ、その後ろに退避した前半部分のデータがセットされます。逆に、前半部分のデータがすべて小さければ、後半部分のデータは移動する必要はないので、work に退避した前半部分のデータを元に戻すことになります。
次の while ループで、前半部分もしくは後半部分どちらかにデータがある間、データの比較と移動を繰り返し行います。前半部分と後半部分を先頭から順番に比較し、小さい方を区間の先頭から順番にセットしていきます。後半部分のデータが先になくなって、作業領域 work にデータが残っている場合は、最後の while ループでデータを後ろに追加します。
●実行結果 (2)
それでは実行結果を示します。
表 : merge sort の結果 (単位 : 秒) 個数 : 乱数 : 昇順 : 逆順 : 山型 --------+-------+-------+-------+------- 1000000 : 0.140 : 0.037 : 0.055 : 0.048 2000000 : 0.286 : 0.078 : 0.115 : 0.100 4000000 : 0.608 : 0.169 : 0.247 : 0.216 8000000 : 1.290 : 0.359 : 0.525 : 0.467
マージソートの実行時間は、要素数を N とすると平均して N * log2 N に比例します。マージソートはクイックソートと同様に高速なアルゴリズムですが、実際にプログラムを作って比較してみるとクイックソートの方が高速です。しかし、マージソートは配列を単純に二分割していくため、クイックソートと違ってデータの種類によって性能が劣化することはありません。ヒープソートと同様に、どのようなデータに対しても力を発揮してくれるわけです。ただし、ヒープソートとは違って作業領域が必要になります。
なお、マージソートは連結リストのソートや外部ソートに適したアルゴリズムです。連結リストのソートはあとで説明します。
●マージソートの改良
マージソートは配列 buff の大きさを N とすると、大きさが N / 2 の作業用領域 work を必要としました。ここで、作業領域 work の大きさを配列 buff と同じ N にすることを考えます。この場合、最初に buff を work にコピーしておいて、再帰のたびに buff と work を交互に入れ換えることで、マージソートの実行速度を改善することができます。
なお、この方法は C++によるソート(sort)のページ 修正マージソート を参考にさせていただきました。有益な情報を公開されている作者様に感謝いたします。
プログラムは次のようになります。
リスト : マージソート (改良版)
void msort(double *a, double *b, int low, int high)
{
if (high - low <= LIMIT) {
insert_sort(b, low, high);
} else {
int mid = low + (high - low) / 2;
msort(b, a, low, mid);
msort(b, a, mid + 1, high);
int i = low;
int j = mid + 1;
int k = low;
while (i <= mid && j <= high) {
if (a[i] <= a[j])
b[k++] = a[i++];
else
b[k++] = a[j++];
}
while (i <= mid) b[k++] = a[i++];
while (j <= high) b[k++] = a[j++];
}
}
void merge_sort1(double *buff, int size)
{
for (int i = 0; i < size; i++) work[i] = buff[i];
msort(work, buff, 0, size - 1);
}
merge_sort1 は buff を配列 work にコピーしてから関数 msort を呼び出してマージソートします。msort(a, b, low, high) は、配列 b の区間 (low, high) を二分割してソートします。msort を再帰呼び出しするとき、引数 a, b を逆にすることに注意してください。二つの区間をソートしたあと、二つの区間をマージした結果は配列 a の区間 (low, high) にセットします。改良前の merge_sort では、あらかじめ buff の前半部分を work に退避していましたが、buff を work にコピーしておいて、buff と work を交互に切り替えることで、buff の前半部分を work に退避する処理が不要になります。
●実行結果 (3)
それでは実行結果を示します。
表 : merge sort (改良版) の結果 (単位 : 秒) 個数 : 乱数 : 昇順 : 逆順 : 山型 --------+-------+-------+-------+------- 1000000 : 0.136 : 0.041 : 0.052 : 0.048 2000000 : 0.289 : 0.088 : 0.111 : 0.103 4000000 : 0.610 : 0.187 : 0.233 : 0.216 8000000 : 1.319 : 0.399 : 0.500 : 0.460
実行速度に大きな差はありませんでした。他のプログラミング言語、たとえば Python3 では改良版のほうが少し速くなったのですが、今回のプログラムでは改良の効果はあまりないようです。他のコンパイラ (gcc など) では異なる結果になるかもしれません。興味のある方は試してみてください。
●連結リストのソート
次は連結リストのソートについて説明します。連結リストはセルを一方向につなげたデータ構造なので、配列のようにランダムアクセスすることはできません。このため、クイックソートのように配列を直接書き換えるアルゴリズムを、そのまま連結リストに適用することはできませんが、枢軸を基準にリストを二分割していくことで、連結リストでもクイックソートすることができます。
●クイックソート
基本的な考え方は簡単です。クイックソートは枢軸を基準にして、要素をそれより大きいものと小さいものの 2 つに分割していくことでソートを行います。枢軸は要素の中から適当な値を選んでいいのですが、連結リストの場合は任意の箇所を簡単に選ぶことができません。この場合は、いちばん簡単に求めることができる先頭の要素を枢軸とします。
次に連結リストを 2 つに分けます。このとき、セルを繋ぎ直していくことで、新しいセルを生成しなくても、連結リストを二分割することができます。そして、それらの連結リストを再帰呼び出しして同様にソートします。最後に、その結果を枢軸を挟んで結合します。これを図に表すと次のようになります。
5 3 7 6 9 8 1 2 4
5 を枢軸に分割
(3, 1, 2, 4) 5 (7, 6, 9, 8)
3を枢軸に分割 7を枢軸に分割
(1, 2) 3 (4) | 5 | (6) 7 (9, 8)
・・・分割を繰り返していく・・・
図 : 連結リストのクイックソート
このように連結リストを分割していくと、最後は空リストになります。ここが再帰の停止条件になります。あとは分割した連結リストを結合すればいいわけです。
●プログラムの作成
最初にセルを定義します。次のリストを見てください。
リスト : セルの定義
typedef struct cell {
double item;
struct cell *next;
} Cell;
// セルの生成
Cell *make_cell(double x, Cell *next)
{
Cell *cp = malloc(sizeof(Cell));
if (cp != NULL) {
cp->item = x;
cp->next = next;
}
return cp;
}
構造体 Cell のメンバ変数 item が格納する要素で、今回は浮動小数点数 (double) としました。メンバ変数 next が次のセルへのポインタです。新しいセルは関数 make_cell で生成します。
クイックソートのプログラムは次のようになります。
リスト : クイックソート
// リストの分割
void partition(Cell *xs, Cell **small, Cell **big)
{
double pivot = xs->item;
xs = xs->next;
while (xs != NULL) {
Cell *ys = xs->next;
if (xs->item < pivot) {
xs->next = *small;
*small = xs;
} else {
xs->next = *big;
*big = xs;
}
xs = ys;
}
}
// リストの連結
Cell *nconc(Cell *xs, Cell *ys)
{
Cell *cp = xs;
if (cp == NULL) return ys;
// 末尾のセル
while (cp->next != NULL) cp = cp->next;
cp->next = ys;
return xs;
}
// クイックソート
Cell *quick_sort(Cell *top)
{
if (top == NULL || top->next == NULL) return top;
Cell *small = NULL;
Cell *big = NULL;
partition(top, &small, &big);
small = quick_sort(small);
big = quick_sort(big);
top->next = big;
return nconc(small, top);
}
関数 quick_sort の引数 top が空リスト (NULL) か、要素が一つしかない (too->next == NULL) の場合は、top をそのまま返します。これが再帰呼び出しの停止条件になります。リストの分割は関数 partition で行います。枢軸未満のデータはリスト small に、枢軸以上のデータはリスト big に格納します。リストを分割したら、それぞれのリストを quick_sort でソートします。それから、枢軸の後ろに big を接続して、関数 nconc で small と top を連結します。
関数 partition は xs の先頭要素を枢軸とし、xs->next からのリストを二分割します。while ループの中で、xs->next を変数 ys に退避します。そして、xs->item が枢軸 pivot よりも小さい場合、*small の先頭にセル xs を追加します。これは xs->next に *small をセットして、*small の値を xs に更新するだけです。ここで xs->next を書き換えるので、あらかじめ値を ys に退避しています。要素が枢軸以上であれば、同様に xs を *big に追加します。ループの最後で、xs を ys に更新します。これで、次のセルに進むことができます。
関数 nconc は引数 xs と ys を連結します。xs が NULL の場合は ys をそのまま返します。次に、xs を変数 cp にセットして、while ループで末尾のセルを求めます。あとは、末尾のセルの後ろ (cp->next) に ys を接続して xs を返すだけです。
●実行結果 (4)
プログラムはこれで完成です。さっそく実行してみましょう。
リスト : 簡単なテスト
int main(void)
{
double a[10] = {5,6,4,7,3,8,2,9,1,0};
Cell *cp = NULL;
for (int i = 0; i < 10; i++) {
cp = make_cell(a[i], cp);
}
print_cell(cp);
cp = quick_sort(cp);
print_cell(cp);
for (int i = 1000000; i <= 8000000; i *= 2) {
cp = make_random(i);
clock_t s = clock();
cp = quick_sort(cp);
printf("%d : %.3f\n", i, (double)(clock() - s) / CLOCKS_PER_SEC);
check(cp);
}
return 0;
}
$ clang -O2 listsort.c $ ./a.out 0 1 9 2 8 3 7 4 6 5 0 1 2 3 4 5 6 7 8 9 1000000 : 0.967 2000000 : 2.390 4000000 : 5.613 8000000 : 15.113
クイックソートは高速なアルゴリズムですが、枢軸の選び方によっては遅いソートと同じになってしまいます。今回のように、リストの先頭要素を枢軸として選ぶ場合、リストの要素が昇順または降順に並んでいると最悪の結果になります。このため、クイックソートをプログラムする場合、枢軸の選び方を工夫するのが一般的です。
ただし、要素を数個選んで中間の値を枢軸とする方法は、連結リストに不向きであることに注意してください。たとえば、要素が 1000 個ある場合、配列であれば 0, 500, 999 番目の要素を取り出すのは簡単ですが、連結リストでは要素数が多くなるほど、後ろの要素を取り出すのに時間がかかるようになります。先頭から 3 つの要素を取り出して枢軸を選んだとしても、降順または昇順に並んだデータには効果が無いのは明らかです。クイックソートは配列に向いているソートアルゴリズムといえます。
●リストのマージ
次は、クイックソートと同様に高速なアルゴリズムであるマージソートを取り上げます。マージソートの場合、連結リストを直接書き換えながらソートすることができます。さっそくプログラムを示しましょう。次のリストを見てください。
リスト : 連結リストのマージソート
// リストのマージ
Cell *merge_list(Cell *xs, Cell *ys)
{
Cell head;
Cell *cp = &head;
while (xs != NULL && ys != NULL) {
if (xs->item <= ys->item) {
cp->next = xs;
cp = xs;
xs = xs->next;
} else {
cp->next = ys;
cp = ys;
ys = ys->next;
}
}
if (xs != NULL)
cp->next = xs;
else
cp->next = ys;
return head.next;
}
関数 merge_list が連結リストをマージ (併合) する関数で、ソート済みの連結リスト xs と ys を一つの連結リストにまとめます。この関数は連結リストを破壊的に修正してマージします。最初に連結リストのヘッダ head を用意します。このあとに、連結リストをつないでいきます。変数 cp は最後尾のセルを示します。
マージ処理はとても簡単です。while ループで xs と ys にデータがある間、2 つのデータ xs->item, y->item を比較し、小さいほうのセルを cp の後ろ (cp->next) につなげます。そして、cp の値をつなげたセルに更新して、次のセルへ進めます。while ループが終了して、xs に連結リストが残っていれば、それを cp の後ろにつなげます。xs が空リストであれば ys に残っている連結リストをつなげます。最後に、return でマージしたリスト head.next を返します。
●マージソート
リスト : 連結リストのマージソート
Cell *merge_sort(Cell *cp, int n)
{
if (n == 1) {
cp->next = NULL;
return cp;
} else {
int m = n / 2;
Cell *xs = cp;
for (int i = 0; i < m; i++) xs = xs->next;
return merge_list(merge_sort(cp, m), merge_sort(xs, n - m));
}
}
マージソートは関数 merge_sort で行います。cp がソートする連結リスト、n が連結リストの長さを表します。merge_sort は連結リストを分割する処理で、新しい連結リストを作らないことに注意してください。次の図を見てください。
merge_sort はソートする連結リストの範囲を開始位置と長さで表しています。上図の連結リストを二分割する場合、前半部分は x と n / 2 で表し、後半部分を y と (n - n / 2) で表します。y は連結リストを n / 2 回たどれば求めることができます。
n が 1 になったら x->next を NULL に書き換えます。これが再帰の停止条件で、要素数が一つの連結リスト、つまりソート済みの連結リストを返すことになります。n が 1 よりも大きい場合は、連結リストを二分割して merge_sort を再帰呼び出しし、その結果を merge_list でマージすればいいわけです。
●実行結果 (5)
それでは実行結果を示します。
$ clang -O2 listsort.c $ ./a.out 0 1 9 2 8 3 7 4 6 5 0 1 2 3 4 5 6 7 8 9 1000000 : 0.368 2000000 : 0.900 4000000 : 2.160 8000000 : 5.065
クイックソートよりもマージソートのほうが速くなりました。連結リストのソートはクイックソートよりもマージソートのほうが適していることがわかります。
なお、これらの結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
●プログラムリスト１
リスト : ヒープソートとマージソート (sort1.c)
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// 昇順
void make_sequence(double buff[], int size)
{
for (int i = 0; i < size; i++) buff[i] = i;
}
// 降順
void make_reverse(double buff[], int size)
{
for (int i = 0, j = size - 1; i < size; i++, j--)
buff[i] = j;
}
// 山型
void make_yama(double buff[], int size)
{
int j = 0;
for (int i = 0; i < size / 2; i++, j += 2)
buff[i] = j;
j--;
for (int i = size / 2; i < size; i++, j -= 2)
buff[i] = j;
}
void shuffle(double *buff, int size)
{
for (int i = size - 1; i > 0; i--) {
int j = rand() % (i + 1);
double tmp = buff[i];
buff[i] = buff[j];
buff[j] = tmp;
}
}
#define N 8000000
double buff[N];
double work[N];
bool check(int size)
{
for (int i = 1; i < size; i++) {
if (buff[i -1] > buff[i]) {
printf("sort error\n");
return false;
}
}
return true;
}
void test(void (*func)(double *, int))
{
printf(" 個数 : 乱数 : 昇順 : 逆順 : 山型 \n");
printf("-------+-------+-------+-------+-------\n");
for (int i = 1000000; i <= N; i *= 2) {
clock_t s;
printf("%6d : ", i);
make_sequence(buff, i);
shuffle(buff, i);
s = clock();
(*func)(buff, i);
printf("%.3f : ", (double)(clock() - s) / CLOCKS_PER_SEC);
check(i);
make_sequence(buff, i);
s = clock();
(*func)(buff, i);
printf("%.3f : ", (double)(clock() - s) / CLOCKS_PER_SEC);
check(i);
make_reverse(buff, i);
s = clock();
(*func)(buff, i);
printf("%.3f : ", (double)(clock() - s) / CLOCKS_PER_SEC);
check(i);
make_yama(buff, i);
s = clock();
(*func)(buff, i);
printf("%.3f\n", (double)(clock() - s) / CLOCKS_PER_SEC);
//printf("------\n");
check(i);
}
}
// ヒープソート
void heap_sort(double *buff, int size)
{
for (int i = size / 2 - 1; i >= 0; i--) {
int c, n = i;
double x = buff[n];
while ((c = 2 * n + 1) < size) {
if (c + 1 < size && buff[c] < buff[c + 1]) c++;
if (x >= buff[c]) break;
buff[n] = buff[c];
n = c;
}
buff[n] = x;
}
for (int i = size - 1; i >= 0; i--) {
int c, n = 0;
double x = buff[i];
buff[i] = buff[0];
while ((c = 2 * n + 1) < i) {
if (c + 1 < i && buff[c] < buff[c + 1]) c++;
if (x >= buff[c]) break;
buff[n] = buff[c];
n = c;
}
buff[n] = x;
}
}
// 挿入ソート
void insert_sort(double *buff, int low, int high)
{
for (int i = low + 1; i <= high; i++) {
int j;
double temp = buff[i];
for (j = i - 1; j >= low && temp < buff[j]; j--) {
buff[j + 1] = buff[j];
}
buff[j + 1] = temp;
}
}
// マージソート
#define LIMIT 32
void merge_sort_sub(double *buff, int low, int high)
{
if (high - low <= LIMIT) {
insert_sort(buff, low, high);
} else {
int mid = low + (high - low) / 2;
merge_sort_sub(buff, low, mid);
merge_sort_sub(buff, mid + 1, high);
int p = 0;
int i = low;
while (i <= mid) work[p++] = buff[i++];
i = mid + 1;
int j = 0;
int k = low;
while (i <= high && j < p) {
if (work[j] <= buff[i]) {
buff[k++] = work[j++];
} else {
buff[k++] = buff[i++];
}
}
while (j < p) buff[k++] = work[j++];
}
}
void merge_sort(double *buff, int size)
{
merge_sort_sub(buff, 0, size - 1);
}
// 改良版
void msort(double *a, double *b, int low, int high)
{
if (high - low <= LIMIT) {
insert_sort(b, low, high);
} else {
int mid = low + (high - low) / 2;
msort(b, a, low, mid);
msort(b, a, mid + 1, high);
int i = low;
int j = mid + 1;
int k = low;
while (i <= mid && j <= high) {
if (a[i] <= a[j])
b[k++] = a[i++];
else
b[k++] = a[j++];
}
while (i <= mid) b[k++] = a[i++];
while (j <= high) b[k++] = a[j++];
}
}
void merge_sort1(double *buff, int size)
{
for (int i = 0; i < size; i++) work[i] = buff[i];
msort(work, buff, 0, size - 1);
}
int main()
{
test(&heap_sort);
test(&merge_sort);
test(&merge_sort1);
return 0;
}
●プログラムリスト２
リスト : 連結リストのソート (listsort.c)
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
// セル
typedef struct cell {
double item;
struct cell *next;
} Cell;
Cell *make_cell(double x, Cell *next)
{
Cell *cp = malloc(sizeof(Cell));
if (cp != NULL) {
cp->item = x;
cp->next = next;
}
return cp;
}
// 乱数データの生成
Cell *make_random(int n)
{
Cell *cp = NULL;
while (n-- > 0)
cp = make_cell(rand(), cp);
return cp;
}
// クイックソート
Cell *quick_sort(Cell *top)
{
if (top == NULL || top->next == NULL) return top;
Cell *big = NULL;
Cell *small = NULL;
Cell *xs = top->next;
while (xs != NULL) {
Cell *ys = xs->next;
if (xs->item < top->item) {
xs->next = small;
small = xs;
} else {
xs->next = big;
big = xs;
}
xs = ys;
}
big = quick_sort(big);
small = quick_sort(small);
if (small == NULL) {
top->next = big;
return top;
} else {
for (xs = small; xs->next != NULL; xs = xs->next);
xs->next = top;
top->next = big;
return small;
}
}
void print_cell(Cell *cp)
{
for (; cp != NULL; cp = cp->next)
printf("%.0f ", cp->item);
printf("\n");
}
bool check(Cell *cp)
{
for ( ; cp->next != NULL; cp = cp->next) {
if (cp->item > cp->next->item) {
fprintf(stderr, "sort error\n");
return false;
}
}
return true;
}
// リストのマージ
Cell *merge_list(Cell *xs, Cell *ys)
{
Cell head;
Cell *cp = &head;
while (xs != NULL && ys != NULL) {
if (xs->item <= ys->item) {
cp->next = xs;
cp = xs;
xs = xs->next;
} else {
cp->next = ys;
cp = ys;
ys = ys->next;
}
}
if (xs != NULL)
cp->next = xs;
else if (ys != NULL)
cp->next = ys;
return head.next;
}
// マージソート
Cell *merge_sort(Cell *cp, int n)
{
if (n == 1) {
cp->next = NULL;
return cp;
} else {
int m = n / 2;
Cell *xs = cp;
for (int i = 0; i < m; i++) xs = xs->next;
return merge_list(merge_sort(cp, m), merge_sort(xs, n - m));
}
}
int main(void)
{
double a[10] = {5,6,4,7,3,8,2,9,1,0};
Cell *cp = NULL;
for (int i = 0; i < 10; i++) {
cp = make_cell(a[i], cp);
}
print_cell(cp);
// cp = quick_sort(cp);
cp = merge_sort(cp, 10);
print_cell(cp);
for (int i = 1000000; i <= 8000000; i *= 2) {
cp = make_random(i);
clock_t s = clock();
// cp = quick_sort(cp);
cp = merge_sort(cp, i);
printf("%d : %.3f\n", i, (double)(clock() - s) / CLOCKS_PER_SEC);
check(cp);
}
return 0;
}
改訂 2023 年 4 月 2 日