はじめに
この記事はクイックソートの勉強の記録として書いたものです。私は本当に素人なので、間違ったことを言うことが多いです。間違いを見つけたときは指摘していただければ幸いです。
自己紹介
- 所属
九州工業大学情報工学部
- ハンドルネーム
buridaikon
使わせていただいた問題
提出したコード
// クイックソート
#include <iostream>
#include <vector>
using namespace std;
/* 配列vecに要素を入力する関数 */
void input(vector<int> &vec) // 配列の参照渡し
{
for (int i = 0; i < vec.size(); i++)
{
cin >> vec[i]; // 要素の入力
}
}
/* 配列vecの要素を一行に出力する関数（末尾で改行） */
void output(vector<int> &vec) // 配列の参照渡し
{
for (int i = 0; i < vec.size() - 1; i++)
{
cout << vec[i] << " "; // 末尾でない配列の要素を出力
}
cout << vec[vec.size() - 1] << endl; // 末尾の要素を出力して改行
}
void quicksort(vector<int> &vec)
{
int n = vec.size();
if (!n) // vecのサイズが0（つまりvecの中身が空だった時）何もしない
{
return; // quicksort関数の終了
}
int div_index = n / 2;
vector<int> left; // 分割後の配列（左側）用
vector<int> right; // 分割後の配列（右側）用
/* ここのループでは分割（leftとrightへの仕分け） */
for (int i = 0; i < n; i++) //
{
if (i == div_index) // i番目が分割する境目の時
{
continue; // 何もせずに次のループへ移行
}
if (vec[i] < vec[div_index]) // pivotの要素より小さい時
{
left.push_back(vec[i]); // leftの末尾に挿入
}
else // pivotの要素より大きい時
{
right.push_back(vec[i]); // rightの末尾に挿入
}
}
quicksort(left);
quicksort(right);
left.push_back(vec[div_index]);
left.insert(left.end(), right.begin(), right.end());
vec = left;
}
int main()
{
int n;
cin >> n;
vector<int> vec(n);
input(vec); // vecにn個の要素を入力
quicksort(vec); // vecをクイックソート
output(vec); // vecの中身を出力
return 0;
}
導入
クイックソートって何？
pivot（本来は「回転軸」という意味。ここでは無作為に取り出した要素、つまり要素の入れ替えの中心軸となる要素のことを指します）を決めて、pivotを中心に要素を左右に振り分けてソートを行います。（今回は要素の並びとして中央に位置する要素をpivotとします）
簡単に言うと、再帰的にpivotの取得、要素の入れ替えをすることで高速にソートするアルゴリズムです。
計算量
- 平均計算量
O(n\log n)
- 最悪計算量
O(n^2)
多くの場合クイックソートを使うことで、平均計算量でソートを完了させることができます。
アルゴリズムの解説
提出したコードのうち、クイックソートを行っているのは以下の部分です。
void quicksort(vector<int> &vec)
{
int n = vec.size();
if (!n) // vecのサイズが0（つまりvecの中身が空だった時）何もしない
{
return; // quicksort関数の終了
}
int div_index = n / 2;
vector<int> left; // 分割後の配列（左側）用
vector<int> right; // 分割後の配列（右側）用
/* ここのループでは分割（leftとrightへの仕分け） */
for (int i = 0; i < n; i++) //
{
if (i == div_index) // i番目が分割する境目の時
{
continue; // 何もせずに次のループへ移行
}
if (vec[i] < vec[div_index]) // pivotの要素より小さい時
{
left.push_back(vec[i]); // leftの末尾に挿入
}
else // pivotの要素より大きい時
{
right.push_back(vec[i]); // rightの末尾に挿入
}
}
quicksort(left);
quicksort(right);
left.push_back(vec[div_index]);
left.insert(left.end(), right.begin(), right.end());
vec = left;
}
クイックソートの手順
①pivotの取得
②振り分けをした要素を入れるための配列を作成（左側／右側用にひとつずつ）
③作成した動的配列leftとrightに入れ替えた要素を入れます（もとのvecとは別の配列であると意識しましょう）
④作成したquicksort関数をquicksort関数内で呼び出して、分割したleft（左側に移した要素たち）とright（右側に移した要素たち）にそれぞれ同じ処理をします（再帰関数）
⑤配列leftとrightを結合させる
⑥最後にもともとの配列、vecにleft（rightとの結合後）のデータを代入します
①pivotの取得
int div_index = n / 2;
ここではpivotをパラメータの配列の中央に位置する要素とします。
②振り分けをした要素を入れるための配列を作成（左側／右側用にひとつずつ）
vector<int> left; // 分割後の配列（左側）用
vector<int> right; // 分割後の配列（右側）用
要素数を指定していない理由は、forの中で末尾に要素を追加（動的配列だからできること）していくためです（現時点では要素数が未定）。
③作成した動的配列leftとrightに入れ替えた要素を入れる（もとのvecとは別の配列であると意識しましょう）
以下のループでは要素を分割して、要素を入れ替え（ソート）しています。
/* ここのループでは分割（leftとrightへの仕分け） */
for (int i = 0; i < n; i++) //
{
if (i == div_index) // i番目が分割する境目の時
{
continue; // 何もせずに次のループへ移行
}
if (vec[i] < vec[div_index]) // pivotの要素より小さい時
{
left.push_back(vec[i]); // leftの末尾に挿入
}
else // pivotの要素より大きい時
{
right.push_back(vec[i]); // rightの末尾に挿入
}
}
if (i == div_index) // i番目が分割する境目の時
{
continue; // 何もせずに次のループへ移行
}
i（調べている場所）がpivot（プログラム内ではdiv_indexが該当）の時、何もせずに次のループに移行します。
if (vec[i] < vec[div_index]) // pivotの要素より小さい時
{
left.push_back(vec[i]); // leftの末尾に挿入
}
else // pivotの要素より大きい時
{
right.push_back(vec[i]); // rightの末尾に挿入
}
④作成したquicksort関数をquicksort関数内で呼び出して、分割したleft（左側に移した要素たち）とright（右側に移した要素たち）にそれぞれ同じ処理をします（再帰関数）
quicksort(left);
quicksort(right);
こうすることで、ソートをしながら調べるスコープを狭めていくことができます。
ちなみに、quicksort関数の中で以下のように書いているのは、スコープを狭めていったときの関数に与えられる配列の要素数が0になるときのために書いているものです。
int n = vec.size();
if (!n) // vecのサイズが0（つまりvecの中身が空だった時）何もしない
{
return; // quicksort関数の修了
}
逆に言うと、quicksort関数のパラメータの配列が要素数ゼロ（ここまで細かくする）であればソートが終了します。
⑤配列leftとrightを結合させる
left.push_back(vec[div_index]);
left.insert(left.end(), right.begin(), right.end());
left.push_back(vec[div_index]);は最後にpivotとなった要素をleftに追加しているところです。pivotは中心軸であり、要素の移動はないのでループの最後に配列へ追加してあげる必要があります。
イテレータ（left.end(), right.begin(), right.end()の部分）の指定の仕方はinsert関数のC++リファレンスをご参照ください。
⑥最後にもともとの配列、vecにleft（rightとの結合後）のデータを代入します
vec = left;
これにてソートが完了です
他の関数やmain関数に関して説明はいらないと思うので割愛します。
補足
関数に配列を渡すときは参照渡しを使いましょう
その理由等はこちらを見ていただければわかります。
以上、ここまで読んでいただきありがとうございました。
間違いがある場合は、遠慮なくご指摘していただければ幸いです。
参考文献
私の説明で分からなかった方のために、わかりやすい解説のリンクを貼っておきます。