RSS
この章の概要です。
この章では、選択ソートを取り上げます。
単純選択ソートと呼ばれることもあります。
選択ソートは、データ列の中で一番小さい（あるいは一番大きい）データを探し、そのデータと先頭のデータを交換します。次に、２番目に小さい（または大きい）データと、先頭から２番目のデータとを交換します。これをデータ列の末尾に行き着くまで繰り返すと、整列済みのデータ列が得られるという方法です。
たとえば、対象のデータ列が次のような配列だとします。
int array[] = {7, 2, 4, 5, 1, 3, 6};まず、一番小さいデータを探します。これは先頭から順番に調べていけば分かることで、結果は array[4] の位置にある 1 が一番小さいことが分かります。これを array[0] の位置に移動させればいいのですから、array[0] と array[4] を交換します。
{1, 2, 4, 5, 7, 3, 6};次に、２番目に小さいデータを探して、array[1] と交換します。２番目に小さいデータは array[1] の位置にある 2 です。つまり、array[1] 同士の交換になるので、配列の内容は変化しません。
次は、３番目に小さいデータを探して、array[2] と交換します。３番目に小さいデータは array[5] にある 3 です。
{1, 2, 3, 5, 7, 4, 6};次は、４番目に小さいデータを探して、array[3] と交換します。４番目に小さいデータは array[5] にある 4 です。
{1, 2, 3, 4, 7, 5, 6};次は、５番目に小さいデータと array[4] の交換です。５番目に小さいデータは array[5] にある 5 です。
{1, 2, 3, 4, 5, 7, 6};次は、６番目に小さいデータと array[5] の交換です。６番目に小さいデータは array[6] にある 6 です。
{1, 2, 3, 4, 5, 6, 7};７番目に小さいデータを探しても、もう交換相手はいませんから、この段階で完了できます。昇順にソートされています。
前章で解説した単純ソートと比べてみると、データ列の先頭から順番に１つずつ確定していく点は同じです。実際、選択ソートは、単純ソートにあった無駄を省くように書き換えただけの改良版とみなせます。
単純ソートの無駄とは、一番小さいデータなのかどうかが確定していないうちから、先頭の要素との交換を行ってしまっていることです。選択ソートでは、一番小さいデータであることが確定してから交換を行うので、単純ソートよりも交換回数を減らせます。
交換回数は減ったものの、比較回数は変わっていません。単純ソートでは、比較の基準を固定しつつ、比較相手を１つずつ変えて比較を繰り返しました。選択ソートも構図は同じです。そのため、計算量でいえば、単純ソートも選択ソートも O(n2) です。
それでは、冒頭で確認した実行過程を踏まえて、選択ソートのプログラムを書いてみましょう。
#include <stdio.h>
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
#define SWAP(type,a,b) { type work = a; a = b; b = work; }
static void selection_sort(int* array, size_t size);
static void print_array(const int* array, size_t size);
int main(void)
{
int array[] = {7, 2, 4, 5, 1, 6};
print_array( array, SIZE_OF_ARRAY(array) );
selection_sort( array, SIZE_OF_ARRAY(array) );
print_array( array, SIZE_OF_ARRAY(array) );
return 0;
}
/*
選択ソート (昇順)
*/
void selection_sort(int* array, size_t size)
{
for( size_t i = 0; i < size - 1; ++i ){
// 第 i 位となる値の位置を探す
size_t min_index = i;
for( size_t j = i + 1; j < size; ++j ){
if( array[min_index] > array[j] ){
min_index = j;
}
}
// 第 i 位の値をもつ要素と、array[i] を交換する
SWAP(int, array[i], array[min_index]);
}
}
/*
配列の要素を出力
*/
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 4 5 1 3 6
1 2 3 4 5 6 7選択ソートをしているのは、selection_sort関数の中です。
外側の for文が制御している変数 i は、その回のループで確定させる順位を示しています。初回のループでは、全体の中で一番小さいデータを確定させるので 0 から開始します（「一番」なので 1 が自然ですが、添字が 0 基準なので 0 から始めます）。
やや細かい話ですが、ループを続ける判定は i < size - 1 のように、要素数から 1 を引いています。冒頭で示した手順の最後にあった、「７番目に小さいデータを探しても、もう交換相手はいませんから、この段階で完了できます」にあたります。末尾まで調べたところで意味がないということです。
for文の内側を見ていきます。
まず、全体の中で第 i 位となる値をもった要素を探します。変数 i が 0 のときなら、第 0 位、つまり一番小さい値をもった要素を探すということです。
全体としては第 i 位ですが、実際には、いつも配列全体から探すわけではありません。たとえば、第 0 位が確定してしまえば、その次の回では、array[0] を調べる必要はないですし、さらに次の回では array[1] も調べなくてよくなります。つまり、だんだん調べる範囲は狭くなっていきます。
そう考えると、実は探している要素はいつも「一番小さい値」です。
配列の中から一番小さい値を探す方法自体も、一種のアルゴリズムなので、ここで説明すべきかも知れませんが、ここでは割愛します。この部分の解説が必要なら、Ｃ言語編 逆引き「配列から最大値（最小値）を探す」 を参照してください。
内側の for文から抜け出したときには、一番小さい値の位置が、変数 min_index に入っています。この値を使って、array[i] の要素と交換すれば、第 i 位の値が確定したことになります。
前章の単純ソートと比較すると、交換を行う回数が減らせることが理解できると思います。単純ソートではこうなっていました。
for( size_t i = 0; i < size - 1; ++i ){
for( size_t j = i + 1; j < size; ++j ){
if( array[i] > array[j] ){
SWAP(int, array[i], array[j]);
}
}
}選択ソートと違って、SWAPマクロの呼び出しが内側の for文の中に入っています。if文が真にならないと実行されませんが、この if文は最終的な順位がどうなるかとは関係なく、手あたり次第に大小関係を見ているだけですから、頻繁に真になることもあり得ます。
選択ソートの場合は、SWAPマクロは、外側の for文が１周するたびに１回しか呼び出されないことが保証されています。
選択ソートの計算量は O(n2) で、遅い整列アルゴリズムだと言えます。この計算量は、単純ソートと同じですが、交換回数が少なくすむため、普通は選択ソートの方が高速です。
なお、選択ソートは安定なアルゴリズムではありません。
実際に、単純ソートと性能比較をしてみます。
#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 SWAP(type,a,b) { type work = a; a = b; b = work; }
static void init_array(int* array, size_t size);
static void simple_sort(int* array, size_t size);
static void selection_sort(int* array, size_t size);
int main(void)
{
int array[ARRAY_SIZE];
init_array( array, SIZE_OF_ARRAY(array) );
PPP_CHECK_PERFORM_BEGIN(1);
simple_sort( array, SIZE_OF_ARRAY(array) );
PPP_CHECK_PERFORM_END("simple_sort");
init_array( array, SIZE_OF_ARRAY(array) );
PPP_CHECK_PERFORM_BEGIN(1);
selection_sort( array, SIZE_OF_ARRAY(array) );
PPP_CHECK_PERFORM_END("selection_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 simple_sort(int* array, size_t size)
{
for( size_t i = 0; i < size - 1; ++i ){
for( size_t j = i + 1; j < size; ++j ){
if( array[i] > array[j] ){
SWAP(int, array[i], array[j]);
}
}
}
}
/*
選択ソート (昇順)
*/
void selection_sort(int* array, size_t size)
{
for( size_t i = 0; i < size - 1; ++i ){
// 第 i 位となる値の位置を探す
size_t min_index = i;
for( size_t j = i + 1; j < size; ++j ){
if( array[min_index] > array[j] ){
min_index = j;
}
}
// 第 i 位の値をもつ要素と、array[i] を交換する
SWAP(int, array[i], array[min_index]);
}
}実行結果：
simple_sort: 0.419000 seconds
selection_sort: 0.187000 seconds10000個の要素を持つ配列を、乱数で適当に初期化したものを、単純ソートと選択ソートによって昇順にソートしています。実行結果にあるように、選択ソートの方が良い結果を示しました。
この差は、交換回数の少なさから来ているので、それぞれの場合の交換回数も調べてみると良いでしょう。これは練習問題に残しておきます。
選択ソートの計算量は O(n2) で、これは遅いアルゴリズムだと言えます。また、安定なソートではありません。
単純ソート（第１章）と同じ計算量ですが、交換回数が減らせるため、選択ソートの方が高速になることが多いです。
また、実際に交換が行われる回数がデータの並び方によって変化する単純ソートと違い、選択ソートの交換回数はデータ数に応じて一定です（n - 1回）。そのため、選択ソートのほうが、実際の処理時間が安定的です。
仕組みが単純ソートと似ており、プログラムもそれほど大きく変わらないので、単純ソートを使うぐらいならば、選択ソートを使った方がいいでしょう。
問題① 降順にソートする選択ソートを作成してください。
問題② 単純ソートと選択ソートとで、交換回数にどれだけ差が出るかを調べてください。
’2015/12/27 SIZE_OF_ARRAYマクロの定義を修正。
’2015/2/21 サンプルプログラムで、ファイルスコープでよい関数に static を付加。
≪さらに古い更新履歴を展開する≫
Programming Place Plus のトップページへ
| はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
| X で ポスト／フォロー | LINE で送る | noteで書く |
|
RSS
|
管理者情報 | プライバシーポリシー |