Anyway, I've implemented a HybridSort algorithm, which behaves like QuickSort when the array appears to be randomly shuffled, and it behaves like MergeSort when the array appears to be nearly-sorted:
Code: Select all
;HybridSort algoritam - kombinacija QuickSort algoritma i MergeSort algoritma.
AsmStart
ispisPoruka=1
macro staviIntNaSistemskiStog x
{
sub esp,4
fld dword [x]
fistp dword [esp]
}
macro staviPokazivacNaSistemskiStog x
{
sub esp,4
lea ebx,[x]
mov [esp],ebx
}
macro staviStringNaSistemskiStog x
{
sub esp,4
mov dword [esp],x
}
format PE console
entry start
include 'win32a.inc'
section '.text' code executable
start:
if ispisPoruka=1
jmp velicinaUnosa$
velicinaUnosa db "Unesite koliko cete brojeva unijeti.",10,0
velicinaUnosa$:
staviStringNaSistemskiStog velicinaUnosa
call [printf]
end if
staviPokazivacNaSistemskiStog n
jmp znakZaFloat$
znakZaFloat db "%f",0
znakZaFloat$:
staviStringNaSistemskiStog znakZaFloat
call [scanf]
if ispisPoruka=1
jmp pitajZaUnos$
pitajZaUnos db "Unesite te brojeve:",10,0
pitajZaUnos$:
staviStringNaSistemskiStog pitajZaUnos
call [printf]
end if
AsmEnd
i:=0
brojac:=0
vrhStoga:=0
While i<n
pokazivac:=4*i
AsmStart
fld dword [pokazivac]
fistp dword [pokazivac]
lea ebx,[original]
add ebx,[pokazivac]
staviPokazivacNaSistemskiStog ebx
staviStringNaSistemskiStog znakZaFloat
call [scanf]
AsmEnd
i:=i+1
EndWhile
AsmStart
call [clock]
mov [procesorskoVrijeme],eax
AsmEnd
razvrstanost:=0
i:=0
While i<n-1
razvrstanost:=razvrstanost+(original(i)<original(i+1))
i:=i+1
brojac:=brojac+1
EndWhile
razvrstanost:=razvrstanost/((n-1)/2)-1
AsmStart
if ispisPoruka=1
jmp izvjesceORazvrstanosti$
izvjesceORazvrstanosti db "Razvrstanost pocetnog niza iznosi: %f",10,0
izvjesceORazvrstanosti$:
fld dword [razvrstanost]
fstp qword [esp]
staviStringNaSistemskiStog izvjesceORazvrstanosti
call [printf]
end if
AsmEnd
i:=2
While i<7 | i=7
razvrstanostNa(i):=pow(abs(razvrstanost),i)
If razvrstanost=0
razvrstanostNa(i):=0
EndIf
If mod(i,2)=1 & razvrstanost<0
razvrstanostNa(i):=-razvrstanostNa(i)
EndIf
i:=i+1
EndWhile
polinomPodApsolutnom:=2.38854*razvrstanostNa(7)-0.284258*razvrstanostNa(6)-1.87104*razvrstanostNa(5)+0.372637*razvrstanostNa(4)+0.167242*razvrstanostNa(3)-0.0884977*razvrstanostNa(2)+0.315119*razvrstanost
eNaKoju:=(ln(n)+ln(ln(n)))*1.05+(ln(n)-ln(ln(n)))*0.83*abs(polinomPodApsolutnom)
ocekivaniBrojUsporedbi:=exp(eNaKoju)
ocekivanoOdMergeSorta:=2*n*ln(n)/ln(2)
AsmStart
if ispisPoruka=1
jmp ispisOTomeStoOcekujemo$
ispisOTomeStoOcekujemo db "Od QuickSorta ocekujemo %f usporedbi, a od MergeSorta ocekujemo %f usporedbi.",10,0
ispisOTomeStoOcekujemo$:
fld dword [ocekivanoOdMergeSorta]
fstp qword [esp+8]
fld dword [ocekivaniBrojUsporedbi]
fstp qword [esp]
staviStringNaSistemskiStog ispisOTomeStoOcekujemo
call [printf]
end if
AsmEnd
najmanjiCijeliBrojKojiSeMozeDodatiNaBrojac:=1
pomocniBrojac:=0
If razvrstanost=1
AsmStart
if ispisPoruka=1
jmp nizJeVecRazvrstan$
nizJeVecRazvrstan db "Niz je vec poredan, ne radimo nista.",10,0
nizJeVecRazvrstan$:
invoke printf,nizJeVecRazvrstan
end if
AsmEnd
ElseIf razvrstanost=(-1)
AsmStart
if ispisPoruka=1
jmp nizJeObrnutoRazvrstan$
nizJeObrnutoRazvrstan db "Niz je obrnuto poredan.",10,0
nizJeObrnutoRazvrstan$:
invoke printf,nizJeObrnutoRazvrstan
end if
AsmEnd
i:=0
While i<n
pomocni(i):=original(n-i-1)
i:=i+1
brojac:=brojac+1
EndWhile
i:=0
While i<n
original(i):=pomocni(i)
i:=i+1
EndWhile
ElseIf ocekivaniBrojUsporedbi<ocekivanoOdMergeSorta
AsmStart
if ispisPoruka=1
jmp radimoQuickSort$
radimoQuickSort db "Primijenit cemo QuickSort algoritam.",10,0
radimoQuickSort$:
invoke printf,radimoQuickSort
end if
AsmEnd
vrhStoga:=vrhStoga+1
stogSDonjimGranicama(vrhStoga):=0
stogSGornjimGranicama(vrhStoga):=n
While vrhStoga>0
gornjaGranica:=stogSGornjimGranicama(vrhStoga)
donjaGranica:=stogSDonjimGranicama(vrhStoga)
vrhStoga:=vrhStoga-1
gdjeJePivot:=donjaGranica
i:=donjaGranica+1
While i<gornjaGranica
If original(i)<original(donjaGranica)
gdjeJePivot:=gdjeJePivot+1
EndIf
i:=i++
EndWhile
staviManje:=donjaGranica
staviVece:=gdjeJePivot+1
pomocni(gdjeJePivot):=original(donjaGranica)
i:=donjaGranica+1
While i<gornjaGranica
If original(i)<original(donjaGranica)
pomocni(staviManje):=original(i)
staviManje:=staviManje+1
Else
pomocni(staviVece):=original(i)
staviVece:=staviVece+1
EndIf
pomocniBrojac:=pomocniBrojac+1
If pomocniBrojac=najmanjiCijeliBrojKojiSeMozeDodatiNaBrojac
brojac:=brojac+pomocniBrojac
pomocniBrojac:=0
EndIf
i:=i+1
EndWhile
i:=donjaGranica
While i<gornjaGranica
original(i):=pomocni(i)
i:=i+1
EndWhile
If gdjeJePivot<gornjaGranica-1
vrhStoga:=vrhStoga+1
stogSDonjimGranicama(vrhStoga):=gdjeJePivot+1
stogSGornjimGranicama(vrhStoga):=gornjaGranica
EndIf
If gdjeJePivot>donjaGranica+1
vrhStoga:=vrhStoga+1
stogSDonjimGranicama(vrhStoga):=donjaGranica
stogSGornjimGranicama(vrhStoga):=gdjeJePivot
EndIf
testZaPreljev:=brojac+najmanjiCijeliBrojKojiSeMozeDodatiNaBrojac ;Potrebna je posebna varijabla za to jer FPU interno radi s 80-bitnim brojevima, a CPU s 32-bitnim.
If not(testZaPreljev>brojac)
najmanjiCijeliBrojKojiSeMozeDodatiNaBrojac:=najmanjiCijeliBrojKojiSeMozeDodatiNaBrojac*2
AsmStart
if ispisPoruka=1
jmp izvjesceOpreljevu$
izvjesceOpreljevu db "Upozorenje: Brojac mozda nece sadrzavati tocan rezultat, dogodio se preljev na %d. iteraciji."
db " Najveca ocekivana pogreska za ovaj preljev je %d krivo prebrojanih izvrsavanja unutarnje petlje.",10,0
izvjesceOpreljevu$:
fld dword [n]
fld dword [najmanjiCijeliBrojKojiSeMozeDodatiNaBrojac]
fsubp
fabs
fistp dword [esp+4]
fld dword [brojac]
fistp dword [esp]
invoke printf,izvjesceOpreljevu
end if
AsmEnd
EndIf
EndWhile
Else
AsmStart
if ispisPoruka=1
jmp radimoMergeSort$
radimoMergeSort db "Primijenit cemo MergeSort algoritam.",10,0
radimoMergeSort$:
invoke printf,radimoMergeSort
end if
AsmEnd
vrhStoga:=vrhStoga+1
stogSDonjimGranicama(vrhStoga):=0
stogSGornjimGranicama(vrhStoga):=n
stogSPodacimaTrebaLiPetljaRazdvajatiIliSpajatiNizove(vrhStoga):=0
While vrhStoga>0
gornjaGranica:=stogSGornjimGranicama(vrhStoga)
donjaGranica:=stogSDonjimGranicama(vrhStoga)
trebaLiSpajatiIliRazdvajati:=stogSPodacimaTrebaLiPetljaRazdvajatiIliSpajatiNizove(vrhStoga)
vrhStoga:=vrhStoga-1
sredinaNiza:=(donjaGranica+gornjaGranica)/2
sredinaNiza:=sredinaNiza-mod(sredinaNiza,1)
If trebaLiSpajatiIliRazdvajati=0
If gornjaGranica-donjaGranica>1
vrhStoga:=vrhStoga+1
stogSDonjimGranicama(vrhStoga):=donjaGranica
stogSGornjimGranicama(vrhStoga):=gornjaGranica
stogSPodacimaTrebaLiPetljaRazdvajatiIliSpajatiNizove(vrhStoga):=1
vrhStoga:=vrhStoga+1
stogSDonjimGranicama(vrhStoga):=donjaGranica
stogSGornjimGranicama(vrhStoga):=sredinaNiza
stogSPodacimaTrebaLiPetljaRazdvajatiIliSpajatiNizove(vrhStoga):=0
vrhStoga:=vrhStoga+1
stogSDonjimGranicama(vrhStoga):=sredinaNiza
stogSGornjimGranicama(vrhStoga):=gornjaGranica
stogSPodacimaTrebaLiPetljaRazdvajatiIliSpajatiNizove(vrhStoga):=0
EndIf
Else
i:=donjaGranica
gdjeSmoUPrvomNizu:=donjaGranica
gdjeSmoUDrugomNizu:=sredinaNiza
While i<gornjaGranica
If (gdjeSmoUPrvomNizu=sredinaNiza | original(gdjeSmoUDrugomNizu)<original(gdjeSmoUPrvomNizu)) & gdjeSmoUDrugomNizu<gornjaGranica
pomocni(i):=original(gdjeSmoUDrugomNizu)
gdjeSmoUDrugomNizu:=gdjeSmoUDrugomNizu+1
Else
pomocni(i):=original(gdjeSmoUPrvomNizu)
gdjeSmoUPrvomNizu:=gdjeSmoUPrvomNizu+1
EndIf
i:=i+1
brojac:=brojac+1
EndWhile
i:=donjaGranica
While i<gornjaGranica
original(i):=pomocni(i)
brojac:=brojac+1
i:=i+1
EndWhile
EndIf
EndWhile
EndIf
AsmStart
call [clock]
sub eax,[procesorskoVrijeme]
mov [procesorskoVrijeme],eax
if ispisPoruka=1
jmp sortiraniNizJe$
sortiraniNizJe db "Sortirani niz je:",10,0
sortiraniNizJe$:
staviStringNaSistemskiStog sortiraniNizJe
call [printf]
end if
AsmEnd
i:=0
While i<n
pokazivac:=4*i
AsmStart
lea ebx,[original]
fld dword [pokazivac]
fistp dword [pokazivac]
add ebx,[pokazivac]
fld dword [ebx]
fstp qword [esp]
staviStringNaSistemskiStog znakZaFloatPlusNoviRedPlusNulZnak
call [printf]
AsmEnd
i:=i+1
EndWhile
AsmStart
if ispisPoruka=1
staviIntNaSistemskiStog brojac
staviStringNaSistemskiStog unutrasnjaPetljaString
call [printf]
AsmEnd
brojac:=n*ln(n)/ln(2)
AsmStart
fld dword [brojac]
fstp qword [esp]
staviStringNaSistemskiStog slozenostString
call [printf]
push dword [procesorskoVrijeme]
invoke printf,sortiranjeJeTrajalo
invoke system,_pause
end if
invoke exit,0
_pause db "PAUSE",0
znakZaCijeliBrojBroj db "%d",0
znakZaNoviRedPlusNulZnak db 10,0
znakZaFloatPlusNoviRedPlusNulZnak db "%f",10,0
unutrasnjaPetljaString db "Unutrasnja petlja izvrsila se %d puta.",10,0
slozenostString db "Ocekivani broj ponavljanja te petlje, po formuli n*log2(n), bio bi %.1f.",10,0
sortiranjeJeTrajalo db "Sortiranje je trajalo %d milisekundi.",10,0
section '.rdata' readable writable
original:
repeat 32768
dd 0
end repeat
n dd ?
result dd ?
brojac dd ?
pokazivac dd ?
i dd ?
stogSDonjimGranicama:
repeat 32768
dd 0
end repeat
stogSGornjimGranicama:
repeat 32768
dd 0
end repeat
pomocni:
repeat 32768
dd 0
end repeat
vrhStoga dd ?
donjaGranica dd ?
gornjaGranica dd ?
staviVece dd ?
staviManje dd ?
gdjeJePivot dd ?
procesorskoVrijeme dd ?
razvrstanost dd ?
razvrstanostNa dd 8 DUP(?)
polinomPodApsolutnom dd ?
eNaKoju dd ?
ocekivaniBrojUsporedbi dd ?
ocekivanoOdMergeSorta dd ?
najmanjiCijeliBrojKojiSeMozeDodatiNaBrojac dd ?
pomocniBrojac dd ?
testZaPreljev dd ?
gdjeSmoUDrugomNizu dd ?
gdjeSmoUPrvomNizu dd ?
trebaLiSpajatiIliRazdvajati dd ?
sredinaNiza dd ?
stogSPodacimaTrebaLiPetljaRazdvajatiIliSpajatiNizove:
repeat 32768
dd 0
end repeat
section '.idata' data readable import
library msvcrt,'msvcrt.dll'
import msvcrt,printf,'printf',system,'system',exit,'exit',scanf,'scanf',clock,'clock'
AsmEnd
The 32-bit Windows executable is available
here. I must say I've expected it to be a lot more efficient than it actually is. I've expected it to be comparable with IntroSort (used in C++ "sort" directive), however, it appears to be a few times slower than IntroSort, as can be seen in this
diagram.
Damn, I don't know if I should study this further, or to just accept that all the low-hanging fruit, along with the not-so-low-hanging fruit, is already gone, and that studying it further is rather pointless.