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

解決済

質問者：catsandanddogs
質問日時：2011/07/24 15:55
回答数：5件

クイックソートの比較交換回数を変数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;
}

通報する

この質問への回答は締め切られました。

質問の本文を隠す

回答 (5件)

ベストアンサー優先
最新から表示
回答順に表示

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

通報する

- 0
- 件

通報する

この回答へのお礼

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

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

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

通報する

お礼日時：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やる上で避けて通れないので、どこかでちゃんと勉強しましょう。