Urejanje z mehurčki

Iz MaFiRaWiki

Vsebina


Urejanje z mehurčki (navadne zamenjave) ali bubble sort je enostavna metoda za urejanje manjšega števila podatkov v tabeli, ko enostavnost kode prevlada nad slabšo učinkovitostjo. Časovna zahtevnost metode je O(n2).

Podobno kot pri metodi navadno vstavljanje, je tudi pri metodi urejanja z mehurčki temeljna operacija zamenjava dveh elementov, toda pri slednji ima bistveno večjo vlogo. Metoda temelji na primerjanju in zamenjavi parov sosednjih elementov, dokler niso vsi elementi urejeni. Elemente urejamo tako, da vsakokrat primerjamo sosednja elementa in ju zamenjamo, če je predhodnjik večji od naslednjika. V nasprotnem primeru elementa pustimo na svojih mestih. Elementi se obnašajo kot različno težki mehurčki, saj se najmanjši element v neurejenem delu tabele spusti na svoje pravo mesto med enim samim izvajanjem zanke, največji element pa za spust na pravo mesto potrebuje večkratno izvajanje zanke.

Opis algoritma

  • Vzemi zadnji element in ga primerjaj z njegovim predhodnikom. Če je predhodnik manjši, potem sta elementa v pravem vrstnem redu in vzemi predhodnika.
  • Če predhodnik ni manjši, zamenjaj elementa.

Algoritem

Pomen spremenljivk:

  • n ...... število elementov v tabeli
  • a[i] ... element v tabeli 0<=i<=n
  • k,j ... pomožna števca
  • min .... vrednost trenutno najmanjšega elementa
k = n
repeat
 j  = k
 k = 0
  for i = 1 to j – 1 
     if(a[i] > a[i + 1]) 
        a[i] zamenjava z a[i + 1]
        k = i
     end_if
  end_for
until k = 0

Primer

Podano tabelo uredimo z metodo Bubble sort.

38 27 43 3 9 82 10

  1. Prehod skozi zanko:
    Vzamemo zadnji element tabele, to je 10 in ga primerjamo z elementom pred njim. Ker 10 < 82, ju zamenjamo,primerjamo 10 in 9, sta že na urejena in ostaneta na mestih, vzamemo element 9 in primerjamo s 3, ostane, pogledamo element 3, ker je 3 < 43 ju zamenjamo. To ponavljamo, dokler ne pridemo do začetka tabele. Po prvem koraku je videti tabela takole:
    3 38 27 43 9 10 82
  2. Prehod skozi zanko:
    Zopet vzamemo zadnjega, ker je 82 > 10, je na pravem mestu, vzamemo elemnt 10 in ga primerjamo z 9, sta urejena, zato ostane, naslednji je 9, ker je 9 < 43, ju zamenjamo, zopet 9 primerjamo z 27, ker je 9 < 27, ju zamenjamo, podobno zamenjamo še 38 in 9. Po drugem koraku zgleda tabela takole:
    3 9 38 27 43 10 82
  3. Prehod skozi zanko:
    Po dveh korakih vemo, da sta prvi in drugi element v tabeli že na pravem mestu. Tretji korak spet začnemo z elementom, ki je na zadnjem mestu in ga primerjamo z elementom pred njim. Ker 10 < 82, elementa ostaneta, primerjamo naslednja, 10 in 43, ker je 10 < 43 ju med sabo zamenjamo. Primerjamo 10 in 27, ker je 10 < 27, zamenjamo. Pred 10 je sedaj še 38 in ker je 10 < 38, ju zamenjamo. Dobimo:
    3 9 10 38 27 43 82
  4. Prehod skozi zanko:
    Prvi, drugi in tretji element so urejeni, zopet pogldamo zadnjega in ga primerjamo z 43, ker je 82 > 43, ostane na svojem mestu, vzamemo 43, ker je 43 > 82, tudi ta ostane na svojem mestu, naslednji je 27, ker je 27 < 38 ju zamenjamo. Po četrtem koraku imamo :
    3 9 10 27 38 43 82
  5. Prehod skozi zanko:
    Peti korak se izvede, vendar so elementi že urejeni. Dobimo tabelo
    3 9 10 27 38 43 82
  6. Prehod skozi zanko:
    Izvede se tudi šesti prehod skozi zanko, vendar je tabela že urejena.
    3 9 10 27 38 43 82

Izboljšave

Pri urejanju z mehurčki se lahko zgodi, da v kakem prehodu ne odkrijemo nobenega para, ki ga je potrebno zamenjati. Tedaj je tabela že urejena, program se lahko konča, četudi zanka ni prišla do konca. Tako bomo za urejanje skoraj urejene tabele 2, 3, 4, 5, 1, 6 potrebovali le dva kroga - v prvem bomo nesli enico do konca in v drugem ugotovili, da ni več česa menjati.

Drugačače je pri drugi, skoraj urejeni tabeli: 1, 6, 2, 3, 4, 5. V prvem krogu zamenjamo le 6 in 2, v drugem krogu 6 in 3, v tretjem 6 in 4 in v četrtem 6 in 5, v petem uvidimo, da je tabela urejena. Elementi, ki morajo na levo, tja prispejo zelo hitro, ti, ki potujejo nazaj, pa so počasni in brez potrebe povzročajo dodatne kroge. Reši nas menjavanje smeri urejanj.

Možne izboljšave:

  • postopek prekinemo, če v nekem prehodu ni nobene zamenjave - Bubblesort1
  • primerjanje dveh sosednjih elementov izvajamo samo do mesta zadnje zamenjave - Bubblesort2
  • menjavamo smeri prehodov - Shakesort

Implementacija

Glej tudi

Osebna orodja