;HybridSort algoritam - kombinacija QuickSort algoritma i MergeSort algoritma.

VerboseMode ON ;Kaze ArithmeticExpressionCompileru da u asemblerski kod koji ispisuje stavi vise komentara.

AsmStart

ispisPoruka=1

macro staviIntNaSistemskiStog x ;"x" treba biti pokazivac na 32-bitni decimalni broj ("float"), kojeg ce ova makro-naredba pretvoriti u 32-bitni cijeli broj ("int") i staviti na sistemski stog.

{

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 ;"PE" je 32-bitna Windowsova ".EXE" datoteka (to nije sve sto FlatAssembler moze stvarati).

entry start

include 'win32a.inc' ;FlatAssemblerove naredbe za upravljanje DLL-ovima (ovdje se koriste za pozivanje C-ovih funkcija iz MSVCRT-a).

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 ;"float" ima 4 bajta.

AsmStart

fld dword [pokazivac]

fistp dword [pokazivac]

lea ebx,[original]

add ebx,[pokazivac]

staviPokazivacNaSistemskiStog ebx

staviStringNaSistemskiStog znakZaFloat

call [scanf]

add esp,4+4 ;Pocisti sistemski stog nakon "scanf" (asemblerski jezik to ne radi automatski, kao sto rade visi jezici).

AsmEnd

i:=i+1

EndWhile

AsmStart

call [clock] ;"clock" na Windowsima vraca broj milisekundi otkad se program pokrenuo, zadnja 32 bita vraca u procesorski registar "eax".

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) ;"pow(x,y)" je u AEC-u samo sintaksni secer za "exp(ln(x)*y)", i to vraca NaN za x=0 ili x<0. Nema ocitog nacina da se "pow(x,y)" prevede na asemblerski.

razvrstanostNa(i):=(razvrstanost=0) ? 0 : (mod(i,2)=1 & razvrstanost<0) ? (-razvrstanostNa(i)) : razvrstanostNa(i) ;C-ov i JavaScriptin uvjetni operator nekad zna znatno skratiti kod, zato sam ga ugradio i u svoj jezik.

i:=i+1

EndWhile

;Formula koju je ispisao genetski algoritam za predvidanje koliko ce usporedbi QuickSort napraviti: https://github.com/FlatAssembler/ArithmeticExpressionCompiler/tree/master/QuickSort/Genetic_algorithm_for_deriving_the_formula

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)

kolikoUsporedbiOcekujemoOdQuickSorta:=exp(eNaKoju)

kolikoUsporedbiOcekujemoOdMergeSorta:=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 [kolikoUsporedbiOcekujemoOdMergeSorta]

fstp qword [esp+8]

fld dword [kolikoUsporedbiOcekujemoOdQuickSorta]

fstp qword [esp]

staviStringNaSistemskiStog ispisOTomeStoOcekujemo

call [printf]

end if

AsmEnd

najmanjiCijeliBrojKojiSeMozeDodatiNaBrojac:=1 ;Da, kada prijedemo MAX_SAFE_INTEGER za "float", ne pokusavamo vise dodavati jedinicu.

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 kolikoUsporedbiOcekujemoOdQuickSorta<kolikoUsporedbiOcekujemoOdMergeSorta

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 ;Gdje ce doci element koji je sada prvi ("pivot").

EndIf

i:=i++ ;"++" je u AEC-u jednostavno sintaksni secer za "+1".

EndWhile

staviManje:=donjaGranica

staviVece:=gdjeJePivot+1

pomocni(gdjeJePivot):=original(donjaGranica)

i:=donjaGranica+1

While i<gornjaGranica ;Preuredi niz original(donjaGranica..gornjaGranica-1) tako da svi elementi koji su manji od onoga koji je bio prvi dodu prije njega.

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

;Razdvoji niz original(donjaGranica..gornjaGranica-1) na nizove original(donjaGranica..gdjeJePivot-1) i original(gdjeJePivot+1..gornjaGranica-1).

