partialsort.cpp

#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;
}