PROWAREtech

articles » current » c-plus-plus » algorithms » quick-sort

C/C++: Quick Sort Algorithm

An O(n•log2(n)) algorithm.

See also: Quick Sort Multi-threaded & Quick Sort in Assembly

Quick sort is a great algorithm for sorting a totally random array. It is just a tad faster sorting an already sorted array. Unlike bubble sort, it performs well on random data. It is a workhorse algorithm that can always give high performance results. The only real downside to quicksort is that it can run out of stack space on very, very large arrays. Performance can be improved upon by using insertion sort to sort the smaller sub arrays and this would seem to help the problem of running out of stack space on very large arrays, too. See the Algorithm Study for more details.

// the original algorithm as posted on Wikipedia
void qsort_int(int array[], const int size){
	if(size < 2)
		return;
	int pivot = array[size / 2];
	int *left = array;
	int *right = array + size - 1;
	while(left <= right){
		if(*left < pivot){
			left++;
			continue;
		}
		if(*right > pivot){
			right--;
			continue;
		}
		int temp = *left;
		*left++ = *right;
		*right-- = temp;
	}
	qsort_int(array, right - array + 1);
	qsort_int(left, array + size - left);
}

void qsort_int_optimized(int array[], const int size){
	if(size < 2)
		return;
	int pivot = array[size / 2];
	int *left = array;
	int *right = array + size - 1;
	while(true){
		while((left <= right) && (*left < pivot)) left++;
		while((left <= right) && (*right > pivot)) right--;
		if(left > right) break;
		int temp = *left;
		*left++ = *right;
		*right-- = temp;
	}
	qsort_int_optimized(array, right - array + 1);
	qsort_int_optimized(left, array + size - left);
}

// sort pointers to ints in ascending order
void qsort_pint_ascending(int ** const pparray, const int size){
	if(size < 2)
		return;
	int pivot = *(pparray[size / 2]);
	int **left = pparray;
	int **right = pparray + size - 1;
	while(true){
		while((left <= right) && (**left < pivot) ) left++;
		while((left <= right) && (**right > pivot) ) right--;
		if(left > right) break;
		int *temp = *left;
		*left++ = *right;
		*right-- = temp;
	}
	qsort_pint_ascending(pparray, right - pparray + 1);
	qsort_pint_ascending(left, pparray + size - left);
}

// sort pointers to ints in descending order
void qsort_pint_descending(int ** const pparray, const int size){
	if(size < 2)
		return;
	int pivot = *(pparray[size / 2]);
	int **left = pparray;
	int **right = pparray + size - 1;
	while(true){
		while((left <= right) && (**left > pivot) ) left++;
		while((left <= right) && (**right < pivot) ) right--;
		if(left > right) break;
		int *temp = *left;
		*left++ = *right;
		*right-- = temp;
	}
	qsort_pint_descending(pparray, right - pparray + 1);
	qsort_pint_descending(left, pparray + size - left);
}

// sort an array of pointers to string objects
void qsort_pstring_ascending(string ** const pparray, const int size){
	if(size < 2)
		return;
	string *pivot = pparray[size / 2];
	string **left = pparray;
	string **right = pparray + size - 1;
	while(true){
		while((left <= right) && **left < *pivot) left++;
		while((left <= right) && **right > *pivot) right--;
		if(left > right) break;
		string *temp = *left;
		*left++ = *right;
		*right-- = temp;
	}
	qsort_pstring_ascending(pparray, right - pparray + 1);
	qsort_pstring_ascending(left, pparray + size - left);
}

// sort an array of c-strings
void qsort_cstring_ascending(char ** const pparray, const int size){
	if(size < 2)
		return;
	char *pivot = pparray[size / 2];
	char **left = pparray;
	char **right = pparray + size - 1;
	while(true){
		while((left <= right) && _stricmp(*left, pivot) < 0) left++;
		while((left <= right) && _stricmp(*right, pivot) > 0) right--;
		if(left > right) break;
		char *temp = *left;
		*left++ = *right;
		*right-- = temp;
	}
	qsort_cstring_ascending(pparray, right - pparray + 1);
	qsort_cstring_ascending(left, pparray + size - left);
}

Now, a study of the above algortihm in assembly:

void __stdcall _qsort_int_asm(int *array, unsigned int siz);
void __stdcall qsort_int_asm(int *array, unsigned int siz)
{
#define PIVOT ebx
#define LEFT  esi
#define RIGHT edi
#define TEMP  eax
#define TEMP2 ecx
#define SIZE  edx
	__asm
	{
		mov SIZE,dword ptr [siz]
		cmp SIZE,2
		jl the_end
		push SIZE
		mov TEMP,dword ptr [array]
		push TEMP
		call _qsort_int_asm
the_end:
	}
}
void __stdcall _qsort_int_asm(int *array, unsigned int siz)
{
	__asm
	{
		mov LEFT,dword ptr [array]
		mov SIZE,dword ptr [siz]

		mov eax,SIZE
		shr eax,1
		mov PIVOT,LEFT
		mov PIVOT,dword ptr [PIVOT+eax*4]
		
		mov eax,SIZE 
		mov RIGHT,LEFT
		lea RIGHT,[RIGHT+eax*4-4] 

main_loop: ;while(true){
left_loop:
		cmp LEFT,RIGHT
		jg right_loop
		cmp [LEFT],PIVOT
		jge right_loop
		add LEFT,4
		jmp left_loop
right_loop:
		cmp LEFT,RIGHT
		jg loop_break
		cmp [RIGHT],PIVOT
		jle loop_break
		sub RIGHT,4
		jmp right_loop
loop_break:
		cmp LEFT,RIGHT
		jg loop_end
swap_left_right:
		mov TEMP,[LEFT]
		mov TEMP2,[RIGHT]
		mov [LEFT],TEMP2
		mov [RIGHT],TEMP
		add LEFT,4
		sub RIGHT,4
		jmp main_loop
loop_end:
		;qsort(array, right - array + 1);
		mov eax,RIGHT
		sub eax,dword ptr [array]
		sar eax,2
		add eax,1
		cmp eax,2
		jl qsort2
		push eax	
		mov ebx,dword ptr [array] 
		push ebx	

		call _qsort_int_asm

qsort2:
		;qsort(left, array + siz - left);
		mov eax,dword ptr [siz]
		mov ebx,dword ptr [array]
		lea ecx,[ebx+eax*4]
		sub ecx,LEFT
		sar ecx,2
		cmp ecx,2
		jl the_end
		push ecx 
		push LEFT

		call _qsort_int_asm

the_end:
	}
}

This site uses cookies. Cookies are simple text files stored on the user's computer. They are used for adding features and security to this site. Read the privacy policy.
CLOSE