質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

解決済

2回答

2744閲覧

デバッグのためにprintfを挿入した時だけ無限ループが起きます

akamakku

総合スコア191

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

0グッド

1クリップ

投稿2015/05/10 01:39

クイックソートを勉強中で参考書の説明の部分だけを見て自分なりに書いてみたのですが、うまくいかず、どこがおかしいのかなとprintfで変数の中身を表示しようとすると無限ループになって最後にコアダンプします。printfを挿入する以外ほかはいじっていません。
挿入したprintfは関数quickの7行目のやつです。
そもそもquickソートができていないのはわかっているのですが、無限ループになってしまうのは自分がまだ知らないタブーを犯してしまっているからなのか、なぜなのかわかる方がいたら教えていただきたいです。ここはquickソート自体のアドバイスももらえたら嬉しいです。

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} 33

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

ベストアンサー

こんにちは。
以下の(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. です。

  1. 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に値として何が入っているかは、
環境によって違うかもしれません。

  1. 配列の中で、基準の値にする要素の選びかた

クイックソートでは、通常、配列の真ん中近くの要素の値を基準にするのですが、
質問に挙がっているコードですと、各要素と比較しているpivが、

lang

1piv=array[left];

としていて、左端の要素の値にしています。

クイックソートを実装したコードを見ると、それがどんな言語で書かれた
ものであっても、ソート対象の配列が、(Quickソートが最も効率を発揮する、
理想的な流れとして)2分の1、4分の1、8分の1、という2の累乗分の1
の要素数の配列に、基準値の左右に分割されていき、分けられなくったところ
まで行き着いたときにソートされていて終了、というようなイメージを持てます。
イメージを持てるというのは、言い換えると
「絵として想像できる」
という意味です。

上記をふまえて、再度、参考書の説明を読まれてみたうえで、
再度、ご質問に挙げられているコードを見直してみては
いかがでしょうか。

以上、ご参考になれば幸いです。

投稿2015/05/10 03:23

jun68ykt

総合スコア9058

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

akamakku

2015/05/10 04:46

whileの条件にplとprを使っていたのを忘れて、forで初期化すればいいやと思っていました!!! ありがとうございます!がんばります!
jun68ykt

2015/05/10 05:34

こんにちは。 私の後もご回答されているRS-offlineさんのおっしゃるように、 元のコードのquickの初めで  int l,pl,pr,piv=array[left]; の後に pl = left; pr = right; を追加して、かつ、左右について再帰するところを  if(pr-left>1) quick(array,left,pl-1);  if(right-pl>1) quick(array,pr+1,right); とすると、確かにソートされた結果が  0 1 2 3 4 5 6 7 8 9 が出力されました。 ただし、quickを上記の修正をしたもののまま、かつ、main() の最初で 作るarrayを以下のように0を10個 array[10]={0,0,0,0,0,0,0,0,0,0}; にすると、自分の環境ではやはり無限ループに入ってしまいました。 配列の中に同じ値が複数あっても、正しくソートされるのが 望ましいところなので、この辺は質問者さんの >がんばり に期待したいと思います。いいコードになるようお祈りしております。
guest

0

plとprをleftとrightで初期化してからwhileループに入ることをお勧めします.
分岐後のquickへの引数を変更したら動きました.

lang

1if(pr-left>1) quick(array,left,pr); 2if(right-pl>1) quick(array,pl,right); 3//これを下記に変更しました. 4if(pr-left>1) quick(array,left,pl-1); 5if(right-pl>1) quick(array,pr+1,right);

投稿2015/05/10 04:12

RS-offline

総合スコア13

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

akamakku

2015/05/10 05:10

whileの条件にplとprを使っていたのを忘れて、forで初期化すればいいやと思っていました!!! シンプルで的確なアドバイスありがとうございました!
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問