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 29, 2024, 2:36 am

Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
C++ "sort"
#31
RE: C++ "sort"
I was scared of computers growing up. Not in the sense that I didn't like them, I do. But in the sense that I always ran into people smarter than me that made me feel stupid.

The irony is, now that towers are going the way of the dinosaurs, at least with hardware, I am no longer afraid. Much like a car mechanic can tell you what a carburetor is or alternator are. I now know what a heat sink is on a tower and what an expansion slot is and what a motherboard is. 

But I never did grasp literal computer language. I can tell you how to erase an entire hard drive and reformat it it in DOS, "Format C:" from the C: promt. But that does not work now. Too many security levels now. 

Outside that I did not understand the "If then, go to" language. And C++ was even more confusing to me than DOS.
Reply
#32
RE: C++ "sort"
(July 6, 2020 at 10:57 am)FlatAssembler Wrote:
(July 4, 2020 at 2:15 pm),Abaddon_ire Wrote: 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.

Why? You already stated you identified the error and it was not yours. I see no purpose to it.
Reply
#33
RE: C++ "sort"
My expertise with computers has never failed me. I simply say, ‘Honey, can you fix this?’ then I go watch cartoons for a bit.

Works every time.

Boru
‘But it does me no injury for my neighbour to say there are twenty gods or no gods. It neither picks my pocket nor breaks my leg.’ - Thomas Jefferson
Reply
#34
RE: C++ "sort"
(July 6, 2020 at 4:37 pm)Abaddon_ire Wrote:
(July 6, 2020 at 10:57 am)FlatAssembler Wrote: 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.

Why? You already stated you identified the error and it was not yours. I see no purpose to it.

That was about a different program. Nevertheless, I figured this Heisenbug by myself, it's about running out of stack memory (but since I used my own stack rather than the system stack, I sometimes got Segmentation Fault and sometimes it just failed silently). Some guy on CodeReview identified even more potential problems.

(July 6, 2020 at 11:32 am)Brian37 Wrote: I was scared of computers growing up. Not in the sense that I didn't like them, I do. But in the sense that I always ran into people smarter than me that made me feel stupid.

The irony is, now that towers are going the way of the dinosaurs, at least with hardware, I am no longer afraid. Much like a car mechanic can tell you what a carburetor is or alternator are. I now know what a heat sink is on a tower and what an expansion slot is and what a motherboard is. 

But I never did grasp literal computer language. I can tell you how to erase an entire hard drive and reformat it it in DOS, "Format C:" from the C: promt. But that does not work now. Too many security levels now. 

Outside that I did not understand the "If then, go to" language. And C++ was even more confusing to me than DOS.
For me, installing and using programs on DOS is more confusing than writing a simple C++ program. And writing C++ programs for DOS is incredibly complicated, something I've only recently discovered how to do.
Reply
#35
RE: C++ "sort"
Yesterday, I've implemented my sorting algorithm in the new version of AEC, to see how it compares to JavaScript "Array.sort":
Code:
/*
* Ovo je prijepis mog hibridnog algoritma razvrstavanja da se može
* pokrenuti na JavaScriptinoj virtualnoj mašini. Kako bi se AEC-om mogla
* ciljati JavaScriptina virtualna mašina, napravio sam novi compiler.
* Ovaj puta je pisan u C++-u, radio sam i novi parser i novi tokenizer.
* Također sam malo promijenio sintaksu, da omogućim pisanje čistijeg koda
* te da podržavam različite vrste podataka (prije je AEC podržavao samo
* 32-bitne decimalne brojeve). Novi compiler proizvodi WebAssembly,
* standardizirani oblik JavaScriptinog bytecodea. Izvorno je WebAssembly
* bio Mozillin standard, ali danas ga podržavaju gotovo sve JavaScriptine
* virtualne mašine. Ovdje ciljamo primarno na NodeJS, JavaScriptinu
* virtualnu mašinu koju razvija Google i primarno je namijenjena da se
* vrti na serverima (no može se pokrenuti i na veoma slabim računalima).
*/

