Naloga: Urejanje s tremi vrstami

Iz MaFiRaWiki

Naloga: Urejanje s tremi vrstami


V Mathematici implementiraj urejanje elementov s tremi vrstami. Imamo tri vrste V1, V2, V3. V vrsti V1 hranimo seznam imen, vrsti V2 in V3 pa sta na začetku prazni. Seznam imen razvrsti po abecedi naraščajoče (rep je "najmanjša" beseda) v vrsto V3. Pomagaš si lahko z vrsto V2. Je naloga rešljiva? Kakšna je najslabša časovna zahtevnost? Ali se da nalogo rešiti le z eno vrsto? Kaj pa z dvema?


Rešitev

Pripravimo si implementacijo vrste s seznamom.

Clear[Pripravi, Vstavi, JePrazna, Celo, Rep, Odstrani];

Pripravi[] := {}

Vstavi[Pripravi[], e_] := {e}
Vstavi[v_, e_] := Prepend[v, e]
Vstavi::usage = "Vstavimo element na rep vrste.";

JePrazna[{}] := True
JePrazna[{___}] := False
JePrazna::usage = "Preverimo, če je dana vrsta prazna.";

Celo[v_] := Last[v]
Celo::usage = "Vrne čelo vrste.";

Rep[v_] := v[[1]]
Rep::usage = "Vrne rep vrste.";

Odstrani[v_] := Drop[v, -1]
Odstrani::usage = "Funkcija odstrani celo in vrne preostanek vrste.";

Definiramo pomožno funkcijo, ki bo poljuben niz vrinila v že urejeno vrsto nizov tako, da bo "nova" vrsta ponovno urejena. Ločimo tri možnosti:

Če je niz manjši od repa dane vrste, ga preprosto vstavimo v vrsto.
Če je niz večji od repa in manjši od čela vrste, vse nize, ki so večji od danega niza, prestavimo v pomožno vrsto. Pri tem se urejenost in "smer" ohranita (to ne velja npr. pri prestavljanju skladov). V pomožno vrsto tedaj vstavimo naš niz in še vse manjše elemente. Na ta način dobimo urejeno vrsto.
Če je dani niz večji (ali enak) čelu vrste, niz vstavimo v pomožno vrsto in ponovimo zadnji korak prejšnje točke.
Vrini[e_String, Pripravi[]] := Vstavi[Pripravi[], e];

Vrini[e_String, V3_List] := Module[{V2,V4},
      
      V2 = Pripravi[];
      V4 = V3;             
      If[Order[Celo[V4], e] ≥ 0,
        V2 = Vstavi[V2, e];
        While[!JePrazna[V4],
          V2 = Vstavi[V2, Celo[V4]];
          V4 = Odstrani[V4];
          ];
        Return[V2];
        ];
      
      If[Order[Rep[V4], e] ≥ 0 && Order[e, Celo[V4]] ≥ 0,
        While[Order[e, Celo[V4]] ≥ 0,
          V2 = Vstavi[V2, Celo[V4]];
          V4 = Odstrani[V4];
          ];
        V2 = Vstavi[V2, e];
        While[!JePrazna[V4],
          V2 = Vstavi[V2, Celo[V4]];
          V4 = Odstrani[V4];
          ];
        Return[V2];
        ];
      
      If[Order[e, Rep[V4]] ≥ 0,
        V2 = Vstavi[V4, e];
        Return[V2];
        ];
      ];
Vrini::usage = "Funkcija v (padajoče) urejeno vrsto vstavi element in vrsto ponovno uredi.";

Sedaj lahko že definiramo funkcijo, ki bo sprejeto vrsto uredila. Kot je razvidno, postopoma "zgradimo" urejeno vrsto; delne vrste sproti urejamo.

Urejanje[V1_List] := Module[{V2,V},
      
      V2 = Pripravi[];
      V = V1;
      While[!JePrazna[V],
        V2 = Vrini[Celo[V], V2];
        V = Odstrani[V];
        ];
      Return[V2];
      ];
Urejanje::usage = "V prazno vrsto vstavljamo elemente dane vrste, pri čemer 
novo vrsto sproti urejamo.";

Primer urejanja:

r = {"aaa", "bb", "e", "t", "bab"}
Urejanje[r]
{aaa, bab, bb, e, t}

Urejanje s tremi vrstami je torej izvedljivo. Če je n dolžina vrste, ki jo nameravamo urediti, pomožna funkcija zahteva v najslabšem primeru O(n) primerjanj in prestavljanj. Potemtakem je časovna zahtevnost celotnega algoritma enaka O(n2).

Problema urejanja vrste se z eno samo vrsto v splošnem ne da rešiti. Če je ena izmed vrst implementirana s stražarjem, je nalogo mogoče rešiti z dvema vrstama.


Osebna orodja