PROWAREtech
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:
}
}
Comment