Rešitev: Urejanje elementov s tremi skladi

Iz MaFiRaWiki

Naloga: Urejanje elementov s tremi skladi


JePrazen[Pripravi[]] := True;
JePrazen[Vstavi[s_, e_]] := False;
JePrazen::usage = "Funkcija JePrazen[s] vrne True, če je sklad s prazen, in False sicer.";

Vrh[Pripravi[]] := Null;
Vrh[Vstavi[s_, e_]] := e;
Vrh::usage = "Funkcija Vrh[s] vrne zgornji element sklada s . Če je sklad prazen, vrne Null.";

Odstrani[Pripravi[]] := Pripravi[]; 
Odstrani[Vstavi[s_, e_]] := s;
Odstrani::usage = "Funkcija Odstrani[s] vrne sklad s brez zgornjega elementa . Če je sklad prazen, vrne prazni sklad.";

prelozi[s1_, s3_] := Module[{s4, s5},
      s4 = Vstavi[s3, Vrh[s1]];
      s5 = Odstrani[s1];
      Return[{s5, s4}];
      ];
prelozi::usage = "Funkcija prelozi[s1,s3] vrne sklad s1 brez zgornjega elementa
                  in sklad s3 z vstavljenim elementom iz sklada s1.";

urediS[ss1_, ss2_, ss3_] :=
    Module[{s1, s2, s3},
      s1 = ss1;
      s2 = ss2;
      s3 = ss3;
      
      While[! JePrazen[s1],
        While[(Vrh[s3] == Null) || (Vrh[s3] ≥ Vrh[s1]),
          {s1, s3} = prelozi[s1, s3]
          ];
        
        If[JePrazen[s1], Return[{s1, s2, s3}]];
        
        While[(Vrh[s2] == Null) || (Vrh[s1] ≥ Vrh[s2]), 
          {s1, s2} = prelozi[s1, s2]];
        While[Vrh[s2] ≥ Vrh[s3], {s3, s1} = prelozi[s3, s1]];
        
        If[JePrazen[s2], Return[{s1, s2, s3}]];
        
        While[Vrh[s2] ≥ Vrh[s1],
          While[Vrh[s2] ≥ Vrh[s1], {s2, s3} = prelozi[s2, s3]];
          While[Vrh[s1] ≥ Vrh[s2], {s1, s3} = prelozi[s1, s3]];
          ];
        ];
      
      Return[{s1, s2, s3}]
      ];
urediS::usage = "Funkcija urediS[s1,s2,s3] vzame sklad s1 z neurejenimi elementi in prazna sklada s2 in s3 
                 ter vrne prazna sklada s1 in s2 in sklad s3 s po velikosti urejenimi elementi.";

ss1[l_List] := ss1[l, Pripravi[]]
ss1[{}, s_] := s
ss1[l_List, s_] := ss1[Drop[l, 1], Vstavi[s, First[l]]]
ss1::usage = "Funkcija ss1[l] vzame seznam in naredi sklad.";

Preizkusimo na primeru:

l = {4, 3, 5, 2, 1, 13, 67, 7};
s1 = ss1[l];
s2 = Pripravi[];
s3 = Pripravi[];

urediS[s1, s2, s3]
{Pripravi[], Pripravi[], Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Pripravi[], 67], 13], 7], 5], 4], 3], 2], 1]}

Najslabša časovna zahtevnost je O(n^2). Naloge se ne da rešiti z enim ali dvema skladoma. Z dvema vrstama se da, če imamo v eni vrsti stražarja.


Glej tudi

Osebna orodja