Our server costs ~$56 per month to run. Please consider donating or becoming a Patron to help keep the site running. Help us gain new members by following us on Twitter and liking our page on Facebook!
Current time: March 28, 2024, 5:10 am

Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
C++ "sort"
#21
RE: C++ "sort"
(December 29, 2019 at 11:35 am)Abaddon_ire Wrote: Tough. I have little time for first year assignments. It matters not how educated any of us may be, trying to lure others into doing ones homework is really, really shoddy no matter how one slices it.

You have little time for first year assignments yet you have enough time to troll someone looking to a community they're part of for help or advice?

It'd be different if this was his first thread. But he's an established member of this community and you're going out of your way to be an incredible dick. There's nothing worse than an officious douche being mean for the sake of being mean. I'll take 1000 people looking to learn over a bag of stinky dicks like you.
"There remain four irreducible objections to religious faith: that it wholly misrepresents the origins of man and the cosmos, that because of this original error it manages to combine the maximum servility with the maximum of solipsism, that it is both the result and the cause of dangerous sexual repression, and that it is ultimately grounded on wish-thinking." ~Christopher Hitchens, god is not Great

PM me your email address to join the Slack chat! I'll give you a taco(or five) if you join! --->There's an app and everything!<---
Reply
#22
RE: C++ "sort"
Done some measurements about the performance of various implementations of QuickSort and MergeSort.
This one is about the time it takes to sort a randomly-generated (and, therefore, randomly shuffled) array of certain size:
[Image: output_of_tester1_as_a_diagram.png]
This one is about the time it takes to sort an array of certain sortedness, all of the arrays being of the same size:
[Image: output_of_tester2_as_a_diagram.png]
Reply
#23
RE: C++ "sort"
I've made a presentation for the seminar about my programming language yesterday. I've spent the entire morning trying to get PowerPoint to run on my laptop. Then I gave up and started doing it in LibreOffice. LibreOffice is horribly buggy, but at least it runs on my laptop, while PowerPoint doesn't even do that. Before closing it, I knew LibreOffice might corrupt the formatting while saving the file, so I exported it to PDF first. And, yes, it did indeed corrupt the formatting (thank God I didn't try to make animations or advanced image editing, I don't know what would have happen had I tried), but now I at least have a usable PDF file, you can download it here.
Reply
#24
RE: C++ "sort"
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:
;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:
[Image: output_of_tester3_as_a_diagram.png]
Reply
#25
RE: C++ "sort"
My professor tells me my seminar is good enough to be published in some computer science journal, if not an international one (for which I should spend time translating my work to English, and have a higher risk my paper will be rejected), than at least in Osječki Matematički List. So, I've re-edited my seminar to make it better. It's available on the same address.
Reply
#26
RE: C++ "sort"
Man, you're a data beast!

Sorting algorithms are really important tools for learning computer science concepts, but unfortunately you won't be implementing them in the practical world aside from in very specialized instances.

Luckily, the knowledge you've gained and your dedication to a thorough understanding of these concepts is going to make you a great hire when you enter the job market.
"There remain four irreducible objections to religious faith: that it wholly misrepresents the origins of man and the cosmos, that because of this original error it manages to combine the maximum servility with the maximum of solipsism, that it is both the result and the cause of dangerous sexual repression, and that it is ultimately grounded on wish-thinking." ~Christopher Hitchens, god is not Great

PM me your email address to join the Slack chat! I'll give you a taco(or five) if you join! --->There's an app and everything!<---
Reply
#27
RE: C++ "sort"
(January 10, 2020 at 10:03 pm)SteelCurtain Wrote: Man, you're a data beast!

Sorting algorithms are really important tools for learning computer science concepts, but unfortunately you won't be implementing them in the practical world aside from in very specialized instances.

Luckily, the knowledge you've gained and your dedication to a thorough understanding of these concepts is going to make you a great hire when you enter the job market.

