Mesti tíminn í Quicksort fer í að skipta stökunum um vendistak. Það er því mikilvægt að sá hluti sé hraðvirkur til að aðferðin í heild sé hraðvirk. Hér að neðan er útfærsla á Quicksort í C++.
void quicksort( int *a, int l, int r)
{
if (r <= l) return;
int i = partition(a, l, r);
quicksort(a, l, i-1);
quicksort(a, i+1, r);
}
Það eru til ýmsar útgáfur af skiptingarfallinu, en við munum nota aðferð
sem skiptir um aftasta stakið (þ.e. stakið lengst til hægri).
int partition(int *a, int l, int r)
{
int i = l-1, j = r;
int v = a[r];
for (;;) {
while (a[++i] < v) ;
while (v < a[--j]) if (j == l) break;
if (i >= j) break;
exch(a[i], a[j]);
}
exch(a[i], a[r]);
return i;
}
Fallið exch víxlar á gildum í tveimur minnishólfum. Þið þurfið
ekki að hafa það sem sérstakt fall.
Þið eigið að skrifa partition-fallið í IA-32 smalamáli, þannig að allur kódi þar sé í smalamáli. Það eina sem á að vera í C++ eru hausinn og breytuskilgreiningar. Skrifið líka aðalforrit sem kallar á Quicksort stefið með 100.000 staka slembivektor. Búið til slembitölurnar með "rand()*32768 + rand()".
hh (hja) hi.is, 24. október, 2001.