- データ構造編①
- ソート編①
問題文の横にある矢印をクリックすると答えが表示されます。
ソート編
Q26 「バブルソートを実装せよ」
-
列の最後尾から順に要素をみていき、逆転があったら前後を入れ替える -> 最も小さい要素が一番先頭にくる
-
同じ操作を最後尾から先頭から二番目まで行うと、次に小さい要素が二番目に来る
-
これを繰り返すことで、全体を整列することができる
#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 << " ";
}
}
Q27 「バブルソートの計算量を求めよ」
$O(n)$のループを2重にまわすので$O(n^2)$
Q28 「クイックソートを実装せよ」
- $O(nlogn)$でソートを行うことのできる効率の良いアルゴリズム
- 分割統治を用いて、与えられた列をある値より大きいものと小さいものに分け、それぞれを再帰的に解いた結果をつなぎ合わせることで、全体の並び替えを行う
#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 << " ";
}
}
Q29 「クイックソートの最悪計算量を求めよ」
分割の度に常に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}$であると仮定すると、
\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}
Q30 「クイックソートの平均計算量を求めよ」
平均計算時間をT(n)と表す。Partitionの結果i個とn-i個の要素に分かれる確率をP(i, n)とすると、
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番目の要素が位置している確率
P(i, n) = \frac{2i}{n(n-1)}
よって、
\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$ のとき成立していると仮定すると、
\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}$
Q31 「マージソートを実装せよ」
- クイックソート同様に分割統治の方法を用いているが、クイックソートが再帰呼び出しの前に振り分け処理をするのに対し、マージソートでは再帰呼び出しからソート
- クイックソートが再帰呼び出しの前に振り分け処理を行うのに対し、マージソートでは再帰呼び出しからソート済みの列が戻ってきた後にそれらを併合する処理を行う
- mergeでは、二つのソート済みの入力列を先頭から走査して、小さいほうの要素を順に取り出して一本の列に返す手続き
#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 << " ";
}
}
Q32 「マージソートの計算量を求めよ」
再帰呼び出しに渡されるデータの大きさが常に半分になるので、平均でも最悪でも$O(n\log{n})$になる。
Q33 「マージソートの利点を述べよ」
クイックソートに比べて最悪計算量を抑えることができ、先頭から順番に読み出し・書き込みをすればいいだけなので、メモリ上に収まりきらない巨大なデータをソートする時にも有向(外部ソート)
Q34 「ヒープソートを実装せよ」
#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;
}
Q35 「ヒープソートの計算量を求めよ」
高さ$i$の部分木のコストが$2^{h}-i$ ($h$は木全体の深さ)である時、
\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})$かかる。
Q36 「ヒープソートの利点を述べよ」
下からk個だけを取り出したいとき、後半部分のループをk回だけまわせばよいので、合計の計算時間は$O(n + k\log{n})$で済む。
Q37 「バケットソートを実装せよ」
#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;
}
Q38 「バケットソートの計算量を求めよ」
バケットの数をm個とすると、バケットの挿入にO(n)、バケットの接続にO(m)かかるので、O(m+n)であり、$m < n$なら、O(n)になる。
Q39 「基数ソートを実装せよ」
#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
Q40 「基数ソートの計算量を求めよ」
i桁目の取りうる値の数を$S_{i}$とすると、その桁のソートに$O(n + S_{i})$かかる。それが1~k桁目まであるので、合計は$O(kn + \sum_{i=1}^{k}S_{i})$となる。$\sum_{i=1}^{k} << n$なら、基数ソートの計算量はO(n)になる。