クイックソートって？？

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

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

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

No.1 回答者： ymmasayan 回答日時： 2001/03/12 19:37

クイックソートは名前の通り「クイック（速い）なソート方法」です。

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

No.2 ベストアンサー 回答者： radiocat 回答日時： 2001/03/12 22:49

たとえば

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

No.3 回答者： yfujii 回答日時： 2001/06/12 23:56

クイックソートは、最初におおざっぱに分けて、だんだん細かい部分を作って分けていきます。

よく切られたトランプ５２枚を小さい順に並べ替える場合、方法１．はじめから完璧に並べ替えをする：１枚１枚を比べていきますから、１枚と並べ替えられた物を比べます。方法２．適当に選んだ１枚（基準の数）と大きいか小さいかだけ考えて山を２つ作ります。（１枚が３であれば、１－３が入った山と４－１３）できた小さい山も同様に小さい山にして行きます。この山作りを１枚になるまでやります。方法２の小さい山を沢山並べ替えようという作戦がクイックソートです。方法１で１００枚の物を並べ替える交換回数は平均１＋２＋．．．＋９９＝１００＊９９／２＝４９５０回ですが１回だけ方法２を使うと最初に５０個と５０個の山に分けて５０個を２回並べ替える場合（１＋２＋．．．４９）＊２＋１００＝５０＊４９＋１００＝２６００回でこちらが早いですね。１回だけではなく最後までやるとかなり早く並べ替える事ができるのが分かります。