こんにちは。
以下の(1)(2)の順に回答します。
(1)無限ループについて
(2)クイックソートの実装の方法について
(1)無限ループについて
以下のように、ご質問にあるコードを、私の手元にある環境(CentOS 6.6)で、
そのままコピペしてCのソースコードを作り、コンパイル、実行してみたところ
無限ループにはならず、ソートはされていないもののプログラムとしては正常
終了しました。以下そのログです。
[ykt68@sakura-vps] cat /etc/redhat-release
CentOS release 6.6 (Final)
[ykt68@sakura-vps] date
2015年 5月 10日 日曜日 11:32:42 JST
[ykt68@sakura-vps] cat question9624.c
lang
1#include<stdio.h>
2#define swap(type,x,y) do{type tmp=x;x=y;y=tmp;}while(0)
3
4int *quick(int array[],int left,int right){
5 int l,pl,pr,piv=array[left];
6 while(pl<pr){
7 for(pl=left;piv>array[pl];pl++){}
8 for(pr=right;piv<array[pr];pr--){}
9 swap(int,array[pr],array[pl]);
10 }
11 printf("pl=%d\npr=%d\n",pl,pr);
12 if(pr-left>1) quick(array,left,pr);
13 if(right-pl>1) quick(array,pl,right);
14
15 return array;
16}
17
18int main(){
19 int i,array[10]={4,6,2,5,3,9,7,1,0,8};
20 puts("input array\t: ");
21 for(i=0;i<10;i++){
22 printf("%d ",array[i]);
23 }
24 putchar('\n');
25 quick(array,0,(sizeof(array)/sizeof(array[0]))-1);
26 puts("devided array\t: ");
27 for(i=0;i<10;i++){
28 printf("%d ",array[i]);
29 }
30 putchar('\n');
31 return 0;
32}
[ykt68@sakura-vps] cc -o question9624 question9624.c
[ykt68@sakura-vps] ls -l question9624 question9624.c
-rwxrwxr-x 1 ykt68 ykt68 10292 5月 10 11:33 2015 question9624
-rw-rw-r-- 1 ykt68 ykt68 791 5月 10 11:33 2015 question9624.c
[ykt68@sakura-vps] ./question9624
input array :
4 6 2 5 3 9 7 1 0 8
pl=4195440
pr=0
devided array :
4 6 2 5 3 9 7 1 0 8
[ykt68@sakura-vps]
(2)クイックソートの実装の方法について
ご質問に挙がっているコードについて、「ここが怪しいのでは?」と
思う点は以下の 1. と2. です。
- plとprの初期値が不明
quick()関数の冒頭で宣言されている、plとpr が、while(pl<pr)の
条件判定に使われる前に、何らかの値で初期化されていないために
意図の見えないコードになっていると思います
たとえば、quickの冒頭に、以下のようにデバッグログを2行追加します。
lang
1int *quick(int array[],int left,int right){
2
3 int l,pl,pr,piv=array[left];
4
5 printf("pl=%d\npr=%d\n",pl,pr); /* 追加 */
6
7 while(pl<pr){
8 printf("in while block"); /* 追加 */
上記で実行すると出力は以下のようになりました。
input array :
4 6 2 5 3 9 7 1 0 8
pl=4195440
pr=0
pl=4195440
pr=0
devided array :
4 6 2 5 3 9 7 1 0 8
つまり、while の中には1度も入っていかないです。
ただし、初期化しないplとprに値として何が入っているかは、
環境によって違うかもしれません。
- 配列の中で、基準の値にする要素の選びかた
クイックソートでは、通常、配列の真ん中近くの要素の値を基準にするのですが、
質問に挙がっているコードですと、各要素と比較しているpivが、
としていて、左端の要素の値にしています。
クイックソートを実装したコードを見ると、それがどんな言語で書かれた
ものであっても、ソート対象の配列が、(Quickソートが最も効率を発揮する、
理想的な流れとして)2分の1、4分の1、8分の1、という2の累乗分の1
の要素数の配列に、基準値の左右に分割されていき、分けられなくったところ
まで行き着いたときにソートされていて終了、というようなイメージを持てます。
イメージを持てるというのは、言い換えると
「絵として想像できる」
という意味です。
上記をふまえて、再度、参考書の説明を読まれてみたうえで、
再度、ご質問に挙げられているコードを見直してみては
いかがでしょうか。
以上、ご参考になれば幸いです。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2015/05/10 04:46
2015/05/10 05:34