abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
    včera 22:44 | Bezpečnostní upozornění

    NÚKIB upozorňuje na kritickou zranitelnost v SharePointu. Jedná se o kritickou zranitelnost typu RCE (remote code execution) – CVE-2025-53770, která umožňuje neautentizovaný vzdálený přístup a spuštění kódu, což může vést k úplnému převzetí kontroly nad serverem. Zranitelné verze jsou pouze on-premise verze a to konkrétně SharePoint Server 2016, 2019 a Subscription Edition. SharePoint Online (Microsoft 365) není touto zranitelností ohrožen.

    Ladislav Hagara | Komentářů: 2
    včera 21:00 | IT novinky

    Společnost Valve zpřísnila pravidla pro obsah, který je možné distribuovat ve službě Steam. Současně řadu her ze Steamu odstranila. V zásadách a pravidlech přibylo omezení 15: Obsah, který by mohl porušovat pravidla a normy stanovené zpracovateli plateb a souvisejícími sítěmi platebních karet a bankami nebo poskytovateli připojení k internetu. Sem spadají zejména určité druhy obsahu pouze pro dospělé.

    Ladislav Hagara | Komentářů: 0
    včera 13:33 | Komunita

    Dle analytics.usa.gov je za posledních 90 dnů 6,2 % přístupů k webových stránkám a aplikacím federální vlády Spojených států z Linuxu.

    Ladislav Hagara | Komentářů: 0
    20.7. 17:44 | Zajímavý článek

    Jak si zobrazit pomocí Chrome a na Chromiu založených webových prohlížečích stránky s neplatným certifikátem? Stačí napsat thisisunsafe.

    Ladislav Hagara | Komentářů: 3
    20.7. 00:33 | Bezpečnostní upozornění

    V repozitáři AUR (Arch User Repository) linuxové distribuce Arch Linux byly nalezeny a odstraněny tři balíčky s malwarem. Jedná se o librewolf-fix-bin, firefox-patch-bin a zen-browser-patched-bin.

    Ladislav Hagara | Komentářů: 15
    20.7. 00:22 | Komunita

    Dle plánu by Debian 13 s kódovým názvem Trixie měl vyjít v sobotu 9. srpna.

    Ladislav Hagara | Komentářů: 1
    19.7. 13:22 | Komunita

    Vývoj linuxové distribuce Clear Linux (Wikipedie) vyvíjené společností Intel a optimalizováné pro jejich procesory byl oficiálně ukončen.

    Ladislav Hagara | Komentářů: 1
    18.7. 14:00 | Zajímavý článek

    Byl publikován aktuální přehled vývoje renderovacího jádra webového prohlížeče Servo (Wikipedie).

    Ladislav Hagara | Komentářů: 0
    18.7. 12:00 | Nová verze

    V programovacím jazyce Go naprogramovaná webová aplikace pro spolupráci na zdrojových kódech pomocí gitu Forgejo byla vydána ve verzi 12.0 (Mastodon). Forgejo je fork Gitei.

    Ladislav Hagara | Komentářů: 2
    17.7. 18:44 | Zajímavý článek

    Nová čísla časopisů od nakladatelství Raspberry Pi zdarma ke čtení: Raspberry Pi Official Magazine 155 (pdf) a Hello World 27 (pdf).

    Ladislav Hagara | Komentářů: 1
    Kolik tabů máte standardně otevřeno ve web prohlížeči?
     (27%)
     (24%)
     (5%)
     (6%)
     (3%)
     (3%)
     (5%)
     (27%)
    Celkem 66 hlasů
     Komentářů: 10, poslední dnes 12:43
    Rozcestník

    Quicksort

    6.3.2005 13:00 | Přečteno: 3953× | Linux | poslední úprava: 8.7.2005 09:43

    Nemaje klasického informatického vzdělání byl jsem toho ve škole ušetřen. O čem mluvím? Všechny ty algoritmy pro třídění a tak. No a pak to člověk potřebuje a neví. Když už to zjistí, tak si to chce vytesat do kamene. Ehm do webu. Tak taky rozšířím zbytečně duplicitní stránky, na kterých je taková, nebo onaká implementace quicksortu. Až to zas někdy budu potřebovat a jestli bude abíčko ještě existovat, tak to třeba tady najdu.

    #include <sys/time.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    #define timedif(start, stop) \
      (u_int)((stop)->tv_sec - (start)->tv_sec - ((stop)->tv_usec < (start)->tv_usec))
    
    #define utimedif(start, stop) \
      (u_int)((stop)->tv_usec - (start)->tv_usec + 1000000*((stop)->tv_usec < (start)->tv_usec))
    
    #define N       (10000000)
    #ifndef __u_char_defined
    typedef __u_int u_int;
    #endif
    u_int numbers[N];
    
    #define swap(i,j) \
      { register u_int pom=*i; *i=*j; *j=pom; }
    
    void quicksort(u_int *start, u_int *end)
    {
      u_int *i, *low=start;       /* low is place for pivot */
      for(i=start; i<end; i++)
      {
        if(*i<*end) /* end element is pivot */
        {
          swap(i, low);
          low++;
        };
      };
      swap(low, end);  /* place pivot to his place */
      if(start<low-1)
        quicksort(start, low-1);
      if(low+1<end)
        quicksort(low+1, end);
    }
    
    int main(void)
    {
      u_int rand_seed;
    #ifdef __USE_BSD
      struct timezone foo_;
      struct timezone *foo=&foo_;
    #else
      void *foo=NULL;
    #endif
      struct timeval start, stop;
    
      gettimeofday(&start, foo);
      rand_seed = start.tv_usec;
      srand(rand_seed);
    
      {     /* init numbers */
        u_int i;
        for(i=0; i<N; i++)
          numbers[i]=rand();
      }
    
      /* start measure */
      gettimeofday(&start, foo);
      quicksort(numbers, numbers+N-1);
      /* measure time */
      gettimeofday(&stop, foo);
      printf("#Sorting %d numbers consumed %d.%06dsec\n",
          N, timedif(&start, &stop), utimedif(&start, &stop));
    
      {     /* test result */
        u_int i;
        char OK=1;
        for(i=0; i<N-1 && (OK &= numbers[i]<= numbers[i+1]); i++);
        printf(OK?"All OK.\n":"Something bad.\n");
        return !OK;
      }
    }

    P.S.: Tato implementace není vhodná pro částečně setříděné pole. Patch pro částečně setříděná pole:

    @@ -20,6 +20,7 @@
     void quicksort(u_int *start, u_int *end)
     {
       u_int *i, *low=start;       /* low is place for pivot */
    +  swap(start+(end-start)/2, end);
       for(i=start; i<end; i++)
       {
         if(*i<*end) /* end element is pivot */
           

    Hodnocení: 100 %

            špatnédobré        

    Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

    Komentáře

    Vložit další komentář

    6.3.2005 15:52 Christof | skóre: 22 | Havířov
    Rozbalit Rozbalit vše BogoSort
    QuickSort je k ničemu, nejlepší třídící algoritmus je BogoSort :-) viz http://en.wikipedia.org/wiki/Bogosort
    6.3.2005 19:15 Hynek (Pichi) Vychodil | skóre: 43 | blog: Pichi | Brno
    Rozbalit Rozbalit vše Re: BogoSort
    Tak ten je fakt dobrej. Ten ihned implementuju do svého realtime adaptivního regulátoru.
    XML je zbytečný, pomalý, nešikovný balast, znovu vynalézané kolo a ještě ke všemu šišaté, těžké a kýčovitě pomalované.
    Vašek Lorenc avatar 7.3.2005 01:02 Vašek Lorenc | skóre: 27
    Rozbalit Rozbalit vše Re: BogoSort
    Tak, jak je tam uvedený, má jednu zásadní chybku -- když půjde všechno šejdrem, není nikde zaručeno, že to vůbec skončí.. Ale jinak je to dost kvalitka, o tom žádná :)
    ...včetně majestátného loosa
    6.3.2005 16:32 Honza "tux" Friesse | skóre: 15 | blog: Tuxův blog | Vyškov
    Rozbalit Rozbalit vše To se hodí...
    ... ještě sem hoď nějaké stromové etudy (AVL stromy,...) a nějaké vyhledávací algoritmy (třeba boyer-moora). To by opravdu mnohým pomohlo (včetně mě).
    Vašek Lorenc avatar 6.3.2005 17:05 Vašek Lorenc | skóre: 27
    Rozbalit Rozbalit vše Re: To se hodí...
    A případně trochu povídání o dynamickém programování a aproximativních algoritmech, ať si lidi trochu počtou -- evidentně je to občas potřeba a praktické příklady kolem toho se hodí..
    ...včetně majestátného loosa
    6.3.2005 23:33 Jiri Bajer | skóre: 34 | blog: Sarimuv koutek | Praha
    Rozbalit Rozbalit vše Re: To se hodí...
    Mrkni se na knihovnu Aapl, treba tam najdes uz hotove reseni... Why to reinvent the wheel? ;-)
    7.3.2005 08:48 Ladislav Thon
    Rozbalit Rozbalit vše Malá noticka terminologická...
    Je to skutečně třídění, nebo spíš řazení? :)
    7.3.2005 09:12 Hynek (Pichi) Vychodil | skóre: 43 | blog: Pichi | Brno
    Rozbalit Rozbalit vše Re: Malá noticka terminologická...
    No to mě mohlo napadnout, ale nenapadlo. Tak jo, je to řazení. Spokojen?
    XML je zbytečný, pomalý, nešikovný balast, znovu vynalézané kolo a ještě ke všemu šišaté, těžké a kýčovitě pomalované.
    7.3.2005 09:26 Hynek (Pichi) Vychodil | skóre: 43 | blog: Pichi | Brno
    Rozbalit Rozbalit vše Re: Malá noticka terminologická...
    A vlastně jo. Je to třídící algoritmus, jehož výsledkem je seřazená posloupnost. Jiné řadící algoritmy možná skutečně provádějí řazení, ale tenhle ne. Tenhle třídí. Co jiného dělá tahle část?
      for(i=start; i<end; i++)
      {
        if(*i<*end) /* end element is pivot */
        {
          swap(i, low);
          low++;
        };
      };
    
    Ta část jednoznačně provádí třídění na prvky menší než *end a na prvky nemenší. To je třídění jak vyšité. Je to třídící algoritmus na řazení rpvků.
    XML je zbytečný, pomalý, nešikovný balast, znovu vynalézané kolo a ještě ke všemu šišaté, těžké a kýčovitě pomalované.
    7.3.2005 17:44 Michal Marek (twofish) | skóre: 55 | blog: { display: blog; } | Praha
    Rozbalit Rozbalit vše Re: Malá noticka terminologická...
    O řadících algoritmech jsem ještě neslyšel... Ale je pravda, že železniční doprava není zrovna můj obor :)
    8.3.2005 08:30 Hynek (Pichi) Vychodil | skóre: 43 | blog: Pichi | Brno
    Rozbalit Rozbalit vše Re: Malá noticka terminologická...
    Ale no tak. Vždyť má pravdu. Třídící algoritmus by musel něco třídit a třídění je rozdělování nějakého souboru dat do kategorií. Výsledkem řazení je seřazený soubor dat, což je jaksi něco úplně jiného.
    XML je zbytečný, pomalý, nešikovný balast, znovu vynalézané kolo a ještě ke všemu šišaté, těžké a kýčovitě pomalované.
    8.8.2005 08:23 net-ray
    Rozbalit Rozbalit vše Dodatek
    Vyraz start+(end-start)/2 lze napsat takto: (start+end)/2
    b42 avatar 7.6.2007 22:44 b42 | skóre: 12 | Ostrava/Brno
    Rozbalit Rozbalit vše Re: Quicksort
    (ja vim ze jsem se asi o dva roky zpozdil, ale kdyby na to nekdo nekdy nahodou narazil tak:) http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

    Založit nové vláknoNahoru

    ISSN 1214-1267   www.czech-server.cz
    © 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.