トップページ – アルゴリズムとデータ構造編 – 【整列アルゴリズム】第7章
問題① ボトムアップ方式のマージソートで、連結リストをソートするプログラムを作成してください(これはそれほど簡単にはいきません。あるデータ構造を併用することがポイントです)
あるデータ構造とはキュー(【データ構造】第6章参照)です。ここでは、コードライブラリの ppps_int_queue を、連結リストを格納できるように型を修正して使っています。
#include <stdio.h>
#include "ppps_int_slist.h"
#include "queue.h"
static void merge_sort(PPPSIntSlist list);
static PPPSIntSlist merge_sort_bottomup(PPPSIntSlist list);
static PPPSIntSlist merge(PPPSIntSlist a, PPPSIntSlist b);
int main(void)
{
= ppps_int_slist_create();
PPPSIntSlist list
( 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 );
ppps_int_slist_add_tail
( "ソート前" );
puts( list );
ppps_int_slist_print
( list );
merge_sort
( "ソート後" );
puts( list );
ppps_int_slist_print
( list );
ppps_int_slist_delete
return 0;
}
/*
マージソート (昇順)
*/
void merge_sort(PPPSIntSlist list)
{
if( list == NULL ){
return;
}
// リスト全体を対象にする
= merge_sort_bottomup( list );
PPPSIntSlist result
->next = result;
list}
/*
マージソート (昇順)
*/
(PPPSIntSlist list)
PPPSIntSlist merge_sort_bottomup{
= NULL;
PPPSIntSlist result
if( list == NULL || list->next == NULL ){
return result;
}
int size = ppps_int_slist_count( list );
= queue_create( size );
Queue queue
// リストの要素をキューへ登録
= list->next;
PPPSIntSlist p while( p != NULL ){
= p->next; // next は NULL にするので先に保存しておく
PPPSIntSlist q ->next = NULL; // 独立した要素として登録するため next は NULL に
p( queue, p ); // キューへ登録
queue_enqueue= q; // 保存しておいた next に復帰
p }
// 初回の enqueue に備えて、1要素だけ取り出しておく
( queue, &result );
queue_try_dequeue
while( !queue_is_empty(queue) ){
, b;
PPPSIntSlist a
// マージ結果をキューへ戻す
// 初回だけは、while文に入る前に dequeue しておいた要素が戻される
( queue, result );
queue_enqueue
// キューから、マージ対象の2つの要素を取り出す
// これらの要素は、初回は要素数1のリストだが、2回目以降は前回までのマージ結果である
if( !queue_try_dequeue( queue, &a ) ){
= NULL;
a }
if( !queue_try_dequeue( queue, &b ) ){
= NULL;
b }
// 取り出された要素同士をマージ
= merge( a, b );
result }
( queue );
queue_delete
return result;
}
/*
マージ
*/
(PPPSIntSlist a, PPPSIntSlist b)
PPPSIntSlist merge{
struct PPPSIntSlist_tag result;
= &result;
PPPSIntSlist x
// リストをマージ
while( a != NULL && b != NULL ){
// 昇順にソートするので、小さい方の要素を優先する。
// == の場合に、前半の側を優先すると安定なソートになる
if( a->value <= b->value ){
->next = a;
x= x->next;
x = a->next;
a }
else{
->next = b;
x= x->next;
x = b->next;
b }
}
// 残っている要素を、末尾へ連結
if( a == NULL ){
->next = b;
x}
else{
->next = a;
x}
return result.next;
}
// queue.h
#ifndef QUEUE_H_INCLUDED
#define QUEUE_H_INCLUDED
#include <stdbool.h>
#include "ppps_int_slist.h"
/*
キュー型
*/
typedef struct Queue_tag* Queue;
/*
キューを作る
引数:
size: 格納できる要素数
戻り値:
作成されたキュー。
使い終わったら、queue_delete関数に渡して削除する。
*/
(size_t size);
Queue queue_create
/*
キューを削除する
引数:
queue: キュー
*/
void queue_delete(Queue queue);
/*
キューに要素を入れる
引数:
queue: キュー
value: 入れる要素
*/
void queue_enqueue(Queue queue, PPPSIntSlist value);
/*
キューから要素を取り出す
引数:
queue: キュー
戻り値:
取り出された要素
要素が空の場合の動作は未定義。
*/
(Queue queue);
PPPSIntSlist queue_dequeue
/*
キューから要素を取り出す (成否判定付き)
引数:
queue: キュー
p: 取り出された要素を受け取るアドレス。
戻り値:
要素を取り出せたら true、取り出せなかったら false を返す。
false が返された場合は、引数p が指す先には何も格納されない。
*/
bool queue_try_dequeue(Queue queue, PPPSIntSlist* p);
/*
キューが空かどうか調べる
引数:
queue: キュー
戻り値:
キューが空であれば true を返し、空でなければ false を返す。
*/
bool queue_is_empty(Queue queue);
#endif
// queue.c
#include "queue.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
static size_t get_next_index(Queue queue, size_t index);
static void* xmalloc(size_t size);
struct Queue_tag {
* data; // 要素を格納する動的配列
PPPSIntSlistsize_t size; // data の要素数
size_t front; // 先頭の要素の位置
size_t tail; // 末尾の要素の位置
};
/* キューを作る */
(size_t size)
Queue queue_create{
// front == tail を空の状態にしようとすると、配列全体を使い切った状態を作れない。
// そこで、指定された size を +1 して、1つ余分に領域を確保しておく。
+= 1;
size
struct Queue_tag* queue = xmalloc( sizeof(struct Queue_tag) );
->data = xmalloc( sizeof(PPPSIntSlist) * size );
queue->size = size;
queue->front = 0;
queue->tail = 0;
queue
return queue;
}
/* キューを削除する */
void queue_delete(Queue queue)
{
( queue->data );
free( queue );
free}
/* キューに要素を入れる */
void queue_enqueue(Queue queue, PPPSIntSlist value)
{
( get_next_index(queue, queue->tail) != queue->front );
assert
->data[queue->tail] = value;
queue
// 次に要素を入れるときに使う位置を求める
// リングバッファ構造なので、単純に +1 するだけではダメ
->tail = get_next_index( queue, queue->tail );
queue}
/* キューから要素を取り出す */
(Queue queue)
PPPSIntSlist queue_dequeue{
( !queue_is_empty(queue) );
assert
= queue->data[queue->front];
PPPSIntSlist pop_value
// 先頭から要素が1つ取り出されるので、先頭位置を更新する
// リングバッファ構造なので、単純に +1 するだけではダメ
->front = get_next_index( queue, queue->front );
queue
return pop_value;
}
/* キューから要素を取り出す (成否判定付き) */
bool queue_try_dequeue(Queue queue, PPPSIntSlist* p)
{
( p != NULL );
assert
if( queue_is_empty(queue) ){
return false;
}
*p = queue->data[queue->front];
// 先頭から要素が1つ取り出されるので、先頭位置を更新する
// リングバッファ構造なので、単純に +1 するだけではダメ
->front = get_next_index( queue, queue->front );
queue
return true;
}
/* キューが空かどうか調べる */
bool queue_is_empty(Queue queue)
{
return queue->front == queue->tail;
}
/* 1つ後ろの添字を取得する */
size_t get_next_index(Queue queue, size_t index)
{
return (index + 1) % queue->size;
}
/* エラーチェック付きの malloc関数 */
void* xmalloc(size_t size)
{
void* p = malloc( size );
if( p == NULL ){
( "メモリ割り当てに失敗しました。", stderr );
fputs( EXIT_FAILURE );
exit}
return p;
}
実行結果:
ソート前
7
2
9
6
4
3
8
5
1
ソート後
1
2
3
4
5
6
7
8
9
まず、キューを ppps_int_slist_count関数を使って作成します。
連結リスト内の要素数を数えて、その要素数を渡していますが、実際に連結リスト内の要素をたどって要素数を数えると、(要素数によっては)大幅に速度低下を招くので、実用上は注意しなければなりません。
キューを作成したら、連結リストの各要素を1要素ずつの細切れ状態にしてキューへ格納します。これは、ボトムアップ方式なので、「ソート前のデータ列の要素を、それぞれ長さ1の列とみなす」ためです。
マージ過程では、キューから要素を2つ取り出してマージし、その結果を再びキューへ戻すことを繰り返せば、ソートを実現できます。merge関数は、本編の実装のままです。
問題② マージソートの性能改善の手段として、ソート対象の要素数が十分小さくなったら、その部分のソートに挿入ソート(第4章)を使うという方法があります。この方法で、トップダウン方式の配列に対するマージソートを改造して、パフォーマンスを測定してください(前章の練習問題③では、クイックソートに対して、同じ方法による性能改善を取り上げています)。
変更されたマージソートでパフォーマンスを計測するプログラムは、次のようになります。
#include <stdio.h>
#include <stdlib.h>
#include "ppp_perform.h"
#define ARRAY_SIZE 100000
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
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 insertion_sort_ex(int* array, int begin, int end);
static void print_array(const int* array, size_t size);
int main(void)
{
static int array[ARRAY_SIZE];
( array, SIZE_OF_ARRAY(array) );
init_array(1);
PPP_CHECK_PERFORM_BEGIN( array, SIZE_OF_ARRAY(array) );
merge_sort("merge_sort");
PPP_CHECK_PERFORM_END
return 0;
}
/*
配列を初期化
*/
void init_array(int* array, size_t size)
{
(0);
srand
for( size_t i = 0; i < size; ++i ){
[i] = rand() % size;
array}
}
/*
マージソート (昇順)
*/
void merge_sort(int* array, size_t size)
{
// 作業用領域を確保
int* work = malloc( sizeof(int) * size );
// 配列全体を対象にする
( array, 0, size - 1, work );
merge_sort_rec
( work );
free}
/*
マージソート (再帰部分、昇順)
*/
void merge_sort_rec(int* array, size_t begin, size_t end, int* work)
{
static const int SMALL_SIZE = 10; // 挿入ソートに切り替える要素数
// 要素が1つしかなければ終了
if( begin >= end ){
return;
}
if( end - begin >= SMALL_SIZE ){
// 2つのデータ列に分割して、それぞれを再帰的に処理
size_t mid = (begin + end) / 2;
( array, begin, mid, work );
merge_sort_rec( array, mid + 1, end, work );
merge_sort_rec
// マージ
{
// 前半の要素を作業用配列へ
for( size_t i = begin; i <= mid; ++i){
[i] = array[i];
work}
// 後半の要素を逆順に作業用配列へ
for( size_t i = mid + 1, j = end; i <= end; ++i, --j){
[i] = array[j];
work}
// 作業用配列の両端から取り出した要素をマージ
{
size_t i = begin;
size_t j = end;
for( size_t k = begin; k <= end; ++k) {
// 昇順にソートするので、小さい方の要素を結果の配列へ移す。
// == の場合に、前半の側を優先すると安定なソートになる
if( work[i] <= work[j] ){
[k] = work[i];
array++i;
}
else{
[k] = work[j];
array--j;
}
}
}
}
}
else{
// データ範囲が狭ければ、挿入ソートに切り替える
( array, begin, end );
insertion_sort_ex}
}
/*
改良版挿入ソート (昇順)
*/
void insertion_sort_ex(int* array, int begin, int end)
{
for( int i = begin + 1; i <= end; ++i ){
int tmp = array[i];
if( array[i-1] > tmp ){
int j = i;
do {
[j] = array[j-1];
array--j;
} while( j > begin && array[j-1] > tmp );
[j] = tmp;
array}
}
}
/*
配列の要素を出力
*/
void print_array(const int* array, size_t size)
{
for( size_t i = 0; i < size; ++i ){
( "%d ", array[i] );
printf}
( "\n" );
printf}
変更前のマージソートと、変更後のマージソートとで、同じデータを使ってパフォーマンスを計測すると、次のような結果になりました。
データ件数 | 変更前 | 変更後 |
---|---|---|
10000個 | 0.002秒 | 0.002秒 |
100000個 | 0.026秒 | 0.020秒 |
1000000個 | 0.266秒 | 0.215秒 |
10000000個 | 2.956秒 | 2.321秒 |
効果が出ているようです。
要素数を意味している「サイズ」について、「要素数」に表記を改めた。
≪さらに古い更新履歴を展開する≫
Programming Place Plus のトップページへ
はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
X で ポスト/フォロー | LINE で送る | noteで書く |
RSS | 管理者情報 | プライバシーポリシー |