回答編集履歴
1
不要な文字の削除
answer
CHANGED
|
@@ -5,7 +5,7 @@
|
|
|
5
5
|
全部を選択ソートでソートしてから中央値を求めるより，約1/4の時間で終わらせることができます．
|
|
6
6
|
|
|
7
7
|
またO(nlogn)のクイックソートを自作したとき，ピボットより大きいグループと小さいグループのどちらかはソート不要になります．
|
|
8
|
-
例えば{3, 1, 4, 6, 2, 7, 5}という元データ
|
|
8
|
+
例えば{3, 1, 4, 6, 2, 7, 5}という元データを考えます．
|
|
9
9
|
ピボットを先頭の3にしたとき，{1, 2}, {3}, {4, 6, 7, 5}という風に分割できます．
|
|
10
10
|
この時，ピボットの3より小さいグループの要素数は2，等しいグループの要素数は1，大きいグループの要素数は4です．
|
|
11
11
|
となると中央値は大きいグループの中に入っていることがわかります．
|