PROWAREtech

articles » current » assembly » x86 » procedures » qsort

x86 Assembly: Quick Sort (qsort) Procedure

The famous quicksort algorithm in x86 assembly.

Use MASM for Visual C++ Express Edition 2005 to compile this procedure.

This same procedure is available in 64-bit x64 Assembly.

Quicksort is a great, reliable general purpose sorting algorithm. The TITLE is the C/C++ function declaration.

This short procedure can sort an array of pointers to strings or objects... or anything. compare_func must return less than zero when element1 is less than element2, zero when they are equal, and greater than zero when element1 is greater than element2. Functions like strcmp and wcsicmp_asm function in this manner. This version of quick sort uses insertion sort to sort smaller sub arrays. An example of using the procedure follows.

The procedure token must be proceeded by a underscore so that the linker will find it for a C/C++ compilation.

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(n2). 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(n2), 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.

TITLE 'extern "C" void qisort(void *array[], const unsigned size, int (*compare_func)(const void *element1, const void *element2));'
.386P

.model FLAT

PUBLIC  _qisort

_TEXT  SEGMENT
_MAX_ISORT_SIZE = 30
_qisort  PROC NEAR

	push  ecx
	push  ebx

	mov  ebx, DWORD PTR [esp+16] ; size
	cmp  ebx, _MAX_ISORT_SIZE
	push ebp
	push esi
	push edi
	jbe  insertion_sort

quick_sort:

	mov  eax, DWORD PTR [esp+24] ; array
	mov  ecx, ebx
	shr  ecx, 1
	mov  edx, DWORD PTR [eax+ecx*4]

	lea  ebp, DWORD PTR [ebx*4]
	mov  DWORD PTR [esp+28], edx ; [esp+28] = pivot (middle)
	mov  edi, eax
	lea  esi, DWORD PTR [eax+ebp-4]

label2:

	cmp  edi, esi
	ja   SHORT label7

label3:

	mov  eax, DWORD PTR [esp+28] ; pivot (middle)
	mov  ecx, DWORD PTR [edi]
	mov  ebx, DWORD PTR [esp+32] ; compare_func
	push eax
	push ecx
	call ebx
	add  esp, 8
	test eax, eax
	jge  SHORT label4
	add  edi, 4
	cmp  edi, esi
	ja   SHORT label8
	jmp  SHORT label3

label4:

	cmp  edi, esi
	ja   SHORT label8

label5:

	mov  edx, DWORD PTR [esp+28] ; pivot (middle)
	mov  eax, DWORD PTR [esi]
	push edx
	push eax
	call ebx
	add  esp, 8
	test eax, eax
	jle  SHORT label6
	sub  esi, 4
	cmp  edi, esi
	ja   SHORT label8
	jmp  SHORT label5

label6:

	cmp  edi, esi
	ja   SHORT label8
	mov  eax, DWORD PTR [edi]
	mov  ecx, DWORD PTR [esi]
	mov  DWORD PTR [edi], ecx
	mov  DWORD PTR [esi], eax
	mov  eax, DWORD PTR [esp+24] ; array
	add  edi, 4
	sub  esi, 4
	jmp  SHORT label2

label7:

	mov  ebx, DWORD PTR [esp+32] ; compare_func
	jmp  SHORT label9

label8:

	mov  eax, DWORD PTR [esp+24] ; array

label9:

	sub  esi, eax
	sar  esi, 2
	push ebx
	inc  esi
	push esi
	push eax
	call _qisort

	mov  edx, DWORD PTR [esp+36] ; array
	sub  ebp, edi
	add  ebp, edx
	sar  ebp, 2
	mov  ebx, ebp
	add  esp, 12
	cmp  ebx, _MAX_ISORT_SIZE
	mov  DWORD PTR [esp+24], edi ; [esp+24] = array
	ja   quick_sort

insertion_sort:

	mov  ebp, 1
	cmp  ebx, ebp
	jbe  SHORT label14
	mov  edx, DWORD PTR [esp+24] ; array
	lea  esi, DWORD PTR [edx+4]
	mov  DWORD PTR -4+[esp+20], esi

