クイックソート、ヒープソートの演習
整列 バブルソート、選択ソートの演習
選択ソートやバブルソートは、データ数Nの二乗で計算が増えるO(N^2)という性質がある。
ここで、半分に分けてN/2個それぞれをソートすると、半分で(N/2)^2 すなわちN^2/4 を二つで、合計ではN^2/2となり、全体でも計算量が減ったことになる。
これを繰り返し突き詰めていくとマージソートになって計算量を O(N log N) に減らせる。
マージソートをメモリ配置やコーディングのしやすい形で工夫したものに、ヒープソート、クイックソートなどがある。
クイックソート
クイックソートは与えられたデータの並びによって性能が変化し、平均的にN log N 、最悪でN^2となる。
アルゴリズムは再帰的に書くとシンプルである。
クイックソートのアルゴリズム
ピボット p を決める
ソート対象を p より小さなもの S と、そうでないもの（大きなもの） B に分ける。（p の取り方によってはS,Bの個数はアンバランスになる）
SとBをそれぞれ、再帰的に（クイック）ソートする
ソートずみの S と B をつなげて終わり
一つの配列をつかってクイックソートすることが多く、この場合振り分け時に、Sを配列の添字の小さい方、Bを大きな方に寄せていくことで最後のS,B が自然とつながっていることになる。
pはなんでも良いが、ソート対象の中央値（原理的には対象のなかに含まれなくてもよい）が好ましく計算量が最小の N log Nになる。ソート対象の外の p を選ぶと、SまたはBにすべてが偏ってしまい、ソートできなくなる。このためなんらかの形で対象データから選ぶ。
配列a[10] のうちa[l] から a[r] までをクイックソートするプログラムは次のとおり。
code:quicksortpart.c
/* ----- prototypes ----- */
void quicksort(int a[], int l, int r);
void print_a(int a[]);
void makedata(int a[]);
/* ----- main ----- */
int main(void){
makedata(a);
print_a(a);
quicksort(a, 0, 9);
print_a(a);
}
/* ----- functions ----- */
void quicksort(int a[], int l, int r){
int p, w;
int i, j;
if(l >= r) return;
p = al; //左端のデータをピポットとする。 i = l; j = r;
while(1){
while(ai < p) i++; //左からピポットより小さいデータはそのままにする、iを右にずらす while(p < aj) j--; //右からピポットより大きいデータはそのままにする、jを左にずらす if (i >= j) break;
w = ai; ai = aj; aj = w; //入れ替え // p=5 1234yy ij xx7689
i++; j--;
}
quicksort(a, l, i-1); // 半分ずつ再帰
quicksort(a, j+1, r);
}
void print_a(int a[]){
int i;
for(i=0; i<10; i++){
}
printf("\n");
}
void makedata(int a[]){
int i;
for(i=0; i<10; i++){
}
}
クイズ
クイックソートの手順をデータの並びを見て復習しよう
5 2 3 1 4 8 7 10 9 6 -> 2 3 1 4 |5 | 8 10 7 9 6 -> 1 |2| 3 4 |5 | 8 10 7 9 6
次のデータの昇順並び替えにかかる計算はどれが多いか？ピポットのデータ p との比較回数で比べてみよう
1 3 5 7 9 2 4 6 8 10
10 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 10
演習
1）クイックソートのプログラムを書き整数を10個読み込んで並べ替えるプログラムを書こう
2）ランダムな数値を作成し配列に格納して、クイックソートするプログラムを書こう。
データ数を 10、100、1000、、と変えて実行時間を比べてみよう