Rešitev: Naloga: Heapsort (Mathematica)

Iz MaFiRaWiki

Algoritem

Preuredi v kopico

In[1]:=  Clear[PreurediVKopico]

In[2]:=  PreurediVKopico[l_List,n_Integer]:=Module[{kopica=l,i=n,j,k=Length[l]},
          While[(j=2 i)≤k,
           If[(j<k)&&(kopica〚j〛>kopica〚j+1〛),j++];
           If[
            kopica〚i〛>kopica〚j〛,
            {kopica〚i〛,kopica〚j〛}={kopica〚j〛,kopica〚i〛};
            i=j,
            i=k+1
           ];
          ];
          kopica
         ];

         PreurediVKopico[l_List]:=Module[{kopica=l,i},
          Do[kopica=PreurediVKopico[kopica,i],{i,Quotient[Length[l],2],1,-1}];
          kopica
         ];

Urejanje s kopico

In[4]:=  Clear[UrejanjeSKopico]

In[5]:=  UrejanjeSKopico[{}]:={};
         UrejanjeSKopico[l_List]/;(Length[l]>0):=Module[{kopica=PreurediVKopico[l],i},
          Append[
           Table[
            i=First[kopica];
            kopica〚1〛=kopica〚n〛;
            kopica=PreurediVKopico[Drop[kopica,-1],1];
            i,
            {n,Length[l],2,-1}
           ],
           Max[kopica]
          ]
         ];

Uporaba

In[7]:=  Clear[l]
In[8]:=  Table[Random[Integer,100],{10}]
Out[8]=  {95, 55, 12, 99, 1, 0, 53, 11, 45, 52}
In[9]:=  UrejanjeSKopico[%]
Out[9]=  {0, 1, 11, 12, 45, 52, 53, 55, 95, 99}

In[10]:= PreurediVKopico[{41, 78, 1, 85, 24, 96, 80, 78, 17, 89}]
Out[10]= {1, 17, 41, 78, 24, 96, 80, 78, 85, 89}

In[11]:= UrejanjeSKopico[{41, 78, 1, 85, 24, 96, 80, 78, 17, 89}]
Out[11]= {1, 17, 24, 41, 78, 78, 80, 85, 89, 96}
Osebna orodja