• ベストアンサー
  • すぐに回答を!

クイックソートって??

  • 質問No.50886
  • 閲覧数370
  • ありがとう数2
  • 気になる数0
  • 回答数3
  • コメント数0

お礼率 22% (39/172)

どこに載せればいいのかわからなかったので
ここに載せてみました。

クイックソートってなんですか??
簡単なアルゴリズムで答えてください!?
  (自分も何言っているのかわらない??)

簡単に言えばクイックソートってナに??  です。
よろしくお願いします。
わかるように簡単でね!!

質問者が選んだベストアンサー

  • 回答No.2
  • ベストアンサー

ベストアンサー率 33% (5/15)

たとえば
「7135264」と並んだ数字があると
適当にピボットをとります。
ここでは5をピボットにすると
「713[5]264」に対して
左が小さく右が大きくなるように
7を5の右、2と4を左に移動
で、左が「1324」右が「76」となって
左は3をピボットとしたら2が左に移動、
右はどちらにしても7と6が入れ替え
これで「1234567」のソート(整列)が完成。
というアルゴリズムです。
基本的な説明はymmasayanさんので完璧です。

その他の回答 (全2件)

  • 回答No.3

ベストアンサー率 17% (14/80)

クイックソートは、最初におおざっぱに分けて、だんだん細かい部分を作って分けていきます。よく切られたトランプ52枚を小さい順に並べ替える場合、方法1.はじめから完璧に並べ替えをする:1枚1枚を比べていきますから、1枚と並べ替えられた物を比べます。方法2.適当に選んだ1枚(基準の数)と大きいか小さいかだけ考えて山を2つ作ります。(1枚が3であれば、1-3が入った山と4-13)できた小さい山も同様に小さい山にして行きます。この山作りを1枚になるまでやります。方法2の小さい山を沢山並べ替えようという作戦がクイックソートです。方法1で100枚の物を並べ替える交換回数は平均1+2+...+99=100*99/2=4950回ですが1回だけ方法2を使うと最初に50個と50個の山に分けて50個を2回並べ替える場合(1+2+...49)*2+100=50*49+100=2600回でこちらが早いですね。1回だけではなく最後までやるとかなり早く並べ替える事ができるのが分かります。
  • 回答No.1

ベストアンサー率 30% (2593/8599)

クイックソートは名前の通り「クイック(速い)なソート方法」です。
データ中のどれか一つを指名して基準値(軸またはピボット)とします。
全データを基準値より大きいグループと小さいグループに分けます。
それぞれのグループの中でまた基準値を決め同じ事を繰り返します。
全データが全てひとりグループになったときソート完了です。
古典的ソートがN**2型の計算量なのに対しクイックソートは
条件が悪くなければN*(log N)型の計算量になります。
マージソートやヒープソートも同じ計算量であり、最速のソート
の仲間です。
このアルゴリズムの実現には「再帰処理」を使うと楽です。
結果を報告する
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。
関連するQ&A

その他の関連するQ&Aをキーワードで探す

ピックアップ

ページ先頭へ