Izpitno vprašanje RAČ2PRA 13800

Iz MaFiRaWiki

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;
  }