//Uvezimo prvo neke funkcije iz JavaScripta, koje će nam trebati...
Function daj_velicinu_niza() Which Returns Integer32 Is External;
Function kopiraj_niz_na_adresu(Integer32Pointer adresa)
    Which Returns Nothing Is External;
Function printString(CharacterPointer str)
    Which Returns Nothing Is External;
Function printInteger(Integer32 n) Which Returns Nothing Is External;
Function printFloat(Decimal32 x) Which Returns Nothing Is External;
Function pocni_mjerenje_vremena() Which Returns Nothing Is External;
Function zavrsi_mjerenje_vremena() Which Returns Nothing Is External;
Function izvijesti_o_obrnuto_poredanim_nizovima(Integer32 n)
    Which Returns Nothing Is External;
Function izvijesti_o_poredanim_nizovima(Integer32 n)
    Which Returns Nothing Is External;
Function izvijesti_o_pokretanju_QuickSorta(Integer32 n)
    Which Returns Nothing Is External;
Function izvijesti_o_pokretanju_MergeSorta(Integer32 n)
    Which Returns Nothing Is External;
Function izvijesti_o_pokretanju_SelectSorta(Integer32 n)
    Which Returns Nothing Is External;
Function izvijesti_JavaScript_o_nedostatku_memorije()
    Which Returns Nothing Is External;

Integer32 DEBUG := 0;

//Napravimo sada omotnicu oko WebAssemblerske naredbe "memory.grow"...
Function zauzmi_memorijske_stranice(Integer32 broj_stranica) Which Returns
    CharacterPointer Does
    Integer32 nova_adresa_u_stranicama :=
        asm_i32 //"asm_i32" kaže compileru da umetne asemblerski kod, i da
                //pretpostavi da će se nakon njega na sistemskom stogu
                //nalaziti vrijednost tipa "i32". To očito nije točno ako
                //netko prebaci JavaScript virtualnu mašinu u 64-bitni
                //način rada, ali nadam se da to nitko neće napraviti.
                //Vjerojatnost da će JavaScript virtualnoj mašini trebati
                //više nego 4GB RAM-a je zanemariva, a vjerojatnost da će
                //se neki korisni programi srušiti zbog prebacivanja u
                //64-bitni način rada nije baš zanemariva.
                ("(memory.grow\n"
                "\t(local.get 0)\n" //Prvi (nulti) argument funkcije,
                                    //"brojStranica".
                ")\n");
    If nova_adresa_u_stranicama = -1 Then //Ako nema više
                                          //slobodne memorije...
        Return -1;
    EndIf
    Return nova_adresa_u_stranicama * 64 * 1024; //Na JavaScript Virtualnoj
                                                 //Mašini, jedna stranica
                                                 //(page) iznosi 64 KB.
EndFunction

Integer32 velicina_niza;
Integer32Pointer originalni_niz, pomocni_niz; //To su globalne varijable,
                                              //po defaultu su u nuli,
                                              //dakle "originalni_niz" i
                                              //"pomocni_niz" su na početku
                                              //programa nulti pokazivači.

Integer32 broj_obrnuto_poredanih_podniza,
          broj_vec_poredanih_podniza,
          broj_pokretanja_QuickSorta,
          broj_pokretanja_MergeSorta,
          broj_pokretanja_SelectSorta;

//Sad ćemo implementirati neke matematicke funkcije koje će nam trebati.
//Ne možemo pozvati JavaScriptine matematičke funkcije, jer one su metode
//singletona "Math", a ne postoji standardizirani način da se zovu
//metode JavaScriptinih objekata iz WebAssemblyja.
Decimal32 PRECISION := 128; //Ovdje možemo balansirati između brzine i
                            //preciznosti. Ako smo previše precizni, bit
                            //ćemo spori. Ako smo previše neprecizni, lako
                            //se može dogoditi da precijenimo koliko se
                            //duboko rekurzija smije granati i izazovemo
                            //stack overflow.
