Blog

CreativeCoders

Blog/
­

Quicksort: Fully multithreaded

Up to a million: Every subcall is threaded. Payoff between multi-threaded-payload and parallelism-benefits. It seems to have an opt. at size 10^6 on my real 4-core i7 CPU machine.

// -----------------------------------------------------------------------
int QS_Sort_thread( QS_ThreadArg_t* p ) {
	if ( p->r - p->l > 1000 * 1000 ) 
		QS_SortMP( p->a, p->l, p->r );
	else 
		QS_Sort( p->a, p->l, p->r );
	
	return 1;
}
By |November 19th, 2015|Uncategorized|0 Comments

Quicksort: Simply multithreaded

Only the first (initial) call has been parallelized.

void QS_SortMP( int a[], int l, int r );

typedef struct {
	DWORD dwPid;
	HANDLE hThread;
	DWORD dwExitCode;

	int p;
	int* a;
	int l;
	int r;
} QS_ThreadArg_t;

int QS_Sort_thread( QS_ThreadArg_t* p ) {
	QS_Sort( p->a, p->l, p->r );
	
	return 1;
}

//-------------------------------------------------------------------------

void QS_SortMP( int a[], int l, int r ) {
	if ( r-l <= 1 ) return;

	QS_ThreadArg_t* p1 = (QS_ThreadArg_t*)calloc( 1, sizeof(QS_ThreadArg_t) );
	if ( !p1 ) _asm int 3;
	QS_ThreadArg_t* p2 = (QS_ThreadArg_t*)calloc( 1, sizeof(QS_ThreadArg_t) );
	if ( !p2 ) _asm int 3;

	p1->p = QS_Partition( a, l, r );
	p2->p = p1->p;

	p1->a = a; p1->l = l; p1->r = p1->p - 1;
	p1->hThread = CreateThread( 0, 0, (LPTHREAD_START_ROUTINE)QS_Sort_thread, p1, 0, &p1->dwPid );

	p2->a = a; p2->l = p2->p + 1; p2->r = r;
	p2->hThread = CreateThread( 0, 0, (LPTHREAD_START_ROUTINE)QS_Sort_thread, p2, 0, &p2->dwPid );

	WaitForSingleObject( p1->hThread, INFINITE );
	WaitForSingleObject( p2->hThread, INFINITE );
	GetExitCodeThread( p1->hThread, &p1->dwExitCode );
	GetExitCodeThread( p2->hThread, &p2->dwExitCode );

	free( p1 );
	free( p2 );
}
By |November 19th, 2015|Uncategorized|0 Comments

Quicksort: How quick is it?

Quicksort is famous for sorting large data in a short amount of time. However its running time strongly depends on how you’ve chosen the pivot. Worst case: Your pivot always splits an array of n numbers into an element of size one and a n-1-element-array on the other side. That way, you’ll end up in O(n^2) comparisons, as your problem (of sorting) gets down by one in every each step.

Mergesort however guarantees that your problem is going to be cut in half in every step. If you do so, you’ll end up with a running time of O(c*n*logn), c being a constant > 1. So why bother using Quicksort then? Simple: Quicksort is inplace, while Mergesort needs extra memory. You might run out of memory using Mergesort!

The actual challenge when it comes to Quicksort remains to be smart on how to chose the pivot. If you’re using item[0] as a pivot (1st element in your array, for example), it’s always possible to create a “bad” input such that the algorithm is going to take O(n^2) steps. Obviously that’s not gonna be possible if the pivot is a random item from the array, or some median of it.

I’ve played a bit with these options and came to the conclusion, that each of these methods are gonna work in practice.

// ------------------------------------------------------------------------

void QS_Exchange( INT& i1, INT& i2 ) {
	int tmp = i1;
	i1 = i2;
	i2 = tmp;
}

// ------------------------------------------------------------------------

int QS_Median( int i1, int i2, int i3 ) {
	if ( i1 > i2 ) {
		if ( i1 > i3 ) return (i2 > i3) ? i2 : i3;
		else return i1;
	}
	else {
		if ( i2 > i3 ) return (i1 > i3) ? i1 : i3;
		return i2;
	}
}

// ------------------------------------------------------------------------

int QS_Partition( int a[], int l, int r ) {
	int iSize = r - l;
	int iPivotPos = (iSize < 5) ? l : /*QS_Median( l, l + (r-l) / 2, r );*/  l + rand() % iSize;
	int iPivot = a[iPivotPos];
	QS_Exchange( a[l], a[iPivotPos] );

	int i = l + 1; 
	int j = r;
	while ( TRUE ) {
		while ( a[i] <= iPivot && i <= r ) i++;
		while ( a[j]  > iPivot ) j--;
		if ( i >= j ) break;
		QS_Exchange( a[i], a[j] );
	}

	QS_Exchange( a[l], a[j] );
	return j;
}

//-------------------------------------------------------------------------

void QS_Sort( int a[], int l, int r ) {
	if ( l >= r ) return;
	
	int p = QS_Partition( a, l, r );
	QS_Sort( a, l, p-1 );
	QS_Sort( a, p+1, r );
}
By |November 18th, 2015|Uncategorized|0 Comments

Bubblesort: Not so bad at all

When it comes to sorting, Bubblesort is often labeled slow and bad. But in fact it has some advantages. First of all, you can use it to verify that your data has been sorted correctly, in \theta(n) time. Remember: Bubblesort has a best case running time (data sorted) of order \theta(n), and worst case (data sorted in reverse order) of \theta(n^2), overall O(n^2). Also, Bubblesort is very easy to implement and acceptable if used on small data.

// ------------------------------------------------------------------------

void BubbleSort( int a[], int n ) {
	while ( TRUE ) {
		bool bChanged = FALSE;
		for ( int i = 0; i < n; i++ ) {
			for ( int j = i+1; j <= n; j++ ) {
				if ( a[i] > a[j] ) {
					QS_Exchange( a[i], a[j] );
					bChanged = TRUE;
				}
			}
			if ( !bChanged ) return;	
		}	
	}
}

// using QS_Exchange taken from Quicksort
// ------------------------------------------------------------------------

void QS_Exchange( INT& i1, INT& i2 ) {
	int tmp = i1;
	i1 = i2;
	i2 = tmp;
}
By |November 18th, 2015|Uncategorized|0 Comments

Mergesort: Running on random data

If you want to run a few tests to sort integers, here is my sample code.

// ------------------------------------------------------------------------
int CALLBACK WinMain( HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow ) {	

	srand( GetTickCount() );

	// set n
	#define NUM_ELEM 1000 * 1000 * 1000
	// must be < MAX_INT = 0x7FFFFFF; 32bit signed
    // real bound: 2GB memory and fragmentation....
	#define MAX_VALUE 0xFFFFFFF

	static int d[NUM_ELEM] = { 0 };

	// generate random (positive) numbered list of n elements
	for ( int i = 0; i < NUM_ELEM; i++ ) {
	    int x = rand() % MAX_VALUE;
		d[i] = x;
	}

	// sort
	MergeSort( d, NUM_ELEM );

	// lame check to verify list is sorted correctly
	for ( int i = 0; i < NUM_ELEM-1; i++ ) {
		if ( d[i] > d[i] + 1 ) _asm int 3;
	}

	return 0;
}
By |November 17th, 2015|Uncategorized|0 Comments