[100本ノック] アルゴリズムとデータ構造 - ソート編 ①

- [データ構造編①](https://qiita.com/Koukyosyumei/items/5772a3b51c201b2e8a51)
- ソート編①

問題文の横にある矢印をクリックすると答えが表示されます。

# ソート編

<details>
<summary>Q26 「バブルソートを実装せよ」</summary>

- 列の最後尾から順に要素をみていき、逆転があったら前後を入れ替える -> 最も小さい要素が一番先頭にくる

- 同じ操作を最後尾から先頭から二番目まで行うと、次に小さい要素が二番目に来る
- これを繰り返すことで、全体を整列することができる

```cpp
#include <iostream>
#include <vector>

template <typename T> std::vector<T> bubblesort(std::vector<T> data) {
  int N = data.size();
  T max_val, tmp_1, tmp_2;
  int max_idx;
  for (int i = N - 1; i >= 0; i--) {
    for (int j = 0; j <= i; j++) {
      if (j == 0 || max_val < data[j]) {
        max_val = data[j];
        max_idx = j;
      }
    }
    tmp_1 = data[i];
    tmp_2 = data[max_idx];
    data[i] = tmp_2;
    data[max_idx] = tmp_1;
  }
  return data;
}

int main() {
  std::vector<int> data = {1, 5, 3, 6, 8, 3, 9, 10, 6, 7, 2, 4, 8, 13, 0};
  for (auto x : data) {
    std::cout << x << " ";
  }
  std::cout << std::endl;
  std::vector<int> sorted_data = bubblesort<int>(data);
  for (auto x : sorted_data) {
    std::cout << x << " ";
  }
}
```
</details>

<details>
<summary>Q27 「バブルソートの計算量を求めよ」</summary>

$O(n)$のループを2重にまわすので$O(n^2)$
</details>

<details>
<summary>Q28 「クイックソートを実装せよ」</summary>

- $O(nlogn)$でソートを行うことのできる効率の良いアルゴリズム
- 分割統治を用いて、与えられた列をある値より大きいものと小さいものに分け、それぞれを再帰的に解いた結果をつなぎ合わせることで、全体の並び替えを行う

```cpp
#include <iostream>
#include <vector>

template <typename T> int find_pivot(std::vector<T> &data, int i, int j) {
  int k = i;
  while (k < j) {
    if (data[k] < data[k + 1]) {
      return k + 1;
    } else if (data[k] > data[k + 1]) {
      return k;
    } else {
      k++;
    }
  }
  return -1;
}

template <typename T> int partition(std::vector<T> &data, int i, int j, T p) {
  int u = i;
  int v = j;

  while (true) {
    while (u <= j && data[u] < p) {
      u++;
    }
    while (v >= i && data[v] >= p) {
      v--;
    }
    if (u > v) {
      break;
    }
    T tmp_1 = data[u];
    T tmp_2 = data[v];
    data[v] = tmp_1;
    data[u] = tmp_2;
  }
  return u - 1;
}

template <typename T> void quicksort(std::vector<T> &data, int i, int j) {
  if (i >= j)
    return;

  int p = find_pivot(data, i, j);
  if (p == -1) {
    return;
  } else {
    int k = partition(data, i, j, data[p]);
    quicksort(data, i, k);
    quicksort(data, k + 1, j);
  }
}

int main() {
  std::vector<int> data = {1, 3,  6, 7, 2,  4,  9, 4, 2,
                           5, 10, 0, 0, 13, 11, 7, 2};
  for (auto x : data) {
    std::cout << x << " ";
  }
  std::cout << std::endl;
  quicksort(data, 0, data.size() - 1);
  for (auto x : data) {
    std::cout << x << " ";
  }
}
```

</details>

<details>
<summary>Q29 「クイックソートの最悪計算量を求めよ」</summary>

分割の度に常に1つとそれ以外に分けられてしまう時が明らかに最悪であり、n個の要素のソートにかかる計算量を $T(n)$ とすると、 $T(n) = T(n-1)+ T(1) + P(n)$となる (P(n)は分割にかかる計算量)。ここで、$T(n) = O(n^2)$であることを示す。$P(n)=C_{2}n$、$n < k$ とおき、 $T(n) \leq C_{1}n^{2}$であると仮定すると、

```math
\begin{align}
  T(n) &\leq C_{1}(n-1)^{2} + C_{2} n \\
       &\leq C_{1}n^{2} \quad (\frac{C_{1}}{2C_{1} - C_{2}} < n)
\end{align}
```

</details>

<details>
<summary>Q30 「クイックソートの平均計算量を求めよ」</summary>

平均計算時間をT(n)と表す。Partitionの結果i個とn-i個の要素に分かれる確率をP(i, n)とすると、

```math
T(n) = \sum_{i=1}^{n-1} P(i, n) \{cn + T(i) + T(n-i)\}
```

ただしここで、cnはpivotを決める時間とpartitionの時間を表す。P(i, n)はpivotがちゅうどi+1番目の要素である確率であり、与えられた列の先頭二つにi以下の要素とi+1番目の要素が位置している確率

```math
P(i, n) = \frac{2i}{n(n-1)}
```

よって、

```math
\begin{align}
  T(n) &= \sum_{i=1}^{n-1} \frac{2i}{n(n-1)} \{cn + T(i) + T(n-i)\} \\
       &= cn + \frac{2}{n(n-1)} \sum_{i=1}^{n-1} \{iT(i) + iT(n-i)\} \\
       &= cn + \frac{2}{n(n-1)} \{\sum_{i=1}^{n-1} iT(i) - \sum_{i=1}^{n-1}(n-i)T(n-i) + n\sum_{i=1}^{n-1}T(n-i)\} \\
       &= cn + \frac{2}{n-1} \sum_{i=1}^{n-1}T(i)
\end{align}
```

$T(n) \leq an\log{n}$ を仮定する。n=2の時は $T(n) = 2c + 2T(1)$ なので、$a = c + T(1)$である。

$n = 1,...,k-1$ のとき成立していると仮定すると、

```math
\begin{align}
T(k) &= ck + \frac{2}{k-1} \sum_{i=1}^{k-1} T(i) \\
     &\leq ck + \frac{2}{k-1} \sum_{i=1}^{k-1} ai\log{i} \\
     &= ck + \frac{2}{k-1} (\sum_{i=1}^{k/2} i\log{i} + \sum_{i=k/2}^{k-1} i\log{i}) \\
     &= ck + \frac{2}{k-1} (\sum_{i=1}^{k/2} i\log{\frac{k}{2}} + \sum_{i=k/2}^{k-1} i\log{k}) \\
     &= ak\log{k} + ck - \frac{ak}{4} - \frac{3ak}{4(k-1)}
\end{align}
```

よって、$a > 4c$の時、$T(k) < ak\log{k}$であり、$a > max(c + T(1), 4c)$であればすべてのnで$T(n) < an\log{n}$

</details>

<details>
<summary>Q31 「マージソートを実装せよ」</summary>

- クイックソート同様に分割統治の方法を用いているが、クイックソートが再帰呼び出しの前に振り分け処理をするのに対し、マージソートでは再帰呼び出しからソート
- クイックソートが再帰呼び出しの前に振り分け処理を行うのに対し、マージソートでは再帰呼び出しからソート済みの列が戻ってきた後にそれらを併合する処理を行う
- mergeでは、二つのソート済みの入力列を先頭から走査して、小さいほうの要素を順に取り出して一本の列に返す手続き


```python
#include <iostream>
#include <vector>

template <typename T>
std::vector<T> mergesort(std::vector<T> &data, int i, int j) {
  if (i == j) {
    return {data[i]};
  } else {
    std::vector<T> left = mergesort(data, i, (j + i) / 2);
    std::vector<T> right = mergesort(data, (j + i) / 2 + 1, j);
    int left_size = left.size();
    int right_size = right.size();
    std::vector<T> result(left_size + right_size);
    int u = 0;
    int v = 0;
    int w = 0;
    while (w < left_size + right_size) {
      while (u < left_size && (v == right_size || left[u] <= right[v])) {
        result[w] = left[u];
        u++;
        w++;
      }
      while (v < right_size && (u == left_size || right[v] <= left[u])) {
        result[w] = right[v];
        v++;
        w++;
      }
    }
    return result;
  }
}

int main() {
  std::vector<int> data = {1, 3, 5, 2, 4, 9, 10, 0, 13, 16, 7, 8, 3, 5, 2};
  for (auto x : data) {
    std::cout << x << " ";
  }
  std::cout << std::endl;
  std::vector<int> sorted_data = mergesort<int>(data, 0, data.size() - 1);
  for (auto x : sorted_data) {
    std::cout << x << " ";
  }
}
```

</details>

<details>
<summary>Q32 「マージソートの計算量を求めよ」</summary>

再帰呼び出しに渡されるデータの大きさが常に半分になるので、平均でも最悪でも$O(n\log{n})$になる。
</details>

<details>
<summary>Q33 「マージソートの利点を述べよ」</summary>

クイックソートに比べて最悪計算量を抑えることができ、先頭から順番に読み出し・書き込みをすればいいだけなので、メモリ上に収まりきらない巨大なデータをソートする時にも有向(外部ソート)
</details>

<details>
<summary>Q34 「ヒープソートを実装せよ」</summary>

```cpp
#include <iostream>
#include <vector>
using namespace std;

void pushdown(vector<int> &array, int first, int last) {
  int i = first;
  int j;
  while (i < (last - 1) / 2) {
    if (array[2 * i + 1] < array[2 * i + 2]) {
      j = 2 * i + 1;
    } else {
      j = 2 * i + 2;
    }

    if (array[j] < array[i]) {
      swap(array[j], array[i]);
      i = j;
    } else {
      return;
    }
  }
}

void heapsort(vector<int> &array) {
  int n = array.size();
  for (int i = n / 2 - 1; i >= 0; i--) {
    pushdown(array, i, n - 1);
  }
  for (int i = n - 1; i >= 1; i--) {
    swap(array[0], array[i]);
    pushdown(array, 0, i - 1);
  }
}

int main() {
  vector<int> xs = {1, 3, 2, 8, 5, 10, 4, 6, 9, 7};
  heapsort(xs);
  for (auto x : xs) {
    cout << x << " ";
  }
  cout << endl;
}
```
</details>

<details>
<summary>Q35 「ヒープソートの計算量を求めよ」</summary>

高さ$i$の部分木のコストが$2^{h}-i$ ($h$は木全体の深さ)である時、

```math
\begin{align}
\sum_{i=0}^{h} i 2^{h-i} &= 2^{h} \sum_{i=0}^{h} i 2^{-i} \\
                         &= 2^{h+1} - h - 2 \\
                         &< 2^{h+1} - 1 \\
                         &= n
\end{align}
```

よって、ヒープを作る部分の計算量はO(n)で済む。後半部分は1つの取り出しに$O(\log{n})$かかるので、ヒープソート全体では$O(n\log{n})$かかる。
</details>

<details>
<summary>Q36 「ヒープソートの利点を述べよ」</summary>

下からk個だけを取り出したいとき、後半部分のループをk回だけまわせばよいので、合計の計算時間は$O(n + k\log{n})$で済む。
</details>

<details>
<summary>Q37 「バケットソートを実装せよ」</summary>

```cpp
#include <iostream>
#include <vector>
using namespace std;

vector<int> bucket_sort(int M, vector<int> &data) {
  int N = data.size();
  vector<int> buckets(M, 0);
  vector<int> result;
  result.reserve(N);

  for (int i = 0; i < N; i++) {
    buckets[data[i]]++;
  }

  for (int j = 0; j < M; j++) {
    for (int i = 0; i < buckets[j]; i++) {
      result.push_back(j);
    }
  }

  return result;
}

int main() {
  vector<int> data = {6, 4, 1, 0, 4, 2, 5, 1, 8, 9, 0, 7, 3, 2, 1, 0, 9, 8};
  for (auto x : data) {
    cout << x << " ";
  }
  cout << endl;
  vector<int> result = bucket_sort(10, data);
  for (auto x : result) {
    cout << x << " ";
  }
  cout << endl;
}
```
</details>

<details>
<summary>Q38 「バケットソートの計算量を求めよ」</summary>

バケットの数をm個とすると、バケットの挿入にO(n)、バケットの接続にO(m)かかるので、O(m+n)であり、$m < n$なら、O(n)になる。
</details>

<details>
<summary>Q39 「基数ソートを実装せよ」</summary>

```cpp
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

void radixsort(vector<int> &array) {
  int max_val = *max_element(array.begin(), array.end());
  int digit_num = to_string(max_val).length();
  int array_length = array.size();
  vector<vector<int>> bucket(10);

  // バケットに値を入れていく
  for (int d = 0, r = 1; d < digit_num; d++, r *= 10) {
    for (int i = 0; i < array_length; i++) {
      int key = (array[i] / r) % 10;
      bucket[key].push_back(array[i]);
    }

    // バケットに格納された値の結合
    for (int j = 0, i = 0; j < bucket.size(); j++) {
      for (auto val : bucket[j]) {
        array[i++] = val;
      }
    }

    // バケットを一度空にする
    for (int j = 0; j < bucket.size(); j++) {
      bucket[j].clear();
    }
  }
}

int main() {
  vector<int> xs = {365, 196, 321, 825, 192};
  radixsort(xs);

  for (auto x : xs) {
    cout << x << " ";
  }
  cou
```
</details>

<details>
<summary>Q40 「基数ソートの計算量を求めよ」</summary>

i桁目の取りうる値の数を$S_{i}$とすると、その桁のソートに$O(n + S_{i})$かかる。それが1~k桁目まであるので、合計は$O(kn + \sum_{i=1}^{k}S_{i})$となる。$\sum_{i=1}^{k} << n$なら、基数ソートの計算量はO(n)になる。
</details>