クイックソートの比較交換回数について

クイックソートの比較交換回数を変数countで計算し、表示させようとしているのですがうまくいきません。
改善策を教えていただけないでしょうか。

/* クイックソート */
void quickSort(randomlist_t data[],int n){ /* 実質的な処理は何もせず、クイックソートを実際に行う関数を呼び出すのみ */
int count = 0;
quickSort_1(data,0,n-1,count);
printf("count:%d\n",count);
}
/* 実際にクイックソートを行う関数 */
void quickSort_1(randomlist_t data[],int l,int r,int count){
int v;
if(l >= r) /* 整列する要素が1つなら、何もしないでリターンする */
return;
v = partition(data,l,r,count); /* 枢軸vを基準に分割する */
quickSort_1(data,l,v-1,count); /* 左の部分の配列a[l]～a[v-1]を整列する */
quickSort_1(data,v+1,r,count); /* 右の部分の配列a[v+1]～a[r]を整列する */
}

/* 配列a[l]～a[r]を分割する。枢軸の添え字を返す */
int partition(randomlist_t data[],int l,int r,int count){
int i,j,pivot;
randomlist_t t;

i = l - 1; j = r; /* ポインタiとjを初期化する */
pivot = data[r].no; /* 一番右端の要素を枢軸にする */
for(;;){ /* ポインタiとjとがぶつかるまで繰り返す */
while(data[++i].no < pivot)
count++; /* ポインタiを右へ進める */
while(i < --j && pivot < data[j].no)
count++; /* ポインタjを左へ進める */
if(i >= j)
break; /* ポインタiとjがぶつかったらループを抜ける */
t = data[i]; data[i] = data[j], data[j] = t; /* iの指す要素とjの指す要素を交換する */
count++;
}
t = data[i]; data[i] = data[r]; data[r] = t; /* a[i]と枢軸を交換する */
count++;
return i;
}

No.2 ベストアンサー 回答者： kmee 回答日時： 2011/07/24 17:11

「値渡し」、聞いたこと無いですか?

Cの関数の引数は「値渡し」といって、値のコピーを作ります。
void quickSort_1(randomlist_t data[],int l,int r,int count)
と宣言した中の変数countは
quickSort_1(data,0,n-1,count);
と呼び出した変数 count のコピーでしかありません。コピーを書き換えてもオリジナルには変化はありません。

オリジナルを変えたかったら、ポインタを使ってオリジナルのアドレスを渡して、関数側でその実体にアクセスするようにします。

では、dataがなぜソートされるか、というと、Cではほとんどの場合、配列とポインタは同等に扱われます。そのため、添字を使って配列の中を操作するのは、ポインタを使って実体を操作するのと同じことになるからです。

この回答への補足

全てcountをポインタを使った表現にしてみましたが、結果は変わりませんでした…

/* クイックソート */
void quickSort(randomlist_t data[],int n){ /* 実質的な処理は何もせず、クイックソートを実際に行う関数を呼び出すのみ */
int *count = 0;
quickSort_1(data,0,n-1,*count);
printf("count:%d\n",*count);
}

/* 実際にクイックソートを行う関数 */
void quickSort_1(randomlist_t data[],int l,int r,int *count){
int v;
if(l >= r) /* 整列する要素が1つなら、何もしないでリターンする */
return;
v = partition(data,l,r,*count); /* 枢軸vを基準に分割する */
quickSort_1(data,l,v-1,*count); /* 左の部分の配列a[l]～a[v-1]を整列する */
quickSort_1(data,v+1,r,*count); /* 右の部分の配列a[v+1]～a[r]を整列する */
}

/* 配列a[l]～a[r]を分割する。枢軸の添え字を返す */
int partition(randomlist_t data[],int l,int r,int *count){
int i,j,pivot;
randomlist_t t;

i = l - 1; j = r; /* ポインタiとjを初期化する */
pivot = data[r].no; /* 一番右端の要素を枢軸にする */
for(;;){ /* ポインタiとjとがぶつかるまで繰り返す */
while(data[++i].no < pivot)
(*count)++; /* ポインタiを右へ進める */
while(i < --j && pivot < data[j].no)
(*count)++; /* ポインタjを左へ進める */
if(i >= j)
break; /* ポインタiとjがぶつかったらループを抜ける */
t = data[i]; data[i] = data[j], data[j] = t; /* iの指す要素とjの指す要素を交換する */
(*count)++;
}
t = data[i]; data[i] = data[r]; data[r] = t; /* a[i]と枢軸を交換する */
(*count)++;
return i;
}

補足日時：2011/07/24 17:38

この回答へのお礼

教えていただいてありがとうございます。

説明を丁寧にしていただいたのにもかかわらず、自分の勉強不足のためにさらに説明していただくという形になって申し訳ありませんでした。
それにもかかわらず、さらに基本について分かりやすいように丁寧に説明していただけて感謝しています。

ポインタについては再度しっかり勉強し直したいと思います。

お礼日時：2011/07/24 23:35

No.5 回答者： kmee 回答日時： 2011/07/24 22:46

> 全てcountをポインタを使った表現にしてみましたが、結果は変わりませんでした…

変わったでしょ。「エラーになってコンパイルが通らない」っていうように。
あるいは、エラーの出る箇所が変わるとか。

patition関数の定義自体は正しいですが、それを呼び出す側が間違ってます。

int * p
と宣言したら
p はポインタで、アドレスが入っている。関数では int * で受ける。
*p は pが示す実体で int型

int c
と宣言したら
cは変数で int型。
&cはcのアドレスで、 p=&cとポインタに代入できるし、関数では int * で受ける

このあたりの対応がバラバラですよね?
何と何が対応しているとかをよく考えて使いましょう。
わからないようなら、とりあえずはグローバル変数でやってもいいですけど。
ポインタはCやる上で避けて通れないので、どこかでちゃんと勉強しましょう。

この回答へのお礼

ポインタについては理解不足なので、今回はグローバル変数でやることにしました。

ポインタについてほとんど理解できていなかったのですが、この投稿によって理解が深まりました。
今後、しっかり勉強しようと思います。

ありがとうございました。

お礼日時：2011/07/24 23:49

No.4 回答者： Tacosan 回答日時： 2011/07/24 22:30

「ポインタを使った」て....

全く理解できていないポインタを無理に使おうとせず, #3 で言われるように大域変数で回避したら?

この回答へのお礼

おっしゃる通りです。
全く間違ったポインタ使い方をしてしまい、お恥ずかしい限りです。

ポインタを使う前に、ポインタについて理解することに取り組みたいと思います。

全く理解していない投稿のせいで、不愉快な思いをさせてしまっていたら、本当に申し訳ありませんでした。

お礼日時：2011/07/24 23:45

No.3 回答者： mk48a 回答日時： 2011/07/24 17:11

ぱっと見で、

countは値渡しされているので、関数内で変更しても呼び出し側では変更されません。
count変数をアドレス渡しにするか、グローバル変数にしてみては？

この回答へのお礼

今回はグローバル変数でやることにしました。
ご助言ありがとうございました。

お礼日時：2011/07/24 23:37

No.1 回答者： episteme 回答日時： 2011/07/24 15:58

なにが/どのように「うまくいきません」なのでしょうか？

この回答へのお礼

説明不足で申し訳ありませんでした。

以後は、そのような点もはっきり質問文に書くように気をつけます。

お礼日時：2011/07/24 23:38