回答編集履歴
4
微修正
answer
CHANGED
|
@@ -1,6 +1,6 @@
|
|
|
1
1
|
たぶんお手本に相応しい実装:標準C++ライブラリのstd::sortを覗いてみました(Visual C++)
|
|
2
2
|
|
|
3
|
-
[1] 要素数が小さいとき(32以下)
|
|
3
|
+
[1] 要素数が小さいとき(32以下) insertion-sortに切り替え
|
|
4
4
|
[2] 分割がある程度進んだらheap-sortに切り替え
|
|
5
5
|
[3] さもなくば先頭/中央/末尾を元にpivot選択してquick-sort
|
|
6
6
|
[3.1] 要素数が小さいなら先頭～末尾間の中央値
|
3
追記
answer
CHANGED
|
@@ -11,4 +11,7 @@
|
|
|
11
11
|
スピード命ですから
|
|
12
12
|
- 要素数が小さいときにはquick-sortはややこしすぎる
|
|
13
13
|
- 中央値の算出に時間かけるわけにはいかん
|
|
14
|
-
ので、上記のようなアルゴリズムなのでしょう。
|
|
14
|
+
ので、上記のようなアルゴリズムなのでしょう。
|
|
15
|
+
|
|
16
|
+
※ [3.1] 要素数が小さいなら先頭～末尾間の中央値
|
|
17
|
+
これもマジメに求めるんじゃなく、"3値の中央値を3つ集めてその中の中央値"みたいなことを繰り返してるポいです。
|
2
微修正
answer
CHANGED
|
@@ -6,7 +6,7 @@
|
|
|
6
6
|
[3.1] 要素数が小さいなら先頭～末尾間の中央値
|
|
7
7
|
[3.2] それ以上なら先頭/中央/末尾の3つの中央値
|
|
8
8
|
|
|
9
|
-
ざっくりこんな↑かんじ。intro-sortと同じ戦略かと。
|
|
9
|
+
ざっくりこんな↑かんじ。intro-sortと同じ戦略かと(てかまんまintro-sortかと)。
|
|
10
10
|
|
|
11
11
|
スピード命ですから
|
|
12
12
|
- 要素数が小さいときにはquick-sortはややこしすぎる
|
1
修正
answer
CHANGED
|
@@ -1,11 +1,12 @@
|
|
|
1
1
|
たぶんお手本に相応しい実装:標準C++ライブラリのstd::sortを覗いてみました(Visual C++)
|
|
2
2
|
|
|
3
|
-
[1] 要素数が小さいとき(32以下)
|
|
3
|
+
[1] 要素数が小さいとき(32以下) insettion-sortに切り替え
|
|
4
|
+
[2] 分割がある程度進んだらheap-sortに切り替え
|
|
4
|
-
[
|
|
5
|
+
[3] さもなくば先頭/中央/末尾を元にpivot選択してquick-sort
|
|
5
|
-
[
|
|
6
|
+
[3.1] 要素数が小さいなら先頭～末尾間の中央値
|
|
6
|
-
[
|
|
7
|
+
[3.2] それ以上なら先頭/中央/末尾の3つの中央値
|
|
7
8
|
|
|
8
|
-
ざっくりこんな↑かんじ。
|
|
9
|
+
ざっくりこんな↑かんじ。intro-sortと同じ戦略かと。
|
|
9
10
|
|
|
10
11
|
スピード命ですから
|
|
11
12
|
- 要素数が小さいときにはquick-sortはややこしすぎる
|