Thank you for being encouraging. But, before entering the job market, I should probably finish the university. It's going relatively well for me, but not exceedingly well. I've right now failed a digital electronics test (though there will be another time for it in a few weeks, and almost certainly a few more this year) and I will, in all likelihood, fail the mathematics test that will be this Friday.
Furthermore, in order for an employer to value my text, it needs to be published in a peer-reviewed journal. My professor told me, when I showed him the newest version of my text, that Osječki Matematički List usually doesn't accept texts that are over 12 pages long. He told me it's a relatively good material to re-edit into three articles.
Of course, he had some objections to my text. The biggest objection he had was that I implemented QuickSort in a different way than he showed us on the lectures. I was using a helper-array instead of the hard-to-understand partial sorting, and professor thinks it makes my program around 3 times slower. He also objected that I was often using terms from linguistics to describe the programming language I designed, instead of using the words and phrases typical of computer science. Some of those words and phrases typical of computer science, I actually have never heard of them. For instance, the professor tells me the correct term for "grammatical illusion" is "semantic analysis".
Reply
#28
RE: C++ "sort"
I've tried to make my program for sorting decimal numbers faster for nearly-sorted or nearly-reverse-sorted arrays by implementing the algorithm recursively, checking the sortedness of the array each iteration. I've implemented it in ArithmeticExpressionCompiler:
Code:
Syntax GAS ;Neka ArithmeticExpressionCompiler ispisuje asemblerski kod kompatibilan s GNU Assemblerom, da bude kompatibilan s GCC-om. Po defaultu ispisuje kod kompatibilan s FlatAssemblerom (a FlatAssembler na Linuxu ne radi bas najbolje).
verboseMode ON ;Neka ArithmeticExpressionCompiler ispisuje vise komentara u asemblerski kod koji ispisuje (da bude laksi za citanje i debuggiranje).
AsmStart ;Neka GNU Assembler obavijesti linkera da je "hybrid_sort" naziv potprograma...
   .global hybrid_sort
   hybrid_sort:
AsmEnd
If gornja_granica-donja_granica<2 ;Ako je niz duljine manje od 2 (0 ili 1), znaci da je vec poredan, pa prekidamo izvodenje ovog potprograma.
   AsmStart ;Kako radimo izvan sekcija, mozemo jednostavno prekinuti izvodenje potprograma asemblerskom naredbom "ret" (inace bismo, da radimo u sekcijama, morali znati vrti li se program na 32-bitnom ili 64-bitnom Linuxu).
       ret
   AsmEnd
EndIf
razvrstanost:=0
i:=donja_granica
While i < gornja_granica - 1
   razvrstanost:=razvrstanost+(originalni_niz[i]<originalni_niz[i+1])
   i:=i+1
