Izpitno vprašanje RAČ2PRA 12900

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka MonikaDraškovič.

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

Razloži algoritem za urejanje z mehurčki.

Odgovor

Osnovna ideja urejanja z mehurčki je primerjava dveh sosednjih objektov in zamenjava, če stojita v napačnem vrstnem redu.

Algoritem

Imamo dve možnosti:

  1. urejen del začnemo graditi na začetku (potapljamo težje)
  2. urejen del začnemo graditi na koncu (lažji priplavajo na vrh)


Poglejmo primer, ko urejen del začnemo graditi na koncu:

  • vzamemo zadnji element in ga primerjamo s svojim predhodnikom
    • če je predhodnik manjši, sta elementa v pravem vrstnem redu in vzamemo predhodnika
    • če je predhodnik večji, ju zamenjamo


  1. public static void mehurcki(int[] a) {
  2. int n = a.length;
  3. //zunanja zanka
  4. for(int i = 0; i < n; i++){
  5. //notranja zanka v kateri se izvajajo primerjave in zamenjave
  6. for(int j = n-1; j >= i; j--){
  7. //primerjamo sosednja elementa in če ustrezata pogoju ju zamenjamo
  8. if (a[j-1] > a[j]){
  9. int tmp = a[j];
  10. a[j] = a[j+1];
  11. a[j+1] = tmp;
  12. }
  13. }
  14. }
  15. }


Primer
1.korak
4 8 2 1 5      primerjanje (1 > 5)
4 8 2 1 5 → 4 8 1 2 5      primerjanje (2 > 1) → zamenjava
4 8 1 2 5 → 4 1 8 2 5      primerjanje (8 > 1) → zamenjava
4 1 8 2 5 → 1 4 8 2 5      primerjanje (4 > 1) → zamenjava
1 | 4 8 2 5      Po prvem koraku je majmanjši element na svojem mestu. Zato v naslednjem koraku tega pustimo na miru in urejamo preostale.
2.korak
1 4 8 2 5      primerjanje (2 > 5)
1 4 8 2 5 → 1 4 2 8 5      primerjanje (8 > 2) → zamenjava
1 4 2 8 5 → 1 2 4 8 5      primerjanje (4 > 2) → zamenjava
1 2 | 4 8 5
3.korak
1 2 4 8 51 2 4 5 8      primerjanje (8 > 5) → zamenjava
1 2 4 5 8      primerjanje (4 > 5)
1 2 4 | 5 8
4.korak
1 2 4 5 8      primerjanje (5 > 8)
1 2 4 5 | 8      Po zadnjem koraku ostane še en element, ki pa je že na svojem mestu.
Osebna orodja