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

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

ただいまの
回答率

90.46%

  • C

    4676questions

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

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

解決済

回答 2

投稿

  • 評価
  • クリップ 1
  • VIEW 1,525

akamakku

score 178

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

int *quick(int array[],int left,int right){
    int l,pl,pr,piv=array[left];
    while(pl<pr){
        for(pl=left;piv>array[pl];pl++){}
        for(pr=right;piv<array[pr];pr--){}
        swap(int,array[pr],array[pl]);
    }
    printf("pl=%d\npr=%d\n",pl,pr);
    if(pr-left>1) quick(array,left,pr);
    if(right-pl>1) quick(array,pl,right);

    return array;
}

int main(){
    int i,array[10]={4,6,2,5,3,9,7,1,0,8};
    puts("input array\t: ");
    for(i=0;i<10;i++){
        printf("%d ",array[i]);
    }
    putchar('\n');
    quick(array,0,(sizeof(array)/sizeof(array[0]))-1);    
    puts("devided array\t: ");
    for(i=0;i<10;i++){
        printf("%d ",array[i]);
    }
    putchar('\n');
    return 0;
}
  • 気になる質問をクリップする

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+2

こんにちは。
以下の(1)(2)の順に回答します。

(1)無限ループについて
(2)クイックソートの実装の方法について

(1)無限ループについて

以下のように、ご質問にあるコードを、私の手元にある環境(CentOS 6.6)で、
そのままコピペしてCのソースコードを作り、コンパイル、実行してみたところ
無限ループにはならず、ソートはされていないもののプログラムとしては正常
終了しました。以下そのログです。

[ykt68@sakura-vps] cat /etc/redhat-releaseCentOS release 6.6 (Final)
[ykt68@sakura-vps] date
2015年  5月 10日 日曜日 11:32:42 JST
[ykt68@sakura-vps] cat question9624.c
#include<stdio.h>
#define swap(type,x,y) do{type tmp=x;x=y;y=tmp;}while(0)

int *quick(int array[],int left,int right){
    int l,pl,pr,piv=array[left];
    while(pl<pr){
        for(pl=left;piv>array[pl];pl++){}
        for(pr=right;piv<array[pr];pr--){}
        swap(int,array[pr],array[pl]);
    }
    printf("pl=%d\npr=%d\n",pl,pr);
    if(pr-left>1) quick(array,left,pr);
    if(right-pl>1) quick(array,pl,right);

    return array;
}

int main(){
    int i,array[10]={4,6,2,5,3,9,7,1,0,8};
    puts("input array\t: ");
    for(i=0;i<10;i++){
        printf("%d ",array[i]);
    }
    putchar('\n');
    quick(array,0,(sizeof(array)/sizeof(array[0]))-1);    
    puts("devided array\t: ");
    for(i=0;i<10;i++){
        printf("%d ",array[i]);
    }
    putchar('\n');
    return 0;
}
[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行追加します。
int *quick(int array[],int left,int right){

    int l,pl,pr,piv=array[left];

    printf("pl=%d\npr=%d\n",pl,pr);  /* 追加 */

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


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

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

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

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

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


投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/05/10 13:46

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

    キャンセル

  • 2015/05/10 14: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};
    にすると、自分の環境ではやはり無限ループに入ってしまいました。

    配列の中に同じ値が複数あっても、正しくソートされるのが
    望ましいところなので、この辺は質問者さんの
    >がんばり
    に期待したいと思います。いいコードになるようお祈りしております。

    キャンセル

0

plとprをleftとrightで初期化してからwhileループに入ることをお勧めします.
分岐後のquickへの引数を変更したら動きました.
if(pr-left>1) quick(array,left,pr);
if(right-pl>1) quick(array,pl,right);
//これを下記に変更しました.
if(pr-left>1) quick(array,left,pl-1);
if(right-pl>1) quick(array,pr+1,right);

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/05/10 14:10

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

    キャンセル

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

  • ただいまの回答率 90.46%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る

  • C

    4676questions

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