Izpitno vprašanje RAČ2PRA 12400

Iz MaFiRaWiki

Vsebina

Vprašanje

Opiši algoritem za hitro urejanje (algoritem, časovna in prostorska zahtevnost)

Odgovor

Hitro urejanje je učinkovit algoritem za sortiranje. Razvil ga je C.A.R. Hoare.Je primer algoritma Deli in Vladaj. Algoritem ima dve fazi:

 1.)Deljenje
    Deli delo na pol
 2.)Sortiranje
    Vladanje polovicam

Deljenje

Izberi delilni element.Poišči mesto za delilni element tako, da so vsi elementi na levi manjši in vsi elementi na desni večji od tega delilnega elementa.

Vladanje

Z rekurzijo uporabi isti algoritem na obeh polovicah.

Zahtevnost

Časovna zahtevnost je Θ(n log n), v najslabšem primeru pa O(n2). Ker vse izvajamo "na mestu" (znotraj iste tabele), je prostorska zahtevnost O(1).

Primer

Imamo števila

  • 13 16 8 9 17 23 7 3 2

Za delilni element (pivot) si izberemo kar prvi element (13). Elemente, ki so manjši od njega ali enaki njemu damo na levo, tiste, ki pa so večji, pa damo na desno. Tako dobimo:

  • 8 9 7 3 2 13 16 17 23.

Sedaj isti postopek ponovimo na levem (vijoličnem) in desnem (modrem) delu tabele. Za pivotni element povsod vzamemo prvega. Sedaj dobimo:

  • 7 3 2 8 9 13 16 17 23

Videli smo, da je drugi del tabele že urejen. Postopek spet ponovimo in dobimo:

  • 3 2 7 8 9 13 16 17 23

In spet ponovimo:

  • 2 3 7 8 9 13 16 17 23

Sedaj pa smo dobili vse elemente urejene po vrsti od najmanjšega do največjega.

Algoritem

 
HitroUrejanje(a,dno,vrh) {
if (dno < vrh) // problem ni majhen
  s = preuredi(a, dno, vrh); 
  //s – mesto, kjer se tabela razdeli
  HitroUrejanje(a,dno,s);
  HitroUrejanje(a,s+1,vrh);
}

 
public static int premeci(int[] a, int levo, int desno) {
  // preuredi tabelo a od leve do desne strani
	int pivot = a[levo];
	int manjsi = levo, vecji = desno;
	while (manjsi < vecji) { // dokler se indeksa ne prekrižata
	    while (manjsi < vecji && a[manjsi] <= pivot) // iščemo večjega
               manjsi = manjsi + 1;         
	    while (manjsi < vecji && a[vecji] > pivot) // iščemo manjšega
               vecji = vecji - 1; 
 
	    if (manjsi < vecji) { // če se nista indeksa prekrižala
		int t = a[manjsi];
		a[manjsi] = a[vecji];
		a[vecji] = t;
	    }
	}
	if (a[manjsi] > pivot)  manjsi = manjsi - 1; 
	a[i] = a[manjsi]; // prenesemo še pivotni element
	a[manjsi] = pivot;
	return manjsi; // kje je meja med deloma
    }
Osebna orodja