Function prirodni_logaritam(Decimal32 x) Which Returns Decimal32 Does
    //Prirodni logaritam je integral od 1/x u intervalu od 1 do x,
    //srednjoškolska matematika.
    Decimal32 zbroj   := 0,
              epsilon := (x - 1) / (5 * PRECISION),
              i       := 1;
    While (epsilon > 0 and i < x) or (epsilon < 0 and i > x) Loop
        zbroj:= zbroj + epsilon / i;
        i    :=         i + epsilon;
    EndWhile
    Return zbroj;
EndFunction

Function Eulerov_broj_na_potenciju(Decimal32 x) Which Returns Decimal32 Does
    //Eulerov Algoritam iz Matematike 2...
    Decimal32 i := 0, y := 1, epsilon := x / PRECISION;
    While (epsilon > 0 and i < x) or (epsilon < 0 and i > x) Loop
        y := y + epsilon * y;
        i :=     i + epsilon;
    EndWhile
    Return y;
EndFunction

Function abs(Decimal32 x) Which Returns Decimal32 Does
    //U svoj sam programski jezik ugradio uvijetni "?:" operator kakav
    //postoji u C-u, C++-u i JavaScriptu. Izgleda malo ružno, ali nekad zna
    //znatno skratiti programske kodove. Odlučio sam implementirati desno
    //asocijativan uvijetni operator, kakav je u C-u, C++-u i JavaScriptu,
    //a ne lijevo asocijativan kakav je u PHP-u i srodnim jezicima.
    //Jednostavno mi ima više smisla da uvijetni operator bude asocijativan
    //na desno nego na lijevo.
    Return (x < 0) ? //Ako je x manji od 0...
               -x    //...vrati (proglasi rezultatom) -x...
           :   x;    //inače, proglasi x rezultatom.
EndFunction

Function ostatak_pri_dijeljenju(Decimal32 x, Decimal32 y)
    Which Returns Decimal32 Does
    If DEBUG = 1 Then
        printString("Zatrazen je ostatak pri dijeljenju od brojeva: ");
        //Neću upotrebljavati hrvatske znakove u stringovima, jer ću
        //naletjeti na probleme pri pretvorbi u JavaScriptin string.
        printFloat(x);
        printFloat(y);
        printString("Sada ce se program mozda srusiti...");
    EndIf
    If abs(x / y) > Eulerov_broj_na_potenciju(prirodni_logaritam(2) * 63) Then
        Return 0; //Imate bolju ideju što da se radi u slučaju da količnik
                  //ne stane niti u Integer64 (C-ovski "long long")?
    EndIf
    Return x - y * Integer64(x / y); //Ako napišem "Integer32",
                                     //riskiram da će JavaScript
                                     //virtualna mašina prekinuti
                                     //izvođenje programa jer je
                                     //broj "x/y" izvan intervala
                                     //koji 32-bitni cijeli brojevi
                                     //mogu prikazati (od oko dvije
                                     //milijarde u pozitivno i
                                     //negativno).
EndFunction

Function pow(Decimal32 x, Decimal32 y) Which Returns Decimal32 Does
    Decimal32 result := Eulerov_broj_na_potenciju(
                            prirodni_logaritam(abs(x)) * y);
    Return x = 0?
              0
           : ostatak_pri_dijeljenju(x, 2) = 1 and x < 0 ?
              -result
           :  result;
EndFunction

