Ordinare un array (2) - ASPCode.it - ASP

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: ")
for i=0 to ubound(a)
 Response.Write(a(i)&" ")
next

call ordina(a)

Response.Write(" Array ordinato: ")
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: ");
for (i=0;i<a.length;i++)
{
 Response.Write(a[i]+" ");
}

ordina(a);

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

Vota questo articolo >>

AspIn.com

Utilità

Segnala questa pagina ad un amico

Versione stampabile di questa pagina

Link

software ecommerce


	Utenti connessi: 192		Home \| Forum \| Tutorials \| Articoli \| Tips&Tricks \| Scripts \| Store \| Hosting \| E-Corsi \| Libri