ch10/agent_sort.c55 lines
#include <stdlib.h>
#include <string.h>
#include "stn_sort.h"
static void merge(struct reading *r, struct reading *tmp,
size_t lo, size_t mid, size_t hi) {
size_t i = lo, j = mid, k = lo;
while (i < mid && j < hi)
tmp[k++] = (r[j].time_s < r[i].time_s) ? r[j++] : r[i++];
while (i < mid) tmp[k++] = r[i++];
while (j < hi) tmp[k++] = r[j++];
memcpy(r + lo, tmp + lo, (hi - lo) * sizeof *r);
}
static void msort(struct reading *r, struct reading *tmp,
size_t lo, size_t hi) {
if (hi - lo < 2) return;
size_t mid = lo + (hi - lo) / 2;
msort(r, tmp, lo, mid);
msort(r, tmp, mid, hi);
merge(r, tmp, lo, mid, hi);
}
/* Stable merge sort by time. O(n log n). */
int stn_merge_sort_by_time(struct reading *r, size_t n) {
if (r == NULL && n > 0) return -1;
struct reading *tmp = malloc(n * sizeof *tmp);
if (tmp == NULL) return -2;
if (n < 2) return 0; /* already sorted */
msort(r, tmp, 0, n);
free(tmp);
return 0;
}
static void swap(struct reading *x, struct reading *y) {
struct reading t = *x; *x = *y; *y = t;
}
/* Quicksort by time. O(n log n). */
static void qs(struct reading *r, size_t lo, size_t hi) {
if (hi - lo < 2) return;
int64_t pivot = r[lo].time_s;
size_t m = lo;
for (size_t i = lo + 1; i < hi; i++)
if (r[i].time_s < pivot) swap(&r[++m], &r[i]);
swap(&r[lo], &r[m]);
qs(r, lo, m);
qs(r, m + 1, hi);
}
int stn_quick_sort_by_time(struct reading *r, size_t n) {
if (r == NULL && n > 0) return -1;
qs(r, 0, n);
return 0;
}
ch10/bench.c30 lines
#define _POSIX_C_SOURCE 199309L
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "bench.h"
/* Seconds on a clock that never jumps backward. */
double now_s(void) {
struct timespec ts;
clock_gettime(CLOCK_MONOTONIC, &ts);
return (double)ts.tv_sec + (double)ts.tv_nsec / 1e9;
}
/* kind: "sorted", "reverse", "equal"; else random */
void fill(int *a, size_t n, const char *kind) {
for (size_t i = 0; i < n; i++) {
if (strcmp(kind, "sorted") == 0) a[i] = (int)i;
else if (strcmp(kind, "reverse") == 0)
a[i] = (int)(n - i);
else if (strcmp(kind, "equal") == 0) a[i] = 7;
else a[i] = rand();
}
}
/* 1 if a[0..n) is in nondecreasing order, else 0. */
int is_sorted(const int *a, size_t n) {
for (size_t i = 1; i < n; i++)
if (a[i - 1] > a[i]) return 0;
return 1;
}
ch10/bench.h7 lines
#ifndef BENCH_H
#define BENCH_H
#include <stddef.h>
double now_s(void);
void fill(int *a, size_t n, const char *kind);
int is_sorted(const int *a, size_t n);
#endif
ch10/count_insertion.c35 lines
#include <stdio.h>
#include <stdlib.h>
static unsigned long comparisons = 0;
void insertion_sort(int *a, size_t n) {
for (size_t i = 1; i < n; i++) {
int key = a[i];
size_t j = i;
while (j > 0 && (comparisons++, a[j - 1] > key)) {
a[j] = a[j - 1]; /* shift right by one */
j--;
}
a[j] = key;
}
}
int main(void) {
enum { N = 1000 };
static int a[N];
const char *names[] = {"sorted", "reverse", "random"};
for (int kind = 0; kind < 3; kind++) {
srand(42);
for (size_t i = 0; i < N; i++) {
if (kind == 0) a[i] = (int)i;
else if (kind == 1) a[i] = (int)(N - i);
else a[i] = rand() % 100000;
}
comparisons = 0;
insertion_sort(a, N);
printf("%-8s n=%d comparisons=%lu\n", names[kind], N,
comparisons);
}
return 0;
}
ch10/count_quick.c40 lines
#include <stdio.h>
#include <stdlib.h>
static unsigned long comparisons = 0;
static void swap(int *x, int *y) {
int t = *x; *x = *y; *y = t;
}
/* Partition a[lo..hi) around a[lo]; return pivot's index. */
static size_t partition_first(int *a, size_t lo, size_t hi) {
int pivot = a[lo];
size_t m = lo; /* a[lo+1..m] < pivot */
for (size_t i = lo + 1; i < hi; i++) {
comparisons++;
if (a[i] < pivot) {
m++;
swap(&a[m], &a[i]);
}
}
swap(&a[lo], &a[m]); /* pivot to its final slot */
return m;
}
static void quick_sort(int *a, size_t lo, size_t hi) {
if (hi - lo < 2) return; /* 0 or 1 element: sorted */
size_t p = partition_first(a, lo, hi);
quick_sort(a, lo, p);
quick_sort(a, p + 1, hi);
}
int main(void) {
enum { N = 1000 };
static int a[N];
srand(7);
for (size_t i = 0; i < N; i++) a[i] = rand() % 100000;
quick_sort(a, 0, N);
printf("random input: %lu comparisons\n", comparisons);
comparisons = 0; /* a is now sorted */
quick_sort(a, 0, N);
printf("sorted input: %lu comparisons\n", comparisons);
return 0;
}
ch10/fuzz.c15 lines
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "sorts.h"
static int cmp(const void *x, const void *y){int a=*(const int*)x,b=*(const int*)y;return (a>b)-(a<b);}
int main(void){
sort_fn f[]={insertion_sort,merge_sort,quick_sort_first,quick_sort_mid};
srand(1);
for(int t=0;t<20000;t++){
size_t n=rand()%60; int a[64],b[64],c[64]; int range=1+rand()%(t%3==0?3:1000);
for(size_t i=0;i<n;i++)a[i]=rand()%range;
memcpy(b,a,sizeof a); qsort(b,n,sizeof(int),cmp);
for(int k=0;k<4;k++){memcpy(c,a,sizeof a);f[k](c,n);if(memcmp(b,c,n*sizeof(int))){printf("FAIL %d n=%zu\n",k,n);return 1;}}
}
puts("all ok");return 0;}
ch10/harness.c40 lines
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include "bench.h"
#include "sorts.h"
/* Usage: ./harness ALG KIND NMIN NMAX (n doubles each row) */
int main(int argc, char **argv) {
if (argc != 5) return 2;
char c = argv[1][0];
sort_fn sort = c == 'i' ? insertion_sort
: c == 'm' ? merge_sort
: c == 'f' ? quick_sort_first : quick_sort_mid;
size_t nmin = strtoul(argv[3], NULL, 10);
size_t nmax = strtoul(argv[4], NULL, 10);
int *a = malloc(nmax * sizeof *a);
if (a == NULL) return 2;
double prev = 0.0;
printf("%9s %10s %6s\n", "n", "seconds", "slope");
for (size_t n = nmin; n <= nmax; n *= 2) {
double best = 1e30; /* best of five runs */
for (int rep = 0; rep < 5; rep++) {
fill(a, n, argv[2]);
double t0 = now_s();
sort(a, n);
double t = now_s() - t0;
if (!is_sorted(a, n)) {
puts("NOT SORTED");
return 1;
}
if (t < best) best = t;
}
printf("%9zu %10.6f", n, best);
if (prev > 0.0) printf(" %6.2f\n", log2(best / prev));
else printf(" %6s\n", "-");
prev = best;
}
free(a);
return 0;
}
ch10/lomuto_rand.c29 lines
#define _POSIX_C_SOURCE 199309L
#include <stdio.h>
#include <stdlib.h>
#include "bench.h"
static void swap(int *x, int *y) { int t = *x; *x = *y; *y = t; }
static void qs(int *a, size_t lo, size_t hi) {
while (hi - lo > 1) {
size_t r = lo + (size_t)rand() % (hi - lo);
swap(&a[lo], &a[r]);
int pivot = a[lo];
size_t m = lo;
for (size_t i = lo + 1; i < hi; i++)
if (a[i] < pivot) { m++; swap(&a[m], &a[i]); }
swap(&a[lo], &a[m]);
if (m - lo < hi - m) { qs(a, lo, m); lo = m + 1; }
else { qs(a, m + 1, hi); hi = m; }
}
}
int main(int argc, char **argv) {
if (argc != 2) return 2; /* kind: sorted, equal, ... */
static int a[1 << 20];
for (size_t n = 4000; n <= 64000; n *= 2) {
fill(a, n, argv[1]);
double t0 = now_s();
qs(a, 0, n);
double t = now_s() - t0;
printf("%7zu %9.6f %d\n", n, t, is_sorted(a, n));
}
}
ch10/pair_sum.c40 lines
#include <stdio.h>
#include <stdlib.h>
#include "bench.h"
/* 1 if some i < j has a[i] + a[j] == target. Any order. */
int has_pair_nested(const int *a, size_t n, long target) {
for (size_t i = 0; i < n; i++)
for (size_t j = i + 1; j < n; j++)
if ((long)a[i] + a[j] == target) return 1;
return 0;
}
/* Same question; a must be sorted ascending. */
int has_pair_sorted(const int *a, size_t n, long target) {
if (n < 2) return 0;
size_t lo = 0, hi = n - 1;
while (lo < hi) {
long sum = (long)a[lo] + a[hi];
if (sum == target) return 1;
if (sum < target) lo++; /* need a bigger sum */
else hi--; /* need a smaller sum */
}
return 0;
}
int main(void) {
printf("%7s %10s %10s\n", "n", "nested_s", "sorted_s");
for (size_t n = 8000; n <= 128000; n *= 2) {
int *a = malloc(n * sizeof *a);
if (a == NULL) return 1;
fill(a, n, "sorted"); /* 0, 1, ..., n-1 */
long target = -1; /* absent: worst case */
double t0 = now_s();
int r1 = has_pair_nested(a, n, target);
double t1 = now_s();
int r2 = has_pair_sorted(a, n, target);
double t2 = now_s();
printf("%7zu %10.6f %10.6f %d%d\n",
n, t1 - t0, t2 - t1, r1, r2);
free(a);
}
return 0;
}
ch10/reading.h11 lines
#ifndef READING_H
#define READING_H
#include <stdint.h>
struct reading {
uint32_t sensor_id;
int64_t time_s;
double value;
uint8_t flags;
};
#endif
ch10/sorts.c91 lines
#include <stdlib.h>
#include "sorts.h"
void insertion_sort(int *a, size_t n) {
for (size_t i = 1; i < n; i++) {
int key = a[i];
size_t j = i;
while (j > 0 && a[j - 1] > key) {
a[j] = a[j - 1];
j--;
}
a[j] = key;
}
}
/* Merge sorted a[lo..mid) and a[mid..hi) through tmp, then
* copy back. tmp is borrowed: the caller allocated it and
* frees it. */
static void merge(int *a, int *tmp,
size_t lo, size_t mid, size_t hi) {
size_t i = lo, j = mid, k = lo;
while (i < mid && j < hi) {
if (a[j] < a[i]) tmp[k++] = a[j++]; /* ties go left */
else tmp[k++] = a[i++];
}
while (i < mid) tmp[k++] = a[i++];
while (j < hi) tmp[k++] = a[j++];
for (k = lo; k < hi; k++) a[k] = tmp[k];
}
static void msort(int *a, int *tmp, size_t lo, size_t hi) {
if (hi - lo < 2) return;
size_t mid = lo + (hi - lo) / 2;
msort(a, tmp, lo, mid);
msort(a, tmp, mid, hi);
merge(a, tmp, lo, mid, hi);
}
void merge_sort(int *a, size_t n) {
if (n < 2) return;
int *tmp = malloc(n * sizeof *tmp);
if (tmp == NULL) abort();
msort(a, tmp, 0, n);
free(tmp);
}
static void swap(int *x, int *y) { int t = *x; *x = *y; *y = t; }
/* Lomuto-style partition around a[lo]; returns pivot's final index. */
static size_t partition_first(int *a, size_t lo, size_t hi) {
int pivot = a[lo];
size_t m = lo; /* a[lo+1..m] < pivot */
for (size_t i = lo + 1; i < hi; i++) {
if (a[i] < pivot) {
m++;
swap(&a[m], &a[i]);
}
}
swap(&a[lo], &a[m]);
return m;
}
static void qs_first(int *a, size_t lo, size_t hi) {
if (hi - lo < 2) return;
size_t p = partition_first(a, lo, hi);
qs_first(a, lo, p);
qs_first(a, p + 1, hi);
}
void quick_sort_first(int *a, size_t n) { qs_first(a, 0, n); }
/* Hoare partition, middle pivot; recurse on smaller side first. */
static void qs_mid(int *a, size_t lo, size_t hi) { /* [lo, hi] */
while (lo < hi) {
int pivot = a[lo + (hi - lo) / 2];
size_t i = lo, j = hi;
for (;;) {
while (a[i] < pivot) i++;
while (a[j] > pivot) j--;
if (i >= j) break;
swap(&a[i], &a[j]);
i++;
j--;
}
/* now [lo, j] <= pivot <= [j+1, hi] */
if (j - lo < hi - j) { qs_mid(a, lo, j); lo = j + 1; }
else { qs_mid(a, j + 1, hi); hi = j; }
}
}
void quick_sort_mid(int *a, size_t n) { if (n > 1) qs_mid(a, 0, n - 1); }
ch10/sorts.h12 lines
#ifndef SORTS_H
#define SORTS_H
#include <stddef.h>
typedef void (*sort_fn)(int *a, size_t n);
void insertion_sort(int *a, size_t n);
void merge_sort(int *a, size_t n); /* stable, Θ(n log n) */
void quick_sort_first(int *a, size_t n); /* first-element pivot */
void quick_sort_mid(int *a, size_t n); /* middle pivot, Hoare */
#endif
ch10/stn_sort.h25 lines
#ifndef STN_SORT_H
#define STN_SORT_H
#include <stddef.h>
#include "reading.h"
/* Sort r[0..n) by time_s, ascending. STABLE: readings with
* equal time_s keep their input order.
* Ownership: the caller owns r; the function borrows it for the
* call. It mallocs at most one temporary, of n readings, and
* frees it before returning, on every path. It keeps no
* pointer to r.
* Errors: returns 0 on success; -1 if r is NULL and n > 0;
* -2 if the temporary cannot be allocated (r is unchanged).
* Budget: Θ(n log n) comparisons on every input; Θ(n) extra
* space; recursion depth at most ceil(log2 n) + 1. */
int stn_merge_sort_by_time(struct reading *r, size_t n);
/* Sort r[0..n) by time_s, ascending. Not stable. No malloc.
* Ownership: borrows r for the call, as above.
* Errors: returns 0 on success; -1 if r is NULL and n > 0.
* Budget: Θ(n log n) time on sorted, reverse-sorted, all-equal
* and random input; recursion depth O(log n) on every input. */
int stn_quick_sort_by_time(struct reading *r, size_t n);
#endif
ch10/test_qstable.c84 lines
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stn_sort.h"
#include "bench.h"
static int failures = 0;
#define CHECK(cond) do { if (!(cond)) { failures++; \
printf("FAIL line %d: %s\n", __LINE__, #cond); } } while (0)
typedef int (*rsort_fn)(struct reading *, size_t);
static int sorted_by_time(const struct reading *r, size_t n) {
for (size_t i = 1; i < n; i++)
if (r[i - 1].time_s > r[i].time_s) return 0;
return 1;
}
/* Four sensors report at each minute; value holds input position. */
static void make_log(struct reading *r, size_t n, const char *kind) {
for (size_t i = 0; i < n; i++) {
int64_t minute = (int64_t)(i / 4);
r[i].sensor_id = 1001 + (uint32_t)(i % 4);
if (strcmp(kind, "sorted") == 0) r[i].time_s = minute * 60;
else if (strcmp(kind, "reverse") == 0) r[i].time_s = -minute * 60;
else if (strcmp(kind, "equal") == 0) r[i].time_s = 0;
else r[i].time_s = (int64_t)(rand() % 100000);
r[i].value = (double)i;
r[i].flags = 1;
}
}
static void test_edges(rsort_fn sort) {
struct reading one[1];
CHECK(sort(NULL, 0) == 0);
CHECK(sort(NULL, 5) == -1);
make_log(one, 1, "random");
CHECK(sort(one, 1) == 0 && one[0].value == 0.0);
}
/* Stable: among equal times, input positions must increase. */
static void test_stable(rsort_fn sort, size_t n) {
struct reading *r = malloc(n * sizeof *r);
if (r == NULL) { failures++; return; }
make_log(r, n, "random");
for (size_t i = 0; i < n; i++)
r[i].time_s %= 50; /* many ties */
CHECK(sort(r, n) == 0);
CHECK(sorted_by_time(r, n));
for (size_t i = 1; i < n; i++)
if (r[i - 1].time_s == r[i].time_s)
CHECK(r[i - 1].value < r[i].value);
free(r);
}
/* Hostile inputs at scale: must sort within the budget. */
static void test_hostile(rsort_fn sort, const char *kind,
size_t n) {
struct reading *r = malloc(n * sizeof *r);
if (r == NULL) { failures++; return; }
make_log(r, n, kind);
double t0 = now_s();
CHECK(sort(r, n) == 0);
double t = now_s() - t0;
CHECK(sorted_by_time(r, n));
CHECK(t < 2.0); /* n log n takes well under 1 s */
printf("%-6s n=%zu %.3f s\n", kind, n, t);
free(r);
}
int main(int argc, char **argv) {
size_t n = argc > 1 ? strtoul(argv[1], NULL, 10) : 1000000;
const char *kinds[] = {"sorted", "reverse", "equal", "random"};
rsort_fn sorts[] = {stn_merge_sort_by_time, stn_quick_sort_by_time};
for (int s = 0; s < 2; s++) {
printf("%s\n", s == 0 ? "merge" : "quick");
test_edges(sorts[s]);
for (int k = 0; k < 4; k++) test_hostile(sorts[s], kinds[k], n);
}
test_stable(stn_quick_sort_by_time, 10000);
printf("%d failure(s)\n", failures);
fflush(stdout); /* before LeakSanitizer runs at exit */
return failures != 0;
}
ch10/test_sort.c84 lines
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stn_sort.h"
#include "bench.h"
static int failures = 0;
#define CHECK(cond) do { if (!(cond)) { failures++; \
printf("FAIL line %d: %s\n", __LINE__, #cond); } } while (0)
typedef int (*rsort_fn)(struct reading *, size_t);
static int sorted_by_time(const struct reading *r, size_t n) {
for (size_t i = 1; i < n; i++)
if (r[i - 1].time_s > r[i].time_s) return 0;
return 1;
}
/* Four sensors report at each minute; value holds input position. */
static void make_log(struct reading *r, size_t n, const char *kind) {
for (size_t i = 0; i < n; i++) {
int64_t minute = (int64_t)(i / 4);
r[i].sensor_id = 1001 + (uint32_t)(i % 4);
if (strcmp(kind, "sorted") == 0) r[i].time_s = minute * 60;
else if (strcmp(kind, "reverse") == 0) r[i].time_s = -minute * 60;
else if (strcmp(kind, "equal") == 0) r[i].time_s = 0;
else r[i].time_s = (int64_t)(rand() % 100000);
r[i].value = (double)i;
r[i].flags = 1;
}
}
static void test_edges(rsort_fn sort) {
struct reading one[1];
CHECK(sort(NULL, 0) == 0);
CHECK(sort(NULL, 5) == -1);
make_log(one, 1, "random");
CHECK(sort(one, 1) == 0 && one[0].value == 0.0);
}
/* Stable: among equal times, input positions must increase. */
static void test_stable(rsort_fn sort, size_t n) {
struct reading *r = malloc(n * sizeof *r);
if (r == NULL) { failures++; return; }
make_log(r, n, "random");
for (size_t i = 0; i < n; i++)
r[i].time_s %= 50; /* many ties */
CHECK(sort(r, n) == 0);
CHECK(sorted_by_time(r, n));
for (size_t i = 1; i < n; i++)
if (r[i - 1].time_s == r[i].time_s)
CHECK(r[i - 1].value < r[i].value);
free(r);
}
/* Hostile inputs at scale: must sort within the budget. */
static void test_hostile(rsort_fn sort, const char *kind,
size_t n) {
struct reading *r = malloc(n * sizeof *r);
if (r == NULL) { failures++; return; }
make_log(r, n, kind);
double t0 = now_s();
CHECK(sort(r, n) == 0);
double t = now_s() - t0;
CHECK(sorted_by_time(r, n));
CHECK(t < 2.0); /* n log n takes well under 1 s */
printf("%-6s n=%zu %.3f s\n", kind, n, t);
free(r);
}
int main(int argc, char **argv) {
size_t n = argc > 1 ? strtoul(argv[1], NULL, 10) : 1000000;
const char *kinds[] = {"sorted", "reverse", "equal", "random"};
rsort_fn sorts[] = {stn_merge_sort_by_time, stn_quick_sort_by_time};
for (int s = 0; s < 2; s++) {
printf("%s\n", s == 0 ? "merge" : "quick");
test_edges(sorts[s]);
for (int k = 0; k < 4; k++) test_hostile(sorts[s], kinds[k], n);
}
test_stable(stn_merge_sort_by_time, 10000);
printf("%d failure(s)\n", failures);
fflush(stdout); /* before LeakSanitizer runs at exit */
return failures != 0;
}