- 629 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 18:36:21.33 ]
- >>619
618なんだが、QuickSortを使うのではなくそのアルゴリズムを使うって話
QuickSortのアルゴリズムのキモの部分は、Pivotを決めてそれより大きいか小さいかでPivotの左右に振り分ける
それを改良して、Pivotを同値がある数値にし、Compareを＝のみ真にして、真なら隣とスワップとする
同値が複数ある場合に備えて、1つスワップしたら、そのスワップする位置が内に1つずつズレていく
そのPivotを同値のある物にしなければならないから検索が必要になるってこと
要素に入っている数値全てに対して行なってもいいけど総当りになるから検索したほうがいいかなってこと
例えば、3, 5, 2, 3, 5, 2, 5, 2, 1なら
同値のある5を右端とスワップして、そのプログラムに通すと
3, 2, 3, 2, 1, 5, 5, 5ってなる
さらに3, 2, 3, 2, 1の部分を抜き出して左端に3を持っていきプログラムに通すと
2, 2, 1, 3, 3ってなる、2の場合も同じ
最終的に、1, 2, 2, 3, 3, 5, 5, 5ってなる、ソートされている状態だけど
3から始めたら、1, 2, 2, 5, 5, 5, 3, 3ってなる
QuickSortのアルゴリズム部分を改良したら行けるんじゃないか？って話
|
 |
