quicksort.c

#define NULL 0

struct pair {
  int first;
  struct pair* rest;
};

void display(struct pair* ls) {
  if (ls == NULL) {
    printf("()");
    return;
  } else {
    printf("(%d", ls->first);
    printf(" . ");
    display(ls->rest);
    printf(")");
    return;
  }
}

struct pair* cons(int i, struct pair* ls){
  struct pair* new = malloc(sizeof(16));
  new->first = i;
  new->rest = ls;
  return new;
}

struct clos {
  int env;
  int(*f)(int,int);
};

struct pair* filter(struct clos* c, struct pair* ls){
  if (ls == NULL){
    return NULL;
  } else {
    if ((*c->f)(c->env, ls->first)) {
      return cons(ls->first, filter(c,ls->rest));
    } else{
      return filter(c, ls->rest);
    }
  }
}

struct pair* append(struct pair* ls1, struct pair* ls2){
  if (ls1 == NULL) {
    return ls2;
  } else {
    return cons(ls1->first,append(ls1->rest,ls2));
  }
}

int lt(int y, int x){
  return y < x;
}

int ge(int y, int x){
  return y >= x;
}

struct pair* quicksort(struct pair* ls) {
  if ((ls == NULL) ||
      ls->rest == NULL) {
    return ls;
  } else {
    int pivot = ls->first;
    struct pair* rst = ls->rest;
    struct clos* cl = malloc(16);
    cl->env = pivot;
    cl->f = (*lt);
    struct clos* cl2 = malloc(16);
    cl2->env = pivot;
    cl2->f = (*ge);
    return append(append(quicksort(filter(cl, rst)),
                         cons(pivot,NULL)),
                  quicksort(filter(cl2, rst)));
  }
}

struct pair* build_list(int(*f)(), int len){
  if (len == 0) {
    return NULL;
  } else {
    return cons((*f)(),build_list(f,len - 1));
  }
}

int mod(int x, int y) {
  if (x >= y) {
    return mod(x - y, y) ;
  } else {
    return x;
  }
}

int seed = 0;

int random() {
  int A = 12312;
  int C = 1;
  int MAX = 100;
  int p = mod(C + A * seed, MAX);
  seed = p;
  return p;
}

int main() {
  display(quicksort(build_list(&random,10000)));
  return 0;
}