asp - asp.net - aspcode.it

COMMUNITY - Login
 Username:
 
 Password:
 
Voglio registrarmi!
Password dimenticata?
 Utenti on-line: 0
 Ospiti on-line: 3861
ASPCode.it - Store

  > > Articoli

Ordinare un array (2)

Data di pubblicazione: 03/02/2003        Voto della community: 4,17 (Votanti: 4)

Nell'articolo precendente abbiamo visto come ordinare un array ma, se ricordate bene, abbiamo posto un limite teorico di 30 elementi da ordinare, determinato dal fatto che il metodo non Ŕ molto efficente se applicato ad array di dimensioni maggiori.
Vedremo ora un altro metodo di ordinamento che funziona in maniera ottimale anche su array di grande dimensione. L'algoritmo che utilizzeremo si chiama Heap Sort; idealmente l'array viene visto come un albero binario dove la radice è il primo elemento e ogni nodo x ha come nodi figli i nodi di indice 2x e 2x+1.Nel primo ciclo l'algoritmo sistema l'albero in modo che ogni nodo sia di valore minore o uguale al nodo padre (quello di indice x modulo 2) così da avere alla fine l'elemento maggiore al primo posto dell'array. Questo elemento viene sostituito con l'ultimo dell'array e il procedimento si ripete con un array di dimensione diminuita di 1. Ecco il codice in VBscript:

<%@ LANGUAGE = VBscript %>
<%

sub heapfy(byref V,j,byval n)
  k=j
  if ((2*j+1)<=n) then
    if (V(2*j+1)>V(k)) then
      k=2*j+1
    end if
  end if
  if ((2*j)<=n) then
    if (V(2*j)>V(k)) then
      k=2*j
    end if
  end if
  if (k<>j) then
    t=V(j)
    V(j)=V(k)
    V(k)=t
    call heapfy(V,k,n)
  end if
end sub

sub ordina(byref V)
  n=ubound(V)
  i=n\2
  while (i>=0)
    call heapfy(V,i,n)
    i=i-1
  wend
  i=n
  while (i>=1)
    t=V(i)
    V(i)=V(0)
    V(0)=t
    call heapfy(V,0,(i-1))
    i=i-1
  wend
end sub

a=array(2,3,5,1,9,4,7,6,8,11)
Response.Write("Array iniziale:<br>")
for i=0 to ubound(a)
  Response.Write(a(i)&" ")
next

call ordina(a)

Response.Write("<br>Array ordinato:<br>")
for i=0 to ubound(a)
  Response.Write(a(i)&" ")
next
%>

Ecco la versione in Jscript:

<%@ LANGUAGE = JScript %>
<%
function heapfy(V,j,n){
  k=j;
  if ((2*j+1)<=n)
    if (V[2*j+1]>V[k])
      k=2*j+1;
    if ((2*j)<=n)
      if (V[2*j]>V[k])
        k=2*j;
  if (k!=j){
    t=V[j];
    V[j]=V[k];
    V[k]=t;
    heapfy(V,k,n);
  }
}

function ordina(V){
  n=V.length-1;
  if (n%2==0)
    x=n/2;
  else
    x=(n-1)/2;
  for (i=x;i>=0;i--){
    heapfy(V,i,n);
  }
  n=V.length-1;
  for (i=n;i>=1;i--){
    t=V[i];
    V[i]=V[0];
    V[0]=t;
    heapfy(V,0,(i-1));
  }
}

var a=new Array(2,3,5,1,9,4,7,6,8,12,11);
Response.Write("Array iniziale:<br>");
for (i=0;i<a.length;i++)
{
  Response.Write(a[i]+" ");
}

ordina(a);

Response.Write("<br>Array ordinato:<br>");
for (i=0;i<a.length;i++)
{
  Response.Write(a[i]+" ");
}
%>




Utenti connessi: 3861