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. Por 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 halla 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();
?>
Búsqueda
La búsqueda es una operación que tiene por
objeto la localización de un elemento dentro de la estructura de datos. A
menudo un programador estará trabajando con grandes cantidades de datos
almacenados en arreglos y pudiera resultar necesario determinar si un arreglo
contiene un valor que coincide con algún valor clave o buscado.
Siendo el array de una
dimensión o lista una estructura de acceso directo y a su vez de acceso
secuencial, encontramos dos técnicas que utilizan estos dos métodos de acceso,
para encontrar elementos dentro de un array: búsqueda lineal y búsqueda
binaria.
Búsqueda Secuencial.
La búsqueda secuencial es la técnica más
simple para buscar un elemento en un arreglo. Consiste en recorrer el arreglo
elemento a elemento e ir comparando con el valor buscado (clave). Se empieza
con la primera casilla del arreglo y se observa una casilla tras otra hasta que
se encuentra el elemento buscado o se han visto todas las casillas. El
resultado de la búsqueda es un solo valor, y será la posición del elemento
buscado o cero. Dado que el arreglo no está en ningún orden en particular,
existe la misma probabilidad de que el valor se encuentra ya sea en el primer
elemento, como en el último. Por lo tanto, en promedio, el programa tendrá que
comparar el valor buscado con la mitad de los elementos del arreglo.
El método de búsqueda lineal
funciona bien con arreglos pequeños o para arreglos no ordenados. Si el arreglo
está ordenado, se puede utilizar la técnica de alta velocidad de búsqueda
binaria, donde se reduce sucesivamente la operación eliminando repetidas veces
la mitad de la lista restante.
Búsqueda Binaria.
La búsqueda binaria es el método más
eficiente para encontrar elementos en un arreglo ordenado. 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.
<?php
/* Busqueda secuencial en un arreglo ordenado */
include "funsionbuscar.php";
$a =array(2,4,5,8,10,14,18,21,7,68,45,24);
// $valor es el elemento a buscar
// $n posicion del valor encontrado
$n = -1;
$valor = 14;
$long = sizeof($a);
$b= buscar ($a,$n,$valor,$long);
?>
<?php
/* funcion buscar
*/
function buscar ($a,$n,$valor,$long) {
for ($i=0;$i <= $long -1;$i++) {
if ($valor == $a[$i]){
$n = $i;
$i = $long;
}
}
if ($n > -1) {
echo "El valor $valor ha sido encontrado en la posicion $n";
} else {
echo "El valor $valor no ha sido encontrado";
}
}
?>
Buen aporte estaba buscado algo básico para practicar algunas cosas y esto me cae del cielo
ResponderEliminar:v tu quicksort esta mal hecho !!! revisalo
ResponderEliminarMuy buenos ejemplos pero el ultimo da un error
ResponderEliminar