Izpitno vprašanje RAČ2PRA 13600

Iz MaFiRaWiki

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

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 mehurčki in analiziraj njegovo časovno zahtevnost.

Odgovor

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


  • ALGORITEM:
    • vzamemo zadnji element in ga primerjamo s svojim predhodnikom:
    o če je predhodnik manjši, potem sta elementa v pravem vrstem redu in zgrabimo predhodnika
    o če predhodnik ni manjši, ju zamenjamo
    o ...
    o najlažji element splava na površje
    o plavanje - zamenjave

slika:Plavanje-zamenjave.JPG

  • METODA:

  1. public static void mehurcki(int[] a) {
  2. int n = a.length;
  3. for(int i=0; i < n; i++){
  4. for(int j=1; j < (n-i); j++){
  5. if (a[j-1] > a[j]){
  6. int tmp = a[j-1];
  7. a[j-1] = a[j];
  8. a[j] = tmp;
  9. }
  10. }
  11. }
  12. }
  • ČASOVNA ZAHTEVNOST:
    • število primerjav:
    o vedno enako
    o 1 korak: n - 1
    o 2 korak: n - 2
    o n - 1 korak: 1
    o n*(n-1)/2 primerjav
    • število zamenjav:
o najboljše:
urejeno zaporedje
nobenega ne premaknemo: 0
o najslabše: 3(n2 - n)/2
o povprečno: 3(n2 - n)/4
--> O(n2)
o Algoritem navadnih zamenjav vsebuje neko zanimivost: medtem ko se najmanjši element v neurejenem delu tabele spusti na svoje pravo mesto med enim samim izvajanjem notranje zanke, porabi največji element za to, da se dvigne do svojega pravega mesta, večkratno izvajanje notranje zanke. Na podlagi te ugotovitve pridemo do različice navadnih zamenjav, kjer smer gibanja "mehurčkov" po vsakem izvajanju notranje zanke zamenjamo. Taki različici pravimo "izmenične zamenjave".
Osebna orodja