C言語：クイックソートのトレースで分からないところ

Question

前提・実現したいこと

C言語のクイックソートのプログラムのトレースを行っています。
そこで、どうしても理解できない疑問が起こりました。

発生している問題・エラーメッセージ

下記の「実行結果」で、(*10)→(*6)、および、(*10)→(*9)にジャンプする箇所があるのですが、なぜそんなことになるのか、いくら考えても分かりません。いろいろprintf()を埋め込んでいって、もうわけが分からなくなってしまいました。

該当のソースコード

#include <stdio.h>
#include <stdlib.h>

#define N 10

void qksort(int d[], int top, int end);

int main(void)
{
    int i;
    int d[] = {11081, 5137, 24671, 5233, 26229,
               14891, 25719, 11578, 5160, 4907};
    
    printf("【整列前】\n");
    for (i = 0; i < N; i++)
        printf("%d ", d[i]);
    printf("\n");
    
    qksort(d, 0, N - 1);
    
    printf("【整列後】\n");
    for (i = 0; i < N; i++)
        printf("%d ", d[i]);
    printf("\n");
    return EXIT_SUCCESS;
}

void qksort(int d[], int top, int end)
{
    int key, wk, i, j;
    int k;                                        /* デバッグ用 */
    
    printf("(*1)\n");                             /* デバッグ用 */
    key = d[(top+end)/2];
    printf("key = %d\n", key);                    /* デバッグ用 */
    i = top - 1;
    j = end + 1;
    while (1) {
        printf("(*2)\n");                         /* デバッグ用 */
        while (d[++i] < key)
            ;
        printf("i = %d\n", i);                    /* デバッグ用 */
        while (d[--j] > key)
            ;
        printf("j = %d\n", j);                    /* デバッグ用 */
        if (i >= j)
            break;
        wk = d[i];
        d[i] = d[j];
        d[j] = wk;
        for (k = 0; k < N; k++)                   /* デバッグ用 */
            printf(" %d", d[k]);                  /* デバッグ用 */
        printf("\n\n");                           /* デバッグ用 */
    }
    printf("(*3)\n");                             /* デバッグ用 */
    printf("top = %d, i-1 = %d\n", top, i-1);     /* デバッグ用 */
	printf("(*4)\n");                             /* デバッグ用 */
    if (top < i-1) {
		printf("(*5)\n");                         /* デバッグ用 */
        printf("qksort(d, %d, %d);\n", top, i-1); /* デバッグ用 */
        qksort(d, top, i - 1); /* 左半分をクイックソート */
    }
	printf("(*6)\n");                             /* デバッグ用 */
    printf("j+1 = %d, end = %d\n", j+1, end);     /* デバッグ用 */
	printf("(*7)\n");                             /* デバッグ用 */
    if (j+1 < end) {
		printf("(*8)\n");                         /* デバッグ用 */
        printf("qksort(d, %d, %d);\n", j+1, end); /* デバッグ用 */
        qksort(d, j + 1, end); /* 右半分をクイックソート */
    }
	printf("(*9)\n");                             /* デバッグ用 */
	printf("(*10)\n");                             /* デバッグ用 */
}

試したこと

すでに上のソースコードに埋め込んでありますが、printf()を使って実行の流れを可視化させました。その実行結果を、下に示します。

(実行結果)

【整列前】
11081 5137 24671 5233 26229 14891 25719 11578 5160 4907
(*1)
key = 26229
(*2)
i = 4
j = 9
 11081 5137 24671 5233 4907 14891 25719 11578 5160 26229

(*2)
i = 9
j = 8
(*3)
top = 0, i-1 = 8
(*4)
(*5)
qksort(d, 0, 8);
(*1)
key = 4907
(*2)
i = 0
j = 4
 4907 5137 24671 5233 11081 14891 25719 11578 5160 26229

(*2)
i = 1
j = 0
(*3)
top = 0, i-1 = 0
(*4)
(*6)
j+1 = 1, end = 8
(*7)
(*8)
qksort(d, 1, 8);
(*1)
key = 11081
(*2)
i = 2
j = 8
 4907 5137 5160 5233 11081 14891 25719 11578 24671 26229

(*2)
i = 4
j = 4
(*3)
top = 1, i-1 = 3
(*4)
(*5)
qksort(d, 1, 3);
(*1)
key = 5160
(*2)
i = 2
j = 2
(*3)
top = 1, i-1 = 1
(*4)
(*6)
j+1 = 3, end = 3
(*7)
(*9)
(*10)
(*6)
j+1 = 5, end = 8
(*7)
(*8)
qksort(d, 5, 8);
(*1)
key = 25719
(*2)
i = 6
j = 8
 4907 5137 5160 5233 11081 14891 24671 11578 25719 26229

