$$$$
超クイックソート(1兆個のデータをそのままソート)
- 最大、最小を求める。abcdefghijと事前にラベリング
- aとj,上位10%下位10%を端に寄せる(細かい順番は適当)
- bcdとghiを端に寄せる
- bとiを端に寄せる(a,jとb,i が重なる)
- de,fgを真ん中に集める
- 2~6を繰り返す
- 最後に一回だけ厳密にソート
- 必要があればa,b,c……それぞれに対し2~7を行い、再帰的処理でソートする
6.は、最終的に厳密にしないと何の意味もないので注意。同じ
「いい加減な処理」を繰り返すことで、整列する。
最後だけ厳密にする。
かわぐちさん「みんなー」
こうぼくん(ピコピコ)