PROWAREtech

C/C++: Quick Sort 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.

Quicksort is a highly efficient and widely used sorting algorithm that employs the divide-and-conquer strategy. Here are the key aspects of the quicksort algorithm:

Basic Idea

Quicksort works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Steps of Quicksort

1. Choose a Pivot: Select an element from the array to serve as the pivot. Various strategies exist for choosing the pivot, such as picking the first element, the last element, a random element, or the median.

2. Partitioning: Rearrange the array so that elements less than the pivot are on the left, elements greater than the pivot are on the right, and the pivot is in its final position. This process is called partitioning.

3. Recursively Sort Sub-arrays: Apply the same process recursively to the sub-arrays of elements with smaller and larger values.

Key Points

• Time Complexity: The average-case time complexity is O(n•log(n)) O(n•log(n)), where n is the number of elements to be sorted. In the worst case, which occurs when the smallest or largest element is always chosen as the pivot, the time complexity is O(n²). However, with good pivot selection (e.g., using the median-of-three rule), the average case is more likely.
• Space Complexity: Quicksort is an in-place sorting algorithm, meaning it requires only a small, constant amount of extra storage space (i.e., O(log(n)) due to the recursion stack).
• Stability: Quicksort is not a stable sort, meaning that the relative order of equal sort items is not preserved.

Advantages and Disadvantages

Advantages:

• Generally faster than other (n•log(n)) algorithms like merge sort and heap sort for most inputs.
• In-place sorting, requiring minimal additional memory.

Disadvantages:

• Worst-case performance is O(n²), though this can be mitigated with good pivot selection.
• Not stable, so it may not be suitable when the stability of equal elements is required.

Practical Considerations

• Pivot Selection: Strategies like random pivot, median-of-three (selecting the median of the first, middle, and last elements), and others help avoid the worst-case scenarios.

Quicksort is widely used due to its efficiency and simplicity, especially for large datasets. Its performance can be significantly improved with good pivot selection and implementation optimizations.

// 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:
	}
}

Comment