V tvém kódu se vrtat nebudu, dělá se to nějak takhle. Za domácí úkol máš zjistit, proč na QuickSort stačí jenom jedna rekurze a ne dvě jak máš ty.
int quicksort(int* pole, unsigned short delka_pole)
{
_asm
{
movzx eax,delka_pole
test eax,eax
jz Exit
mov esi,pole
lea edi,dword ptr [esi+eax*4-4]
mov ebx,edi
Start:
lea eax,dword ptr [esi+edi]
shr eax,1
and eax,~0x03
mov ecx,dword ptr [eax]
Left:
cmp ecx,dword ptr [esi]
jng Right
lea esi,dword ptr [esi+4]
jmp Left
Right:
cmp ecx,dword ptr [edi]
jnl Swap
lea edi,dword ptr [edi-4]
jmp Right
Swap:
cmp esi,edi
ja NestingLeft
mov eax,dword ptr [esi]
mov edx,dword ptr [edi]
mov dword ptr [esi],edx
mov dword ptr [edi],eax
lea esi,dword ptr [esi+4]
lea edi,dword ptr [edi-4]
cmp esi,edi
jb Left
NestingLeft:
sub edi,pole
jbe NestingRight
shr edi,2
lea edi,dword ptr [edi+1]
push edi
mov eax,pole
push eax
call quicksort
add esp,8
NestingRight:
mov eax,ebx
sub eax,esi
jbe Exit
shr eax,2
lea eax,dword ptr [eax+1]
mov pole,esi
mov delka_pole,ax
mov edi,ebx
jmp Start
Exit:
}
}
Jak jste prosím zjistil, že rekurze má být jenn jedna? Já jsem k zápočtu odevzdával kód, regurzi mám pro pravou i levou, a nevidím na tom nic špatného. Je to tedy v NASM..
BITS 32
section .data
global a_quick_sort
section .text
a_quick_sort: ;int quick_sort (int *a, int ll, int rr)
enter 10, 0
push EBX
push ECX
push EDX
; pole hodnot
mov EBX, [EBP+8]
; levy a pravy index
mov ESI, [EBP+12] ; v ESI je l = ll
mov EDI, [EBP+16] ; v EDI je r = rr
; medianem je prvni prvek
mov EAX, ESI
add EAX, EDI
xor EDX, EDX
mov ECX, 2
div ECX
mov EAX, [EBX+EAX*4]
do: ; hlavni cyklus do-while
w1: cmp [EBX+ESI*4], AX ; cyklus while pro levou polovinu
jnl w2
inc ESI
jmp w1
w2: cmp AX, [EBX+EDI*4] ; cyklus while pro pravou polovinu
jnl x
dec EDI
jmp w2
x: cmp ESI, EDI ; if (l<=r) pak prehod prvky
jg xx
mov EDX, [EBX+ESI*4]
mov ECX, [EBX+EDI*4]
mov [EBX+ESI*4], ECX
mov [EBX+EDI*4], EDX
inc ESI
dec EDI
xx: ; jinak neprehazuj
cmp ESI, EDI ; while (l<=r)
jle do
; setrideni leveho useku
r1: cmp [EBP+12], EDI
jge r2
push EDI
push dword [EBP+12]
push dword [EBP+8]
call a_quick_sort
pop EAX
pop EAX
pop EAX
; setrideni praveho useku
r2: cmp ESI, [EBP+16]
jge nr
push dword [EBP+16]
push ESI
push dword [EBP+8]
call a_quick_sort
pop EAX
pop EAX
pop EAX
nr:
xor EAX, EAX ; navratova hodnota
pop EDX
pop ECX
pop EBX
leave
ret
end
22 Odpovědí
10779 Zhlédnutí