COUNTING SORT
ALGORITMO:
for x:=1 to 9 do
count[x]:=0;
for i:=1 to n do //n è la taglia del vettore
count[a[i]]:=count[a[i]]+1;
for x:=2 to 9 do
count[x]:=count[x]+count[pred(x)];
for i:=n downto 1 do begin
b[count[a[i]]]:=a[i];
count[a[i]]:=count[a[i]]-1;
SPIEGAZIONE ALGORTIMO
In lavorazione...
COMPLESSITA’
Questo algoritmo ha complessità dell’ordine di O(n) (anche se sembrerebbe più complesso) in quanto non fa confronti tra i vari elementi dei vettori ma di volta in volta ha accesso lineare al valore cercato, ragion per cui la complessità è proporzionale alla taglia dell’input.
Torna a Programmazione e Lab.
Non ci sono commenti in questa pagina. [Scrivi commento]