Question

Task is to implement the following algorithms in Assembly language for x86 processor. 1) Quick sort Demonstrate Sorted Array of 10 elements in Watch Window for each one Running time of each algorithm

sample bubble sort code:
;----------------------------------------------------------
BubbleSort PROC USES eax ecx esi,
pArray:PTR DWORD, ; pointer to array
Count:DWORD ; array size
;
; Sort an array of 32-bit signed integers in ascending
; order, using the bubble sort algorithm.
; Receives: pointer to array, array size
; Returns: nothing
;-----------------------------------------------------------
mov ecx,Count
dec ecx ; decrement count by 1
L1: push ecx ; save outer loop count
mov esi,pArray ; point to first value
L2: mov eax,[esi] ; get array value
cmp [esi+4],eax ; compare a pair of values
jg L3 ; if [ESI] <= [ESI+4], no exchange
xchg eax,[esi+4] ; exchange the pair
mov [esi],eax
L3: add esi,4 ; move both pointers forward
loop L2 ; inner loop
pop ecx ; retrieve outer loop count
loop L1 ; else repeat outer loop
L4: ret
BubbleSort ENDP

Answer 1

QUICK SORT IN X86 ASSEMBLY :

Quick sort 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.

CODE

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

.686

.model FLAT

PUBLIC _qisort

_QSRT 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

_QSRT ENDS

END _______________________________________________________________________________________________________