C++ "sort"

[SteelCurtain]

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.

[FlatAssembler]

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:

This one is about the time it takes to sort an array of certain sortedness, all of the arrays being of the same size:

[FlatAssembler]

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.

[FlatAssembler]

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:

[FlatAssembler]

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.

[SteelCurtain]

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.

[FlatAssembler]

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".

[FlatAssembler]

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.

Implementing it as a static linking library rather than as an executable also makes it easier to see what's going on inside:

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).

[Abaddon_ire]

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.

[FlatAssembler]

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.