回答編集履歴
2
誤字修正
answer
CHANGED
|
@@ -1,13 +1,11 @@
|
|
|
1
|
-
### Step 1.
|
|
1
|
+
### Step 1. sort 関数 vs クイックソート，マージソート，ヒープソート
|
|
2
2
|
|
|
3
3
|
#### Step 1.1. アルゴリズム
|
|
4
4
|
|
|
5
5
|
Pythonの sort 関数は、KojiDoi 様が書かれている通り TimSort というアルゴリズムで実装されています。このアルゴリズムは、クイックソート, マージソート, ヒープソート, 挿入ソートを混ぜ込んだものです。
|
|
6
6
|
|
|
7
|
-
なぜ、混ぜ込むと速くなるのか？ということなのですが、それは各ソートアルゴリズムごとに得意な「データの形式」が異なるからです。
|
|
7
|
+
なぜ、混ぜ込むと速くなるのか？ということなのですが、それは各ソートアルゴリズムごとに得意な「データの形式」が異なるからです。出くわした「データの形式」に合わせて、アルゴリズムを切り替えています。どのアルゴリズムが、どの「データの形式」を取り扱うのが、得意かは自分も把握はしていません。
|
|
8
8
|
|
|
9
|
-
出くわした「データの形式」に合わせて、アルゴリズムを切り替えています。どのアルゴリズムが、どの「データの形式」を取り扱うのが、得意かは自分も把握はしていません。
|
|
10
|
-
|
|
11
9
|
ここで言う「データの形式」と言うのは、例としてはよくないですが、クイックソートは一般にデータに偏りがあると遅くなることが知られています。この例なら大抵の教科書には乗っているので、伝わってくれればと感じています。
|
|
12
10
|
|
|
13
11
|
以下のページに、どの「データ形式」なら速くなるか書かれているので、良いかなと思いました。
|
1
誤字修正
answer
CHANGED
|
@@ -37,7 +37,7 @@
|
|
|
37
37
|
|
|
38
38
|
対して、マージソートやヒープソートは、いくらか無駄な手がはいっている感じがします。無駄ってなんだよって感じですが。ヒープ、ヒープソート, マージソートについては、それぞれ以下の記事で可視化しました。もし雰囲気が伝われば幸いです。
|
|
39
39
|
|
|
40
|
-
* [Python でヒープ](https://python.ms/heap/)
|
|
40
|
+
* [Python でヒープ](https://python.ms/binary-heap/)
|
|
41
41
|
* [Python でヒープソート](https://python.ms/heap-sort/)
|
|
42
42
|
* [Python でマージソート](https://python.ms/merge-sort/)
|
|
43
43
|
|