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