クイックソート

Facebookシェア Twitterツイート LINEで送る Googleシェア このエントリーをはてなブックマークに追加
この章を学ぶ前に必要な知識
Up
0
Down

要約

概要

一般的に早いとされるソート.データの並び順によっては他のソートが早いことも多々ある.
ーポイントー
  • 最悪計算時間はn^2になる非安定ソート
  • ランダムなデータでは平均的に他のソートよりは早いと言われる

解  説

クイックソートのアルゴリズムの概要 どんなケースでも早いソートのアルゴリズムではありません。また、最悪計算時間はn^2になります。 アルゴリズムの手順は以下の通りです。

小さい順で左から並べることを想定する。

  1. ランダムにピボットを選択
  2. ピボットより左側のデータでピボットより大きいものを右側に右側のデータで小さいものを左側に交換する。
  3. 交換を終えたら、そのピボットの値を確定して、分割された右側と左側のそれぞれで1.からを繰り返す.
QuickSortアルゴリズム概略
Quickソートではピボットの選択によって最悪ケースになるかどうかが決まる。 その最悪ケースは、ピボットがソートする列の最大か最小を選んだ時なので、同一の値が多い時等は、そのケースにハマりやすく遅くなりやすいです。 実装次第ですが、既にソートされているものや逆順にソートされているものにおいて最初のピボットを選んでしまう場合も遅くなります。
QuickSort のポイント
大方並び終えた時に挿入ソートに変更して高速化することがなどが頻繁に 行われる。
QuickSortと他の組み合わせ
この章を学んで新たに学べる
Comments

Reasons
>>隠す