STEP 2.1 パーティション (partition) - 分割コンパイル

問題

[実行例] 
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

[ヒント]
分割コンパイル
  • main関数のファイルを0201.cとするとき、#include "swap.h" すること (全体で共有する情報。swap関数のプロトタイプ）
  • gcc -c 0201.c
  • gcc -0 0201 0201.o swap.o
  • ./0201
注意
  • 教科書に沿った解答を
  • 自分なりの解答を作り出した場合は、教科書の疑似コード、プログラムを理解しておくこと
  • 教科書と異なるコードについては、必ずコメントを
  • 仲間で協力してください。

解答例

[プログラム] 

解答例 (swap.c, swap.hは再利用) 
#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) { /* おかしな値になったら停止。a[i] >= pivotのとき */ 
            i++;
        } 
        while (a[j] > pivot) { /* こちらはpivotより小さい値になったら停止 */ 
            j--;
        } 
        if (i <= j)  { /* おかしな2つを交換する。1つだけ残っているなら、下で交換 */ 
            swap(&a[i], &a[j]);
            i++; 
            j--;
        } 
     } 
     swap(&a[left], &a[j]); /* jの位置は、小さい部分の一番後ろ。pivotと交換　*/ 
     return (j) ;
 }