//I sada krećemo pisati taj hibridni algoritam razvrstavanja...
Function hybrid_sort(Integer32 donja_granica,
                     Integer32 gornja_granica,
                     Integer32 dubina_rekurzije)
    Which Returns Nothing Does
    If gornja_granica - donja_granica < 2 Then //Ako je niz duljine manje od
                                               //2 (0 ili 1), znači da je već
                                               //poredan, pa prekidamo
                                               //izvođenje ovog potprograma.
        Return;
    ElseIf gornja_granica - donja_granica = 2 Then //Najčesći slučaj,
                                                   //vrijedi ga posebno
                                                   //obraditi jer time
                                                   //možemo znatno ubrzati
                                                   //program.
        If
            ValueAt(originalni_niz + donja_granica) >
            ValueAt(originalni_niz + donja_granica + 1)
        Then
            Integer32 pomocna_varijabla_za_zamijenu :=
                ValueAt(originalni_niz + donja_granica);
            ValueAt(originalni_niz + donja_granica) :=
                ValueAt(originalni_niz + donja_granica + 1);
            ValueAt(originalni_niz + donja_granica + 1) :=
                pomocna_varijabla_za_zamijenu;
        EndIf
        Return;
    ElseIf gornja_granica - donja_granica < 8 Then //Za male je nizove
                                                    //SelectionSort brži
                                                    //i od MergeSorta i
                                                    //QuickSorta.
        broj_pokretanja_SelectSorta := broj_pokretanja_SelectSorta + 1;
        Integer32 i := donja_granica;
        While i < gornja_granica Loop
            Integer32 gdje_je_minimum := i;
            Integer32 j := i + 1;
            While j < gornja_granica Loop
                If
                    ValueAt(originalni_niz + gdje_je_minimum) >
                    ValueAt(originalni_niz + j)
                Then
                    gdje_je_minimum := j;
                EndIf
                j := j + 1;
            EndWhile
            Integer32 pomocna_varijabla_za_zamijenu :=
                ValueAt(originalni_niz + i);
            ValueAt(originalni_niz + i) :=
                ValueAt(originalni_niz + gdje_je_minimum);
            ValueAt(originalni_niz + gdje_je_minimum) :=
                pomocna_varijabla_za_zamijenu;
            i := i + 1;
        EndWhile
        Return;
    EndIf
    Decimal32 razvrstanost := 0;
    Integer32 i := donja_granica, je_li_niz_vec_poredan := 1;
    While i < gornja_granica - 1 Loop
        razvrstanost := razvrstanost +
            (ValueAt(originalni_niz + i) < ValueAt(originalni_niz + i + 1)
            or ValueAt(originalni_niz + i) = ValueAt(originalni_niz + i + 1) );
        If ValueAt(originalni_niz + i) > ValueAt(originalni_niz + i + 1) Then
            je_li_niz_vec_poredan := 0;
        EndIf
        i := i + 1;
    EndWhile
    razvrstanost := razvrstanost /
        ( (gornja_granica - donja_granica - 1) / 2.) - 1;
    //Provjeri je li sve u redu, i, ako nije, obavijesti.
    If abs(razvrstanost) > 1 Then
        //To ne smije biti...
        printString("Apsolutna vrijednost razvrstanosti je veca od 1!");
        printString("Relevantni dio niza iznosi:"); //Da se ne moram baktati s
                                                    //debuggerima za JavaScript
                                                    //virtualnu mašinu ako dođe
                                                    //do problema, lakše mi
                                                    //je ispisati brojeve u
                                                    //programu nego tražiti
                                                    //kako narediti
                                                    //debuggeru da ih
                                                    //ispiše.
        i := donja_granica;
        While i < gornja_granica Loop
            printInteger(ValueAt(originalni_niz + i));
            i := i + 1;
        EndWhile
        printString("Kraj relevantnog dijela niza!");
    EndIf
    If je_li_niz_vec_poredan and not(razvrstanost = 1 or razvrstanost > 1) Then
        //Opet ne smije biti...
        printString("Niz je poredan, a razvrstanost nije 1.");
        printString("Relevantni dio niza iznosi:");
        i := donja_granica;
        While i < gornja_granica Loop
            printInteger(ValueAt(originalni_niz + i));
            i := i + 1;
        EndWhile
        printString("Kraj relevantnog dijela niza!");
    EndIf
    If
        not(je_li_niz_vec_poredan) and (razvrstanost = 1 or razvrstanost > 1)
    Then
        //Open ne smije biti...
        printString("Razvrstanost je 1, a niz nije poredan!");
        printString("Relevantni dio niza iznosi:");
        i := donja_granica;
        While i < gornja_granica Loop
            printInteger(ValueAt(originalni_niz + i));
            i := i + 1;
        EndWhile
        printString("Kraj relevantnog dijela niza!");
    EndIf
    //Idemo dalje...
    Decimal32 razvrstanost_na_potenciju[8] := {1}; //Formula će se brže
                                                   //izračunati ako ne
                                                   //pozivamo "pow" gdje
                                                   //ne treba (kad je
                                                   //eksponent prirodan
                                                   //broj).
    i := 1;
    While i < 8 Loop
        razvrstanost_na_potenciju[i] :=
            razvrstanost_na_potenciju[i - 1] * razvrstanost;
        i := i + 1;
    EndWhile
    //Formula koju je ispisao genetski algoritam za predviđanje koliko će
    //usporedbi QuickSort napraviti:
