📄 quicksort.asm
字号:
; Date: 18.04.2004
.code
IFNDEF PURE_ALGORITHM
QuickSort PROTO :DWORD, :DWORD
QuickSort_Sort PROTO :DWORD, :DWORD
StraightQuickSort PROTO :DWORD, :DWORD
QuickSort PROC Arr:DWORD, count:DWORD
mov eax, Arr
mov ebx, count
lea ebx, [eax + ebx*4 - 4]
push ebx
push eax
call QuickSort_Sort
@Return:
ret
QuickSort ENDP
QuickSort_Sort PROC left:DWORD, right:DWORD
mov edx, right
mov ebx, edx
mov eax, left
sub eax, 4
mov ecx, DWORD PTR [edx]
@Loop1:
@@:
add eax, 4
;-------------------------------------------------------------------------------
IncCMPCounter
DelayAfterComparison eax, edx
;-------------------------------------------------------------------------------
cmp ecx, DWORD PTR [eax]
ja @B
@@:
cmp ebx, left
je @F
sub ebx, 4
;-------------------------------------------------------------------------------
IncCMPCounter
DelayAfterComparison ebx, edx
;-------------------------------------------------------------------------------
cmp ecx, DWORD PTR [ebx]
jb @B
@@:
mov esi, DWORD PTR [eax]
mov edi, DWORD PTR [ebx]
mov DWORD PTR [ebx], esi
mov DWORD PTR [eax], edi
;-------------------------------------------------------------------------------
IncMOVCounter
RefreshElement eax
RefreshElement ebx
DelayAfterExchange
;-------------------------------------------------------------------------------
cmp ebx, eax
ja @Loop1
mov edi, DWORD PTR [eax]
mov DWORD PTR [ebx], edi
;-------------------------------------------------------------------------------
IncMOVCounter
RefreshElement ebx
DelayAfterExchange
;-------------------------------------------------------------------------------
mov edi, DWORD PTR [edx]
mov DWORD PTR [eax], edi
mov DWORD PTR [edx], esi
;-------------------------------------------------------------------------------
IncMOVCounter
RefreshElement eax
RefreshElement edx
DelayAfterExchange
DelayAfterPass
;-------------------------------------------------------------------------------
push eax
push edx
mov ecx, left
sub eax, 4
cmp eax, ecx
jna @F
push eax
push ecx
call QuickSort_Sort
@@:
pop edx
pop eax
add eax, 4
cmp edx, eax
jna @Return
push edx
push eax
call QuickSort_Sort
@Return:
ret
QuickSort_Sort ENDP
StraightQuickSort PROC Arr:DWORD, count:DWORD
LOCAL First :DWORD
LOCAL Last :DWORD
LOCAL cntr :DWORD
LOCAL temp :DWORD
LOCAL tempElementIndex :DWORD
mov esi, Arr ; source address in ESI
mov cntr, 0
; --------------------------
; allocate temporary buffer
; --------------------------
mov eax, count
add eax, 40
mov SortInfo.usedMemory, eax
invoke SysAllocStringByteLen, 0, eax
test eax, eax
jz @InsufficientMemory
mov SortInfo.hMemory, eax
mov edi, eax ; buffer address in EDI
; ------------------------------------
; set First and Last reference values
; ------------------------------------
mov First, 0
mov eax, count
dec eax
mov Last, eax ; Last = count - 1
@Loop1:
;-------------------------------------------------------------------------------
DelayAfterPass
;-------------------------------------------------------------------------------
; -------------------
; calculate midpoint
; -------------------
mov eax, Last
add eax, First
shr eax, 1
; =========================
mov ebx, DWORD PTR [esi + eax*4] ; midpoint in EBX
;-------------------------------------------------------------------------------
push esi
lea esi, [esi + eax*4]
mov tempElementIndex, esi
pop esi
;-------------------------------------------------------------------------------
mov temp, ebx
; =========================
mov ecx, First
mov edx, Last
; ---------------------------------------------------------
@Loop2:
;-------------------------------------------------------------------------------
IncCMPCounter
push esi
push ebx
lea esi, [esi + ecx*4]
mov ebx, tempElementIndex
DelayAfterComparison esi, ebx
pop ebx
pop esi
;-------------------------------------------------------------------------------
cmp DWORD PTR [esi + ecx*4], ebx
jge wl2
inc ecx
jmp @Loop2
wl2:
;-------------------------------------------------------------------------------
IncCMPCounter
push esi
push ebx
lea esi, [esi + edx*4]
mov ebx, tempElementIndex
DelayAfterComparison esi, ebx
pop ebx
pop esi
;-------------------------------------------------------------------------------
cmp DWORD PTR [esi+edx*4], ebx
jle wl2Out
dec edx
jmp wl2
wl2Out:
cmp ecx, edx ; If ecx > edx, exit inner loop
jg exit_innerx
; =========================
mov eax, DWORD PTR [esi+ecx*4]
mov ebx, DWORD PTR [esi+edx*4] ; swap elements
mov DWORD PTR [esi+ecx*4], ebx
mov DWORD PTR [esi+edx*4], eax
;-------------------------------------------------------------------------------
IncMOVCounter
push eax
lea eax, [esi+ecx*4]
RefreshElement eax
lea eax, [esi+edx*4]
RefreshElement eax
pop eax
DelayAfterExchange
;-------------------------------------------------------------------------------
; =========================
mov ebx, temp ; restore EBX
inc ecx
dec edx
cmp ecx, edx
jle @Loop2
exit_innerx:
; ---------------------------------------------------------
cmp ecx, Last ; If ecx < Last jump over
jg iNxt
; =========================
mov eax, cntr
mov DWORD PTR [edi+eax*4], ecx
mov ebx, Last
mov DWORD PTR [edi+eax*4+4], ebx
;-------------------------------------------------------------------------------
IncMOVCounter
;-------------------------------------------------------------------------------
; =========================
add cntr, 2
iNxt:
mov ebx, temp ; restore EBX
mov Last, edx ; Last = EDX
cmp edx, First ; compare Last & First
jg @Loop1
cmp cntr, 0
jz @Return
sub cntr, 2
; =========================
mov eax, cntr
mov ebx, DWORD PTR [edi+eax*4]
mov First, ebx
mov ebx, DWORD PTR [edi+eax*4+4]
mov Last, ebx
;-------------------------------------------------------------------------------
IncMOVCounter
;-------------------------------------------------------------------------------
; =========================
mov ebx, temp ; restore EBX
jmp @Loop1
@Return:
invoke SysFreeString, SortInfo.hMemory
ret
@InsufficientMemory:
mov SortInfo.errorId, ERROR_NOT_ENOUGH_MEMORY
ret
StraightQuickSort ENDP
ELSE
QuickSort_PURE PROTO :DWORD, :DWORD
QuickSort_Sort_PURE PROTO :DWORD, :DWORD
StraightQuickSort_PURE PROTO :DWORD, :DWORD
QuickSort_PURE PROC Arr:DWORD, count:DWORD
mov eax, Arr
mov ebx, count
lea ebx, [eax + ebx*4 - 4]
push ebx
push eax
call QuickSort_Sort_PURE
@Return:
ret
QuickSort_PURE ENDP
QuickSort_Sort_PURE PROC left:DWORD, right:DWORD
mov edx, left
mov ebx, right
mov eax, edx
sub eax, 4
mov ecx, DWORD PTR [ebx]
@Loop1:
@@:
add eax, 4
;-------------------------------------------------------------------------------
IncCMPCounter
;-------------------------------------------------------------------------------
cmp ecx, DWORD PTR [eax]
ja @B
@@:
cmp ebx, edx
je @F
sub ebx, 4
;-------------------------------------------------------------------------------
IncCMPCounter
;-------------------------------------------------------------------------------
cmp ecx, DWORD PTR [ebx]
jb @B
@@:
mov esi, DWORD PTR [eax]
mov edi, DWORD PTR [ebx]
mov DWORD PTR [ebx], esi
mov DWORD PTR [eax], edi
;-------------------------------------------------------------------------------
IncMOVCounter
;-------------------------------------------------------------------------------
cmp ebx, eax
ja @Loop1
mov edx, right
mov edi, DWORD PTR [eax]
mov DWORD PTR [ebx], edi
;-------------------------------------------------------------------------------
IncMOVCounter
;-------------------------------------------------------------------------------
mov edi, DWORD PTR [edx]
mov DWORD PTR [eax], edi
mov DWORD PTR [edx], esi
;-------------------------------------------------------------------------------
IncMOVCounter
;-------------------------------------------------------------------------------
push eax
push edx
mov ecx, left
sub eax, 4
cmp eax, ecx
jna @F
push eax
push ecx
call QuickSort_Sort_PURE
@@:
pop edx
pop eax
add eax, 4
cmp edx, eax
jna @Return
push edx
push eax
call QuickSort_Sort_PURE
@Return:
ret
QuickSort_Sort_PURE ENDP
StraightQuickSort_PURE PROC Arr:DWORD, count:DWORD
LOCAL First :DWORD
LOCAL Last :DWORD
LOCAL cntr :DWORD
LOCAL temp :DWORD
mov esi, Arr ; source address in ESI
mov cntr, 0
; --------------------------
; allocate temporary buffer
; --------------------------
mov eax, count
add eax, 40
mov SortInfo.usedMemory, eax
invoke SysAllocStringByteLen, 0, eax
test eax, eax
jz @InsufficientMemory
mov SortInfo.hMemory, eax
mov edi, eax ; buffer address in EDI
; ------------------------------------
; set First and Last reference values
; ------------------------------------
mov First, 0
mov eax, count
dec eax
mov Last, eax ; Last = count - 1
@Loop1:
; -------------------
; calculate midpoint
; -------------------
mov eax, Last
add eax, First
shr eax, 1
; =========================
mov ebx, DWORD PTR [esi + eax*4] ; midpoint in EBX
mov temp, ebx
; =========================
mov ecx, First
mov edx, Last
; ---------------------------------------------------------
@Loop2:
;-------------------------------------------------------------------------------
IncCMPCounter
;-------------------------------------------------------------------------------
cmp DWORD PTR [esi + ecx*4], ebx
jge wl2
inc ecx
jmp @Loop2
wl2:
;-------------------------------------------------------------------------------
IncCMPCounter
;-------------------------------------------------------------------------------
cmp DWORD PTR [esi+edx*4], ebx
jle wl2Out
dec edx
jmp wl2
wl2Out:
cmp ecx, edx ; If ecx > edx, exit inner loop
jg exit_innerx
; =========================
mov eax, DWORD PTR [esi+ecx*4]
mov ebx, DWORD PTR [esi+edx*4] ; swap elements
mov DWORD PTR [esi+ecx*4], ebx
mov DWORD PTR [esi+edx*4], eax
;-------------------------------------------------------------------------------
IncMOVCounter
;-------------------------------------------------------------------------------
; =========================
mov ebx, temp ; restore EBX
inc ecx
dec edx
cmp ecx, edx
jle @Loop2
exit_innerx:
; ---------------------------------------------------------
cmp ecx, Last ; If ecx < Last jump over
jg iNxt
; =========================
mov eax, cntr
mov DWORD PTR [edi+eax*4], ecx
mov ebx, Last
mov DWORD PTR [edi+eax*4+4], ebx
;-------------------------------------------------------------------------------
IncMOVCounter
;-------------------------------------------------------------------------------
; =========================
add cntr, 2
iNxt:
mov ebx, temp ; restore EBX
mov Last, edx ; Last = EDX
cmp edx, First ; compare Last & First
jg @Loop1
cmp cntr, 0
jz @Return
sub cntr, 2
; =========================
mov eax, cntr
mov ebx, DWORD PTR [edi+eax*4]
mov First, ebx
mov ebx, DWORD PTR [edi+eax*4+4]
mov Last, ebx
;-------------------------------------------------------------------------------
IncMOVCounter
;-------------------------------------------------------------------------------
; =========================
mov ebx, temp ; restore EBX
jmp @Loop1
@Return:
invoke SysFreeString, SortInfo.hMemory
ret
@InsufficientMemory:
mov SortInfo.errorId, ERROR_NOT_ENOUGH_MEMORY
ret
StraightQuickSort_PURE ENDP
ENDIF⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -