ｋ番目に小さい数

クイックソートを使いｋ番目に小さい数を返す（平成27年 春 午後問8）

　問題のイメージがどうしてもトレースできないので、プログラムを打ってみました。（ｃ言語です）
　添え字がゼロから始まるので、x[0]に捨てデータを入れて、個数nを計算するときに、そのデータ分を 1 引いてあります。

ル－プの途中で break があるのは伏兵

　この問題の様に、ループの最後まで行ってループを抜けないで、途中で中途半端に break がある（出題時の行数は、16-17行）のは、どうも好きにはなれません。
　下まで行って終わりかと思ったら、そうではなくて、途中までまたちょっと帰ってから、いくらかの処理をさせるのでした。
　「構造化言語」と言われだした頃にプログラムを始めたので、breakを使う習慣など全くないもんだから、こんなのはめちゃくちゃ気持ちが悪い。

ル－プのカウントを制御してないのも嫌

　それともう一つ、ル－プのカウントで制御してない（出題時の行数は、10、13行）のも嫌らしいですね。問題の引っ掛けになっているので、わざとそうしているのでしょうが、そんなことをするから、分からなくなる。添え字の範囲を超えないような制御は、少々野暮ったくても、しておくべきでしょう。
　こんなん、間違いのもと。試験になんか出すな！

 #include <stdio.h> 

int main(){
  int x[] = {0,3,5,6,4,7,2,1};
    /* 最初の 0 はダミー　添え字が[1]から始まるため　*/
  int k = 3;  /* 取り出すk番目の数 */

  int i, j,m, n,Top,Last,Pivot,work;
  
  n = sizeof x / sizeof x[0] -1; /* データの個数 n */

  printf("データ数 n = %d \n", n);
  for (m = 1; m <= n; m++) {
    printf("x[%d]  =  %d \n",m, x[m]); /* m カウント変数 */
  }

  Top = 1;
  Last = n;
  while (Top < Last) {
    Pivot = x[k];
    printf("\n 大ループ Pivot = %d \n", Pivot); /* Pivot設定 */
    i = Top;
    j = Last;
    while (1) {
      while (x[i] < Pivot) {
        ++i;
        printf("i  =  %d \n", i); /* i　Pivotより小さい数の位置 */
      }
      while (Pivot < x[j]) {
        --j;
        printf("j  =  %d \n", j); /* j　Pivotより大きい数の位置 */
      }
      if (i >= j) {
        break;  /* ループから抜ける */
      }
      work = x[i];
      x[i] = x[j];
      x[j] = work;
      printf("\n入れ替えた x[%d] = %d と x[%d] = %d\n",i, x[i],j, x[j]);
        /* 大小の入れ替え */
      ++i;
      --j;
      for (m = 1; m <= n; m++) {
        printf("x[%d]  =  %d \n", m, x[m]); /* m カウント変数 */
      }
    }
    if (i <= k) {
      Top = j + 1;
      printf("i(%d)<= k(%d),j(%d)  Top位置設定  =  %d Last位置 =  %d \n",i,k,j, Top, Last);
        /* Topの位置設定 */
    }
    if (k <= j) {
      Last = i - 1;
      printf("i(%d), k(%d) <= j(%d)  Top位置  =  %d Last位置設定 =  %d \n",i,k,j, Top, Last);
        /* Topの位置設定 */
    }
  }
  printf(" \n\n ");
  printf(" n番目の数 = %d \n\n ", x[k]);
  for (m = 1; m <= n; m++) {
    printf("x[%d]  =  %d \n ", m, x[m]); /* m カウント変数 */
  }
  return 0;
}

　実行結果

データ数 n = 7
x[1]  =  3
x[2]  =  5
x[3]  =  6
x[4]  =  4
x[5]  =  7
x[6]  =  2
x[7]  =  1

 大ループ Pivot = 6
i  =  2
i  =  3

入れ替えた x[3] = 1 と x[7] = 6
x[1]  =  3
x[2]  =  5
x[3]  =  1
x[4]  =  4
x[5]  =  7
x[6]  =  2
x[7]  =  6
i  =  5

入れ替えた x[5] = 2 と x[6] = 7
x[1]  =  3
x[2]  =  5
x[3]  =  1
x[4]  =  4
x[5]  =  2
x[6]  =  7
x[7]  =  6
i(6), k(3) <= j(5)  Top位置  =  1 Last位置設定 =  5

 大ループ Pivot = 1
j  =  4
j  =  3

入れ替えた x[1] = 1 と x[3] = 3
x[1]  =  1
x[2]  =  5
x[3]  =  3
x[4]  =  4
x[5]  =  2
x[6]  =  7
x[7]  =  6
j  =  1
i(2)<= k(3),j(1)  Top位置設定  =  2 Last位置 =  5

 大ループ Pivot = 3

入れ替えた x[2] = 2 と x[5] = 5
x[1]  =  1
x[2]  =  2
x[3]  =  3
x[4]  =  4
x[5]  =  5
x[6]  =  7
x[7]  =  6
j  =  3
i(3)<= k(3),j(3)  Top位置設定  =  4 Last位置 =  5
i(3), k(3) <= j(3)  Top位置  =  4 Last位置設定 =  2


  n番目の数 = 3

 x[1]  =  1
 x[2]  =  2
 x[3]  =  3
 x[4]  =  4
 x[5]  =  5
 x[6]  =  7
 x[7]  =  6