Triediace algoritmy

04.08 | 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 | 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 06.08 | 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 | 09:31
        Avatar LUcoRP Debian, *Ubuntu, Android  Používateľ

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

        • RE: Triediace algoritmy 06.08 | 10:15
          Avatar debian   Návštevník

          Ved data zanonymizuj a suhlas Ti nebude treba?

          • RE: Triediace algoritmy 06.08 | 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 | 10:59
          Avatar easySolution   Návštevník

          pekna zbierka je aj na hovnokod.cz

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

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

            • RE: Triediace algoritmy 07.08 | 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 15.08 | 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.