Sortiranje ...

Naravno većina je pomislila da ću pričati nesto o algoritmima sortiranja. Neću, pokušaću da napišem program koji sortira nekoliko promenljivih. Konkretno 3 :).

Poučen negativnim iskustvom izbora mladih programera, a bogami i starijih, uz ideju Dušana Milanova počeo sam da na intervijuima zadajem zadatak da se napiše mali program za sortiranje tri promenljive. Recimo da imate tri celobrojne promenljive a, b i c i da želite da po zavrsetku programa/algoritma/koda važi da je a <= b <= c. Hoce reći da ih sortirate u neopadajući niz :).

Svačega sam se naslušao, neću ni da pokušavam da se setim svega toga. Zar vam deluje to kao težak zadatak ako mislite da se bavite programiranjem?
Ispada da jeste težak zadatak za mnoge. Ako mislite da ste programer, prestanite sa čitanjem ovde i pokušajte da sami napravite neku svoju verziju.

Pa da krenemo, po meni sortiranje tri promenljive je dosta složeno, pa bi ja da prvo uradimo sortiranje dve promljive:

void sort2(int* a, int* b)
{
  if(*a > *b)
    swap(a, b);
}

Naravno sada možemo da koristeći sort2 uradimo sort3:

void sort3(int* a, int* b, int* c)
{
  sort2(a, b);
  sort2(a, c);
  sort2(b, c);
}

Da li je to bilo teško? Po meni je dosta logično. sort2 je nekako intutivan, neću ni da pokušam da ga opravdam. sort3 je ono što bi prvo uradili i napisali, da uredimo svakog sa svakim. Naravno pitanje je da li to može bolje?

Ajde da prvo analiziramo ovaj kod, uzmimo da su a, b i c iz skupa {2, 3, 5} i različiti (što ne 4, eto iz hira, uzeo sam proste brojeve):

a	b	c	swaps
2	3	5	0
2	5	3	1
3	2	5	1
3	5	2	2
5	2	3	2
5	3	2	3

Uvek će biti 3 poredjenja, ali brojimo swapove, jedino ono na kraju mi ne pije vodu, ocigledno da moze samo sa jednim swapom.
Gde je problem? Za prvi sort2 treba izabrati nešto što je neminovno, ali što ne moze pokvariti redosled. Ako bi izabrali da prvo uradimo sort2(a, c) nećemo puno pokvariti. Dakle sada je progam ovakav:

void sort3(int* a, int* b, int* c)
{
  sort2(a, c);
  sort2(a, b);
  sort2(b, c);
}

Pogledajmo sada koliko će biti swapova:

a	b	c	swaps
2	3	5	0
2	5	3	1
3	2	5	1
3	5	2	2
5	2	3	2
5	3	2	1

Ovo sada već deluje optimalno po broju swapova, ali kako stoje stvari sa brojem poredjenja. Može se uraditi sa minimalno 2 poredjenja a ne uvek sa 3. Doduše izgubićemo optimalnopst po broju swapova. Kako znamo da ćemo izgubiti optimalnost po broju swapova, pa tako što poredjenje a i c mora doći na kraju. Dva prva poredjenja koja moramo da izvršimo su a sa b i b sa c. Ako nam je poredjenje skupo, primenićemo recimo:

void sort3(int* a, int* b, int* c)
{
  sort2(a, b);
  if(*b > *c)
  {
    swap(b, c);
    sort(a, b);
  }
}

Doduše opet u nekim slučajevima imamo testiranje viška, recimo za slučaj 2, 5, 3. Koje je rešenje, pa i nema ga :). Najbolje što možemo je da napustimo ovaj lep koncpet svodjenja sort3 na sort2 i napisemo mrežu testova.

void sort3(int* a, int* b, int* c)
{
  if(*a < *b)
  {
    /* a < b */
    if(*b < *c)
    {
      /* a < b && b < c => a, b, c */
    }
    else
    {   
      /* a < b && c < b */
      if(*a < *c)
      {
        /* a < b && c < b && a < c => a, c, b */
        swap(b, c);
      }
      else
      {
        /* a < b && c < b && c < a => c, a, b */
        swap(a, c);
        swap(b, c);
      }
    }
  }
  else
  {
    /* b < a */
    if(*a < *c)
    {
      /* b < a && a < c => b, a, c */
      swap(a, b);
    }
    else
    {
      /* b < a && c < a  */
      if(*b < *c)
      {
        /* b < a && c < a && b < c => b, c, a */
        swap(a, b);
        swap(b, c);
      }
      else
      {
        /* b < a && c < a && c < b => c, b, a */
        swap(a, c);
      }
    }
  }
}

Šta je sada zanimljivo, i dalje imamo utisak da može bolje, ali eto ja ne znam kako. Po broju swapova ne može, to je to, ali nekada imamo suvišne testove, recimo za slučaj 5, 3, 2. Ovaj kod je već dosta složen i nepregeldan. Da li je bolje ostaviti sladak i fin kod ili ići na totalnu optimizaciju.

I ovde stajem. Za razmišljanje je sledeće: kako uraditi sort4 recimo. Naravno koristeći sort2 i sort3 :). Za one baš napredne, nadjite paralelu izmedju raznih algoritama sortiranja i raznih realizacija sort4 (sortn). Možda o tome nekada.

P.S. Inače, većina zna, nisam baš neki pristalica C++, ali često čujem kako je std::sort iz C++ brži od qsort u C-u. Jeste, istina je, ne baš zbog toga što je C++ brži/bolji/moćniji jezik od C-a, nego zato što std::sort koristi introsort i direktno ugradjuje funkciju za komparaciju za razliku od qsort koji koristi quick sort i pozivanje funkcije za komparaciju :).