-PR-
解決
済み

クイックソートって??

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

お礼率 22% (39/172)

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

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

簡単に言えばクイックソートってナに??  です。
よろしくお願いします。
わかるように簡単でね!!
通報する
  • 回答数3
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

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

  • 回答No.2
レベル7

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

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

その他の回答 (全2件)

  • 回答No.1
レベル14

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

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


  • 回答No.3
レベル9

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

クイックソートは、最初におおざっぱに分けて、だんだん細かい部分を作って分けていきます。よく切られたトランプ52枚を小さい順に並べ替える場合、方法1.はじめから完璧に並べ替えをする:1枚1枚を比べていきますから、1枚と並べ替えられた物を比べます。方法2.適当に選んだ1枚(基準の数)と大きいか小さいかだけ考えて山を2つ作ります。(1枚が3であれば、1-3が入った山と4-13)できた小さい山も同様に小さい山にし ...続きを読む
クイックソートは、最初におおざっぱに分けて、だんだん細かい部分を作って分けていきます。よく切られたトランプ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回だけではなく最後までやるとかなり早く並べ替える事ができるのが分かります。
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
こんな書き方もあるよ!この情報は知ってる?あなたの知識を教えて!
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

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

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