Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#include <Windows.h>
#include <math.h>
#include <stdio.h>
#define DATASIZE 1024//*1024
#define SUBSET 32//256
void swap(int *a, int *b)
{
int t = *a; *a = *b; *b = t;
}
// -------------
void partial_quicksort_iterative(int *data, int len, int k)
{
int left = 0, stack[24], pos = 0, right;
for (;;) { /* outer loop */
for (; left + 1 < len; len++) { /* sort left to len-1 */
if (pos == 24) len = stack[pos = 0]; /* stack overflow, reset */
int pivot = data[left]; /* pick random pivot */
stack[pos++] = len; /* sort right part later */
for (right = left - 1;;) { /* inner loop: partitioning */
while (data[++right] < pivot); /* look for greater element */
while (pivot < data[--len]); /* look for smaller element */
if (right >= len) break; /* partition point found? */
int temp = data[right];
data[right] = data[len]; /* the only swap */
data[len] = temp;
} /* partitioned, continue left part */
}
if (pos == 0) break; /* stack empty? */
if (left >= k) break;
left = len; /* left to right is sorted */
len = stack[--pos]; /* get next range to sort */
}
}
// -------------
#define MAX 64
void quicksort_iterative(int *cvxarray, unsigned len)
{
unsigned left = 0, stack[MAX], pos = 0, seed = rand();
for (;;) { /* outer loop */
for (; left + 1 < len; len++) { /* sort left to len-1 */
if (pos == MAX) len = stack[pos = 0]; /* stack overflow, reset */
int pivot = cvxarray[left + seed % (len - left)]; /* pick random pivot */
seed = seed * 69069 + 1; /* next pseudorandom number */
stack[pos++] = len; /* sort right part later */
for (unsigned right = left - 1;;) { /* inner loop: partitioning */
while (cvxarray[++right] < pivot); /* look for greater element */
while (pivot < cvxarray[--len]); /* look for smaller element */
if (right >= len) break; /* partition point found? */
int temp = cvxarray[right];
cvxarray[right] = cvxarray[len]; /* the only swap */
cvxarray[len] = temp;
} /* partitioned, continue left part */
}
if (pos == 0) break; /* stack empty? */
left = len; /* left to right is sorted */
len = stack[--pos]; /* get next range to sort */
}
}
// -------------
void rec_partial_qsort2(int arr[], int beg, int end, int k)
{
if (end > beg + 1)
{
int piv = arr[beg], l = beg + 1, r = end;
while (l < r)
{
if (arr[l] <= piv)
l++;
else
swap(&arr[l], &arr[--r]);
}
swap(&arr[--l], &arr[beg]);
rec_partial_qsort2(arr, beg, l, k);
if (beg < k - 1)
rec_partial_qsort2(arr, r, end, k);
}
}
// -------------
void rec_partial_qsort(int arr[], int beg, int end, int k)
{
if (end > beg + 1)
{
int piv = arr[beg], l = beg + 1, r = end;
while (l < r)
{
if (arr[l] <= piv)
l++;
else
swap(&arr[l], &arr[--r]);
}
swap(&arr[--l], &arr[beg]);
rec_partial_qsort(arr, beg, l, k);
if (beg < k - 1)
rec_partial_qsort(arr, r, end, k);
}
}
// -------------
void rec_qsort(int arr[], int beg, int end)
{
if (end > beg + 1)
{
int piv = arr[beg], l = beg + 1, r = end;
while (l < r)
{
if (arr[l] <= piv)
l++;
else
swap(&arr[l], &arr[--r]);
}
swap(&arr[--l], &arr[beg]);
rec_qsort(arr, beg, l);
rec_qsort(arr, r, end);
}
}
// -------------
void quickSort(int *arr, int elements)
{
#define MAX_LEVELS 1000
int piv, beg[MAX_LEVELS], end[MAX_LEVELS], i = 0, L, R;
beg[0] = 0; end[0] = elements;
while (i >= 0) {
L = beg[i]; R = end[i] - 1;
if (L<R) {
piv = arr[L];
while (L<R) {
while (arr[R] >= piv && L<R) R--; if (L<R) arr[L++] = arr[R];
while (arr[L] <= piv && L<R) L++; if (L<R) arr[R--] = arr[L];
}
arr[L] = piv; beg[i + 1] = L + 1; end[i + 1] = end[i]; end[i++] = L;
}
else {
i--;
}
}
}
// -------------
int cmpfunc(const void * a, const void * b)
{
return (*(int*)a - *(int*)b);
}
void std_qsort(int *data)
{
qsort(data, DATASIZE, sizeof(int), cmpfunc);
}
// -----------------
void partial_bubble(int *data)
{
int i, j;
for (i = 0; i < SUBSET; i++)
{
for (j = DATASIZE - 2; j >= i; j--)
{
if (data[j + 1] < data[j])
{
int t = data[j];
data[j] = data[j + 1];
data[j + 1] = t;
}
}
}
}
void bubble(int *data)
{
int i, j;
for (i = 0; i < DATASIZE; i++)
{
for (j = DATASIZE - 2; j >= i; j--)
{
if (data[j + 1] < data[j])
{
int t = data[j];
data[j] = data[j + 1];
data[j + 1] = t;
}
}
}
}
static unsigned long state[16] =
{
0x01234567, 0x89abcdef, 0x00112233, 0x44556677,
0x8899aabb, 0xccddeeff, 0x00011122, 0x23334445,
0x55666777, 0x888999aa, 0xabbbcccd, 0xddeeefff,
0x00001111, 0x22223333, 0x44445555, 0x66667777
};
static unsigned int index = 0;
unsigned long WELLRNG512(void)
{
unsigned long a, b, c, d;
a = state[index];
c = state[(index + 13) & 15];
b = a^
c ^
(a << 16) ^ (c << 15);
c = state[(index + 9) & 15];
c ^= (c >> 11);
a
= state[index] = b^c;
d
= a ^ ((a << 5) &
0xDA442D24UL);
index = (index + 15) & 15;
a
= state[index];
state[index] = a^b^d ^ (a << 2) ^ (b << 18) ^ (c << 28);
return state[index];
}
int _main(int parc, char ** pars)
{
int i;
int *data;
data = new int[DATASIZE];
int sum = 0;
int j = 0;
//for (j = 0; j < 20; j++)
while (1)
{
j++;
for (i = 0; i < DATASIZE; i++)
{
data[i] = i * 10;
}
for (i = 0; i < DATASIZE; i++)
swap(data + i, data + (WELLRNG512() % DATASIZE));
//(int)abs(sin(i * 0.0023487) * DATASIZE));
/*
for (i = 0; i < 20; i++)
printf("%d ", data[i]);
printf("\n");
*/
__int64 t1 = __rdtsc();
//bubble(data); // ~5350k
//std_qsort(data); // ~324k
//partial_bubble(data); // ~201k
//quicksort_iterative(data, DATASIZE); // ~217k
//rec_qsort(data, 0, DATASIZE); // ~158k
//quickSort(data, DATASIZE); // ~154k
//rec_partial_qsort(data, 0, DATASIZE, SUBSET); // ~44k
partial_quicksort_iterative(data, DATASIZE, SUBSET); // ~22k
__int64 t2 = __rdtsc();
sum += (int)((t2 - t1) / 1000);
if ((j & 1023) == 0)
printf("\r%d) %dk clocks. Avg %dk. ", j, (int)((t2 - t1) / 1000), sum / j);
/*
for (i = 0; i < 20; i++)
printf("%d ", data[i]);
printf("\n");
*/
int subsetsum = 0;
for (i = 0; i < SUBSET; i++)
{
subsetsum += data[i];
if (data[i] >= SUBSET * 10)
{
printf("bad data.\n");
return -1;
}
}
if (subsetsum != 4960)
{
printf("bad checksum - %d\n", subsetsum);
return -1;
}
}
printf("Avg %d\n", sum / 20);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.