MÉTODOS DE ORDENAMIENTO
ORDENAMIENTO DE BURBUJA
La Ordenación de burbuja (Bubble
Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando
cada elemento de la lista que va a ser ordenada con el siguiente,
intercambiándolos de posición si están en el orden equivocado. Es necesario
revisar varias veces toda la lista hasta que no se necesiten más intercambios,
lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre
de la forma con la que suben por la lista los elementos durante los
intercambios, como si fueran pequeñas "burbujas". También es conocido
como el método del intercambio directo. Dado que solo usa comparaciones para
operar elementos, se lo considera un algoritmo de comparación, siendo el más
sencillo de implementar.
Éste algoritmo es esencialmente
un algoritmo de fuerza bruta lógica.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
<?php
function burbuja($A,$n)
{
for($i=1;$i<$n;$i++)
{
for($j=0;$j<$n-$i;$j++)
{
if($A[$j]>$A[$j+1])
{$k=$A[$j+1];
$A[$j+1]=$A[$j]; $A[$j]=$k;}
}
}
return $A;
}
function main()
{
$VectorA=array(5,4,3,2,1);
$VectorB=burbuja($VectorA,sizeof($VectorA));
for($i=0;$i<sizeof($VectorB);$i++)
echo $VectorB[$i]."\n";
}
main();
?>
|
El ordenamiento Shell
El ordenamiento Shell (Shell sort
en inglés) es un algoritmo de ordenamiento. El método se denomina Shell en
honor de su inventor Donald Shell. Su implementación original, requiere O(n2)
comparaciones e intercambios en el peor caso. Un cambio menor presentado en el
libro de V. Pratt produce una implementación con un rendimiento de O(n log2 n)
en el peor caso. Esto es mejor que las O(n2) comparaciones requeridas por
algoritmos simples pero peor que el óptimo O(n log n). Aunque es fácil
desarrollar un sentido intuitivo de cómo funciona este algoritmo, es muy
difícil analizar su tiempo de ejecución.
El Shell sort es una
generalización del ordenamiento por inserción, teniendo en cuenta dos
observaciones:
El ordenamiento por inserción es
eficiente si la entrada está "casi ordenada".
El ordenamiento por inserción es
ineficiente, en general, porque mueve los valores sólo una posición cada vez.
El algoritmo Shell sort mejora el
ordenamiento por inserción comparando elementos separados por un espacio de
varias posiciones. Esto permite que un elemento haga "pasos más
grandes" hacia su posición esperada. Los pasos múltiples sobre los datos
se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell
sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado
que los datos del vector están casi ordenados.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
<?php
function ordenamientoShell($A,$n)
{
for($inc = 1 ;
$inc<$n;$inc=$inc*3+1);
while ($inc > 0)
{
for ($i=$inc; $i < $n; $i++)
{
$j = $i;
$temp = $A[$i];
while (($j >= $inc)
&& ($A[$j-$inc] > $temp))
{
$A[$j]
= $A[$j -
$inc];
$j = $j - $inc;
}
$A[$j]
= $temp;
}
$inc/=
2;
}
return $A;
}
function main()
{
$VectorA=array(5,4,3,2,1);
$VectorB=ordenamientoShell($VectorA,sizeof($VectorA));
for($i=0;$i<sizeof($VectorB);$i++)
echo $VectorB[$i]."\n";
}
main();
?>
|
Quicksort en acción sobre una
lista de números aleatorios. Las líneas horizontales son valores pivote.
El ordenamiento rápido (quicksort
en inglés) es un algoritmo creado por el científico británico en computación C.
A. R. Hoare basado en la técnica de divide y vencerás, que permite, en
promedio, ordenar n elementos en un tiempo proporcional a n log n.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
<?php
function quicksort($A,
$izq, $der )
{
$i =
$izq;
$j =
$der;
$x =
$A[ ($izq + $der) /2 ];
do{
while(
($A[$i] < $x) && ($j <= $der) )
{
$i++;
}
while(
($x < $A[$j]) && ($j >
$izq) )
{
$j--;
}
if(
$i <= $j )
{
$aux =
$A[$i]; $A[$i] = $A[$j]; $A[$j] = $aux;
$i++;
$j--;
}
}while(
$i <= $j );
if(
$izq < $j )
quicksort(
$A, $izq, $j );
if(
$i < $der )
quicksort(
$A, $i, $der );
return $A;
}
function main()
{
$VectorA=array(5,4,3,2,1);
$VectorB=quicksort($VectorA,0,sizeof($VectorA)-1);
for($i=0;$i<sizeof($VectorB);$i++)
echo $VectorB[$i]."\n";
}
main();
?>
|
Ordenamiento por inserción
El ordenamiento por inserción
(insertion sort en inglés) es una manera muy natural de ordenar para un ser
humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en
forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n
elementos.
Inicialmente se tiene un solo elemento,
que obviamente es un conjunto ordenado. Después, cuando hay k elementos
ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los
elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor
(todos los elementos mayores han sido desplazados una posición a la derecha) o
cuando ya no se encuentran elementos (todos los elementos fueron desplazados y
este es el más pequeño). En este punto se inserta el elemento k+1 debiendo
desplazarse los demás elementos.
<?php
function insercionDirecta($A,$n)
{
for ($i = 1; $i < $n; $i++)
{
$v = $A[$i];
$j = $i - 1;
while ($j >= 0 &&
$A[$j] > $v)
{
$A[$j + 1] = $A[$j];
$j--;
}
$A[$j + 1] = $v;
}
return $A;
}
function main()
{
$VectorA=array(5,4,3,2,1);
$VectorB=insercionDirecta($VectorA,sizeof($VectorA));
for($i=0;$i<sizeof($VectorB);$i++)
echo $VectorB[$i]."\n";
}
main();
?>
Ordenamiento por inserción Binaria
<?php
function insercionBinaria($A,$n)
{
for($i=1;$i<$n;$i++)
{
$aux = $A[$i];
$izq=0;
$der=$i-1;
while($izq<=$der)
{
$m=(($izq+$der)/2);
if ($aux<$A[$m])
$der=$m-1;
else
$izq=$m+1;
}
$j=$i-1;
while($j>=$izq)
{
$A[$j+1]=$A[$j];
$j=$j-1;
}
$A[$izq]=$aux;
}
return $A;
}
function main()
{
$VectorA=array(5,4,3,2,1);
$VectorB=insercionBinaria($VectorA,sizeof($VectorA));
for($i=0;$i<sizeof($VectorB);$i++)
echo $VectorB[$i]."\n";
}
main();
?>
Ordenamiento por selección
El ordenamiento por selección (Selection Sort en inglés) es
un algoritmo de ordenamiento que requiere O(n^2) operaciones para ordenar una
lista de n elementos.
Su funcionamiento es el siguiente:
Buscar el mínimo elemento de la lista
Intercambiarlo con el primero
Buscar el siguiente mínimo en el resto de la lista
Intercambiarlo con el segundo
Y en general:
Buscar el mínimo elemento entre una posición i y el final de
la lista
Intercambiar el mínimo con el elemento de la posición i.
<?php
function selectionsort($A,$n)
{
for ($i=0; $i<$n-1; $i++)
{
$min=$i;
for($j=$i+1;
$j<$n; $j++)
if($A[$min]
> $A[$j])
$min=$j;
$aux=$A[$min];
$A[$min]=$A[$i];
$A[$i]=$aux ;
}
return $A;
}
function main()
{
$VectorA=array(5,4,3,2,1);
$VectorB=selectionsort($VectorA,sizeof($VectorA));
for($i=0;$i<sizeof($VectorB);$i++)
echo $VectorB[$i]."\n";
}
main();
?>
Heapsort
El ordenamiento por montículos
(heapsort en inglés) es un algoritmo de ordenamiento no recursivo, no estable,
con complejidad computacional \Theta(n\log n)
Este algoritmo consiste en
almacenar todos los elementos del vector a ordenar en un montículo (heap), y
luego extraer el nodo que queda como nodo raíz del montículo (cima) en
sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento
en una propiedad de los montículos, por la cual, la cima contiene siempre el
menor elemento (o el mayor, según se haya definido el montículo) de todos los
almacenados en él.
<?php
function heapsort($A,$n)
{
for($k=$n-1;$k>=0;$k--)
{
for($i=1;$i<=$k;$i++)
{
$item=$A[$i];
$j=$i/2;
while($j>0
&& $A[$j]<$item)
{
$A[$i]=$A[$j];
$i=$j;
$j=$j/2;
}
$A[$i]=$item;
}
$temp=$A[0];
$A[0]=$A[$k];
$A[$k]=$temp;
}
return $A;
}
function main()
{
$VectorA=array(5,4,3,2,1);
$VectorB=heapsort($VectorA,sizeof($VectorA));
for($i=0;$i<sizeof($VectorB);$i++)
echo $VectorB[$i]."\n";
}
main();
?>
BIOGRAFIAS
http://saforas.wordpress.com/2011/01/14/metodos-de-ordenamiento-hechos-en-php/
http://saforas.wordpress.com/2011/01/14/metodos-de-ordenamiento-hechos-en-php/
