Triediace algoritmy

04.08.2018 | 19:41 | originalnynazovblogu | LUcoRP

Začína sa nimi už v základoch programovania a nikto, kto to myslí s programovaním vážne sa bez nich nezaobíde. Poznáte všetky triediace algoritmy podľa ich efektivity?

Určite áno, kto nie, môže si pozrieť vizualizáciu v krátkom videu venujúcemu sa práve porovnaniu efektivity triediacich algoritmov.

Pre ostatných vypisujem súťaž o najNEefektívnejší triediaci algoritmus. Vyhrať môžte jedno veľké bezcenné plus, alebo tri menšie o nič viac cenné plusy. Aby ste to nemali také ľahké, v úvode uvádzam štyri, ktoré tým pádom nemôžete použiť:

  1. Bogo sort [AKA monkey sort, stupid sort, permutation sort, slowsort, shotgun sort...] → Trochu pomalší voči bubble sortu. Ide o algoritmus založený na náhodnom generovaní poradia prvkov, až kým sa netrafí správne zoradené poradie. Analógiou je vyhadzovanie balíčku kariet do vzduchu, až kým balíček nedopadne v zotriedenom poradí. Je často mylne považovaný za najmenej efektívny algoritmus.
  2. Stupid monkey sort → Môj vlastný vynález, aj keď pochybujem že som prvý kto mal tento úžasný nápad a možno ho poznáte pod iným názvom. Inšpirovaný Bogo sortom. Majme N prvkovú množinu, ktorej prvky náhodne generujeme, až kým prvok N1 < N2. Následne si odložíme prvok N1 do stacku a náhodne generujeme skupinu N-[N1] až kým nie je N2 < N3. Pozor, teraz príde krása tohto riešenia, pokiaľ je však prvok N2 > N3, tak si zo stacku odoberieme predtým odložený prvok N1. A takto postupujeme, až kým nebude zoradená celá skupina prvkov. Samozrejme, čím je prvkov v skupine viac, tým je tento algoritmus krajší a menej efektívny.
  3. Assumption sort → predpokladajme že je skupina prvkov zoradená a vráťme ju. Úspešnosť tohto algoritmu je síce zanedbateľná, ale zato je brutálne rýchly.
  4. Miracle sort → môj obľúbený. V loope kontrolujeme, či sú prvku zoradené, ak áno, vrátime výsledok, ak nie chvíľu počkáme a kontrolujeme znova.

