参考
漫画の並べ替えを例にしていてわかりやすかった。
デカルトみを感じたいなら、コンピュータ科学をやれ！【アルゴリズム3】#3 - YouTube
選択ソート
1000巻の漫画から1巻を探して一番左に配置。
次に2巻を探して1巻の隣に配置。
これを繰り返す。
1000回の比較
999回の比較
998
997
・
・
・
1
平均すると500回の比較を999回繰り返す。
なので計算量は
999 * 500 = 499500
(n-1)(n÷2)
O(n^2)
クイックソート
1000巻の漫画から真ん中500巻を取り出す。（本当は真ん中ではないがわかりやすくするため）
500巻より小さいのを左に、大きいのを右に分割する。
比較を1000回行うことになる。
左のからさらに1冊を取り出す。同様に小さいのを左、大きいのを右。
繰り返し分割していくと
1000
500
250
125
62
31
15
7
3
1
計10回で1冊に分割できる。
1回の分割ごとに1000回比較するから計算量は
1000 * log1000 = 10000
n * log1000
O(nlogn)
クイックソートは分割統治アルゴリズ。
分割統治は大きな問題を小さく分割して解決すること。
プログラマーは分割統治が重要らしい。
カプセル化とか関数の機能分割とかは確かに分割統治してる気がする。
