Add quicksort-killer testcase

This doesn't generate an input sequence up-front, but rather generates it
on the fly in response to the order in which the algorithm is comparing
elements in such a way as to invoke quadratic runtime in most quicksort
implementations.

1 files changed, 31 insertions, 0 deletions

diff --git a/testcases.c b/testcases.c
index eba3983..b40fa5a 100644
--- a/testcases.c
+++ b/testcases.c
@@ -90,6 +90,36 @@ static void init_reverse_noise(size_t size)
 	add_noise(size);
 }
 
+/* quicksort-killer testcase from http://www.cs.dartmouth.edu/~doug/mdmspe.pdf */
+static int    qsk_buffer[MAX_SIZE];
+static size_t qsk_nsolid;
+static size_t qsk_candidate;
+
+static void init_qsk(size_t size)
+{
+	qsk_nsolid = qsk_candidate = 0;
+	for (size_t i = 0; i < size; i++) {
+		qsk_buffer[i] = INT_MAX;
+		buffer[i]     = i;
+	}
+}
+
+static int qsk_compare(const void *a, const void *b)
+{
+	const int x = *(const int*)a;
+	const int y = *(const int*)b;
+
+	if (qsk_buffer[x] == INT_MAX && qsk_buffer[y] == INT_MAX) {
+		if (qsk_buffer[x] == INT_MAX) qsk_buffer[x] = qsk_nsolid++;
+		else                          qsk_buffer[y] = qsk_nsolid++;
+	}
+
+	if (qsk_buffer[x] == INT_MAX) qsk_candidate = x;
+	else if (qsk_buffer[y] == INT_MAX) qsk_candidate = y;
+
+	return compare(qsk_buffer + x, qsk_buffer + y);
+}
+
 const struct testcase testcases[] = {
 	{ .name = "random",        .init = init_random,        .cmp = compare },
 	{ .name = "sorted",        .init = init_sorted,        .cmp = compare },
@@ -97,5 +127,6 @@ const struct testcase testcases[] = {
 	{ .name = "constant",      .init = init_constant,      .cmp = compare },
 	{ .name = "sorted+noise",  .init = init_sorted_noise,  .cmp = compare },
 	{ .name = "reverse+noise", .init = init_reverse_noise, .cmp = compare },
+	{ .name = "qsort-killer",  .init = init_qsk,           .cmp = qsk_compare },
 	{ 0 }
 };