09.12.35 Uppbygging tölva

Forritunarverkefni 3


Ķ žessu verkefni eigiš žiš aš skrifa skiptingarfall (partition) fyrir Quicksort röšunarašferšina ķ IA-32 smalamįli inni ķ (inline) Visual C++.

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()".


Skiliš śtprentun ķ hólf ķ VR-II og keyrsluskrį sem višhengi ķ tölvupósti til Pįls föstudaginn 2. nóvember.

hh (hja) hi.is, 24. október, 2001.