クイックソート（備忘録）

## はじめに
　この記事はクイックソートの勉強の記録として書いたものです。私は本当に素人なので、間違ったことを言うことが多いです。間違いを見つけたときは指摘していただければ幸いです。

## 自己紹介
- 所属
> **九州工業大学情報工学部**
- ハンドルネーム
> **buridaikon**

## 使わせていただいた問題

https://algo-method.com/tasks/442

## 提出したコード
```cpp:sec1pro1.cpp
// クイックソート

#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の取得、要素の入れ替えをすることで高速にソートするアルゴリズム**です。

#### 計算量
- 平均計算量
```math
O(n\log n)
```
- 最悪計算量
```math
O(n^2)
```
　多くの場合クイックソートを使うことで、平均計算量でソートを完了させることができます。
 
## アルゴリズムの解説
　提出したコードのうち、クイックソートを行っているのは以下の部分です。
 ```cpp:quicksort
 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の取得**
```cpp
int div_index = n / 2;
```

　ここではpivotをパラメータの配列の中央に位置する要素とします。

##### **②振り分けをした要素を入れるための配列を作成（左側／右側用にひとつずつ）**
```cpp
vector<int> left;  // 分割後の配列（左側）用
vector<int> right; // 分割後の配列（右側）用
```
　要素数を指定していない理由は、forの中で末尾に要素を追加（動的配列だからできること）していくためです（現時点では要素数が未定）。

##### **③作成した動的配列leftとrightに入れ替えた要素を入れる（もとのvecとは別の配列であると意識しましょう）**

　以下のループでは要素を分割して、要素を入れ替え（ソート）しています。
```cpp
/* ここのループでは分割（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の末尾に挿入
       }
   }
```
```cpp
if (i == div_index) // i番目が分割する境目の時
{
    continue; // 何もせずに次のループへ移行
}
```
　i（調べている場所）がpivot（プログラム内ではdiv_indexが該当）の時、何もせずに次のループに移行します。
```cpp
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（右側に移した要素たち）にそれぞれ同じ処理をします（再帰関数）**
```cpp
quicksort(left);
quicksort(right);
```
　こうすることで、ソートをしながら調べるスコープを狭めていくことができます。
 　ちなみに、quicksort関数の中で以下のように書いているのは、スコープを狭めていったときの関数に与えられる配列の要素数が0になるときのために書いているものです。
```cpp
int n = vec.size();
if (!n) // vecのサイズが0（つまりvecの中身が空だった時）何もしない
{
       return; // quicksort関数の修了
}
```
 　逆に言うと、quicksort関数のパラメータの配列が要素数ゼロ（ここまで細かくする）であればソートが終了します。

##### **⑤配列leftとrightを結合させる**
```cpp
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との結合後）のデータを代入します**
```cpp
vec = left;
```
これにてソートが完了です

他の関数やmain関数に関して説明はいらないと思うので割愛します。

## 補足
　関数に配列を渡すときは参照渡しを使いましょう
 その理由等はこちらを見ていただければわかります。
 
https://qiita.com/buridaikon_kyutech/items/78d9fe679352a613b8d8

以上、ここまで読んでいただきありがとうございました。
間違いがある場合は、遠慮なくご指摘していただければ幸いです。

## 参考文献
私の説明で分からなかった方のために、わかりやすい解説のリンクを貼っておきます。

https://qiita.com/drken/items/44c60118ab3703f7727f#6-%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88-%E4%B9%B1%E6%8A%9E%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AE%E3%82%88%E3%81%84%E9%A1%8C%E6%9D%90


https://www.momoyama-usagi.com/entry/info-algo-sort-advance#1