効率よくデータを並べ換える方法を勉強してみた！
プログラムを開発していて、配列はよく使うが、効率よく並べ換えるアルゴリズムに「クイックソート」がある。
アルゴリズムは知っているが、プログラムにおこすとなると少し難易度が上がる。
「クイックソート」アルゴリズムとは？
クイックソートは、配列を整列するアルゴリズムの一種。
概要は、
配列の適当な要素を基準値にして、より小さい要素が前、より大きい要素が後ろになるように移動する。
基準値の前側の部分配列と、後ろ側の部分配列で、同じ処理を繰り返し行う。
である。
プログラムに落とし込むのは少し困難
クイックソートのプログラムを書くポイントは、基準値との大小関係において、配列を２つの部分配列に分けることにあるが、
これだけでプログラムに表現していくことは困難。よって、ここではこの書き方を習得していく。
書き方には複数のバリエーションがあるが、ここでは簡単な方法を書く。
そのために…
- 適当な要素とは何番目の要素なのか？
- 前側や後ろ側に移動するにはどうしたらよいか？
- 基準値と同じ値の要素の処理はどうすればいいか？
という疑問が残る
これらの疑問を解決しよう！
適当な要素とは？
配列の先頭の要素を基準値にすればいい！！
残りの"要素を先頭+1"（先頭の次）、および末尾から1つずつチェックして、大小関係に応じて両者を入れ替えれば、要素の移動ができる。
この際に「より小さい」「より大きい」ではなく。「以下」「以上」で比較すれば、基準値と同じ値の要素も処理できる。
変数leftは、配列の要素を先頭+1からたどるループカウンタ。変数rightは、配列の要素を末尾からたどるループカウンタ。
ループの終了条件は、"left>= right"となる。
"left > right"ならチェックが終わっているが、最終的にleftとrightが同じ要素を示す場合もあり得るため、left>=rightという終了条件になる。
処理の最後に、rightが示す要素と基準値を入れ替えることにも注意。
ループ終了時のrightは、基準値以下の要素を指す。基準値は、rightが指す要素より大きい場合があるので入れ替える。
この手順を"arrangerArray"関数にまとめると以下のようになる。
あとでクイックソートを行う際に、繰り返し適応するので、部分配列の先頭の要素を引数"head"、末尾の要素を引数"tail"で指定する。
int arrangerArray(int a[], int head, int tail) {
int pivot, left, right, temp;
pivot = a[head]; //基準値
left = head + 1; //先頭+1からたどるループカウンタ
right = tail; //末尾からたどるループカウンタ
//大小関係に応じて要素を入れ替える
while(-1) {
//配列を先頭+1からたどる
while (left < tail && pivot > a[left]) left++;
//配列の末尾からたどる
while (pivot < a[right]) right--;
//ループの終了
if (left >= right) break;
//leftとrightが刺す要素を入れ替える
temp = a[left];
a[left] = a[right];
a[right] = temp;
//次の要素チェックに進む
left++;
right--;
}
//最後に基準値とrightが指す要素を入れ替える
a[head] = a[right];
a[right] = pivot;
//部分配列を区切る要素の番号を返す
return right;
}クイックソートを行う関数を作成してみる
部分配列に繰り返しarrangeArray関数を適応する処理は、再帰呼び出しを使って書くと容易。
quickSort関数の引数startとendには、ソートを行う配列の先頭と末尾の要素番号を指定する。
最初にquickSort関数を呼び出すときには、これらの引数に配列全体の先頭と末尾の要素番号を指定する。
quickSort関数が再帰呼び出しされる時、これら引数に部分配列の先頭と末尾の要素b何号が指定される。
void quickSort(int a[], int start, int end) {
int p; //部分配列を区切る要素番号
//要素が２つ以上ある配列なら処理を行う
if (start < end) {
//基準値と大小関係に応じて２つの部分配列に分ける
p = arrengeArray(a, start, end);
//前側の部分配列に同じ処理を適応する
quickSort(a, start, p - 1)
//後側の部分配列に同じ処理を適応する
quickSort(a, p + 1, end);
}
}あらかじめ"arrangeArray"関数を作っておいたので、quickSort関数を作成したため、
"quickSort"関数の処理をスッキリ書けた。
"arrangerArray"関数で行なっている処理が、クイックソートのポイント。
