トップページ – アルゴリズムとデータ構造編 – 【整列アルゴリズム】第4章
問題① 元のデータ列が事前にソートされている範囲を変えると、実行時間はどのくらい増減しますか? ご自分の実行環境で確認してみてください。
本編の「性能」のところで使ったプログラムを改造して試してみます。
init_array関数に引数を追加して、ソート済みにする要素数も指定できるようにしました。
配列全体が未整列の場合、20%、40%、60%、80% が整列済みの場合、そして全体が整列済みの場合をそれぞれ調べてみます。
#include <stdio.h>
#include <stdlib.h>
#include "ppp_perform.h"
#define ARRAY_SIZE 50000
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
static void init_array(int* array, size_t size, size_t sorted_size);
static void insertion_sort_ex(int* array, size_t size);
int main(void)
{
int array[ARRAY_SIZE];
( array, ARRAY_SIZE, 0 );
init_array(1);
PPP_CHECK_PERFORM_BEGIN( array, SIZE_OF_ARRAY(array) );
insertion_sort_ex("insertion_sort_ex (0%)");
PPP_CHECK_PERFORM_END
( array, ARRAY_SIZE, ARRAY_SIZE / 10 * 2 );
init_array(1);
PPP_CHECK_PERFORM_BEGIN( array, SIZE_OF_ARRAY(array) );
insertion_sort_ex("insertion_sort_ex (20%)");
PPP_CHECK_PERFORM_END
( array, ARRAY_SIZE, ARRAY_SIZE / 10 * 4 );
init_array(1);
PPP_CHECK_PERFORM_BEGIN( array, SIZE_OF_ARRAY(array) );
insertion_sort_ex("insertion_sort_ex (40%)");
PPP_CHECK_PERFORM_END
( array, ARRAY_SIZE, ARRAY_SIZE / 10 * 6 );
init_array(1);
PPP_CHECK_PERFORM_BEGIN( array, SIZE_OF_ARRAY(array) );
insertion_sort_ex("insertion_sort_ex (60%)");
PPP_CHECK_PERFORM_END
( array, ARRAY_SIZE, ARRAY_SIZE / 10 * 8 );
init_array(1);
PPP_CHECK_PERFORM_BEGIN( array, SIZE_OF_ARRAY(array) );
insertion_sort_ex("insertion_sort_ex (80%)");
PPP_CHECK_PERFORM_END
( array, ARRAY_SIZE, ARRAY_SIZE );
init_array(1);
PPP_CHECK_PERFORM_BEGIN( array, SIZE_OF_ARRAY(array) );
insertion_sort_ex("insertion_sort_ex (100%)");
PPP_CHECK_PERFORM_END
return 0;
}
/*
配列を初期化
*/
void init_array(int* array, size_t size, size_t sorted_size)
{
(0);
srand
size_t i;
for( i = 0; i < sorted_size; ++i ){
[i] = (int)i;
array}
for( size_t i = 0; i < size; ++i ){
[i] = rand() % size;
array}
}
/*
改良版挿入ソート (昇順)
*/
void insertion_sort_ex(int* array, size_t size)
{
for( size_t i = 1; i < size; ++i ){
int tmp = array[i];
if( array[i-1] > tmp ){ // 挿入が必要か先に調べる
size_t j = i;
// 初回の j > 0 は必ず真であるし、
// array[j-1] > tmp も先ほどチェックしたところなので、
// do-while文にして条件判定を後に回す方が効率的。
do {
[j] = array[j-1];
array--j;
} while( j > 0 && array[j-1] > tmp );
[j] = tmp; // ここで行えば、挿入が不要ならば通過しなくて済む
array}
}
}
実行結果:
insertion_sort_ex (0%): 2.335000 seconds
insertion_sort_ex (20%): 1.748000 seconds
insertion_sort_ex (40%): 1.530000 seconds
insertion_sort_ex (60%): 1.391000 seconds
insertion_sort_ex (80%): 1.005000 seconds
insertion_sort_ex (100%): 0.000000 seconds
整列済みの部分が増えると、順当に高速になっていることが分かります。
問題② 改良版挿入ソートを、降順にソートするようにしてください。
不等号の向きを逆にするだけで実現できます。
大小比較を行っている箇所が2つあることに注意してください。書き換えたのは、if文の条件式と、do-while文の条件式の2か所です。
void insertion_sort_ex(int* array, size_t size)
{
for( size_t i = 1; i < size; ++i ){
int tmp = array[i];
if( array[i-1] < tmp ){ // 挿入が必要か先に調べる
size_t j = i;
// 初回の j > 0 は必ず真であるし、
// array[j-1] > tmp も先ほどチェックしたところなので、
// do-while文にして条件判定を後に回す方が効率的。
do {
[j] = array[j-1];
array--j;
} while( j > 0 && array[j-1] < tmp );
[j] = tmp; // ここで行えば、挿入が不要ならば通過しなくて済む
array}
}
}
問題③ 挿入位置を探すとき、二分探索(【探索】第4章参照)の考え方を使えば高速化を図れる可能性があります。改良版挿入ソートをこの方法で実装してください。
このような実装方法は、二分挿入ソートと呼ばれています。
前提として、二分探索📘を理解しなければなりません。【探索】第4章で説明していますが、わりと一般的な実装方法だと、同じ値が複数含まれているとき、どれを見つけ出すか不定になります。この問題によって、決定される挿入位置も不定(同じ値の集まりのどこが選ばれるかということなので、ソートできないわけではありません)になるため、不定にならない実装を使う必要があります。
/*
二分挿入ソート (昇順)
*/
void binary_insertion_sort_ex(int* array, size_t size)
{
for( size_t i = 1; i < size; ++i ){
int tmp = array[i];
if( array[i-1] > tmp ){ // 挿入が必要か先に調べる
// 挿入位置を二分探索で探す
size_t lower = 0;
size_t upper = i;
while( lower < upper ){
size_t mid = (lower + upper) / 2;
if( array[mid] < tmp ){
= mid + 1;
lower }
else{
= mid;
upper }
}
// 発見した挿入位置へ挿入
size_t j;
for( j = i; j > lower; --j ){
[j] = array[j-1];
array}
[j] = tmp;
array}
}
}
元の改良版挿入ソートと、この二分挿入ソートの性能を比較してみましょう。
#include <stdio.h>
#include <stdlib.h>
#include "ppp_perform.h"
#define ARRAY_SIZE 50000
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
static void init_array(int* array, size_t size, size_t sorted_size);
static void insertion_sort_ex(int* array, size_t size);
static void binary_insertion_sort_ex(int* array, size_t size);
int main(void)
{
int array[ARRAY_SIZE];
//
// 事前ソートなし
//
( array, ARRAY_SIZE, ARRAY_SIZE );
init_array(1);
PPP_CHECK_PERFORM_BEGIN( array, SIZE_OF_ARRAY(array) );
insertion_sort_ex("insertion_sort_ex (0%)");
PPP_CHECK_PERFORM_END
( array, ARRAY_SIZE, ARRAY_SIZE );
init_array(1);
PPP_CHECK_PERFORM_BEGIN( array, SIZE_OF_ARRAY(array) );
binary_insertion_sort_ex("binary_insertion_sort_ex (0%)");
PPP_CHECK_PERFORM_END
//
// 事前に 80% までソート済み
//
( array, ARRAY_SIZE, ARRAY_SIZE / 10 * 8 );
init_array(1);
PPP_CHECK_PERFORM_BEGIN( array, SIZE_OF_ARRAY(array) );
insertion_sort_ex("insertion_sort_ex (80%)");
PPP_CHECK_PERFORM_END
( array, ARRAY_SIZE, ARRAY_SIZE / 10 * 8 );
init_array(1);
PPP_CHECK_PERFORM_BEGIN( array, SIZE_OF_ARRAY(array) );
binary_insertion_sort_ex("binary_insertion_sort_ex (80%)");
PPP_CHECK_PERFORM_END
return 0;
}
/*
配列を初期化
*/
void init_array(int* array, size_t size, size_t sorted_size)
{
(0);
srand
size_t i;
for( i = 0; i < sorted_size; ++i ){
[i] = (int)i;
array}
for( size_t i = 0; i < size; ++i ){
[i] = rand() % size;
array}
}
/*
改良版挿入ソート (昇順)
*/
void insertion_sort_ex(int* array, size_t size)
{
for( size_t i = 1; i < size; ++i ){
int tmp = array[i];
if( array[i-1] > tmp ){ // 挿入が必要か先に調べる
size_t j = i;
// 初回の j > 0 は必ず真であるし、
// array[j-1] > tmp も先ほどチェックしたところなので、
// do-while文にして条件判定を後に回す方が効率的。
do {
[j] = array[j-1];
array--j;
} while( j > 0 && array[j-1] > tmp );
[j] = tmp; // ここで行えば、挿入が不要ならば通過しなくて済む
array}
}
}
/*
二分挿入ソート (昇順)
*/
void binary_insertion_sort_ex(int* array, size_t size)
{
for( size_t i = 1; i < size; ++i ){
int tmp = array[i];
if( array[i-1] > tmp ){ // 挿入が必要か先に調べる
// 挿入位置を二分探索で探す
size_t lower = 0;
size_t upper = i;
while( lower < upper ){
size_t mid = (lower + upper) / 2;
if( array[mid] < tmp ){
= mid + 1;
lower }
else{
= mid;
upper }
}
// 発見した挿入位置へ挿入
size_t j;
for( j = i; j > lower; --j ){
[j] = array[j-1];
array}
[j] = tmp;
array}
}
}
実行結果:
insertion_sort_ex (0%): 2.235000 seconds
binary_insertion_sort_ex (0%): 1.976000 seconds
insertion_sort_ex (80%): 2.179000 seconds
binary_insertion_sort_ex (80%): 1.941000 seconds
二分挿入ソートの方が良い結果を示しました。
Programming Place Plus のトップページへ
はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
X で ポスト/フォロー | LINE で送る | noteで書く |
![]() |
管理者情報 | プライバシーポリシー |