git.sur5r.net Git - cc65/blob - test/ref/sort.c

   1 /*
   2   !!DESCRIPTION!! simple quicksort, tests recursion
   3   !!ORIGIN!!      LCC 4.1 Testsuite
   4   !!LICENCE!!     own, freely distributeable for non-profit. read CPYRIGHT.LCC
   5 */
   6
   7 #include <stdlib.h>
   8 #include <stdio.h>
   9
  10 int in[] = {10, 32, -1, 567, 3, 18, 1, -51, 789, 0};
  11 int *xx;
  12
  13 /* exchange - exchange *x and *y */
  14 exchange(int *x,int *y) {
  15 int t;
  16
  17         printf("exchange(%d,%d)\n", x - xx, y - xx);
  18         t = *x; *x = *y; *y = t;
  19 }
  20
  21 /* partition - partition a[i..j] */
  22 int partition(int a[], int i, int j) {
  23 int v, k;
  24
  25         j++;
  26         k = i;
  27         v = a[k];
  28         while (i < j) {
  29                 i++; while (a[i] < v) i++;
  30                 j--; while (a[j] > v) j--;
  31                 if (i < j) exchange(&a[i], &a[j]);
  32         }
  33         exchange(&a[k], &a[j]);
  34         return j;
  35 }
  36
  37 /* quick - quicksort a[lb..ub] */
  38 void quick(int a[], int lb, int ub) {
  39         int k;
  40
  41         if (lb >= ub)
  42                 return;
  43         k = partition(a, lb, ub);
  44         quick(a, lb, k - 1);
  45         quick(a, k + 1, ub);
  46 }
  47
  48 /* sort - sort a[0..n-1] into increasing order */
  49 sort(int a[], int n) {
  50         quick(xx = a, 0, --n);
  51 }
  52
  53 /* putd - output decimal number */
  54 void putd(int n) {
  55         if (n < 0) {
  56                 putchar('-');
  57                 n = -n;
  58         }
  59         if (n/10)
  60                 putd(n/10);
  61         putchar(n%10 + '0');
  62 }
  63
  64 int main(void) {
  65         int i;
  66
  67         sort(in, (sizeof in)/(sizeof in[0]));
  68         for (i = 0; i < (sizeof in)/(sizeof in[0]); i++) {
  69                 putd(in[i]);
  70                 putchar('\n');
  71         }
  72
  73         return 0;
  74 }
  75