label10:

	test ebp, ebp
	mov  eax, DWORD PTR [esi]
	mov  DWORD PTR [esp+28], eax ; [esp+28] = temp for swapping
	mov  edi, ebp
	jbe  SHORT label13

	add  esi, -4          ; fffffffcH

label11:

	mov  ecx, DWORD PTR [esi]
	mov  edx, DWORD PTR [esp+28] ; [esp+28] = temp for swapping
	push ecx
	push edx
	call DWORD PTR [esp+40] ; compare_func
	add  esp, 8
	test eax, eax
	jge  SHORT label12

	mov  eax, DWORD PTR [esi]
	mov  DWORD PTR [esi+4], eax

	dec  edi
	sub  esi, 4
	test edi, edi
	ja   SHORT label11

label12:

	mov  esi, DWORD PTR -4+[esp+20]

label13:

	mov  ecx, DWORD PTR [esp+28] ; [esp+28] = temp for swapping
	mov  edx, DWORD PTR [esp+24] ; array
	inc  ebp
	add  esi, 4
	cmp  ebp, ebx
	mov  DWORD PTR [edx+edi*4], ecx
	mov  DWORD PTR -4+[esp+20], esi
	jb   SHORT label10

label14:

	pop  edi
	pop  esi
	pop  ebp
	pop  ebx
	pop  ecx

	ret  0

_qisort  ENDP
_TEXT  ENDS
END

See the x64 assembly example for a study of the quicksort algorithm in assembly.

This is an example program using the above qisort procedure to sort an array of integers.

#include <stdlib.h>
#include <time.h>

extern "C" void qisort(void *array[], const unsigned size, int (*compare_func)(const void *element1, const void *element2));

int compare_ascending(const int a, const int b)
{
	return a - b;
}

int array[1000000];

int main()
{
	srand(time(NULL));
	int i;
	unsigned size = sizeof(array)/sizeof(void*);
	for(i = 0; i < size; i++)
	{
		if(rand() % 3 == 0)
			array[i] = -rand();
		else
			array[i] = rand();
	}
	qisort((void **)array, size, (int (*)(const void*,const void*))compare_ascending);
	return 0;
}

This is an example program using the above qisort procedure with objects.

#include <stdio.h>
#include <string.h>

extern "C" void qisort(void *array[], const unsigned size, int (*compare_func)(const void *element1, const void *element2));

class Person
{
	char last[100], first[100];
	Person(){}
public:
	Person(const char *lastname, const char *firstname)
	{
		strcpy_s(last, lastname);
		strcpy_s(first, firstname);
	}
	const char *lastname() const {return last;}
	const char *firstname() const {return first;}
};

int compare_people(const Person *p1, const Person *p2)
{
	if(int i = strcmp(p1->lastname(), p2->lastname()))
		return i;
	return strcmp(p1->firstname(), p2->firstname());
}

int main()
{
	Person *array[] = {
		new Person("Smith","John"),
		new Person("Smith","Jane"),
		new Person("Bleaux","Joe"),
		new Person("Jackson","Miles"),
		new Person("Jackson","Andrew")
	};
	unsigned size = sizeof(array)/sizeof(void*);
	qisort((void **)array, size, (int (*)(const void*,const void*))compare_people);
	for(int i = 0; i < size; delete array[i++])
		printf("%s, %s\r\n", array[i]->lastname(), array[i]->firstname());
	return 0;
}

This quick sort procedure sorts an array of integers.

TITLE 'extern "C" void __stdcall qsort(int array[], const unsigned int size);'

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

.386P

.model FLAT

PUBLIC	_qsort@8

_TEXT	SEGMENT
_qsort@8 PROC NEAR

