Quicksort

6.3.2005 13:00 | Přečteno: 4155× | 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 */

       

Komentáře

[Christof]

QuickSort je k ničemu, nejlepší třídící algoritmus je BogoSort viz http://en.wikipedia.org/wiki/Bogosort

[Hynek (Pichi) Vychodil]

Tak ten je fakt dobrej. Ten ihned implementuju do svého realtime adaptivního regulátoru.

[Vašek Lorenc]

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

[Honza "tux" Friesse]

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

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

[Jiri Bajer]

Mrkni se na knihovnu Aapl, treba tam najdes uz hotove reseni... Why to reinvent the wheel?

[Ladislav Thon]

Je to skutečně třídění, nebo spíš řazení? :)

[Hynek (Pichi) Vychodil]

No to mě mohlo napadnout, ale nenapadlo. Tak jo, je to řazení. Spokojen?

[Hynek (Pichi) Vychodil]

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

[Michal Marek (twofish)]

O řadících algoritmech jsem ještě neslyšel... Ale je pravda, že železniční doprava není zrovna můj obor :)

[Hynek (Pichi) Vychodil]

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.

[net-ray]

Vyraz start+(end-start)/2 lze napsat takto: (start+end)/2

[b42]

(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