問題

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; /* 右から左へ動くポインター */ /* 疑似コードを基に、本体部分を作成してください */ 
    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) ; 
}