(*2)
i = 8
j = 7
(*3)
top = 5, i-1 = 7
(*4)
(*5)
qksort(d, 5, 7);
(*1)
key = 24671
(*2)
i = 6
j = 7
 4907 5137 5160 5233 11081 14891 11578 24671 25719 26229

(*2)
i = 7
j = 6
(*3)
top = 5, i-1 = 6
(*4)
(*5)
qksort(d, 5, 6);
(*1)
key = 14891
(*2)
i = 5
j = 6
 4907 5137 5160 5233 11081 11578 14891 24671 25719 26229

(*2)
i = 6
j = 5
(*3)
top = 5, i-1 = 5
(*4)
(*6)
j+1 = 6, end = 6
(*7)
(*9)
(*10)
(*6)
j+1 = 7, end = 7
(*7)
(*9)
(*10)
(*6)
j+1 = 8, end = 8
(*7)
(*9)
(*10)
(*9)
(*10)
(*9)
(*10)
(*6)
j+1 = 9, end = 9
(*7)
(*9)
(*10)
【整列後】
4907 5137 5160 5233 11081 11578 14891 24671 25719 26229

補足情報（FW/ツールのバージョンなど）

OSはWindows10、コンパイラはVisual Studio2012です。

前提・実現したいこと

C言語のクイックソートのプログラムのトレースを行っています。
そこで、どうしても理解できない疑問が起こりました。

発生している問題・エラーメッセージ

下記の「実行結果」で、(*10)→(*6)、および、(*10)→(*9)にジャンプする箇所があるのですが、なぜそんなことになるのか、いくら考えても分かりません。いろいろprintf()を埋め込んでいって、もうわけが分からなくなってしまいました。

該当のソースコード

#include <stdio.h>
#include <stdlib.h>

#define N 10

void qksort(int d[], int top, int end);

int main(void)
{
    int i;
    int d[] = {11081, 5137, 24671, 5233, 26229,
               14891, 25719, 11578, 5160, 4907};
    
    printf("【整列前】\n");
    for (i = 0; i < N; i++)
        printf("%d ", d[i]);
    printf("\n");
    
    qksort(d, 0, N - 1);
    
    printf("【整列後】\n");
    for (i = 0; i < N; i++)
        printf("%d ", d[i]);
    printf("\n");
    return EXIT_SUCCESS;
}

void qksort(int d[], int top, int end)
{
    int key, wk, i, j;
    int k;                                        /* デバッグ用 */
    
    printf("(*1)\n");                             /* デバッグ用 */
    key = d[(top+end)/2];
    printf("key = %d\n", key);                    /* デバッグ用 */
    i = top - 1;
    j = end + 1;
    while (1) {
        printf("(*2)\n");                         /* デバッグ用 */
        while (d[++i] < key)
            ;
        printf("i = %d\n", i);                    /* デバッグ用 */
        while (d[--j] > key)
            ;
        printf("j = %d\n", j);                    /* デバッグ用 */
        if (i >= j)
            break;
        wk = d[i];
        d[i] = d[j];
        d[j] = wk;
        for (k = 0; k < N; k++)                   /* デバッグ用 */
            printf(" %d", d[k]);                  /* デバッグ用 */
        printf("\n\n");                           /* デバッグ用 */
    }
    printf("(*3)\n");                             /* デバッグ用 */
    printf("top = %d, i-1 = %d\n", top, i-1);     /* デバッグ用 */
	printf("(*4)\n");                             /* デバッグ用 */
    if (top < i-1) {
		printf("(*5)\n");                         /* デバッグ用 */
        printf("qksort(d, %d, %d);\n", top, i-1); /* デバッグ用 */
        qksort(d, top, i - 1); /* 左半分をクイックソート */
    }
	printf("(*6)\n");                             /* デバッグ用 */
    printf("j+1 = %d, end = %d\n", j+1, end);     /* デバッグ用 */
	printf("(*7)\n");                             /* デバッグ用 */
    if (j+1 < end) {
		printf("(*8)\n");                         /* デバッグ用 */
        printf("qksort(d, %d, %d);\n", j+1, end); /* デバッグ用 */
        qksort(d, j + 1, end); /* 右半分をクイックソート */
    }
	printf("(*9)\n");                             /* デバッグ用 */
	printf("(*10)\n");                             /* デバッグ用 */
}

試したこと

すでに上のソースコードに埋め込んでありますが、printf()を使って実行の流れを可視化させました。その実行結果を、下に示します。

