jueves, 7 de junio de 2012

Ordenamiento y Busqueda

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;
    }


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 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();
?>
 
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.

No hay comentarios:

Publicar un comentario