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

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

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

このQ&Aに関連する最新のQ&A

A 回答 (3件)

たとえば


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

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

よく切られたトランプ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回だけではなく最後までやるとかなり早く並べ替える事ができるのが分かります。
    • good
    • 0

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


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

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

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

アルゴリズムが苦手な上、アルゴリズム解説自体C言語ベースで書かれ
ている物が多く処理のイメージが沸かずクイックソートもコピペや既存
の関数で処理していて、満足に理解出来ていないのですが。
以下の問題を、お解かりになるかた教えて頂けませんでしょうか?

■問題
2万件位の数値データの中から重複要素を削除しながら昇順または降順で、
ソートするアルゴリズム(※1)

■条件
BASIC的(※2)な記述やプログラム中のコメントなどの形式でも構いま
せん出来るだけ簡単に示して頂けると助かります。

補足
(※1)ソートする際、重複要素を消すともっと処理が早くなるのではと
思ったので。
目的は、処理の速さを求める事と、次回から応用が聞くよ
うにソート自体を理解したいのでクイックソートで無くても構いません。

(※2)実際に動かなくても構いません、イメージが掴みやすい方が良いと
   いう意味でとって下さい。

Aベストアンサー

>pythonで実行してみたのですが、うまく行きませんでした。
>2行目のIf文でエラーが出るようです。
投稿するとインテンドがきえてしまいました。以下のタブをタブに替えてください。
def qsort(list):
タブif len(list) != 0:
タブタブlt_list = [x for x in list if x < list[0]]
タブタブgt_list = [x for x in list if x > list[0]]
タブタブreturn qsort(lt_list) + [list[0]] + qsort(gt_list)
タブelse:
タブタブreturn []

>他の言語で置き換えようと調べてみたのですが、
>以下の解釈が解からないためよろしければ、教えて頂けるとありがたいのですが。
>3行目、4行目→x for x in list if x
これはpythonのリスト内包表記といって配列の中からある条件の配列を取り出しています。
gt_list = [x for x in list if x > list[0]]
はVBでいうと
for each x in list
if x > list(0) then
gt_listにx追加
end if
next
と同じです。
>ちなみに、以下は
>qsort(lt_list) + [list[0]] + qsort(gt_list)
>ソートと重複削除済みのリストが戻されると解釈して良いのでしょうか?
そうです。[list[0]]にはひとつしか値が入らないし、
lt_list,gt_listにもlist[0]と同じ値は入ってませんよね。

>pythonで実行してみたのですが、うまく行きませんでした。
>2行目のIf文でエラーが出るようです。
投稿するとインテンドがきえてしまいました。以下のタブをタブに替えてください。
def qsort(list):
タブif len(list) != 0:
タブタブlt_list = [x for x in list if x < list[0]]
タブタブgt_list = [x for x in list if x > list[0]]
タブタブreturn qsort(lt_list) + [list[0]] + qsort(gt_list)
タブelse:
タブタブreturn []

>他の言語で置き換えようと調べてみたのですが、
>以下の解釈が解...続きを読む

QMLのクイックソート

quicksort([],[]).
quicksort([A|B],C) :-
partition(B,A,B1,B2),
quicksort(B1,C1),
quicksort(B2,C2);
append(C1,[A|C2],C).

partition([],_,[],[]).
partition([D|B],A,[D|B1],B2) :-
D < A,
partition(B,A,B1,B2).
partition([D|B],B1,[D|B2]) :-
D >= A,
partition(D,A,B1,B2).

このプログラムがどのように動いているのか、
よくわかりません。誰か、どう処理しているのか教えてください。

Aベストアンサー

No.3です。
昨夜回答した後一晩経っても違和感が消えず、見直してみました。
このプログラムはMLではなくてPrologですね。
その点以外はNo.3で書いた内容の修正はありません。

> この3つの部分が具体的に何をしているのか
> 分からないです。

> quicksort([A|B],C) :-

quicksort()という述語を定義する。:- の後ろ、ピリオドまでがquicksort()の本体部。本体部でquicksort()を参照する再帰的定義になっている。
quicksort(B2,C2)の後ろのセミコロンはコロンが正しいはず。

> partition(B,A,B1,B2),

リストBの内容をB1とB2に分ける。B1の要素はA未満の値、B2の要素はA以上の値。
ただし、No.3でも書いたとおりpartition()の定義が間違っている。

> append(C1,[A|C2],C).

リストC1とリスト[A|C2]を連結したものをCとする。

参考URL:http://ja.wikipedia.org/wiki/Prolog

No.3です。
昨夜回答した後一晩経っても違和感が消えず、見直してみました。
このプログラムはMLではなくてPrologですね。
その点以外はNo.3で書いた内容の修正はありません。

> この3つの部分が具体的に何をしているのか
> 分からないです。

> quicksort([A|B],C) :-

quicksort()という述語を定義する。:- の後ろ、ピリオドまでがquicksort()の本体部。本体部でquicksort()を参照する再帰的定義になっている。
quicksort(B2,C2)の後ろのセミコロンはコロンが正しいはず。

