RSS
この章の概要です。
名前に「マージ」が含まれているように、マージソートはマージ処理を利用してソートを行おうというアルゴリズムです。マージについては、【その他】第４章で説明しているので、そちらを参照してください。
マージソートが特徴的なのは、連結リストのソートに適していることです。これはマージを利用しているからこその特徴です。配列をソートすることも可能ですが、メモリ使用量の面で問題があります（あとで実装を見るときに説明します）。
前章のクイックソートと同様に、マージソートも再帰の考え方が重要です。また、再帰処理で実現できる一方で、再帰を使わずに実装する手法も存在しています。
再帰版マージソートはトップダウン方式と呼ばれることもあります。対して、非再帰版のマージソートはボトムアップ方式と呼ばれることもあります。ここではまずトップダウン方式で解説します。ボトムアップ方式のマージソートについては、後で取り上げます。
トップダウン方式のマージソートでは、まず元のデータ列を２つに分割することから始めます。分割されたら、その片方をさらに分割します。ここが再帰的に繰り返されます。要素が２つになった部分を分割して、１個１個に分かれたら、その２つをマージによって結合します。このマージ処理を、昇順（あるいは降順）になるように行えば、マージ結果がソート済みな状態になります。
トップダウン方式のマージソートの流れを具体的にみていきます。元のデータ列は、{7, 2, 6, 4, 3, 8, 5, 1} とします。
まず、データ列を２つに分割します。これは単純に、真ん中から２つに分ければいいだけです。結果、
{7, 2, 6, 4} {3, 8, 5, 1}このように分かれます。分割前のデータ数が奇数だときれいに分けられませんが、気にする必要はありません。3個と 4個のような感じにしてしまって問題ありません。
この分割操作を再帰的に繰り返します。まず左側だけ見ていきます。
{7, 2} {6, 4} {3, 8, 5, 1}{7} {2} {6, 4} {3, 8, 5, 1}要素数が１つになったら、その部分に対する再帰処理を終えて、マージ作業を行います。{7} と {2} を昇順になるようにマージします。
{2, 7} {6, 4} {3, 8, 5, 1}再帰を１つ上へ戻して、今度は {6, 4} の分割です。
{2, 7} {6} {4} {3, 8, 5, 1}{6} と {4} をマージします。
{2, 7} {4, 6} {3, 8, 5, 1}再帰を１つ上へ戻します。ここで、{2, 7} {4, 6} をマージします。
{2, 4, 6, 7} {3, 8, 5, 1}再帰を１つ上へ戻します。左半分はこれで終わったので、右半分の処理に移ります。過程はまったく同じなので、データ列の変化だけを挙げていきます。
{2, 4, 6, 7} {3, 8} {5, 1}{2, 4, 6, 7} {3} {8} {5} {1}{2, 4, 6, 7} {3, 8} {1, 5}{2, 4, 6, 7} {1, 3, 5, 8}再帰が再び先頭に戻ってきました。あとは、左半分と右半分をマージして完了です。
{1, 2, 3, 4, 5, 6, 7, 8}肝心のマージのやり方については、【その他】第４章で取り上げています。具体的には、２つのデータ列の先頭要素を比較して、小さい方（降順にソートする場合は大きい方）を取り出して、結果を受け取る配列へ格納します。データ列が空になったら、他方のデータ列の残りの要素すべてを取り出して、結果の配列へ移します。
この章ではこの後、まずはこれまでの章と同様、配列に対するマージソートを試します。その後で、連結リストをマージソートを使ってソートする方法を見ていきます。
では、実際にマージソートを行うプログラムを確認しましょう。まずは、配列をソートしてみます。
#include <stdio.h>
#include <stdlib.h>
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
static void merge_sort(int* array, size_t size);
static void merge_sort_rec(int* array, size_t begin, size_t end, int* work);
static void print_array(const int* array, size_t size);
int main(void)
{
int array[] = {7, 2, 9, 6, 4, 3, 8, 5, 1};
print_array( array, SIZE_OF_ARRAY(array) );
merge_sort( array, SIZE_OF_ARRAY(array) );
print_array( array, SIZE_OF_ARRAY(array) );
return 0;
}
/*
マージソート (昇順)
*/
void merge_sort(int* array, size_t size)
{
// 作業用領域を確保
int* work = malloc( sizeof(int) * size );
// 配列全体を対象にする
merge_sort_rec( array, 0, size - 1, work );
free( work );
}
/*
マージソート (再帰部分、昇順)
*/
void merge_sort_rec(int* array, size_t begin, size_t end, int* work)
{
// 要素が１つしかなければ終了
if( begin >= end ){
return;
}
// ２つのデータ列に分割して、それぞれを再帰的に処理
size_t mid = (begin + end) / 2;
merge_sort_rec( array, begin, mid, work );
merge_sort_rec( array, mid + 1, end, work );
// マージ
{
// 前半の要素を作業用配列へ
for( size_t i = begin; i <= mid; ++i){
work[i] = array[i];
}
// 後半の要素を逆順に作業用配列へ
for( size_t i = mid + 1, j = end; i <= end; ++i, --j){
work[i] = array[j];
}
// 作業用配列の両端から取り出した要素をマージ
{
size_t i = begin;
size_t j = end;
for( size_t k = begin; k <= end; ++k) {
// 昇順にソートするので、小さい方の要素を結果の配列へ移す。
// == の場合に、前半の側を優先すると安定なソートになる
if( work[i] <= work[j] ){
array[k] = work[i];
++i;
}
else{
array[k] = work[j];
--j;
}
}
}
}
}
/*
配列の要素を出力
*/
void print_array(const int* array, size_t size)
{
for( size_t i = 0; i < size; ++i ){
printf( "%d ", array[i] );
}
printf( "\n" );
}実行結果：
7 2 9 6 4 3 8 5 1
1 2 3 4 5 6 7 8 9merge_sort関数が入口になっており、ここで作業用領域を確保しています。
作業用領域が必要になる理由は、マージする２つのデータ列と、マージ結果を格納する配列がそれぞれ必要となるためです。「元の配列 ＝ 結果を格納する配列」ですから、マージ前の２つのデータ列を置く場所を作らないと、マージ作業中に、結果を格納する配列を破壊してしまいます。
作業用領域には、ソート対象の配列の要素数以上が必要です。ソート対象の配列の要素数が事前に分からないので、動的メモリ割り当てによって確保しています。
マージなので２つの配列を追加で用意するのでもいいのですが、ここでは１つの作業用領域にまとめることにします。作業用領域の前半部分が１つのデータ列、後半部分を１つのデータ列とみなします。
次に merge_sort_rec関数です。
この関数は再帰する関数なので、どこかで再帰を終わらせる必要があります。それを最初の if文のとこで行っています。この章の冒頭で説明した手順のとおり、分割を繰り返して、要素が１つになるまで続けるので、対象範囲（引数 begin と end で表される）に含まれる要素数が１個になっていたら、return させています。
要素数が２個以上あるのなら、分割処理を行います。分割処理といっても、begin と end の値を変更して対象範囲を縮め、merge_sort_rec関数を再帰呼び出しするだけです。再帰呼び出しが繰り返されることによって、begin と end はどんどん縮まっていきます。
merge_sort_rec関数の再帰呼び出しは、対象範囲内の要素数が１個になったら終わり、そのときに限って、その先にあるマージ処理へ進みます。
マージのアルゴリズムについては、【その他】第４章を参照してください。
マージ処理では、まず２つの範囲を作業用配列へコピーしています。このとき、前半部分は作業用配列の前半へそのまま素直にコピーしますが、後半部分は逆順になるようにコピーします。こうすることで、前半部分のうちの最小の値を持った要素が作業用配列の先頭に来て、後半部分のうちの最小の値を持った要素が作業用配列の末尾に来ます。
マージの過程では、作業用配列の先頭と末尾の要素を調べ、小さい方（降順にソートするなら大きい方）を元の配列へ格納するようにすれば良いということになります。値が同じときには、先頭の要素を優先すれば、安定なソートになります。
前の項では、配列を使ったマージソートの実装を確認しました。しかし、マージソートは、配列のソートにはあまり向いていません。なぜなら、大きな作業用配列を用意しなければならないという欠点があるからです。
一方で、マージソートは、連結リスト（【データ構造】第３章参照）のソートには適しています。連結リストの場合、作業用領域が必要なく、ポインタの付け替えだけで済ませられるからです。
配列版マージソートのサンプルプログラムを、連結リストに置き換えると、次のようになります。連結リストの実装には、コードライブラリの ppps_int_slist を使用しています。
#include <stdio.h>
#include "ppps_int_slist.h"
static void merge_sort(PPPSIntSlist list);
static PPPSIntSlist merge_sort_rec(PPPSIntSlist list);
static PPPSIntSlist merge(PPPSIntSlist a, PPPSIntSlist b);
int main(void)
{
PPPSIntSlist list = ppps_int_slist_create();
ppps_int_slist_add_tail( list, 7 );
ppps_int_slist_add_tail( list, 2 );
ppps_int_slist_add_tail( list, 9 );
ppps_int_slist_add_tail( list, 6 );
ppps_int_slist_add_tail( list, 4 );
ppps_int_slist_add_tail( list, 3 );
ppps_int_slist_add_tail( list, 8 );
ppps_int_slist_add_tail( list, 5 );
ppps_int_slist_add_tail( list, 1 );
puts( "ソート前" );
ppps_int_slist_print( list );
merge_sort( list );
puts( "ソート後" );
ppps_int_slist_print( list );
ppps_int_slist_delete( list );
return 0;
}
/*
マージソート (昇順)
*/
void merge_sort(PPPSIntSlist list)
{
if( list == NULL ){
return;
}
// リスト全体を対象にする
PPPSIntSlist result = merge_sort_rec( list->next );
list->next = result;
}
/*
マージソート (再帰部分、昇順)
*/
PPPSIntSlist merge_sort_rec(PPPSIntSlist list)
{
// 要素が１つしかなければ終了
if( list == NULL || list->next == NULL ){
return list;
}
// ２つのリストに分割するため、リストの中心を探す。
// （最終的に a が、リストの中心を指している）
PPPSIntSlist a = list;
PPPSIntSlist b = list->next;
if( b != NULL ){
b = b->next;
}
while( b != NULL ){
a = a->next;
b = b->next;
if( b != NULL ){
b = b->next;
}
}
// リストを前半と後半に分離。
//
// 前半の先頭は list が指しているが、その末尾を作る必要がある。
// 前半の末尾を a にして、a->next がヌルポインタになるようにしている。
// 後半の末尾は、（ヌルポインタにする前の）a->next から始まるようにする。
PPPSIntSlist x = a->next;
a->next = NULL;
// 前半と後半のリストをマージする
return merge( merge_sort_rec(list), merge_sort_rec(x) );
}
/*
マージ
*/
PPPSIntSlist merge(PPPSIntSlist a, PPPSIntSlist b)
{
struct PPPSIntSlist_tag result;
PPPSIntSlist x = &result;
// リストをマージ
while( a != NULL && b != NULL ){
// 昇順にソートするので、小さい方の要素を優先する。
// == の場合に、前半の側を優先すると安定なソートになる
if( a->value <= b->value ){
x->next = a;
x = x->next;
a = a->next;
}
else{
x->next = b;
x = x->next;
b = b->next;
}
}
// 残っている要素を、末尾へ連結
if( a == NULL ){
x->next = b;
}
else{
x->next = a;
}
return result.next;
}実行結果：
ソート前
7
2
9
6
4
3
8
5
1
ソート後
1
2
3
4
5
6
7
8
9配列版の実装とは違って、merge_sort関数内で作業用の領域を確保していません。
merge_sort_rec関数でしていることは、基本的に配列版と同じです。対象のデータ列を分割する際、連結リストの中心で分けるようにしています。
単方向線形リストで、中心の要素を探すためには、先頭を指すポインタを２つ用意し、一方は１つずつ、他方は２つずつ先へ先へと進めていきます。２つずつ進めている方が末尾に行き着いたとき、１つずつ進めていた方のポインタがちょうど中心の要素を指しています。
マージ処理は、merge関数で行っています。連結リストの操作に慣れていないと、複雑で難しく見えると思いますが、していることは配列版と同じです。
ここまでに取り上げたマージソートはトップダウン方式でした。分割を繰り返して、要素を１つ１つのばらばらな状態にしていく過程が、木構造（【データ構造】第７章）を上から下へ降りていくように見えることに由来します。
一方で、ボトムアップ方式と呼ばれる実装方法があります。こちらは、ソート前のデータ列が、すでに１要素ずつに分割済みであるように仮定して、うまく結合していくことを考える方式です。分割済みな状態から開始して、ソート済みのデータ列を作り上げていく過程を、木構造を下から上へ上がっていくように見立てて、ボトムアップ方式と呼びます。
別の言い方をすると、トップダウン方式は再帰処理を活用しますが、ボトムアップ方式は再帰しません。第６章で取り上げたクイックソートに、再帰版と非再帰版があったことと同じです。
それでは、ボトムアップ方式でのマージソートの動作をみていきましょう。元のデータ列は、{7, 2, 6, 4, 3, 8, 5, 1} とします。
まず、ソート前のデータ列の要素を、それぞれ長さ１の列とみなします。つまり、次のように考えるということです。
{7} {2} {6} {4} {3} {8} {5} {1}次に、隣り合う要素２つずつをマージします。このとき、昇順（あるいは降順）になるようにマージします。すると、次のようになります。
{2, 7} {4, 6} {3, 8} {5, 1}同じことを繰り返します。
{2, 4, 6, 7} {1, 3, 5, 8}{1, 2, 3, 4, 5, 6, 7, 8}これでソート完了となります。
それでは、ボトムアップ方式のマージソートで、配列をソートするプログラムを見てみましょう。
#include <stdio.h>
#include <stdlib.h>
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
#define MIN(a, b) (a < b) ? (a) : (b)
static void merge_sort_bottomup(int* array, size_t begin, size_t end);
static void merge(int* array, size_t begin, size_t end, size_t mid, int* work);
static void print_array(const int* array, size_t size);
int main(void)
{
int array[] = {7, 2, 9, 6, 4, 3, 8, 5, 1};
print_array( array, SIZE_OF_ARRAY(array) );
merge_sort_bottomup( array, 0, SIZE_OF_ARRAY(array) );
print_array( array, SIZE_OF_ARRAY(array) );
return 0;
}
/*
マージソート (昇順)
*/
void merge_sort_bottomup(int* array, size_t begin, size_t end)
{
// 作業用領域を確保
int* work = malloc( sizeof(int) * (end - begin + 1) );
for( size_t i = 1; i <= end - begin; i *= 2 ){
for( size_t j = begin; j <= end - i; j += i * 2 ){
merge( array, j, MIN(j + i * 2 - 1, end), j + i - 1, work);
}
}
free( work );
}
/*
マージ
*/
void merge(int* array, size_t begin, size_t end, size_t mid, int* work)
{
// 前半の要素を作業用配列へ
for( size_t i = begin; i <= mid; ++i){
work[i] = array[i];
}
// 後半の要素を逆順に作業用配列へ
for( size_t i = mid + 1, j = end; i <= end; ++i, --j){
work[i] = array[j];
}
// 作業用配列の両端から取り出した要素をマージ
{
size_t i = begin;
size_t j = end;
for( size_t k = begin; k <= end; ++k) {
// 昇順にソートするので、小さい方の要素を結果の配列へ移す。
// == の場合に、前半の側を優先すると安定なソートになる
if( work[i] <= work[j] ){
array[k] = work[i];
++i;
}
else{
array[k] = work[j];
--j;
}
}
}
}
/*
配列の要素を出力
*/
void print_array(const int* array, size_t size)
{
for( size_t i = 0; i < size; ++i ){
printf( "%d ", array[i] );
}
printf( "\n" );
}実行結果：
7 2 9 6 4 3 8 5 1
1 2 3 4 5 6 7 8 9merge_sort_bottomup関数は、空白行を入れてもわずか 7行で、再帰もしていないので、非常にすっきりして見えますが、ぱっと見では分かりづらい処理になっています。
作業用領域は、トップダウン方式のときと同じです。
まず、外側の for文では、マージ範囲の大きさを表す変数 i を制御しています。最初は i = 1 で始まり、１周ごとに 2倍されていきます。これは、さきほどの手順の説明のように、マージを行うたびに、対象範囲が大きくなっていくためです。
内側の for文では、マージ範囲の左端の位置を表す変数 j を制御しています。最初は begin から始まっていますが、これはソート対象範囲の先頭です。１周ごとに、変数 i の 2倍だけ増加します。変数 i がマージ範囲の大きさですから、次のマージ範囲の先頭まで進めているということです。
２つの for文の中では、merge関数を呼び出してマージ処理を実行しています。
終端位置の指定で、MINマクロを使って少し複雑なことをしていますが、これはソート範囲の終端を超えてしまわないようにするための処置です。変数 i を、配列の大きさを気にせずに増加させているので、MINマクロによる制御を加えないと範囲外アクセスが起こる可能性があります。
さて、マージソートなので連結リストをソートする方法も見ていきたいところですが、ボトムアップ方式のマージソートで連結リストをソートするのは、少し難しさがあります。
この話題は、練習問題① で取り上げることにします。
マージソートの性能を確認してみます。
ここでは、トップダウン方式のマージソート、ボトムダウン方式のマージソート、そして比較のために、自力でスタックを実装するタイプのクイックソート（第６章 練習問題②）で実験します。
#include <stdio.h>
#include <stdlib.h>
#include "ppp_perform.h"
#define ARRAY_SIZE 10000
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
#define MIN(a, b) (a < b) ? (a) : (b)
#define SWAP(type,a,b) { type work = a; a = b; b = work; }
static void init_array(int* array, size_t size);
static void merge_sort(int* array, size_t size);
static void merge_sort_rec(int* array, size_t begin, size_t end, int* work);
static void merge_sort_bottomup(int* array, size_t begin, size_t end);
static void merge(int* array, size_t begin, size_t end, size_t mid, int* work);
static void quick_sort(int* array, size_t size);
static void quick_sort_body(int* array, int begin, int end);
static inline int select_pivot(const int* array, int begin, int end);
int main(void)
{
static int array[ARRAY_SIZE];
init_array( array, SIZE_OF_ARRAY(array) );
PPP_CHECK_PERFORM_BEGIN(1);
merge_sort( array, SIZE_OF_ARRAY(array) );
PPP_CHECK_PERFORM_END("merge_sort");
init_array( array, SIZE_OF_ARRAY(array) );
PPP_CHECK_PERFORM_BEGIN(1);
merge_sort_bottomup( array, 0, SIZE_OF_ARRAY(array) );
PPP_CHECK_PERFORM_END("merge_sort_bottomup");
init_array( array, SIZE_OF_ARRAY(array) );
PPP_CHECK_PERFORM_BEGIN(1);
quick_sort( array, SIZE_OF_ARRAY(array) );
PPP_CHECK_PERFORM_END("quick_sort");
return 0;
}
/*
配列を初期化
*/
void init_array(int* array, size_t size)
{
srand(0);
for( size_t i = 0; i < size; ++i ){
array[i] = rand() % size;
}
}
/*
マージソート (昇順)
*/
void merge_sort(int* array, size_t size)
{
// 作業用領域を確保
int* work = malloc( sizeof(int) * size );
// 配列全体を対象にする
merge_sort_rec( array, 0, size - 1, work );
free( work );
}
/*
マージソート (再帰部分、昇順)
*/
void merge_sort_rec(int* array, size_t begin, size_t end, int* work)
{
// 要素が１つしかなければ終了
if( begin >= end ){
return;
}
// ２つのデータ列に分割して、それぞれを再帰的に処理
size_t mid = (begin + end) / 2;
merge_sort_rec( array, begin, mid, work );
merge_sort_rec( array, mid + 1, end, work );
// マージ
{
// 前半の要素を作業用配列へ
for( size_t i = begin; i <= mid; ++i){
work[i] = array[i];
}
// 後半の要素を逆順に作業用配列へ
for( size_t i = mid + 1, j = end; i <= end; ++i, --j){
work[i] = array[j];
}
// 作業用配列の両端から取り出した要素をマージ
{
size_t i = begin;
size_t j = end;
for( size_t k = begin; k <= end; ++k) {
// 昇順にソートするので、小さい方の要素を結果の配列へ移す。
// == の場合に、前半の側を優先すると安定なソートになる
if( work[i] <= work[j] ){
array[k] = work[i];
++i;
}
else{
array[k] = work[j];
--j;
}
}
}
}
}
/*
マージソート (昇順)
*/
void merge_sort_bottomup(int* array, size_t begin, size_t end)
{
// 作業用領域を確保
int* work = malloc( sizeof(int) * (end - begin + 1) );
for( size_t i = 1; i <= end - begin; i *= 2 ){
for( size_t j = begin; j <= end - i; j += i * 2 ){
merge( array, j, MIN(j + i * 2 - 1, end), j + i - 1, work);
}
}
free( work );
}
/*
マージ
*/
void merge(int* array, size_t begin, size_t end, size_t mid, int* work)
{
// 前半の要素を作業用配列へ
for( size_t i = begin; i <= mid; ++i){
work[i] = array[i];
}
// 後半の要素を逆順に作業用配列へ
for( size_t i = mid + 1, j = end; i <= end; ++i, --j){
work[i] = array[j];
}
// 作業用配列の両端から取り出した要素をマージ
{
size_t i = begin;
size_t j = end;
for( size_t k = begin; k <= end; ++k) {
// 昇順にソートするので、小さい方の要素を結果の配列へ移す。
// == の場合に、前半の側を優先すると安定なソートになる
if( work[i] <= work[j] ){
array[k] = work[i];
++i;
}
else{
array[k] = work[j];
--j;
}
}
}
}
/*
クイックソート (昇順)
*/
void quick_sort(int* array, size_t size)
{
// 配列全体を対象にする
quick_sort_body( array, 0, (int)(size - 1) );
}
/*
クイックソート (本体、昇順)
*/
void quick_sort_body(int* array, int begin, int end)
{
int stack[64];
int sp = 0;
stack[sp++] = begin;
stack[sp++] = end;
// スタックが空になるまで繰り返す
while( sp > 0 ){
// 範囲の情報をスタックから取り出す
// スタックは後入れ先出しの構造なので、
// 積んだときとは逆の順序で取り出さなければならない点に注意
end = stack[--sp];
begin = stack[--sp];
while( 1 ){
// 範囲が逆転していたら何もすることはない
if( begin >= end ){
break;
}
int pivot = select_pivot( array, begin, end );
int i = begin;
int j = end;
while( 1 ){
while( array[i] < pivot ){ ++i; } // 基準値以上の値が見つかるまで右方向へ進めていく
while( array[j] > pivot ){ --j; } // 基準値以下の値が見つかるまで左方向へ進めていく
if( i >= j ){ break; } // 左右から進めてきたiとjがぶつかったらループを終える
// 基準値位置よりも左側にあり、基準値よりも大きい値 (array[i]) と、
// 基準値位置よりも右側にあり、基準値よりも小さい値 (array[j]) の
// 位置関係を交換する。
SWAP( int, array[i], array[j] );
// 次回に備えて、注目点をずらす
i++;
j--;
}
// 左右の配列のうち、要素数が少ない方を先に処理する。
// (i - begin) は左側の要素数、
// (end - j) は右側の要素数を計算している。
//
// 後で処理する側の範囲情報をスタックへ積んでおく。
if( i - begin < end - j ){
// 右側の範囲情報をスタックへ積み、
// 左側の範囲を先に処理する。
stack[sp++] = j + 1;
stack[sp++] = end;
end = i - 1;
}
else{
// 左側の範囲情報をスタックへ積み、
// 右側の範囲を先に処理する。
stack[sp++] = begin;
stack[sp++] = i - 1;
begin = j + 1;
}
}
}
}
/*
基準値を選ぶ
*/
inline int select_pivot(const int* array, int begin, int end)
{
return array[(begin + end) / 2]; // 中央の要素を基準値とする
}データ件数ごとの比較結果はこうなりました。
| データ件数 | トップダウンマージソート | ボトムアップマージソート | クイックソート |
|---|---|---|---|
| 10000個 | 0.002秒 | 0.003秒 | 0.002秒 |
| 100000個 | 0.026秒 | 0.021秒 | 0.019秒 |
| 1000000個 | 0.266秒 | 0.244秒 | 0.171秒 |
| 10000000個 | 2.956秒 | 2.528秒 | 1.773秒 |
計算量としては、マージソートは O(n log n) であり、これはクイックソートと同じです。しかし実際には、マージソートの方が処理が複雑になるため、クイックソートの性能には敵いません。
一方で、クイックソートの場合、データの並び方によっては、計算量が O(n2) まで落ち込むのに対して、マージソートはつねに O(n log n) の計算量が保証されます。マージソートの場合、分割の際に要素の値の大小関係を見ていないため、データ列がどのように並んでいても無関係に処理できるからです。
マージソートの計算量は、O(n log n) です。これはクイックソートと同じですが、実際の性能はクイックソートにはかないません。マージソートの方が、処理が複雑だからです。
クイックソートでは、最悪時に計算量が O(n2) まで落ち込むことに対し、マージソートの計算量は安定して、O(n log n) です。
このように、良い計算量が維持されることは利点といえますが、前章で説明しているとおり、クイックソートの性能悪化は軽減する手段があるので、大抵はクイックソートを使う方が高速です。
ただ、マージソートは、クイックソートと違って、安定なソートアルゴリズムであるという利点もあります。ですから、安定性が不要ならクイックソートを使い、安定でなければならないときはマージソートを使うという選択基準もあり得ます。
マージソートの性能を語る上では、メモリ使用量の性能にも触れておく必要があります。
マージソートを使って配列をソートする場合、マージの作業用に O(n) に相当する領域を用意しなければなりません。連結リストをソートする場合は、作業用領域を必要としません。このような事情があるため、実のところ、マージソートは配列のソートにはあまり向いていません。
マージソートは、連結リストや、ディスク上のデータのソートを効率的に行えるという利点もあります。他のソートアルゴリズムでもできなくはないですが、ほとんどの場合、非効率になってしまいます。
問題① ボトムアップ方式のマージソートで、連結リストをソートするプログラムを作成してください（これはそれほど簡単にはいきません。あるデータ構造を併用することがポイントです）
問題② マージソートの性能改善の手段として、ソート対象の要素数が十分小さくなったら、その部分のソートに挿入ソート（第４章）を使うという方法があります。この方法で、トップダウン方式の配列に対するマージソートを改造して、パフォーマンスを測定してください（前章の練習問題③では、クイックソートに対して、同じ方法による性能改善を取り上げています）。
要素数を意味している「サイズ」について、「要素数」に表記を改めた。
≪さらに古い更新履歴を展開する≫
Programming Place Plus のトップページへ
| はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
| X で ポスト／フォロー | LINE で送る | noteで書く |
|
RSS
|
管理者情報 | プライバシーポリシー |