Naloga/Podatkovne strukture in algoritmi/Hitro urejanje

Iz MaFiRaWiki

Sestavi metodo ali funkcijo, ki uredi podatke v tabeli. Uporabi hitro urejanje.

Sestavi več rešitev z različnimi izbirami pivota:

  • pivot je prvi element
  • pivot je naključni element
  • pivot je mediana prvega, zadnjega in srednjega elementa

Glej tudi

Rešitev

Clear[Razbij]
      
Razbij[s_List] := Module[{a, n, s1, s2, s3, i, r = {}},
          a = s[[1]];
          n = Length[s];
          s1 = {};
          s2 = {a};
          s3 = {};
          For[i = 2, i ≤ n, i++,
            If[s[[i]] < a, s1 = Append[s1, s[[i]]], If[s[[i]] > a, s3 = 
          Append[s3, s[[i]]], s2 = Append[s2, s[[i]]]]];
            ];
          r = {s1, s2, s3};
          Return[r]
          ]

      
Clear[Uredi]
      
Uredi[{}] := {}
Uredi[{a_}] := {a}
Uredi[{a_, b_}] := If[a ≤ b, {a, b}, {b, a}]
Uredi[s_List] := Module[{l, n, r, t = {}},
          l = Razbij[s];
          n = Length[s];
          r = {Uredi[l[[1]]], Uredi[l[[2]]], Uredi[l[[3]]]};
          t = Flatten[r, n];
          Return[t]
          ]

Primer:


Clear[Razbij,Uredi]
In[1]:= Razbij[{3, 2, 6, 4, 1, 3, 5, 6}]
In[2]:= Uredi[{3, 2, 6, 4, 1, 3, 5, 6}]
Out[1]:= {{2, 1}, {3, 3}, {6, 4, 5, 6}}
Out[2]:= {1, 2, 3, 3, 4, 5, 6, 6}

Osebna orodja