Izpitno vprašanje RAČ2PRA 13800

Iz MaFiRaWiki

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

  1. public static int razdeli(double[] tocke, int zacetek, int konec){
  2. double pivot = tocke[zacetek];
  3. int manjsi = zacetek;
  4. int vecji = konec;
  5. //dokler se indeksa ne prekrizata
  6. while(manjsi < vecji){
  7. while(tocke[manjsi] <= pivot) manjsi++; //iscemo indeks vecjega elementa od pivota
  8. while(tocke[vecji] > pivot) vecji--; //iscemo indeks manjsega elementa od pivota
  9. //ce se indeksa nista prekrizala, zamenjamo elementa
  10. if(manjsi<vecji){
  11. double podatek = tocke[vecji];
  12. tocke[vecji] = tocke[manjsi];
  13. tocke[manjsi] = podatek;
  14. }
  15. }
  16. //zamenjamo pivotni element z elementom na meji
  17. tocke[zacetek] = tocke[vecji];
  18. tocke[vecji] = pivot;
  19. //vrnemo mejo
  20. return vecji;
  21. }
Osebna orodja