Sortiranje

Koju su efikasni algoritmi za sortiranje? Da li mora u zadacima da se radi Quick Sort ili postoji jos neki koji je takodje efikasan?

Pa Quick Sort je efikasan i lako se kuca. U srednjem slucaju njegova vremenska slozenost je O(n log n), bar ona verzija QSa koju takmicari najcesce kucaju.

Pored toga postoji merge sort koji uvek radi O(n log n). Postoji heap sort koji takodje ima takvu slozenost. Ti sam onda proceni kada ti je dovoljno da iskucas Selection sort ili kad moras da kucas quick sort, merge sort i slicno. Ako koristis C++ tamo imas ugradjen sort koji sigurno radi u najgorem slucaju O(n log n), ali svakako je dobro da prvo naucis kako se kuca, pa onda kasnije da koristis gotovo.

A sta ti smeta QSort? :)

Postoje Heap i Merge sort koji rade u NlogN, dok QSort u proseku radi NlogN.
Mada ja ne vidim zasto ne bi koristio QSort u zadacima, on je sasvim dovoljan...

boba ti je vec detaljnije odgovorio...

Znam da C++ ima ugradjen sort, i to sam koristio, ali sada radim jedan zadatak u Pascalu i trebam nesto da sortiram a ne znam da li moze da prodje neki sporiji sort kao sto su Selection i Bubble ili moram da kucam neki brzi sort. Radi se o zadatku Kamen sa okruznog takmicenja 2008.


Da li je dobar ovaj C++ kod za QSort.

void QSort (int l, int d)
{
int Tmp, pivot, i, j;
if (l < d)
{
pivot = a [(l + d) / 2];
i = l;
j = d;
do
{
while (a [i] > pivot) i++;
while (a [j] < pivot) j--;
if (i <= j)
{
Tmp = a [i]; a [i] = a [j]; a [j] = Tmp;
i++; j--;
}
}
while (i <= j);
QSort (l, j);
QSort (i, d);
}
}

Ne smeta mi QSort ali nikako ne mogu da ga napisem kako treba. :S

Da, taj zadatak sam ja dao i ima par malo podmuklih test primera gde onaj QS koji se najcesce kuca ne prolazi. Probaj, a ako ne uspes onda iskucaj heap sort taman ces nauciti kako se koristi heap (ako vec ne znas) i uraditi zadatak :) Idejno ni jedan nije tezak.

u paskalu bi trebalo da imas folder examples gde ima qsort

Ok, hvala na pomocji. ;)

Bobo tu si mi uzeo 10p xD
A po programu takmicenja pise da su nlogn sortovi tek za republicko xD

xD Heap je prosao bez problema, hvala jos jednom. ;)

http://www.z-trening.com/new/www/html/submit.php?submit=7100012748&subm_code=1

Meni je za taj zadatak prosao i "uobicajeni" QSort...

meni je na tak radio za 90 jer mi nije palo na pamet da pisem nesto vise od buble xD

Tmp = a ; a = a [j]; a [j] = Tmp;
mozes umesto toga samo
swap(a,a[j]); :)
koristi sort ili qsort iz STL, naravno kad ih naucis:)

ili ako si u pascalu, i ne zelis koristiti tmp:
a += b
b = a - b
a -= b

npr.
a = 4
b = 2

a += b -> a = 4 + 2 = 6
b = a - b -> b = 6 - 2 = 4
a -= b -> a = 6 - 4 = 2

ili jos brze
a = a xor b
b = a xor b
a = a xor b

a i lepo izgleda

Ok , hvala. Sada cju da radim tako jer kazete da je brze. ;)