Izpitno vprašanje RAČ2PRA 13500

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka UrskaBerce.

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

Napiši algoritem za urejanje z izbiranjem in analiziraj njegovo časovno zahtevnost?

Odgovor


  • enostavno urejanje
  • preprosta zasnova
  • ne najbolj učinkovit
  • primeren za majhne tabele, n < 10 (enostavna koda odtehta slabo učinkovitost)


ALGORITEM:


SPLOŠNO:

  • poišči najmanjšega ,
  • zamenjaj s prvim ,
  • od 2 do n poišči najmanjšega ,
  • zamenjaj z drugim

...

imamo dva dela:

UREJENI DEL / NEUREJENI DEL

  • PONAVLJAJ:
    • v neurejenem delu zamenjaj prvi in najmanjši element
    • najmanjši (prvi) element v neurejenem delu preseli v urejen del - urejeni del se poveča za ena
    • na začetku je urejeni del prazen
    • končamo, ko izčrpamo neurejeni del


METODA:

  1. public static void urejanjeIzbira(int[] tab){
  2. int kjeNajm;
  3. for (int a = 1; a < koliko – 1; a++){
  4. kjeNajm = poisciNajmanjsega(tabela, a, koliko - 1);
  5. t = tabela[a];
  6. tabela[a] = tabela[kjeNajm];
  7. tabela[kjeNajm] = t;
  8. }
  9. }
  10. private static int poisciNajmanjsega(int[] tab, int odKje, int doKam){
  11. int i_najm = odKje;
  12. for (int i = odKje + 1; i <= doKam; i++){
  13. if (tab[i] < tab[i_najm])
  14. i_najm = i;
  15. }
  16. return i_najm;
  17. }


ČASOVNA ZAHTEVNOST: število primerjav:

  • vedno enako
  • 1 korak: n - 1
  • 2 korak: n - 2
  • n - 1 korak: 1
  • n*(n-1)/2 primerjav

število zamenjav:

  • najboljše:
    • urejeno zaporedje
    • n -1 elementov premaknemo: 3
    • 3n - 3
  • najslabše:
    • n2/4 + 3(n-1)
  • povprečno:
    • n(ln n + 0.577216…)

--> O(n2)

Osebna orodja