;Znamo gdje je pivot, pa njega ne trebamo ukljuciti ni u jedan od tih nizova.

;I ne trebamo na stog stavljati naputke o razvrstavanju nizova velicine 0 ili 1.

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. Izgubio sam hrpu vremena da to shvatim.

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 [gornjaGranica]

fld dword [donjaGranica]

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):=razdvajati

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=razdvajati ;Razdvoji niz original(donjaGranica..gornjaGranica-1) na original(donjaGranica..sredinaNiza-1) i original(sredinaNiza..gornjaGranica-1).

If gornjaGranica-donjaGranica>1 ;Niz velicine 0 ili 1 vec je poredan i ne radimo nista dalje.

vrhStoga:=vrhStoga+1

stogSDonjimGranicama(vrhStoga):=donjaGranica

stogSGornjimGranicama(vrhStoga):=gornjaGranica

stogSPodacimaTrebaLiPetljaRazdvajatiIliSpajatiNizove(vrhStoga):=spajati

;Stavljamo naputak za spajanje nizova prvog na stog kako bi on onda bio zadnji izvaden iz njega.

vrhStoga:=vrhStoga+1

stogSDonjimGranicama(vrhStoga):=donjaGranica

stogSGornjimGranicama(vrhStoga):=sredinaNiza

stogSPodacimaTrebaLiPetljaRazdvajatiIliSpajatiNizove(vrhStoga):=razdvajati

vrhStoga:=vrhStoga+1

stogSDonjimGranicama(vrhStoga):=sredinaNiza

stogSGornjimGranicama(vrhStoga):=gornjaGranica

stogSPodacimaTrebaLiPetljaRazdvajatiIliSpajatiNizove(vrhStoga):=razdvajati

EndIf

Else ;Spoji vec poredane nizove original(donjaGranica..sredinaNiza-1) i original(sredinaNiza..gornjaGranica-1) u novi poredani niz original(donjaGranica..gornjaGranica-1).

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] ;"printf" za "%f" ocekuje "double", ili, u asemblerskoj terminologiji, "qword".

staviStringNaSistemskiStog znakZaFloatPlusNoviRedPlusNulZnak

call [printf]

AsmEnd

i:=i+1

EndWhile

AsmStart

if ispisPoruka=1

staviIntNaSistemskiStog brojac

staviStringNaSistemskiStog unutrasnjaPetljaString

call [printf]

AsmEnd

n*ln(n)/ln(2) ;Ovo ce se spremiti u "result", pomocnu varijablu koju koristi compiler za AEC.

AsmStart

fld dword [result]

fstp qword [esp] ;"printf" iz MSVCRT-a za "%f" ocekuje 64-bitni "double", ili, na asemblerskom jeziku, "qword".

staviStringNaSistemskiStog slozenostString

call [printf]

push dword [procesorskoVrijeme]

invoke printf,sortiranjeJeTrajalo

invoke system,_pause

end if

invoke exit,0

;"Konstante", ako njih pokusamo mijenjati, dobijemo Segmentation Fault:

_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

razdvajati dd 0f

spajati dd 1f

section '.rdata' readable writable ;Varijable i polja (u drugom segmentu programa nego sto je izvrsni dio).

original:

repeat 32768 ;Nije preporucljivo ovako na asemblerskom deklarirati nizove, ali zasto bih se pretvarao da radim za racunalom s 4 MB RAM-a, gdje je problem ucitati program gdje je jedan segment velik 640 KB?

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 ?

kolikoUsporedbiOcekujemoOdQuickSorta dd ?

kolikoUsporedbiOcekujemoOdMergeSorta 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' ;"msvcrt.dll" je Microsoft Visual C Runtime Library, dostupna u "C:\Windows\System32\msvcrt.dll" na Windows 98 i novijim.

import msvcrt,printf,'printf',system,'system',exit,'exit',scanf,'scanf',clock,'clock'

AsmEnd