(実行結果)

【整列前】
11081 5137 24671 5233 26229 14891 25719 11578 5160 4907
(*1)
key = 26229
(*2)
i = 4
j = 9
 11081 5137 24671 5233 4907 14891 25719 11578 5160 26229

(*2)
i = 9
j = 8
(*3)
top = 0, i-1 = 8
(*4)
(*5)
qksort(d, 0, 8);
(*1)
key = 4907
(*2)
i = 0
j = 4
 4907 5137 24671 5233 11081 14891 25719 11578 5160 26229

(*2)
i = 1
j = 0
(*3)
top = 0, i-1 = 0
(*4)
(*6)
j+1 = 1, end = 8
(*7)
(*8)
qksort(d, 1, 8);
(*1)
key = 11081
(*2)
i = 2
j = 8
 4907 5137 5160 5233 11081 14891 25719 11578 24671 26229

(*2)
i = 4
j = 4
(*3)
top = 1, i-1 = 3
(*4)
(*5)
qksort(d, 1, 3);
(*1)
key = 5160
(*2)
i = 2
j = 2
(*3)
top = 1, i-1 = 1
(*4)
(*6)
j+1 = 3, end = 3
(*7)
(*9)
(*10)
(*6)
j+1 = 5, end = 8
(*7)
(*8)
qksort(d, 5, 8);
(*1)
key = 25719
(*2)
i = 6
j = 8
 4907 5137 5160 5233 11081 14891 24671 11578 25719 26229

(*2)
i = 8
j = 7
(*3)
top = 5, i-1 = 7
(*4)
(*5)
qksort(d, 5, 7);
(*1)
key = 24671
(*2)
i = 6
j = 7
 4907 5137 5160 5233 11081 14891 11578 24671 25719 26229

(*2)
i = 7
j = 6
(*3)
top = 5, i-1 = 6
(*4)
(*5)
qksort(d, 5, 6);
(*1)
key = 14891
(*2)
i = 5
j = 6
 4907 5137 5160 5233 11081 11578 14891 24671 25719 26229

(*2)
i = 6
j = 5
(*3)
top = 5, i-1 = 5
(*4)
(*6)
j+1 = 6, end = 6
(*7)
(*9)
(*10)
(*6)
j+1 = 7, end = 7
(*7)
(*9)
(*10)
(*6)
j+1 = 8, end = 8
(*7)
(*9)
(*10)
(*9)
(*10)
(*9)
(*10)
(*6)
j+1 = 9, end = 9
(*7)
(*9)
(*10)
【整列後】
4907 5137 5160 5233 11081 11578 14891 24671 25719 26229

補足情報（FW/ツールのバージョンなど）

OSはWindows10、コンパイラはVisual Studio2012です。

Answer 1

再帰してるんだから、呼び出した関数が終了(*10を出力)したら、呼び出し元に戻って、関数qsort呼び出し直後の処理(6や9の出力)をしますよ。

Comments

[sanshirou]

あ、そうですね(照れ笑い)…。奥歯に挟まった物が取れたように爽快です。ありがとうございました。

Answer 2

printf の入れ方が混乱の原因と思います。
流れを追うのでしたら、関数の始まりと終わり(この場合でしたら1と10)の対応をハッキリさせないと、いつ何の処理が始まり・終わったのかの区別がつきません。

良くあるのは、関数に入ったら entryやstart、出るときはreturnやendという文字列と共に、引数を表示するものです。(呼ぶ側ではなく呼ばれる側で表示します。)

void qksort( 略 )
{
  printf("qksort entry. top=%d, end=%d¥n", top, end);

(略)

  printf("qksort return. top=%d, end=%d¥n", top, end);
}

もちろん return する場所が複数あれば全てに return の表示を入れ、それぞれにそれこそ番号等固有の文字列を付けます。
このようにすれば、少しは混乱を減らせるのではないでしょうか。

Answer 3

参考までに再帰関数の呼び出しを図示してみました。
「└→」が qksort 関数の開始
「←┘」が qksort 関数の終了
になります。

└→
  └→
  (*6)
    └→
      └→
      (*6)
      (*9)
      (*10)
      ←┘
      (*6)
      └→
        └→
          └→
          (*6)
          (*9)
          (*10)
          ←┘
          (*6)
          (*9)
          (*10)
        ←┘
        (*6)
        (*9)
        (*10)
      ←┘
      (*9)
      (*10)
    ←┘
    (*9)
    (*10)
  ←┘
  (*6)
  (*9)
  (*10)
←┘

Comments

[sanshirou]

ご親切に、ありがとうございました。自分で書けるようによく理解しておきます。