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 -o 0201 0201.o swap.o
  • ./0201.exe (./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;  /* 右から左へ動くポインター */


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

}