> partition(B,A,B1,...続きを読む

QEXCEL VBAでクイックソート

学生の頃に学んだクイックソート。
学生の当時もあまり理解していた記憶は無いのですが、
最近ふと思い出して、いろんなサイトを見ながら
ExcelVBAを使用してクイックソートが出来るよう
ぺかぺかとプログラミングしていたわけですが・・・・

さっぱり理解が出来ません。

・・・で、初心者でもよくわかるようなサイトとかが
ありましたら教えてください。

もちろんここでわかりやすく教えていただいてもけっこうなのですが
すごい長文になってしまいますよね?

私的にはいっこうにかまわないのですが、それはそれで
大変だと思いますので。

ご存知の方、よろしくお願いします。

Aベストアンサー

さっぱり理解できないということですが、どのあたりがわからないのでしょう?
最悪ケースを回避するとか、要素数が少なくなったら別のアルゴリズムを使うとか
ピボットの選択で乱数使ったりするようなことのない素朴なやつなら
そんなに難しくはないと思うのですが。

大前提の、
・ある値を選んで、その値より大きいグループと小さいグループに分ける
・分けたグループについてクイックソートを再帰的に適用する
というのはよいですか?

参考URL:http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/quick-sort.html

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

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

Aベストアンサー

目的によって違う。
単純な速度については一般的にクイックソートはマージソートより2倍程度速いとされている。
ただしクイックソートはマージソートと違って固定的(キー値が同じオブジェクトの順序を変えない)ではないので、複数キーを使って繰り返しソートするような場合には使えないし、ランダムアクセスをするのでメモリ上に入りきらない大きなデータに対するソートには使えない。
またクイックソートは平均的にはn*log(n)速度だが最悪時はn^2オーダーになることがある。
ちなみにJavaのjava.util.Arrays.sortでは基本型に対するものは「調整されたクイックソート」が、オブジェクト型に対するものは「修正マージソート」が使われている。

Qクイックソート後の出力(pascal)

20個の整数データをクイックソートして出力せよ、という課題が出ました。クイックソートまでは出来た(コンパイルできたのでおそらく)のですが、その順に出力する方法がわかりません。どなたかお教えください。

program sort(input,output);
const n = 20;
type
index = 1..n;
var A: array[1..n] of integer;
i,x,a : integer;
p,j,k : index;

function PIVOT(i,j : index):integer;
var k:index;
begin
k:=i+1;
while (A[i]=A[k]) and (k<=j) do k:=k+1;
if k>j then PIVOT:=0
else if A[i]>=A[k] then PIVOT:=i
else PIVOT:=k
end;

procedure SWAP(var x,y:integer);
var
temp:integer;
begin
temp:=x; x:=y; y:=temp
end;

procedure PARTITION(i,j:index; a:integer; var k:index);
var l,r:index;
begin
l:=i; r:=j;
while A[l]<a do l:=l+1;
while A[r]>=a do r:=r-1;
while l<=r do
begin
SWAP(A[l],A[r]);
l:=l+1; r:=r-1;
while A[l]<a do l:=l+1;
while A[r]>=a do r:=r-1;
end;
k:=l
end;

procedure QUICKSORT(i,j:index);
var a:integer; p:index; k:index;
begin
p:=PIVOT(i,j);
if p<>0 then
begin
a:=A[p];
PARTITION(i,j,a,k);
QUICKSORT(i,k-1);
QUICKSORT(k,j)
end
end;

begin
i:=0;
i:=1+1;
for i:= 1 to n do
begin
A[i]:=0;
end;
i:=0;
i:=i+1;
for i:= 1 to n do
begin
readln(x);
A[i]:=x
end;
a:=PIVOT(p,j);
PARTITION(p,j,A[a],k);
QUICKSORT(p,j)
end.

QUICKSORT(p,j)とend. の間に出力方法を書き込みたいのです。

20個の整数データをクイックソートして出力せよ、という課題が出ました。クイックソートまでは出来た(コンパイルできたのでおそらく)のですが、その順に出力する方法がわかりません。どなたかお教えください。

program sort(input,output);
const n = 20;
type
index = 1..n;
var A: array[1..n] of integer;
i,x,a : integer;
p,j,k : index;

function PIVOT(i,j : index):integer;
var k:index;
begin
k:=i+1;
while (A[i]=A[k]) and (k<=j) do k:=k+1;
if k>j then PIVOT:...続きを読む

Aベストアンサー

んー、自分の手元では
質問にあるソースでは配列名の A と 通常変数名の aとが
衝突するのでコンパイルできないし、
名前を変えて衝突しないようにすると、コンパイルは通るのだけど

$a < lll
a: value out of range (error #300 at 4015e8)

と実行時エラーになります。

使ったPascalコンパイラは gpc (GNU Pascal)です。

どうも partitionがうまくできてないような気がするんだけどなあ。
#時間がないので追いかけてないです

ソートがきちんとできていれば
>for i := 1 to n do writeln(A[i]) と最初考えたのですが
でいいはずで、
元の内容と同じものが出たというのは元からソート済みのデータでもなければ
プログラムがどっかおかしいということだと思います。


人気Q&Aランキング

おすすめ情報