• ベストアンサー

クイックソートって??

yfujiiの回答

  • yfujii
  • ベストアンサー率17% (14/80)
回答No.3

クイックソートは、最初におおざっぱに分けて、だんだん細かい部分を作って分けていきます。よく切られたトランプ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

  • クイックソート

    クイックソートのアルゴリズムの問題で 9 1 8 5 3 4 2 6 7 と上記のようなデータ列を昇順に整列するときに 9 1 8 5 3 4 2 6 7 6 1 8 5 3 4 2 9 7 6 1 2 5 3 4 8 9 7 とここで詰まってしまうんですけどどうしたら昇順に導けますか?

  • クイックソート

    N個のデータを降順に並び替えるプログラムをクイックソートで書きたいのですがよく分かりません。アルゴリズムの部分をどなたか教えてください。できれば詳しい説明もお願いします。

  • アルゴリズムの問題なのですが、マージソートとクイックソートについて教え

    アルゴリズムの問題なのですが、マージソートとクイックソートについて教えてください。 数列の(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

  • クイックソート

    次の配列 2 12 4 9 7 8 5 3 6 11 15 1 をクイックソートで並び変えるとどうなりますか? やり方教えてください

  • クイックソートとマージソート

    クイックソートとマージソートではどちらか実用的でしょうか? 教えてください。

  • クイックソートのアルゴリズムについて

    (1)クイックソートが使われるのは実際にはどのような場面なのでしょうか?メインメモリで使われていると聞きましたが‥ (2)クイックソートが一番早いと聞きましたがコームソートやバブルソートなどは使われないのでしょうか? (3)マージソートはどのような局面で使われるのでしょうか?

  • シェルソート,クイックソート

    シェルソートは比較数が小さいとクイックソートよりも早いですが,なぜでしょうか?

  • クイックソートしながら重複要素削除アルゴリズム

    アルゴリズムが苦手な上、アルゴリズム解説自体C言語ベースで書かれ ている物が多く処理のイメージが沸かずクイックソートもコピペや既存 の関数で処理していて、満足に理解出来ていないのですが。 以下の問題を、お解かりになるかた教えて頂けませんでしょうか? ■問題 2万件位の数値データの中から重複要素を削除しながら昇順または降順で、 ソートするアルゴリズム(※1) ■条件 BASIC的(※2)な記述やプログラム中のコメントなどの形式でも構いま せん出来るだけ簡単に示して頂けると助かります。 補足 (※1)ソートする際、重複要素を消すともっと処理が早くなるのではと 思ったので。 目的は、処理の速さを求める事と、次回から応用が聞くよ うにソート自体を理解したいのでクイックソートで無くても構いません。 (※2)実際に動かなくても構いません、イメージが掴みやすい方が良いと    いう意味でとって下さい。

  • それぞれのソート方法の特徴の違いについて

    ソートを勉強しているのですが、 ヒープソートや、クイックソートなど効率の良いやり方と、 バブルソートのように、そうでないものがあるらしいことを 知ったのですが、最強のアルゴリズムは存在するのですか? それとも、ソート対象の状況によって、有効なアルゴリズムが違ってくるのですか? もし違うとしたら、どのように違うのでしょうか。