問題

10個の要素からなる配列a[] = {42,33,78,19,46,63,25,11,54,17} を、先頭の要素をpivotとして、分割せよ。swap関数を利用せよ。

もう少し、しつこくプリントするバージョン
i =< j　の間、a[i]とa[j]の交換
iとjが交差してしまった場合、pivotとa[j]の交換

BEFORE : 42  33  78  19  46  63  25  11  54  17

pivotより大きい要素 i =  2, a[2] = 78
pivotと等しいか小さい要素 j =  9, a[9] = 17
交換する a[2] = 78, a[9] = 17 || a[2] = 17, a[9] = 78
SWAPPED : 42  33  17  19  46  63  25  11  54  78

pivotより大きい要素 i =  4, a[4] = 46
pivotと等しいか小さい要素 j =  7, a[7] = 11
交換する a[4] = 46, a[7] = 11 || a[4] = 11, a[7] = 46
SWAPPED : 42  33  17  19  11  63  25  46  54  78

pivotより大きい要素 i =  5, a[5] = 63
pivotと等しいか小さい要素 j =  6, a[6] = 25
交換する a[5] = 63, a[6] = 25 || a[5] = 25, a[6] = 63
SWAPPED : 42  33  17  19  11  25  63  46  54  78

最後にpivotを交換する a[0] = 42, a[j] = a[5] = 25 || a[0] = 25, a[5] = 42
 pivot : a[5] = 42
 AFTER : 25  33  17  19  11  42  63  46  54  78

解答例

[プログラム]

#include "swap.h"

#define N 10
int a[N]={42,33,78,19,46,63,25,11,54,17};

int partition(int left, int right); /* 戻り値は、pivotの位置。そこから前後を見る */
void print_array(int left, int right);

void print_array(int from, int to) { /* from番目から to番目までの要素をプリント */
   int i;

   for (i = from ; i <= to; i ++)
     printf("%3d ", a[i]);

   printf("\n\n");

}

int main (void) {
   int left, right, j;

   left = 0;
   right = N - 1;

   /* パーティション前 */
   printf ("BEFORE :");
   print_array(left, right);

   /* パーティション */
   j = partition(left, right);

   /* パーティション後 pivotの前の配列、後ろの配列に注目 */
   printf("pivot : a[%d] = %d \n", j, a[j]);

   printf (" AFTER :");
   print_array(left, right);

   return (0);

}

int partition(int left, int right){
   int i, j, pivot;

   pivot = a[left];  /* pivotは、最左 */
   i = left+1;       /* 左から右へ動くポインター */
   j = right;        /* 右から左へ動くポインター */

   while (i <= j){  /* ポインタが逆転しない間 */
        while (i <= right && a[i] <= pivot) {   /* pivotより大きくなったら、停止 */
           i++;
        }

        printf("pivotより大きい要素 i =  %d, a[%d] = %d \n", i, i, a[i]); 

        while (a[j] > pivot) {   /* こちらはpivotより小さい値になったら停止 */
           j--;
        }

        printf("pivotと等しいか小さい要素 j =  %d, a[%d] = %d \n", j, j, a[j]);

        if (i <= j) {  /* おかしな2つを交換する。1つだけ残っているなら、下で交換 */
           printf("交換する a[%d] = %d, a[%d] = %d || a[%d] = %d, a[%d] = %d\n", i, a[i],j,a[j], i, a[j], j, a[i]);
           swap(&a[i], &a[j]); 
           i++;
           j--;

           /* 交換後 */
           printf ("SWAPPED :");
           print_array(left, right);
        }


   }

   printf("最後にpivotを交換する a[%d] = %d, a[j] = a[%d] = %d || a[%d] = %d, a[%d] = %d\n", left, a[left],j,a[j], left, a[j], j, a[left]);
   swap(&a[left], &a[j]);  /* jの位置は、小さい部分の一番後ろ。pivotと交換　*/
   return (j) ;
}