問題

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

BEFORE : 42  33  78  19  46  63  25  11  54  17    (42をpivotに、配列の要素を移動)

pivot : a[5] = 42 (pivotの42は、a[5]の位置に。a[5]が中心になる。a[0]-a[4]はa[5]より小さい要素、a[6]-a[9]には大きい要素)
 AFTER : 25  33  17  19  11  42  63  46  54  78

[ヒント]

このプログラムではswap関数もあわせて1つのファイルにしています。
教科書の解答は、分割コンパイルになっています。後のためにも分割コンパイルを使えるようにしよう。

解答例

[プログラム]

#include <stdio.h>
#define N 10
int a[N]={42,33,78,19,46,63,25,11,54,17};

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

void swap(int *x, int *y) {
   int tmp;

   tmp = *x;
   *x = *y;
   *y = tmp;

}

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;  /* 右から左へ動くポインター */


   /* 疑似コードを基に、本体部分を作成してください */

}