- ベストアンサー
クイックソートって??
どこに載せればいいのかわからなかったので ここに載せてみました。 クイックソートってなんですか?? 簡単なアルゴリズムで答えてください!? (自分も何言っているのかわらない??) 簡単に言えばクイックソートってナに?? です。 よろしくお願いします。 わかるように簡単でね!!
- yosayosa
- お礼率22% (39/172)
- その他(プログラミング・開発)
- 回答数3
- ありがとう数2
- みんなの回答 (3)
- 専門家の回答
質問者が選んだベストアンサー
たとえば 「7135264」と並んだ数字があると 適当にピボットをとります。 ここでは5をピボットにすると 「713[5]264」に対して 左が小さく右が大きくなるように 7を5の右、2と4を左に移動 で、左が「1324」右が「76」となって 左は3をピボットとしたら2が左に移動、 右はどちらにしても7と6が入れ替え これで「1234567」のソート(整列)が完成。 というアルゴリズムです。 基本的な説明はymmasayanさんので完璧です。
その他の回答 (2)
- yfujii
- ベストアンサー率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回だけではなく最後までやるとかなり早く並べ替える事ができるのが分かります。
- ymmasayan
- ベストアンサー率30% (2593/8599)
クイックソートは名前の通り「クイック(速い)なソート方法」です。 データ中のどれか一つを指名して基準値(軸またはピボット)とします。 全データを基準値より大きいグループと小さいグループに分けます。 それぞれのグループの中でまた基準値を決め同じ事を繰り返します。 全データが全てひとりグループになったときソート完了です。 古典的ソートがN**2型の計算量なのに対しクイックソートは 条件が悪くなければN*(log N)型の計算量になります。 マージソートやヒープソートも同じ計算量であり、最速のソート の仲間です。 このアルゴリズムの実現には「再帰処理」を使うと楽です。
関連するQ&A
- アルゴリズムの問題なのですが、マージソートとクイックソートについて教え
アルゴリズムの問題なのですが、マージソートとクイックソートについて教えてください。 数列の(21 99 38 22 15 6)をマージソートで並び変えて、クイックソートでも並び変えたいのです。 マージソートで並び変えた手順は (21 99 38 22 15 6) (下矢印) (21 99 38)(22 15 6) (下矢印) (21 99)(38)(22 15)(6) (下矢印) (21)(99)(38)(22)(15)(6) (下矢印) (21 99)(38)(15 22)(6) (下矢印) (21 38 99)(6 15 22) (下矢印) (6 15 21 22 38 99) となりました。 この時、分割回数と統合回数がともに5なのですが、どう見たら5回なのでしょうか。 分割回数は3で統合回数も3ではないのでしょうか? クイックソートの方なのですが、 回答は (21 99 38 22 15 6) (下矢印) (15 6)(21)(99 38 22) (下矢印) (6)(15)(21)(22 38)(99) (15と38にした場合) (下矢印) (6)(15)(21)(22)(38)(99) となっていて、 最も効率のよいピボットを選択した場合分割回数は3となっています。 私がやってみたところ (21 99 38 22 15 6) (下矢印) (15 6)(21)(99 38 22) (下矢印) (6)(15)(21)(22)(38)(99) (15と38を選んだ) これではいけないのでしょうか。 長くなりましたが、よろしくお願いします。
- ベストアンサー
- その他([技術者向] コンピューター)
- クイックソートでソート数が1個や2個でも正しくソートできるのでしょうか?
使用上意味がないのですが、クイックソートでソート数が1個や2個でも正しくソートできるのでしょうか? 引数に quick_sort( a[], 0, n - 1 )と、n-1となっているために nは0は無理そうですが、n=1なら0でうまくいくかなと思うのですが、 原理上、どうなっているのでしょうか? 詳しい方教えて下さい。 http://www.daccho-it.com/program/algo/quick.c
- 締切済み
- 数学・算数
- クイックソートのアルゴリズムについて
(1)クイックソートが使われるのは実際にはどのような場面なのでしょうか?メインメモリで使われていると聞きましたが‥ (2)クイックソートが一番早いと聞きましたがコームソートやバブルソートなどは使われないのでしょうか? (3)マージソートはどのような局面で使われるのでしょうか?
- ベストアンサー
- C・C++・C#
- クイックソートしながら重複要素削除アルゴリズム
アルゴリズムが苦手な上、アルゴリズム解説自体C言語ベースで書かれ ている物が多く処理のイメージが沸かずクイックソートもコピペや既存 の関数で処理していて、満足に理解出来ていないのですが。 以下の問題を、お解かりになるかた教えて頂けませんでしょうか? ■問題 2万件位の数値データの中から重複要素を削除しながら昇順または降順で、 ソートするアルゴリズム(※1) ■条件 BASIC的(※2)な記述やプログラム中のコメントなどの形式でも構いま せん出来るだけ簡単に示して頂けると助かります。 補足 (※1)ソートする際、重複要素を消すともっと処理が早くなるのではと 思ったので。 目的は、処理の速さを求める事と、次回から応用が聞くよ うにソート自体を理解したいのでクイックソートで無くても構いません。 (※2)実際に動かなくても構いません、イメージが掴みやすい方が良いと いう意味でとって下さい。
- ベストアンサー
- その他(プログラミング・開発)
- それぞれのソート方法の特徴の違いについて
ソートを勉強しているのですが、 ヒープソートや、クイックソートなど効率の良いやり方と、 バブルソートのように、そうでないものがあるらしいことを 知ったのですが、最強のアルゴリズムは存在するのですか? それとも、ソート対象の状況によって、有効なアルゴリズムが違ってくるのですか? もし違うとしたら、どのように違うのでしょうか。
- ベストアンサー
- C・C++・C#