EndWhile
razvrstanost:=razvrstanost/((gornja_granica-donja_granica-1)/2)-1
i:=2
While i<7 | i=7
   razvrstanost_na_potenciju[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.
   razvrstanost_na_potenciju[i] := (razvrstanost=0) ? 0 : (mod(i,2)=1 & razvrstanost<0) ? (-razvrstanost_na_potenciju[i]) : razvrstanost_na_potenciju[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
polinom_pod_apsolutnom := 2.38854*razvrstanost_na_potenciju[7] - 0.284258*razvrstanost_na_potenciju[6] - 1.87104*razvrstanost_na_potenciju[5] + 0.372637*razvrstanost_na_potenciju[4] + 0.167242*razvrstanost_na_potenciju[3] - 0.0884977*razvrstanost_na_potenciju[2] + 0.315119*razvrstanost
Eulerov_broj_na_koju_potenciju := (ln(gornja_granica - donja_granica) + ln(ln(gornja_granica - donja_granica))) * 1.05 + (ln(gornja_granica - donja_granica) - ln(ln(gornja_granica - donja_granica)) - ln(2)) * 0.9163 * abs(polinom_pod_apsolutnom)
koliko_usporedbi_ocekujemo_od_QuickSorta := exp(Eulerov_broj_na_koju_potenciju)
koliko_usporedbi_ocekujemo_od_MergeSorta := 2 * (gornja_granica - donja_granica) * ln(gornja_granica - donja_granica) / ln(2)
If razvrstanost=1 ;Ako je niz vec poredan.
   broj_vec_poredanih_podniza := broj_vec_poredanih_podniza + 1
   AsmStart
       ret
   AsmEnd
ElseIf razvrstanost = -1 ;Ako je niz obrnuto poredan...
   broj_obrnuto_poredanih_podniza := broj_obrnuto_poredanih_podniza + 1
   i:=donja_granica
   j:=gornja_granica-1
   While i<gornja_granica
       pomocni_niz[i] := originalni_niz[j]
       j := j - 1
       i := i + 1
   EndWhile
   i := donja_granica
   While i < gornja_granica
       originalni_niz[i] := pomocni_niz[i]
       i := i + 1
   EndWhile
   AsmStart
       ret
   AsmEnd
ElseIf koliko_usporedbi_ocekujemo_od_MergeSorta < koliko_usporedbi_ocekujemo_od_QuickSorta ;MergeSort algoritam (priblizno poredani podnizovi, za koje je MergeSort efikasniji od QuickSorta)...
   broj_pokretanja_MergeSorta := broj_pokretanja_MergeSorta + 1
   sredina_niza:=(gornja_granica+donja_granica)/2
   sredina_niza:=sredina_niza-mod(sredina_niza,1)
   vrh_stoga:=vrh_stoga+1 ;Zauzmi mjesta na stogu za rekurziju. Ne koristimo sistemski stog, kao sto koristi C++, nego koristimo vise globalnih polja kao stogove. Da koristimo sistemski stog, morali bismo znati pokrecemo li se na 32-bitnom Linuxu ili 64-bitnom Linuxu, jer oni nisu kompatibilni u tom pogledu.
   stog_s_donjim_granicama[vrh_stoga]:=donja_granica
   stog_s_gornjim_granicama[vrh_stoga]:=gornja_granica
   stog_sa_sredinama_niza[vrh_stoga]:=sredina_niza
   gornja_granica:=sredina_niza
   AsmStart
       call hybrid_sort
   AsmEnd
   donja_granica:=stog_s_donjim_granicama[vrh_stoga] ;Sad je rekurzija gotovo sigurno izmijenila sve globalne varijable koje nam trebaju ("donja_granica", "gornja_granica" i "sredina_niza"), ali zato imamo njihove stare vrijednosti na stogovima.
   gornja_granica:=stog_s_gornjim_granicama[vrh_stoga]
   sredina_niza:=stog_sa_sredinama_niza[vrh_stoga]
   donja_granica:=sredina_niza
   AsmStart
       call hybrid_sort
   AsmEnd
   donja_granica:=stog_s_donjim_granicama[vrh_stoga]
   gornja_granica:=stog_s_gornjim_granicama[vrh_stoga]
   sredina_niza:=stog_sa_sredinama_niza[vrh_stoga]
   ;Spajanje nizova originalni_niz[donja_granica..sredina_niza] i originalni_niz[sredina_niza..gornja_granica] u jedan niz...
   i:=donja_granica
   gdje_smo_u_prvom_nizu:=donja_granica
   gdje_smo_u_drugom_nizu:=sredina_niza
   While i<gornja_granica
       If (gdje_smo_u_prvom_nizu=sredina_niza | originalni_niz[gdje_smo_u_drugom_nizu]<originalni_niz[gdje_smo_u_prvom_nizu]) & gdje_smo_u_drugom_nizu<gornja_granica
           pomocni_niz[i]:=originalni_niz[gdje_smo_u_drugom_nizu]
           gdje_smo_u_drugom_nizu:=gdje_smo_u_drugom_nizu+1
       Else
           pomocni_niz[i]:=originalni_niz[gdje_smo_u_prvom_nizu]
           gdje_smo_u_prvom_nizu:=gdje_smo_u_prvom_nizu+1
       EndIf
       i:=i+1
   EndWhile
   i:=donja_granica
   While i<gornja_granica
       originalni_niz[i]:=pomocni_niz[i]
       i:=i+1
   EndWhile
   vrh_stoga:=vrh_stoga-1 ;Oslobodi mjesto na stogovima.
   AsmStart
       ret
   AsmEnd
Else ;QuickSort algoritam (nasumicno ispremjestani podnizovi)...
   broj_pokretanja_QuickSorta := broj_pokretanja_QuickSorta + 1
   ;Daljnji kod je priblizno prepisan s https://www.geeksforgeeks.org/quick-sort/
   pivot := originalni_niz[gornja_granica - 1]
   i := donja_granica - 1
   j := donja_granica
   While j < gornja_granica - 1
       If originalni_niz[j] < pivot
           i := i + 1
           pomocna_varijabla_za_zamijenu := originalni_niz[i]
           originalni_niz[i] := originalni_niz [j]
           originalni_niz[j] := pomocna_varijabla_za_zamijenu
       EndIf
       j:=j+1
   EndWhile
   pomocna_varijabla_za_zamijenu := originalni_niz[i + 1]
   originalni_niz[i + 1] := originalni_niz[gornja_granica - 1]
   originalni_niz[gornja_granica - 1] := pomocna_varijabla_za_zamijenu
   gdje_je_pivot := i + 1
   vrh_stoga := vrh_stoga + 1 ;Zauzmi mjesta na stogu za rekurziju (ne koristimo sistemski stog, kao sto koristi C++, nego koristimo vise globalnih polja kao stogove).
   stog_s_donjim_granicama[vrh_stoga] := donja_granica
   stog_s_gornjim_granicama[vrh_stoga] := gornja_granica
   stog_sa_sredinama_niza[vrh_stoga] := gdje_je_pivot
   gornja_granica := gdje_je_pivot
   AsmStart
       call hybrid_sort
   AsmEnd
   donja_granica := stog_s_donjim_granicama[vrh_stoga]
   gornja_granica := stog_s_gornjim_granicama[vrh_stoga]
   gdje_je_pivot := stog_sa_sredinama_niza[vrh_stoga]
   donja_granica := gdje_je_pivot
   AsmStart
       call hybrid_sort
   AsmEnd
   vrh_stoga := vrh_stoga - 1 ;Oslobodi mjesto na stogovima.
   AsmStart
       ret
   AsmEnd
EndIf
AsmStart ;Ovdje tok programa ne smije doci. Ako dode, pozovi debugger.
   call abort
AsmEnd
This time, I didn't make an executable program using FlatAssembler, but a static library that can be compiled using GNU Assembler and linked with, for instance, a C++ program that will test it. So, I can get more precise measurements of its performance. Now it works better than last time for nearly-sorted arrays (it's as fast as C++ "sort" directive), but it's around 50 times slower than C++ "sort" is if the array is randomly shuffled, and around 2 times slower than my last program was. Oddly, I thought I implemented QuickSort(running when the sortedness is near 0) much more efficiently now.
[Image: test_results.png]
Implementing it as a static linking library rather than as an executable also makes it easier to see what's going on inside:
[Image: which_algorithms_are_used.png]
There also appears to be some surge in the number of QuickSorts executed when the sortedness is around 0.9 (when MergeSort will almost certainly do a better job), I can't figure out exactly why (yet alone that there is an easy fix).
Reply
#29
RE: C++ "sort"
(December 29, 2019 at 3:26 pm)SteelCurtain Wrote:
(December 29, 2019 at 11:35 am)Abaddon_ire Wrote: Tough. I have little time for first year assignments. It matters not how educated any of us may be, trying to lure others into doing ones homework is really, really shoddy no matter how one slices it.

You have little time for first year assignments yet you have enough time to troll someone looking to a community they're part of for help or advice?

It'd be different if this was his first thread. But he's an established member of this community and you're going out of your way to be an incredible dick. There's nothing worse than an officious douche being mean for the sake of being mean. I'll take 1000 people looking to learn over a bag of stinky dicks like you.

See, I went to the trouble for this guy to block out some time in my office just to run his code and determine where any issue might lie. Under covid restrictions, this is not easy. 

And he shat on me.

I am disinclined to make any further effort.
Reply
#30
RE: C++ "sort"
(July 4, 2020 at 2:15 pm),Abaddon_ire Wrote:
(December 29, 2019 at 3:26 pm)SteelCurtain Wrote: You have little time for first year assignments yet you have enough time to troll someone looking to a community they're part of for help or advice?

It'd be different if this was his first thread. But he's an established member of this community and you're going out of your way to be an incredible dick. There's nothing worse than an officious douche being mean for the sake of being mean. I'll take 1000 people looking to learn over a bag of stinky dicks like you.

See, I went to the trouble for this guy to block out some time in my office just to run his code and determine where any issue might lie. Under covid restrictions, this is not easy. 

And he shat on me.

I am disinclined to make any further effort.

Well, the executable programs for 32-bit Linux, 64-bit Linux, 32-bit Windows and FreeDOS are all available in this ZIP-archive, and at least one of them should be relatively easy to run on any actual computer of today. And compiling it for some other i686-compatible platform (basically, any computer less than 20 years old running whichever operating system) should also be easy. Yeah, it's written in my own programming language, but the compiler for it can be run in Duktape, that is, on any platform with a C99 compiler (including FreeDOS), and it (in this case) generates assembly compatible with GNU Assembler (also with archaic versions of it). So, I see no reason why having to work on some other computer than you usually work on would make it hard to run my program.
Reply





Users browsing this thread: 1 Guest(s)