// https://github.com/FlatAssembler/ArithmeticExpressionCompiler/tree/master/QuickSort/Genetic_algorithm_for_deriving_the_formula
    Decimal32 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;
    Decimal32 Eulerov_broj_na_koju_potenciju :=
        (prirodni_logaritam(gornja_granica - donja_granica) +
        prirodni_logaritam(prirodni_logaritam(gornja_granica
        - donja_granica))) * 1.05
        + (prirodni_logaritam(gornja_granica - donja_granica) -
        prirodni_logaritam(prirodni_logaritam(gornja_granica -
        donja_granica)) - prirodni_logaritam(2))
        * 0.9163 * abs(polinom_pod_apsolutnom);
    Decimal32 koliko_usporedbi_ocekujemo_od_QuickSorta :=
        prirodni_logaritam(Eulerov_broj_na_koju_potenciju);
    Decimal32 koliko_usporedbi_ocekujemo_od_MergeSorta :=
        2 * (gornja_granica - donja_granica) *
        prirodni_logaritam(gornja_granica - donja_granica)
        / prirodni_logaritam(2);
    //I sada kreće grananje na temelju izračunatog...
    If razvrstanost = 1 or razvrstanost > 1 Then
        broj_vec_poredanih_podniza := broj_vec_poredanih_podniza + 1;
        Return;
    ElseIf razvrstanost = -1 or razvrstanost < -1 Then
        broj_obrnuto_poredanih_podniza := broj_obrnuto_poredanih_podniza + 1;
        Integer32 i                    :=                      donja_granica;
        Integer32 j                    :=                 gornja_granica - 1;
        While i < gornja_granica Loop
            ValueAt(pomocni_niz + i) := ValueAt(originalni_niz + j);
            j                        :=                      j - 1;
            i                        :=                      i + 1;
        EndWhile
        i := donja_granica;
        While i < gornja_granica Loop
            ValueAt(originalni_niz + i) := ValueAt(pomocni_niz + i);
            i                           :=                    i + 1;
        EndWhile
        Return;
    ElseIf
        koliko_usporedbi_ocekujemo_od_MergeSorta <
        koliko_usporedbi_ocekujemo_od_QuickSorta or
        dubina_rekurzije > pow(2,
            12 - prirodni_logaritam(velicina_niza) / prirodni_logaritam(2))
                                     //JavaScriptina virtualna mašina ima
                                     //4KB memorije na sistemskom stogu,
                                     //i alociranje više heap memorije
                                     //ne mijenja tu nesretnu činjenicu.
                                     //Ne znam kako Emscripten (modificirana
                                     //verzija CLANG-a koja compilira
                                     //C++ u WebAssembly) to rješava.
    Then
        //MergeSort algoritam (približno poredani podnizovi,
        //za koje je MergeSort efikasniji od QuickSorta,
        //a moj ga program također koristi kada ima još
        //malo mjesta na sistemskom stogu, pa QuickSort
        //nije opcija)...
        broj_pokretanja_MergeSorta :=       broj_pokretanja_MergeSorta + 1;
        Integer32 sredina_niza     := (gornja_granica + donja_granica) / 2;
        //Prvo, rastavi niz na koji pokazuje pokazivač "originalni_niz"
        //na niz od originalni_niz+donja_granica do
        //originalni_niz+sredina_niza i niz od
        //originalni_niz+sredina_niza do
        //originalni_niz+gornja_granica,
        //i poredaj ta dva niza.
        hybrid_sort(donja_granica, sredina_niza, dubina_rekurzije + 1);
        hybrid_sort(sredina_niza, gornja_granica, dubina_rekurzije + 1);
        //Spajanje nizova originalni_niz[donja_granica..sredina_niza]
        //i originalni_niz[sredina_niza..gornja_granica] u jedan niz...
        Integer32 i                      := donja_granica;
        Integer32 gdje_smo_u_prvom_nizu  := donja_granica;
        Integer32 gdje_smo_u_drugom_nizu := sredina_niza;
        While i < gornja_granica Loop
        If (gdje_smo_u_prvom_nizu = sredina_niza or
            ValueAt(originalni_niz + gdje_smo_u_drugom_nizu)
            < ValueAt(originalni_niz + gdje_smo_u_prvom_nizu))
            and gdje_smo_u_drugom_nizu < gornja_granica Then
            ValueAt(pomocni_niz + i):=
                ValueAt(originalni_niz + gdje_smo_u_drugom_nizu);
            gdje_smo_u_drugom_nizu  := gdje_smo_u_drugom_nizu + 1;
        Else
            ValueAt(pomocni_niz + i) :=
                ValueAt(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 Loop
            ValueAt(originalni_niz + i) := ValueAt(pomocni_niz + i);
            i                           :=                    i + 1;
        EndWhile
        Return;
    Else //QuickSort algoritam (nasumično ispremještani podnizovi)...
        broj_pokretanja_QuickSorta := broj_pokretanja_QuickSorta + 1;
        //Daljnji kod je približno prepisan s
        // https://www.geeksforgeeks.org/quick-sort/
        //Iskreno, ne razumijem ni ja točno kako funkcionira.
        //On navodno preuređuje niz tako da svi elementi koji su manji
        //od onog koji je bio prvi (pivot) dođu prije njega, a ostali
        //poslije njega.
        Integer32 pivot := ValueAt(originalni_niz + gornja_granica - 1);
        Integer32 i     :=                            donja_granica - 1;
        Integer32 j     :=                                donja_granica;
        Integer32 pomocna_varijabla_za_zamijenu;
        While j < gornja_granica - 1 Loop
            If ValueAt(originalni_niz + j) < pivot Then
                i                             :=                         i + 1;
                pomocna_varijabla_za_zamijenu :=   ValueAt(originalni_niz + i);
                ValueAt(originalni_niz + i)   :=   ValueAt(originalni_niz + j);
                ValueAt(originalni_niz + j)   := pomocna_varijabla_za_zamijenu;
            EndIf
            j := j + 1;
        EndWhile
        pomocna_varijabla_za_zamijenu   := ValueAt(originalni_niz + i + 1);
        ValueAt(originalni_niz + i + 1) :=
            ValueAt(originalni_niz + gornja_granica - 1);
        ValueAt(originalni_niz + gornja_granica - 1) :=
            pomocna_varijabla_za_zamijenu;
        Integer32 gdje_je_pivot := i + 1;
        hybrid_sort(donja_granica, gdje_je_pivot, dubina_rekurzije + 1);
        hybrid_sort(gdje_je_pivot, gornja_granica, dubina_rekurzije + 1);
        Return;
    EndIf
    //Ovdje tok programa ne smije doći.
    printString("Izgleda da compiler nije ispravno "
                "preveo kontrolne strukture!");
EndFunction

//Ovo je funkcija koju će pozvati JavaScript...
Function pocetna_AEC_funkcija() Which Returns Nothing Does
    If originalni_niz = -1 or pomocni_niz = -1 Then
        Return; //Ako JavaScript nastavlja pokretati ovaj program
                //unatoč nedostatku memorije, neka onda on ne radi ništa.
    EndIf
    //Testiraj matematičke funkcije...
    If abs(pow(3, 3) - 27) > 2 Then //Da, one su jako neprecizne, ali zato
                                    //jako brze.
        printString("Izgleda da matematicke funkcije ne funkcioniraju dobro.");
        printString("pow(3, 3) =");
        printFloat(pow(3, 3));
    EndIf
    //Doznaj veličinu niza iz JavaScripta...
    Integer32 prijasnja_velicina_niza :=       velicina_niza;
    velicina_niza                     := daj_velicinu_niza();
    //Ako je potrebno, zauzmi još memorije...
    If
        velicina_niza / (64 * 1024 / 4) +
        not(not(mod(velicina_niza, 64 * 1024 / 4))) >
        prijasnja_velicina_niza / (64 * 1024 / 4) +
        not(not(mod(prijasnja_velicina_niza, 64 * 1024 / 4))) or
        prijasnja_velicina_niza = 0
    Then
        originalni_niz := zauzmi_memorijske_stranice(
                            4 * velicina_niza / (64 * 1024) +
                            not(not(mod(velicina_niza, 64 * 1024 / 4))));
        pomocni_niz    := zauzmi_memorijske_stranice(
                            4 * velicina_niza / (64 * 1024) +
                            not(not(mod(velicina_niza, 64 * 1024 / 4))));
        If originalni_niz = -1 or pomocni_niz = -1 Then
            printString("Nema dovoljno memorije za nastavak programa!?");
            izvijesti_JavaScript_o_nedostatku_memorije();
            Return; //Prekini izvršavanje ovog programa.
        EndIf
    EndIf
    //Sada zatraži od JavaScripta da kopira niz koji treba poredati
    //na memorijski prostor koji si (prethodno ili sada) zauzeo.
    kopiraj_niz_na_adresu(originalni_niz);
    //I sada ga kreni razvrstavati i mjeriti koliko ti treba vremena.
    broj_obrnuto_poredanih_podniza  :=
        broj_vec_poredanih_podniza  :=
        broj_pokretanja_QuickSorta  :=
        broj_pokretanja_MergeSorta  :=
        broj_pokretanja_SelectSorta := 0;
    pocni_mjerenje_vremena();
    hybrid_sort(0, velicina_niza, 0);
    zavrsi_mjerenje_vremena();
    izvijesti_o_obrnuto_poredanim_nizovima(broj_obrnuto_poredanih_podniza);
    izvijesti_o_poredanim_nizovima(broj_vec_poredanih_podniza);
    izvijesti_o_pokretanju_QuickSorta(broj_pokretanja_QuickSorta);
    izvijesti_o_pokretanju_MergeSorta(broj_pokretanja_MergeSorta);
    izvijesti_o_pokretanju_SelectSorta(broj_pokretanja_SelectSorta);
    Integer32 i := 0;
    While i < velicina_niza - 1 Loop
        If ValueAt(originalni_niz + i) > ValueAt(originalni_niz + i + 1) Then
            printString("Niz nije poredan!");
            Return; //Nemoj to ispisati više puta, nego prekini program čim
                    //si uočio prvu nepodudarnost.
        EndIf
        i := i + 1;
    EndWhile
EndFunction
JavaScript "Array.sort" is significantly faster:
[Image: rezultati_mjerenja.jpg]
Studying algorithms is a very unthankful job. It often happens that you write 500 lines of code, and it turns out your solution isn't even as good as the standard library is.
Reply





Users browsing this thread: 1 Guest(s)