Skip to content

Instantly share code, notes, and snippets.

@alexreinking

alexreinking/sort7.c

Created Jul 13, 2017
Embed
What would you like to do?
Super fast way to sort fixed integer arrays of size 7.
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <sys/time.h>
#include <sys/resource.h>
#define NTESTS (5000000)
static double get_time()
{
struct timeval t;
struct timezone tzp;
gettimeofday(&t, &tzp);
return t.tv_sec + t.tv_usec*1e-6;
}
static void sort7(int* a) {
#define max(x, y) (x ^ ((x ^ y) & -(x < y)))
#define min(x, y) (y ^ ((x ^ y) & -(x < y)))
#define SWAP(i, j) do { int temp = max(a[i], a[j]); a[i] = min(a[i], a[j]); a[j] = temp; } while(0)
// sorting network from the site below:
// http://pages.ripco.net/~jgamble/nw.html
SWAP(1, 2); SWAP(0, 2); SWAP(0, 1); SWAP(3, 4);
SWAP(5, 6); SWAP(3, 5); SWAP(4, 6); SWAP(4, 5);
SWAP(0, 4); SWAP(0, 3); SWAP(1, 5); SWAP(2, 6);
SWAP(2, 5); SWAP(1, 3); SWAP(2, 4); SWAP(2, 3);
#undef SWAP
#undef min
#undef max
}
int main() {
srand(time(NULL));
// init test cases
int* arr = new int[7 * NTESTS];
for (int i = 0; i < 7 * NTESTS; i++) {
arr[i] = rand();
}
// begin testing
double startTime = get_time();
for (int i = 0; i < NTESTS; i++) {
sort7(&arr[7 * i]);
}
double elapsed = get_time() - startTime;
// verify
for (int i = 0; i < NTESTS; i++) {
for (int j = 0; j < 6; j++) {
if (arr[7 * i + j] > arr[7 * i + j + 1]) {
printf("FAILED!!!\n");
return 1;
}
}
}
printf("Completed %d sorts in %lfs\n", NTESTS, elapsed);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment