gistfile1.txt

#include <stdio.h>
#include <stdlib.h>

// read the array a of n elements from fp
void reada(FILE *fp, int *a, int *n);

// output the array a of n elements
void printa(int *a, int n);

// randomized quick sort
void rqs(int *a, int left, int right);

void usage(void);

int main(int argc, char **argv)
{
    FILE *fp = NULL;
    int a[300], n;

    printf("randomized quick sort\n");

    if (argc != 2) usage();

    if ((fp = fopen(argv[1], "r")) == NULL) {
        fprintf(stderr, "can't open file\n");
        exit(1);
    }
    
	printf("befor sort\n");
    reada(fp, a, &n);
	printa(a, n);
    rqs(a, 0, n);
	printf("after sort\n");
    printa(a, n);
    
    return 0;
}

void reada(FILE *fp, int *a, int *n)
{
    int i;
    // read the number of elements
    fscanf(fp, "%d", n);
    
    // read elements
    for (i=0; i < *n; ++i) {
        fscanf(fp, "%d", &a[i]);
    }
}

void printa(int *a, int n)
{
    int i;
    for (i=0; i < n; ++i)
        fprintf(stdout, "%d ", a[i]);
    putchar('\n');
}

void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

// [left, right)
void rqs(int *a, int left, int right)
{
	int pivot = 0;
    int i=left, j=right-1;
	int k; // debug
	
	if (right-left <= 1) return;
	
    // define pivot
	pivot = a[(rand() % (right-left))+left];
    while (1) {
        while (a[i] <  pivot) i++;
        while (a[j] >  pivot) j--;
    	if (i >= j) break;
        swap(&a[i], &a[j]);
    	i++, j--;
    }
    rqs(a, left, i);
    rqs(a, i, right);
}

void usage(void)
{
    printf("<実行ファイル> <filepath>\n");
    exit(1);
}