こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

クイックソート(C言語)

こんにちは<_ _>
クイックソートについての質問です。
左端を軸にクイックソートでデータを昇順にソートする
プログラムを作ったのですがうまく動きません

#include<stdio.h>

void quick(int *,int,int);

#define N 10

int main(void)
{
static int a[]={41,24,76,11,45,64,21,69,19,36};
int k,b=0;

quick(a,0,N-1);

for(k=0;k<N;k++)
printf(" %d",a[k]);

return 0;
}

void quick(int a[],int left,int right)
{
int s,t,i,j;

t=right;
i=left+1;
j=a[left];

if(right>left){
while(1){
while(a[++i]>j);
while(a[--t]<j && t>0);
if(i>=t){
break;
}
s=a[i];
a[i]=a[t];
a[t]=s;
}
s=a[i];
a[i]=j;
a[left]=s;

quick(a,left,t-1);
quick(a,t+1,right);
}
}
値の入れ替え、軸の入れ替えもしましたが結果として
「41 41 76 69 45 64 41 19 0 36」
このような結果で出力されてしまいます・・・
時間に余裕のある方いましたらご指導をお願いします。
よろしくお願いします。<_ _>

投稿日時 - 2007-05-29 11:11:26

QNo.3039559

暇なときに回答ください

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

#include<stdio.h>

void quick(int *,int,int);
#define N 10

int main(void)
{
static int a[]={41,24,76,11,45,64,21,69,19,36};
int k,b=0;


quick(a,0,N-1);

for(k=0;k<N;k++)
printf(" %d",a[k]);
printf("\r\n");return 0;
}

void quick(int a[],int left,int right)
{
int s,t,i,j,z;

z=(a[left]<a[left+1]?1:0);
j=a[left+z];

if(right>left){
while(1){
t=right;
i=left+z;
while(!(a[++i]>j) && i<N);
while(!(a[--t]<j) && t>0);
if(i>=t){
break;
}
s=a[i];
a[i]=a[t];
a[t]=s;
}
if (a[left+z]>a[right])
{
s=a[right];
a[right]=j;
a[left+z]=s;
}
quick(a,left,t);
quick(a,t+(a[left]>a[left+1]?0:1),right);
}
}

でいきますが、やはり質問者さんのリストですと、
条件網羅がぬけておりピボットが正しく打たれていないようです。

投稿日時 - 2007-05-30 01:03:09

お礼

回答ありがとうございます<_ _>

追加で質問なのですが
z=(a[left]<a[left+1]?1:0);
の「?1:0」とは何をしているのでしょうか?

あつかましくてすいませんが
よろしければお願いできないでしょうか?
お願いします<_ _>

投稿日時 - 2007-05-30 11:02:40

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(5)

ANo.5

>z=(a[left]<a[left+1]?1:0);
>の「?1:0」とは何をしているのでしょうか?
3項演算子の体裁はTacosanさんの仰るとおりです。

ようは左から見て、一番目数値>二番目数値 のとき、
通常進行ですとピボットが二番目数値となるため、あえて
ピボット(リストでは t のこと)をインクリメントさせないよう
にします。
一番目数値<二番目数値のときは通常処理(t+1)を行います。

質問者さんのリストから修正した点は、
・最小値検索と最大値検索のスルー条件が逆である
・入れ替えをした際、サイドポジション(left,right)に戻っていない
・その他もろもろ・・(すみません割愛で)

投稿日時 - 2007-05-30 19:21:39

お礼

細かい解説までありがとうございました<_ _>
大変ためになりました!

また機会がありましたらどうかよろしくお願いします<_ _>
失礼いたします。

投稿日時 - 2007-05-31 11:35:58

ANo.4

「3項演算子」というもので, 「A?B:C」の形で使います. これは
1.まず A を評価 (= 計算) し (A に関する副作用はここで全て処理する),
2.それが 0 でなければ B を, 0 なら C を評価する.
というものです. 副作用については, 例えば A が「*p++ != 0」という式だったとすると, この ++ の処理は B や C の評価を行う前に終了している (従って B や C で p を参照すると, その値は「この式を評価する前の p の値」より 1 だけ大きくなる) という意味です.
今の場合, 比較演算子は 0 か 1 を返すので実際には不要といえば不要ですが「0 か 1 という数字を使う」ということを意識しているのでこの形になっているものと思われます.

投稿日時 - 2007-05-30 13:04:20

ANo.2

個人的にクイックソートは (バグを作り込む自信があるので) 嫌いなんだけど....
ぱっと見たところ,
while(a[++i]>j);
while(a[--t]<j && t>0);
の 2行は危険な感じがします. 前者には i <= right のチェックがあるべきだと思うし, 後者は t>0 じゃなくって t > left (>= かも) ではないでしょうか?

投稿日時 - 2007-05-29 23:46:02

あなたにオススメの質問