;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