Takže dokážete vymyslieť niečo ešte menej efektívne? :)

    • RE: Triediace algoritmy 05.08.2018 | 08:14
      Avatar dusan2   Návštevník

      Seems sorted sort - Zotriedi len prvych 10 percenet, clovek sa pozrie na zaciatok, vyzera to byt zotriedene, dalej nepozera

      Blockchain sort - Zotriedi sa pomocou technologie Blockchain, je to velmi perspektivna technologia a ocakavaju sa velke vynosy, vzorky 10 predtriedenych poloziek ponukame na predaj za $200 este pred zverejnenim samotneho celkoveho poradia. Viac info viď whitepaper

      Google sort - Bol zruseny

      Apple sort - Pozerate sa na prvky mnoziny zle, je to zotriedene.

      Oracle sort - prakticky bubble sort, platite za kazdy triedeny prvok ale ak ma vas procesor hyper threading platite 2x tolko

      • RE: Triediace algoritmy 05.08.2018 | 10:26
        Avatar LUcoRP Debian, *Ubuntu, Android  Administrátor

        ROFL :D

        git blame | Muj Desvorc je vetsi nez tvuj!
      • RE: Triediace algoritmy 06.08.2018 | 08:19
        Avatar Andrej Lacho Debian, CentOS ...  Administrátor

        :D :D

    • RE: Triediace algoritmy 06.08.2018 | 09:17
      Avatar WlaSaTy   Návštevník

      Bude aj pokračovanie?

      Pripomenulo mi to starú otázku z pohovoru: Riešite javový servlet pre užívateľskú session. Ako zistíte najmenší a najväčší prvok z poľa?

      Najhoršia odpoveď bola: Použijem internú funkcioanlitu javy na zotriedenie poľa, a vezmem krajné hodnoty.

      Pri bežnom loade malého podnikového servera s cca 20k až 50k užívateľov by si na tom garbage collector vylámal zuby. Najsmutnejšie na tom je to, že z nedostatku kvalifikovaných ľudí ich prijali. Jediné pozitívum je, že ich nedali na backend. Výsledkom sú stránky kde človek použije na frontend minimálne 5 toolkitov a aj s CSS to zaberie 0.5M textu. Výsledný TAB v prehliadači bez problémov zožerie viac ako 0.5G RAM.

      • RE: Triediace algoritmy 06.08.2018 | 09:31
        Avatar LUcoRP Debian, *Ubuntu, Android  Administrátor

        Uff :D

        Pri review kodu juniorov narazam na rozne veci, tak si najzaujimavejsie z nich zacnem odkladat a ked ich bude dostatok, tak moze dojst aj k uverejneniu, samozrejme so suhlasom autorov. :)

        git blame | Muj Desvorc je vetsi nez tvuj!
        • RE: Triediace algoritmy 06.08.2018 | 10:15
          Avatar debian   Návštevník

          Ved data zanonymizuj a suhlas Ti nebude treba?

          • RE: Triediace algoritmy 06.08.2018 | 10:26
            Avatar WlaSaTy   Návštevník

            Bude, firemný.

            Ale inak na podobné veci je tu známa bugzilla.

        • RE: Triediace algoritmy 06.08.2018 | 10:59
          Avatar easySolution   Návštevník

          pekna zbierka je aj na hovnokod.cz

          • RE: Triediace algoritmy 07.08.2018 | 08:38
            Avatar marekz   Návštevník

            Dobrý link. Pekná zbierka úplne bežného kódu.

            • RE: Triediace algoritmy 07.08.2018 | 15:01
              Avatar WlaSaTy   Návštevník

              Takých je veľa. Napríklad ukážka http://ioccc.org/2018/anderson/prog.c od jedného z tohoto ročných výhercov The International Obfuscated C Code Contest

      • RE: Triediace algoritmy 13.09.2020 | 22:40
        Avatar ra100   Návštevník
        Výsledkom sú stránky kde človek použije na frontend minimálne 5 toolkitov a aj s CSS to zaberie 0.5M textu. Výsledný TAB v prehliadači bez problémov zožerie viac ako 0.5G RAM.

        no koli tomuto som prestal pracovat, ako web develop, lebo tieto web bludy "vystudovanych" neprogramatorov a uzivatelov kdeakych frameworkov ma vazne nebavilo riesit a hrabat sa v tych exkrementoch.

        strasna hromada tagov, sialene hordy css, kopa js a uplne sialene php a nulova ochrana uzivatelskych dat, nulova bezpecnost webu ziadne escapovanie a ochrana vstupov a vystupov z databaz.

        mrte stranok som v tedy radsej prerobil od znova, lebo to bolo "jednoduhsie" a ten ich sialeny vytvor - kod som dokazal v klude zredukovat aj o viac, ako 85%, kedz nic viac stranka uz nepotrebovala.

        a hlavne, uz nikdy viac toto nechcem robit.

    • RE: Triediace algoritmy 15.08.2018 | 09:23
      Avatar jo   Návštevník

      Sleep sort: In general, sleep sort works by starting a separate task for each item to be sorted, where each task sleeps for an interval corresponding to the item's sort key, then emits the item. Items are then collected sequentially in time.

      Zotriedte nim pole {1, INT_MAX} a ked to zbehne sa ozvite.

    • RE: Triediace algoritmy 12.09.2020 | 22:19
      Avatar ra100   Návštevník

      moj postup je, ak je N vstup s nahodnymi cislami, kde dokonca rozne cisla mozu v klude chybat -

      prejdenie celeho vstupu,kde sa beru cisla rad za radom, kde kazde nasledujuce cislo je testovane, ci je vacsie, ako to predosle, nieco v style -

      if(nasledujuce N > aktualne N) najvissie N = nasledujuce N;

      takto ziskame najvacsie cislo z N.

      ulozene najvissie N spustit v cykle od nuly, nieco na styl -

      for($i = 0;$i <= najvissie N;$i++) if($i existuje vo vstupe) zapis do poradia.

      takto sa nam pekne zotriedia v poradi.

      ma to aj svoje temne minusy, priklad - do vstupu dame iba 3 N - N1 = 371 N2 = 1 000 000 000 N3 = 2

      tak toto by bolo trochu peklo, no pri hustejsich a lepsie zorganizovanych vstupoch, alebo pri kompletnom, hoci prehadzanom ciselnom poradi, je to vcelku lahodka.

      na zaver dufam, ze som dobre pochopil clanok, ak nie, tak som trafil iba vedla :D

      • RE: Triediace algoritmy 12.09.2020 | 22:36
        Avatar ra100   Návštevník

        este dodam, ze ak vieme naisto, ze vstupy N su v lubovolnych prehadzanych rozpatiach, kde naisto nechyba ziadne cislo v poradi, staci nam iba zratat pocet rozhadzanych N, bez akejkolvek analyzy a hned mame zotriedenie hotove.

        • RE: Triediace algoritmy 12.09.2020 | 23:05
          Avatar ra100   Návštevník

          este dodam k predoslemu prispevku, ze sa logicky jedna o lubovolne rozhadzane rozpatia, zacinajucich nulou, alebo jednotkou.

          jedna sa o relativne jednoduchy zasah pri pouziti 0/1 pri zaciatku rozpatia.

          a cele by som to riesil takto -

          prjdenim celeho vstupu od zaciatku do konca, kde -

          prechadzanim vstupu N, kde -

          $najnizsieN = prveN;
          $najvyssieN = prveN;
          if($najnizsieN < nasledujuceN)
          $najnizsieN = nasledujuceN;
          if($najvyssieN < nasledujuceN)
          $najvyssieN = nasledujuceN;

          a cele to zkopit v neakom cykle -

          for($i=$najnizsieN; $i <= $najvyssieN; $i++)
          if($i existuje kdesi vo vstupe N)
          premenna neake poradie = $i;
          vcelku vylepsena verzia prveho prispevku.

          • RE: Triediace algoritmy 12.09.2020 | 23:25
            Avatar ra100   Návštevník

            este mala oprava.

            Nie -

            if($najnizsieN < nasledujuceN)
                $najnizsieN = nasledujuceN;
            

            ale -

            if($najnizsieN > nasledujuceN)
                $najnizsieN = nasledujuceN;