Urejanje s stresanjem

Iz MaFiRaWiki

Vsebina


Urejanje s stresanjem ali Shake Sort, tudi Cocktail sort je eden izmed algoritmov za urejanje manjšega števila podatkov v tabeli, ko enostavnost kode prevlada nad slabšo učinkovitostjo. Časovna zahtevnost metode je O(n2).

Je izboljšana verzija algoritma urejanja z mehurčki (Bubble Sort), kjer primerjamo dva sosednja elementa v tabeli po njuni vrednosti, ter ju, če še nista v pravilnem vrstnem redu, zamenjamo. Začnemo na začetku in primerjamo prva dva elementa tabele, isto storimo z drugim in tretjim, tretjim in četrtim... in tako do konca. Pri tem je največji element tabele gotovo prišel na zadnje mesto. Postopek ponovimo, gremo pa le od začetka do predzadnjega para, zadnji element pustimo pri miru, ker je že na pravem mestu. Tako je drugi največji element prišel na predzadnje mesto. Ko se vse skupaj ponovi tolikokrat, kolikor ima tabela elementov, je vse urejeno.

Algoritem

Metoda urejanja s stresanjem temelji na menjavanju smeri primerjanj, kar pomeni, da v enem prehodu skozi zanko:

  • z pregledovanjem od desne proti levi pripeljemo na pravo mesto najmanjši element
  • z pregledovanjem od leve proti desni pripeljemo na pravo mesto največji element

Pri vsakem prehodu si sproti zapomnimo lokacijo že uspešno prestavljenih elementov in se tako izognemo nepotrebnem sprehodu po že urejenem delu. Na ta način omejujemo interval še neurejenih elementov, v vsakem prehodu skozi zanko za dva. Ker imamo na sredini še neurejene elemente, postopek ponavljamo, neurejeni del pa se postopoma oži. Algoritem se konča, ko se leva in desna meja srečata na sredini tabele.

Prednost tega algoritma je, da se bistveno se zmanjša število primerjanj, število zamenjav pa ostane enako kot pri urejanju z mehurčki, metoda ima še vedno kvadratno časovno zahtevnost. Takšen primer je recimo tabela (2,3,4,5,1), ki jo uredimo z metodo Shake sort v enem prehodu skozi zanko, pri urejanju z Bubble sort metodo pa bi za to potrebovali 4 prehode.


Algoritem v psevdokodi pri čemer je:

  • A začetna neurejena tabela
  • sestavljena iz elementov z indeksi od l do r (l je leva meja tabele in r desna meja)
  • prvi element z indeksom 0
SHAKESORT(tab A, int l, int r) 
 while (l < r) do    // ponavljaj, dokler ne prideš do konca tabele
   stresi1(A, l, r)  // z metodo pregledaš tabelo z leve, na njen konec premakneš največji element
     r = r-1         // postavi novo desno mejo
   stresi2(A, l, r); // z metodo pregledaš tabelo z desne, na njen začetek premakneš najmanjši element
     l = l+1         // postavi novo levo mejo
   
stresi1(tab A, int l, int r) 
  for i:=l to r-1 do         // pregledamo vse elemente od leve proti desni
    if (A[i] > A[i+1]) then  // če je kakšen levi element večji od svojega naslednika
      menjava(A[i], A[i+1])  // zamenjaj

stresi2(tab A, int l, int r) 
  for i:=r downto l+1 do     // pregledamo vse elemente od desne proti levi
    if (A[i] < A[i-1]) then  // če je kakšen desni element manjši od svojega predhodnika
      menjava(A[i], A[i-1])  // zamenjaj


Primer

Sortirati želimo tabelo velikosti n. Primerjamo sosednja elementa v tabeli od konca do začetka, odrežemo urejeni del tabele in ponovimo primerjavo v drugo smer, brez urejenega dela. Zopet odrežemo urejen del na koncu, ter ponovimo postopek v drugo smer, dokler niso vsi elementi urejeni. V vsakem prehodu se tabela neurejenih elementov skrajša za en element. Ker pa to počnemo v zanki, se v istem izvajanju zanke izvede pregledovanje še v obe smeri. Neurejeni del tabele na sredini se postopoma oži, postopek zaključimo, ko ne naredimo več nobene zamenjave.

Poglejmo konkreten primer na tabeli z osmimi elementi:

44 55 12 42 94 18 6 67

  1. Prehod skozi zanko:
    levi indeks = 0, desni indeks = 7:
    Vzamemo zadnji element tabele, to je 67 in ga primerjamo z elementom pred njim. Ker 6 < 67 sta že na pravih mestih, vzamemo element 6 in primerjamo z 18. Ker je 18 > 6 ju zamenjamo. To ponavljamo, dokler ne pridemo do začetka tabele. Po prvem koraku je videti tabela takole:
    6 44 55 12 42 94 18 67

    levi indeks = 1, desni indeks = 7:
    Sedaj pa smer premikov obrnemo, tako da med sabo primerjamo drugi in tretji element (za prvega vemo, da je na pravem mestu). Ker je 44 < 55 , sta že na pravih mestih, pogledamo tretji in četrti. Ker je 55 > 12, ju zamenjamo, pogledamo četrti in peti, ker je 55 > 42, ju zamenjamo. Vzamemo peti in šesti element, ker je 55 < 94, ju pustimo, pogledamo šesti in sedmi element, ker je 94 > 18, ju zamenjamo. Na koncu primerjamo še zadnja dva elementa, ker je 94 > 67 ju zamenjamo. Po drugem koraku zgleda tabela takole:

    6 44 12 42 55 18 67 94
  2. Prehod skozi zanko:
    levi indeks = 1, desni indeks = 6
    Po dveh korakih vemo, da sta prvi in zadnji element v tabeli že na pravem mestu. Drugi prehod skozi zanko, to je tretji korak začnemo z elementom, ki je na predzadnjem mestu in ga primerjamo z elementom pred njim. Ker 18 < 67, elementa ostaneta, primerjamo 18 in 55, ker je 55 > 18 ju med sabo zamenjamo. Primerjamo 18 in 42, ker je 42 > 18 zamenjamo. Pred 18 je sedaj 12 in ker je 12 < 18, 18 ostane na mestu, nadaljujemo z 12. Ker je 42 > 12 ju zamenjamo. Dobimo:
    6 12 44 18 42 55 67 94

    levi indeks= 2, desni indeks= 6
    Prvi in drugi element sta urejena, vzamemo tretjega in ga primerjamo s četrtim, ker 44 > 18 ju zamenjamo, nadaljujemo in primerjamo 44 z naslednjim, petim elementom, ker je 44 > 42, ju zamenjamo. Primerjamo 44 s šestim elementom in ker je 44 < 55, ostane na tem mestu, primerjamo še šesti in sedmi element, ker je 55 < 67. Ostane. Po četrtem koraku imamo :

    6 12 18 42 44 55 67 94
  3. Prehod skozi zanko:
    levi = 2, desni = 3
    Peti korak se bo izvedel, vendar so elementi že urejeni. Dobimo isto tabelo
    6 12 18 42 44 55 67 94

    levi = 3, desni = 3
    Šesti korak se ne izvede, saj sta levi in desni indeks elentov enaka. Po izhodu iz zanke dobimo tabelo

    6 12 18 42 44 55 67 94

    Ker algoritem v zadnji zanki ni opravil nobene menjave, se postopek zaključi.

Implementacija

Glej tudi

Viri

Osebna orodja