質問編集履歴
2
ミス
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -7,7 +7,7 @@
|
|
|
7
7
|
|
|
8
8
|
---------------追記--------------------
|
|
9
9
|
私の認識が正しいか確認お願いします
|
|
10
|
-
以下のような配列があった場合、下のように均等に分割できたとします。次にグループAで同じ処理を繰り返すとき、Bの要素は無視してAの中の要素とだけ比較すればよい。Bの要素を無視するので比較回数・交換回数が大幅に減る。Bも同様
|
|
10
|
+
以下のような配列があった場合、下のようにpivotに中央値を選び均等に分割できたとします。次にグループAで同じ処理を繰り返すとき、Bの要素は無視してAの中の要素とだけ比較すればよい。Bの要素を無視するので比較回数・交換回数が大幅に減る。Bも同様
|
|
11
11
|
よって中央値で分割できると高速で処理できる。
|
|
12
12
|
```ここに言語を入力
|
|
13
13
|
[4,3,2,5,7,6,9,10,8]
|
1
追加
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -2,4 +2,30 @@
|
|
|
2
2
|
|
|
3
3
|
①pivotを中央値にして分割を行い、分割の階数（深さ）を少なくすることで結果として、比較回数や交換回数を減らすことができるから
|
|
4
4
|
|
|
5
|
-
この説明がいまいちな気がするんですが、添削をお願いします。
|
|
5
|
+
この説明がいまいちな気がするんですが、添削をお願いします。
|
|
6
|
+
|
|
7
|
+
|
|
8
|
+
---------------追記--------------------
|
|
9
|
+
私の認識が正しいか確認お願いします
|
|
10
|
+
以下のような配列があった場合、下のように均等に分割できたとします。次にグループAで同じ処理を繰り返すとき、Bの要素は無視してAの中の要素とだけ比較すればよい。Bの要素を無視するので比較回数・交換回数が大幅に減る。Bも同様
|
|
11
|
+
よって中央値で分割できると高速で処理できる。
|
|
12
|
+
```ここに言語を入力
|
|
13
|
+
[4,3,2,5,7,6,9,10,8]
|
|
14
|
+
↓基準値を6とする
|
|
15
|
+
[4,3,2,5][確定：6][7,8,9,10] ///[4,3,2,5]を**グループA**,[7,8,9,10]を**グループB**とします
|
|
16
|
+
|
|
17
|
+
以降それぞれで処理
|
|
18
|
+
|
|
19
|
+
```
|
|
20
|
+
|
|
21
|
+
反対に最小値や最大値をpivotとして選んだ場合、上記の例のように中央値で分割できていないためグループに大きな偏りが生じる。グループCの場合、分割によって比較回数や交換回数をあまり減らすことができていない。
|
|
22
|
+
つまり処理が遅くなってします。
|
|
23
|
+
|
|
24
|
+
```ここに言語を入力
|
|
25
|
+
[4,3,2,5,7,6,9,10,8]
|
|
26
|
+
↓基準値を2とする
|
|
27
|
+
[確定：2][4,3,5,6,7,8,9,10] ///[4,3,5,6,7,8,9,10] をグループCとする
|
|
28
|
+
↓
|
|
29
|
+
以降も最小値を選び続ける
|
|
30
|
+
|
|
31
|
+
```
|