;if (size > 1) {

mov  eax, DWORD PTR [esp+8] ; size
cmp  eax, 1
jbe  SHORT label8
push ebx
push ebp
push esi
push edi
mov  edi, DWORD PTR [esp+20] ; array

label1:

;	int pivot = array[size / 2];

mov  ecx, eax
shr  ecx, 1
mov  edx, DWORD PTR [edi+ecx*4]

;	int *left = array;
;	int *right = array + size - 1;

lea  ebx, DWORD PTR [eax*4]
mov  esi, edi
lea  eax, DWORD PTR [ebx+edi-4]

label2:

;	while (1) {
;		while ((left <= right) && (*left < pivot)) left++;

cmp  esi, eax
ja   SHORT label7

label3:

cmp  DWORD PTR [esi], edx
jge  SHORT label4
add  esi, 4
cmp  esi, eax
ja   SHORT label7
jmp  SHORT label3

label4:

;		while ((left <= right) && (*right > pivot)) right--;

cmp  esi, eax
ja   SHORT label7

label5:

cmp  DWORD PTR [eax], edx
jle  SHORT label6
sub  eax, 4
cmp  esi, eax
ja   SHORT label7
jmp  SHORT label5

label6:

;		if (left > right) break;

cmp  esi, eax
ja   SHORT label7

;		int temp = *left;
;		*left++ = *right;

mov  ebp, DWORD PTR [eax]
mov  ecx, DWORD PTR [esi]
mov  DWORD PTR [esi], ebp
add  esi, 4

;		*right-- = temp;

mov  DWORD PTR [eax], ecx
sub  eax, 4
jmp  SHORT label2

label7:

;	}
;	qsort(array, right - array + 1);

sub  eax, edi
sar  eax, 2
inc  eax
push eax
push edi
call _qsort@8

;	qsort(left, array + size - left);

sub  ebx, esi
add  ebx, edi
sar  ebx, 2
mov  eax, ebx
cmp  eax, 1
mov  edi, esi
ja   SHORT label1

pop  edi
pop  esi
pop  ebp
pop  ebx

label8:

ret  8
_qsort@8 ENDP
_TEXT	ENDS
END

This quicksort algorithm uses insertion sort when sorting a subarray of 30 or less elements; so big arrays are sorted with quicksort and insertion sort cleans up the little ones for a roughly 20% performance improvement.

TITLE 'extern "C" void __stdcall qisort(int array[], const unsigned int size);'

;void __stdcall qisort(int array[], const unsigned int size) {
;	if (size > 30) {
;		int pivot = array[size / 2];
;		int *left = array;
;		int *right = array + size - 1;
;		while (1) {
;			while ((left <= right) && (*left < pivot)) left++;
;			while ((left <= right) && (*right > pivot)) right--;
;			if (left > right) break;
;			int temp = *left;
;			*left++ = *right;
;			*right-- = temp;
;		}
;		qisort(array, right - array + 1);
;		qisort(left, array + size - left);
;	}
;	else {
;		for (unsigned int i = 1; i < size; ++i) {
;			int temp = array[i];
;			unsigned int j = i;
;			while (j > 0 && temp < array[j - 1]) {
;				array[j] = array[j - 1];
;				j--;
;			}
;			array[j] = temp;
;		}
;	}
;}

.386P

.model FLAT

PUBLIC	_qisort@8

_TEXT	SEGMENT
_MAX_ISORT_SIZE = 30
_qisort@8 PROC NEAR

push  ebx
push  ebp

;if (size > 30) {

mov  ebp, DWORD PTR [esp+12] ; array
push esi
push edi
mov  edi, DWORD PTR [esp+24] ; size
cmp  edi, _MAX_ISORT_SIZE
jbe  SHORT insertion_sort

quick_sort:

;	int pivot = array[size / 2];

mov  eax, edi
shr  eax, 1
mov  edx, DWORD PTR [ebp+eax*4]

;	int *left = array;
;	int *right = array + size - 1;

shl  edi, 2
mov  esi, ebp
lea  eax, DWORD PTR [edi+ebp-4]

quick_sort_loop:

;	while (1) {
;		while ((left <= right) && (*left < pivot)) left++;

cmp  esi, eax
ja   SHORT label5
  
label1:

cmp  DWORD PTR [esi], edx
jge  SHORT label2
add  esi, 4
cmp  esi, eax
ja   SHORT label5
jmp  SHORT label1
  
label2:

;		while ((left <= right) && (*right > pivot)) right--;

cmp  esi, eax
ja   SHORT label5

label3:

cmp  DWORD PTR [eax], edx
jle  SHORT label4
sub  eax, 4
cmp  esi, eax
ja   SHORT label5
jmp  SHORT label3

label4:

;		if (left > right) break;

cmp  esi, eax
ja   SHORT label5

;		int temp = *left;
;		*left++ = *right;

mov  ebx, DWORD PTR [eax]
mov  ecx, DWORD PTR [esi]
mov  DWORD PTR [esi], ebx
add  esi, 4

;		*right-- = temp;

mov  DWORD PTR [eax], ecx
sub  eax, 4
jmp  SHORT quick_sort_loop

label5:

;	}
;	qisort(array, right - array + 1);

sub  eax, ebp
sar  eax, 2
inc  eax
push eax
push ebp
call _qisort@8

;	qisort(left, array + size - left);

sub  edi, esi
add  edi, ebp
sar  edi, 2
cmp  edi, _MAX_ISORT_SIZE
mov  ebp, esi
ja   SHORT quick_sort

;}
;else {

insertion_sort:

;	for (unsigned int i = 1; i < size; ++i) {

mov  esi, 1
cmp  edi, esi
jbe  SHORT label10
lea  ecx, DWORD PTR [ebp+4]
mov  DWORD PTR 8+[esp+12], ecx

label6:

;		unsigned int j = i;
;		while (j > 0 && temp < array[j - 1]) {

test esi, esi
mov  ebx, DWORD PTR [ecx]
mov  eax, esi
jbe  SHORT label9

;			int temp = array[i];

add  ecx, -4

label7:

;		unsigned int j = i;
;		while (j > 0 && temp < array[j - 1]) {

mov  edx, DWORD PTR [ecx]
cmp  ebx, edx
jge  SHORT label8

;			array[j] = array[j - 1];

mov  DWORD PTR [ecx+4], edx

;			j--;

dec  eax
sub  ecx, 4
test eax, eax
ja   SHORT label7

label8:

;		unsigned int j = i;
;		while (j > 0 && temp < array[j - 1]) {

mov  ecx, DWORD PTR 8+[esp+12]

label9:

;	}
;	else {
;		for (unsigned int i = 1; i < size; ++i) {

inc  esi
add  ecx, 4
cmp  esi, edi

;	}
;	array[j] = temp;

mov  DWORD PTR [ebp+eax*4], ebx
mov  DWORD PTR 8+[esp+12], ecx
jb   SHORT label6

label10:

pop  edi
pop  esi
pop  ebp
pop  ebx

ret  8

_qisort@8 ENDP
_TEXT	ENDS
END
.
..
x86 Assembly: atoi Procedure

ASCII string to int - Convert Strings to Numbers.
x86 Assembly: itoa Procedure

int to ASCII string - Convert Numbers to Strings.
x86 Assembly: Quick Sort (qsort) Procedure

The famous quicksort algorithm in x86 assembly.
x86 Assembly: strcpy Procedure

Copy ASCII string.
x86 Assembly: strlen Procedure

Find ASCII string length.
x86 Assembly: strstr Procedure

Find ASCII substring in an ASCII string.
x86 Assembly: strtok Procedure

Find tokens in ASCII string.
x86 Assembly: strtowcs Procedure

ASCII string to wide-char string.
x86 Assembly: wcscmp Procedure

compare two wide-char strings.
x86 Assembly: wcscpy Procedure

Copy wide-char string.
x86 Assembly: wcsicmp Procedure

Compare two wide-char strings, ignore case.
x86 Assembly: wcslen Procedure

Find wide-char string length.
x86 Assembly: wcsncpy Procedure

Copy wide-char string with specified length.
x86 Assembly: wcstok Procedure

Find tokens in wide-char string.

PROWAREtech

Hello there! How can I help you today?
Ask any question

PROWAREtech

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.
ACCEPT REJECT