ORDENAMIENTO
Uno
de los procedimientos más comunes y útiles en el procesamiento de datos, es la
clasificación u ordenación de los mismos. Se considera ordenar al proceso de
reorganizar un conjunto dado de objetos en una secuencia determinada. Cuando se
analiza un método de ordenación, hay que determinar cuántas comparaciones e
intercambios se realizan para el caso más favorable, para el caso medio y para
el caso más desfavorable.
La colocación en orden de una lista de valores se
llama Ordenación.
Ejemplo:
Se podría disponer una lista de valores numéricos
en orden ascendente o descendente, o bien una lista de nombres en orden
alfabético. La localización de un elemento de una lista se llama búsqueda.
Tipos De
Métodos De Ordenamiento
Ordenamiento
Por El Método De La Burbuja.
Este método consiste en acomodar el vector moviendo el mayor hasta la última
casilla comenzando desde la casilla cero del vector hasta haber acomodado el
número más grande en la última posición, una vez acomodado el más grande,
prosigue a encontrar y acomodar el siguiente más grande comparando de
nuevo los números desde el inicio del vector, y así sigue hasta ordenar todo
los elementos el arreglo. Este algoritmo es muy deficiente ya que al ir
comparando las casillas para buscar el siguiente más grande, éste vuelve a
comparar las ya ordenadas. A pesar de ser el algoritmo de ordenamiento más
deficiente que hay, éste es el más usado en todos los lenguajes de programación.
Entonces:
Dado un
vector a1, a2, a3,... an.
1)
Comparar a1 con a2 e intercambiarlos si a1>a2 (o a12)
2) Seguir
hasta que todo se haya comparado an-1 con an
3)
Repetir el proceso anterior n-1 veces
Algoritmo
for(i=0; i < n-1; i++){
for(j=0; j < n-1;
j++){
if(vec[j] >
vec[j+1]){
aux=vec[j];
vec[j]=vec[j+1];
vec[j+1]=aux;}
}
}
El procedimiento de la burbuja
es el siguiente:
Ir
comparando desde la casilla 0 numero tras número hasta encontrar uno mayor, si
este es realmente el mayor de todo el vector se llevará hasta la última
casilla, si no es así, será reemplazado por uno mayor que él.
Este procedimiento seguirá así hasta que haya
ordenado todas las casillas del vector.
Una de
las deficiencias del algoritmo es que ya cuando a ordenado parte del vector
vuelve a compararlo cuando esto ya no es necesario.
Ejemplo:
El código realiza un Ordenamiento de datos
numéricos haciendo uso del Método de la Burbuja:
<?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();
?>
Método De
Ordenamiento SHELL.
El
método Shell pertenece a los métodos de clasificación avanzados, nombrado así
en honor a su desarrollador, Donald Shell.
Este
método utiliza una segmentación entre los datos. Funciona comparando elementos
que estén distantes; la distancia entre comparaciones decrece conforme el
algoritmo se ejecuta hasta la última fase, en la cual se comparan los elementos
adyacentes, por esta razón se le llama ordenación por disminución de
incrementos.
La
ordenación de Shell usa una secuencia, h1, h2,. . ., ht, conocida como la
secuencia de incrementos. Al principio de todo proceso, se fija una secuencia
decreciente de incrementos. Cualquier secuencia funcionará en tanto que empiece
con un incremento grande, pero menor al tamaño del arreglo de los datos a
ordenar, y que el último valor de dicha secuencia sea 1.
Ejemplo:
Se desean
ordenarse las siguientes claves del arreglo
A: 15,
67, 08, 16, 44, 27, 12, 35, 56, 21, 13, 28, 60, 36, 07, 10
Primera
Pasada
Los
elementos se dividen en 8 grupos:
A: 15,
67, 08, 16, 44, 27, 12, 35 | 56, 21, 13, 28, 60, 36, 07, 10
La
ordenación produce:
A: 15,
21, 08, 16, 44, 27, 07, 10, 56, 67, 13, 28, 60, 36, 12, 35
Segunda
Pasada
Se
dividen los elementos en 4 grupos:
A: 15,
21, 08, 16 | 44, 27, 07, 10 | 56, 67, 13, 28 | 60, 36, 12, 35
La
ordenación produce:
A: 15,
21, 07, 10, 44, 27, 08, 16, 56, 36, 12, 28, 60, 67, 13, 35
Tercera
Pasada
Se divide
los elementos 2 grupos
A: 15, 21
| 07, 10 | 44, 27 | 08, 16 | 56, 36 | 12, 28 | 60, 67 | 13, 35
La
ordenación produce:
A = 07,
10, 08, 16, 12, 21, 13, 27, 15, 28, 44, 35, 56, 36, 60, 67
Cuarta
Pasada
Divida
los elementos en un solo grupo.
La
ordenación produce:
A: 07,
08, 10, 12, 13, 15, 16, 21, 27, 28, 35, 36, 44, 56, 60, 67
El código
realiza un Ordenamiento de datos numéricos haciendo uso del Método Shell:
<?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();
?>
Método De
Ordenamiento QUICKSORT.
El método de ordenamiento Quick Sort es actualmente el más eficiente y veloz de
los métodos de ordenación interna. Es también conocido con el nombre del método
rápido y de ordenamiento por partición, en el mundo de habla hispana.
Este
método es una mejora sustancial del método de intercambio directo y recibe el
nombre de Quick Sort por la velocidad con que ordena los elementos del arreglo.
Su autor C.A. Hoare lo bautizó así.
La idea
central de este algoritmo consiste en los siguientes:
Se toma
un elemento x de una posición cualquiera del arreglo.
Se trata
de ubicar a x en la posición correcta del arreglo, de tal forma que todos los
elementos que se encuentran a su izquierda sean menores o iguales a x y todos
los elementos que se encuentren a su derecha sean mayores o iguales a x.
Se repiten
los pasos anteriores pero ahora para los conjuntos de datos que se encuentran a
la izquierda y a la derecha de la posición correcta de x en el arreglo.
Ejemplo:
A:
15,67,08,16,44,27,12,35
Se
selecciona A[i] x=15
Primera
pasada (DER-IZQ)
A[8]
>= x 35 >= 15 No hay intercambio
A[7]
>= x 12 >= 15 Si hay intercambio
A:
12,67,08,16,44,27,15,35
(IZQ-DER)
A[2] <
= X 67 < = 15 Si hay intercambio
A:12,15,08,16,44,27,67,35
2da.
Pasada (DER-IZQ)
A[6]
>= x 27 >= 15 No hay intercambio
A[5]
>= x 44 >= 15 No hay intercambio
A[4]
>= x 16 >= 15 No hay intercambio
A[3]
>= x 08 >= 15 Si hay intercambio
A:
12,08,15,16,44,27,67,35
Como el
recorrido de izquierda a derecha debería iniciarse en la misma posición
donde se
encuentra el elemento x, el proceso se termina ya que el elemento x, se
encuentra
en la posición correcta.
A: 12,
08, 15, 16, 44, 27, 67, 35
1er 2do
Conjunto
Conjunto
16, 44,
27, 67, 35
x16
(DER-IZQ)
A[8]>=x
No hay intercambio
A[7]>=x
No hay intercambio
A[6]>=x
No hay intercambio
A[5]>=x
No hay intercambio
A: 12,
08, 15, 16, 44, 27, 67, 35
xß44
(DER-IZQ)
A[8]>=
x Si hay intercambio
A: 12,
08, 15, 16, 35, 27, 67, 44
(IZQ-DER)
A[6] <
= x No hay intercambio
A[7] <
= x Si hay intercambio
12, 08,
15, 16, 35, 27, 44, 67
12, 08,
15, 16, 35, 27, 44, 67
35, 27,
44, 67
xß35
(DER-IZQ)
A[8]
>= x No hay intercambio
A[7]
>= x No hay intercambio
A[6]
>= x Si hay intercambio
12, 08,
15, 16, 27, 35, 44, 67
12,08
xß12
(DER-IZQ)
A[2]>=x
Si hay intercambio
EL VECTOR
ORDENADO:
08,12,15,16,27,35,44,67
El código
realiza un Ordenamiento de datos numéricos haciendo uso del Método Quicksort:
<?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();
?>
Método De
Ordenamiento Inserción Directa.
El método de inserción directa
es el que generalmente utilizan los jugadores de cartas cuando ordenan éstas,
de ahí que también se conozca con el nombre de método de la baraja.
La idea
central de este algoritmo consiste en insertar un elemento del arreglo en la
parte izquierda del mismo, que ya se encuentra ordenada. Este proceso se repite
desde el segundo hasta el n-esimo elemento.
Ejemplo:
Se desean ordenarse las siguientes claves del
arreglo A: 15, 67, 08, 16, 44, 27, 12, 35
Primera
pasada
A[2] <
A[1] 67 < 15 No hay intercambio
A: 15,
67, 08, 16, 44, 27, 12, 35
Segunda
pasada
A[3] <
A[2] 08 < 67 Si hay intercambio
A[2] <
A[1] 08 < 15 Si hay
A: 15,
08, 67, 16, 44, 27, 12, 35
Tercera
pasada
A[4] <
A[3] 08 < 15 Si hay intercambio
A[3] <
A[2] 08 < 15 Si hay intercambio
A= 08,
15, 67, 16, 44, 27, 12, 35
Hasta la
séptima pasada el arreglo queda ordenado: 08, 12, 15, 16, 27, 35, 44, 67
El código
realiza un Ordenamiento de datos numéricos haciendo uso del Método de Inserción
Directa:
<?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 Método De Inserción Binaria.
El algoritmo de inserción directa se mejora fácilmente al notar que la
secuencia destino aj..ai-1, donde debe insertarse el nuevo elemento, ya está
ordenada. Por eso puede ser empleado un método más rápido para determinar el
punto de inserción. La elección obvia es una búsqueda binaria que prueba la
secuencia destino en la mitad y continúa buscando hasta encontrar el punto de
inserción. El algoritmo de clasificación modificado recibe el nombre de
inserción binaria.
Características
1.- La secuencia destino donde debe
insertarse el nuevo elemento ya esta ordenada.
2.-Búsqueda Binaria para localizar el
lugar de inserción.
3.-Desplazar elementos.
4.-Insertar. Análisis: Al realizar la
búsqueda binaria se divide una longitud L por la mitad un número determinado de
veces.
Algoritmo:
para
(i=2 hasta N)
{
aux =
A[i];
izq=1;
der=i-1;
mientras
(izq<=der)
{
m=[parte
entera ((izq+der)/2)];
si
(aux<A[m])
{
der=m-1;
}
si no
{
izq=m+1;
}
}
j=i-1;
mientras
(j>=izq)
{
A[j+1]=A[j];
j=j-11;
}
A[izq]=auz;
}
Procedimiento:
El proceso comienza comparando el elemento central del arreglo con el valor
buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento
buscado será mayor o menor en sentido estricto que el central del arreglo. Si el
elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray
superior, si el elemento buscado es menor que el contenido de la casilla
central, se debe cambiar el segmento a considerar al segmento que está a la
izquierda de tal sitio central.
El código
realiza un Ordenamiento de datos numéricos haciendo uso del Método de 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();
?>
Método De
Selección.
El método de ordenamiento por selección consiste en encontrar el menor de todos
los elementos del arreglo e intercambiarlo con el que está en la primera
posición. Luego el segundo más pequeño, y así sucesivamente hasta ordenar todo
el arreglo.
Procedimiento
Selection Sort.
Paso 1:
[Para cada pos. del arreglo] For i <- 1
to N do
Paso 2:
[Inicializa la pos. del menor] menor <- i
Paso 3:
[Recorre todo el arreglo] For j <- i+1 to N do
Paso 4:
[Si a[j] es menor] If a[j] < a[menor] then
Paso 5:
[Reasigna el apuntador al menor] min
= j
Paso 6:
[Intercambia los datos de la pos.
Min y
posición i] Swap(a, min, j).
Paso 7:
[Fin] End.
Ejemplo:
El
arreglo a ordenar es a =
['a','s','o','r','t','i','n','g','e','x','a','m','p','l','e'].
Se
empieza por recorrer el arreglo hasta encontrar el menor elemento. En este caso
el menor elemento es la primera 'a'. De manera que no ocurre ningún cambio.
Luego se procede a buscar el siguiente elemento y se encuentra la segunda 'a'.
Esta se intercambia con el dato que está en la
segunda posición, la 's', quedando el arreglo así después de dos recorridos: a
= ['a','a','o','r','t','i','n','g','e','x','s','m','p','l','e'].
El siguiente elemento, el tercero en orden de menor
mayor es la primera 'e', la cual se intercambia con lo que está en la tercera
posición, o sea, la 'o'. Le sigue la segunda 's', la cual es intercambiada con
la 'r'.
El arreglo ahora se ve de la siguiente manera: a =
['a','a','e','e','t','i','n','g','o','x','s','m','p','l','r'].
De esta manera se va buscando el elemento que debe
ir en la siguiente posición hasta ordenar todo el arreglo.
El número
de comparaciones que realiza este algoritmo es :
Para el primer elemento se comparan n-1 datos, en
general para el elemento i-ésimo se hacen n-i comparaciones, por lo tanto, el
total de comparaciones es:
la sumatoria para i de 1 a n-1 (n-i) = 1/2 n (n-1).
El código realiza un Ordenamiento de datos
numéricos haciendo uso del Método de Selección:
<?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();
?>
Método De
HEAPSORT.
El ordenamiento por heapsort es
un algoritmo de ordenación no recursivo, no estable, con complejidad
computacional.
El Heapsort está basado en el uso de un tipo
especial de árbol binario (llamado apilamiento) para estructurar el proceso de
ordenamiento. La estructura de ramificación del árbol conserva el número de
comparaciones necesarias en O(n log n).
Características:
Las llaves están acomodadas en
los nodos de tal manera que, para cada nodo i, Ki <= Kj donde el nodo j es
el padre del nodo i. Es decir, al recorrer el camino desde la raíz hacia abajo,
las claves se encuentran en orden descendente.
El árbol se llena de izquierda a derecha, lo
que implica que si algún(os) nodo(s) no está(n) en el mismo nivel que el resto,
éste(os) estará(n) entonces lo más a la izquierda posible del árbol.
Pasos de
Heap:
1º. Saca el valor máximo del Heap. (El de la
posición 1).
2º. Pone el valor sacado en el arreglo ordenado.
3º. Reconstruir el Heap con un elemento menos.
El código
realiza un Ordenamiento de datos numéricos haciendo uso del Método Heapsort:
<?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();
?>
http://apontejuanunefa.blogspot.com/2012/06/ordenamiento-y-busqueda.html
