回答編集履歴
4
微修正
test
CHANGED
|
@@ -2,7 +2,7 @@
|
|
|
2
2
|
|
|
3
3
|
|
|
4
4
|
|
|
5
|
-
[1] 要素数が小さいとき(32以下) inset
|
|
5
|
+
[1] 要素数が小さいとき(32以下) insertion-sortに切り替え
|
|
6
6
|
|
|
7
7
|
[2] 分割がある程度進んだらheap-sortに切り替え
|
|
8
8
|
|
3
追記
test
CHANGED
|
@@ -25,3 +25,9 @@
|
|
|
25
25
|
- 中央値の算出に時間かけるわけにはいかん
|
|
26
26
|
|
|
27
27
|
ので、上記のようなアルゴリズムなのでしょう。
|
|
28
|
+
|
|
29
|
+
|
|
30
|
+
|
|
31
|
+
※ [3.1] 要素数が小さいなら先頭～末尾間の中央値
|
|
32
|
+
|
|
33
|
+
これもマジメに求めるんじゃなく、"3値の中央値を3つ集めてその中の中央値"みたいなことを繰り返してるポいです。
|
2
微修正
test
CHANGED
|
@@ -14,7 +14,7 @@
|
|
|
14
14
|
|
|
15
15
|
|
|
16
16
|
|
|
17
|
-
ざっくりこんな↑かんじ。intro-sortと同じ戦略かと。
|
|
17
|
+
ざっくりこんな↑かんじ。intro-sortと同じ戦略かと(てかまんまintro-sortかと)。
|
|
18
18
|
|
|
19
19
|
|
|
20
20
|
|
1
修正
test
CHANGED
|
@@ -2,17 +2,19 @@
|
|
|
2
2
|
|
|
3
3
|
|
|
4
4
|
|
|
5
|
-
[1] 要素数が小さいとき(32以下)
|
|
5
|
+
[1] 要素数が小さいとき(32以下) insettion-sortに切り替え
|
|
6
6
|
|
|
7
|
-
[2]
|
|
7
|
+
[2] 分割がある程度進んだらheap-sortに切り替え
|
|
8
8
|
|
|
9
|
-
[
|
|
9
|
+
[3] さもなくば先頭/中央/末尾を元にpivot選択してquick-sort
|
|
10
10
|
|
|
11
|
+
[3.1] 要素数が小さいなら先頭～末尾間の中央値
|
|
12
|
+
|
|
11
|
-
[
|
|
13
|
+
[3.2] それ以上なら先頭/中央/末尾の3つの中央値
|
|
12
14
|
|
|
13
15
|
|
|
14
16
|
|
|
15
|
-
ざっくりこんな↑かんじ。
|
|
17
|
+
ざっくりこんな↑かんじ。intro-sortと同じ戦略かと。
|
|
16
18
|
|
|
17
19
|
|
|
18
20
|
|