CAbuseSort
CAbuse Sort (caboose sort) is an implementation of quicksort packed into the header of a for loop. This relies on a few interesting features of the C Language, but in no way violates the standard.
Comma Expressions
C executes Statements in a top down manner, but it also executes Expressions in a left to right order with the value of the expessions being the value of the rightmost expression in the list.
int f, b, x = (f = foo(), b = bar(), f + b);
The previous code snippet creates 3 variables assigns f the return value of foo(), b the return value of bar and assigns to x their sum. This is a single statement, but contains a list of exressions. This allows for many computational steps to be taken in a single statement.
Logical Operators with short circuiting
Short circuiting is a useful feature of the Logical Operators.
if (x != NULL && x->foo < 0xdeadbeef) {
...
}
The previous code snippet will evaluate the nullity check and if it fails it will apply the identity that false && anything
is false to immediately drop out. This is useful because if it went on to evaluate x->foo we would be accessing an invalid pointer.
if (x != NULL) {
if (x->foo < 0xdeadbeef) {
...
}
}
If it did not short circuit we would have to restructure the code to prevent the execution of the field access when the pointer was NULL.
A similar property holds for logical or where anytime the result of the first operand is true the execution short circuits.
Ternary Expressions
The C language doesn't have nice if expressions like some languages, but ternaries provide the same functionality with a slightly uglier syntax.
int x = cond() ? foo() : bar();
This assigns x the value of foo() or bar() depending on the result of cond(). It is important to note that this is not a statement, but rather an exression meaninng they can be placed in a comma expression.
int x = cond1() ? foo1() : foo2(), cond2() ? bar() : baz();
We execute foo1 or foo2 based on the result of cond1 and then go on to assign to x the value of bar() or baz() depending on cond2.
XOR Swapping
xor swapping provides a way to swap two variables "in place."
int x = 5, y = 12;
x = x ^ y; // x = (x ^ y), y = y
y = y ^ x; // x = (x ^ y), y = y ^ (x ^ y) = x
x = x ^ y; // x = (x ^ y) ^ x = y
Using the definition that (x ^ y) ^ y == x
we can swap the two variables
Again these are all expressions which means this can be placed in a single statement
x ^= y, y ^= x, x ^= y;
Put it all together and you get:
void qs(int * a, int s) {
for (int i = 0, w = 0; s > 1 && (i < s-1 || (qs(a,w), qs(a+w+1,s-w-1), 0)); ((a[i] < a[s-1] ? (a[i] != a[w] ? a[w] ^= a[i], a[i] ^= a[w], a[w] ^= a[i], w++ : w++): 1), i++), i == s-1 ? (a[w] != a[s-1] ? a[s-1] ^= a[w], a[w] ^= a[s-1], a[s-1] ^= a[w], 1 : 1) : 1);
}
Or slightly more readably. When formatting code to more closely resemble lisp syntax increases readability something is wrong.
void qs(int * a, int s) {
for (
// Initialization:
int i = 0, w = 0;
// Comparison
// Use short circuiting to loop until all elements swapped
s > 1 &&
// Check if we need to resurse deeper, and if so make recursive calls
(i < s-1 || (qs(a,w), qs(a+w+1,s-w-1), 0));
// Increment
// Check if we need to swap an element
((a[i] < a[s-1] ? // Check if a[i] is less than the pivot
(a[i] != a[w] ? // Xor swap if the values are different and increment w
a[w] ^= a[i], a[i] ^= a[w], a[w] ^= a[i], w++ :
w++):
1), // We need a value so 1 is as good as any, this is just the branch where we don't swap
i++), // Increment to the next element
// If at the end put the pivot in place
i == s-1 ?
(a[w] != a[s-1] ? a[s-1] ^= a[w], a[w] ^= a[s-1], a[s-1] ^= a[w], 1 :
1) :
1);
}