Izpitno vprašanje RAČ2PRA 13800
Iz MaFiRaWiki
Različica od 21:00, 10 oktober 2006; poglej trenutno različico
←Starejša različica | Novejša različica→
←Starejša različica | Novejša različica→
![]() | Avtor tega članka je študent/ka BrankaJandrijevic.
Pripravil/a ga je pri predmetu Računalništvo 2(FMF PRA). Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu. |
Vprašanje
Osnova za algoritem hitrega urejanja je algoritem za preureditev tabele na dva dela - levo damo elemente manjše od izbranega, desno pa večje. Napiši metodo public static int razdeli(double[] tocke, int zacetek, int konec), ki to naredi na tabeli tocke z elementi med indeksoma zacetek ter konec in vrne ločnico med odsekoma preurejene tabele. To naredi učinkovito!
Odgovor
public static int razdeli(double[] tocke, int zacetek, int konec){ double pivot = tocke[zacetek]; int manjsi = zacetek; int vecji = konec; //dokler se indeksa ne prekrizata while(manjsi < vecji){ while(tocke[manjsi] <= pivot) manjsi++; //iscemo indeks vecjega elementa od pivota while(tocke[vecji] > pivot) vecji--; //iscemo indeks manjsega elementa od pivota //ce se indeksa nista prekrizala, zamenjamo elementa if(manjsi<vecji){ double podatek = tocke[vecji]; tocke[vecji] = tocke[manjsi]; tocke[manjsi] = podatek; } } //zamenjamo pivotni element z elementom na meji tocke[zacetek] = tocke[vecji]; tocke[vecji] = pivot; //vrnemo mejo return vecji; }