ALGORITMOS DE ORDENACIÓN

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.

Ordenamiento de burbuja

El primer ordenamiento que presentamos es quizá el más ampliamente conocido entre los estudiantes que se inician en la programación. Una de las características de este ordenamiento es que es fácil de entender y programar. Aunque, es uno de los algoritmos mas ineficiente.

La idea básica subyacente en el ordenamiento de burbuja es pasar a través del arreglo de datos varias veces en forma secuencial. Cada paso consiste en la comparación de cada elemento en el arreglo con su sucesor (x[i] con  x[i+1]) y el intercambio de los dos elementos si no están en el orden correcto. Considérese el siguiente arreglo de datos:

25 57 48 37 12 92 86 33

En el primer paso se realizan las siguientes operaciones:

x[0] con x[1] (25 con 57)  no intercambio.

x[1] con x[2] (57 con 48)      intercambio.

x[2] con x[3] (57 con 32)      intercambio.

x[3] con x[4] (57 con 12)      intercambio.

x[4] con x[5] (57 con 92)  no intercambio.

x[5] con x[6] (92 con 86)      intercambio.

x[6] con x[7] (92 con 33)      intercambio.

Así después del primer paso, el arreglo está en el siguiente orden:

25 48 37 12 57 86 33 92

Obsérvese que después del primer paso, el elemento mayor (en este caso 92) está en la posición correcta dentro del arreglo. En general x[n-i] estará en su posición correcta después de la iteración i. El método se lama ordenamiento de burbuja porque cada número “burbujea” con lentitud hacia su posición correcta. El conjunto completo de iteraciones es:

iteración 0 :                     25 57 48 37 12 92 86 33

iteración 1:                       25 48 37 12 57 86 33 92

iteración 2:                       25 37 12 48 57 33 86 92

iteración 3:                       25 12 37 48 33 57 86 92

iteración 4:                       12 25 37 33 48 57 89 92

iteración 5:                       12 25 33 37 48 57 89 92

La implementación de este algoritmo en Java queda como:

   void Burbuja(int x[], int n)

  {

    int b, j, t;

    do

    {

      b = 0;

      for(j=0; j<n; j++)

      {

         if(x[j] > x[j+1])

         {

           t = x[j];

           x[j] = x[j+1];

           x[j+1] = t;

           b++;

         }

      }

      n--;

    }

    while(b > 0);

  }

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 siguiente:
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

Ordenamiento "Shell Sort".

1. Shell Sort
2. Pedirle a un ordenador que haga algo intuitivamente es, de momento, bastante complicado, así que sustituiremos la intuición por un procedimiento mecánico más o menos ingenioso. Veamos el siguiente arreglo:
3. 74, 14, 21, 44, 38, 97, 11, 78, 65, 88, 30
4. Shell nos propone que hagamos sobre el arreglo una serie de ordenaciones basadas en la inserción directa, pero dividiendo el arreglo original en varios sub-arreglo tales que cada elemento esté separado k elementos del anterior (a esta separación a menudo se le llama salto o gap )... Se debe empezar con k=n/2 , siendo n el número de elementos de arreglo, y utilizando siempre la división entera.... después iremos variando k haciéndolo más pequeño mediante sucesivas divisiones por 2, hasta llegar a k=1. Pero vamos a ello... En nuestro ejemplo, n=11 (porque hay 11 elementos). Así que k=n/2=11/2=5
5. Empezamos con k=5. Así pues, vamos a dividir nuestro arreglo original en 5 sub-arreglo, en los cuales, sus elementos estarán separados por 5 lugares del arreglo original (el salto o gap es 5). Vamos a hacerlo con colores. Tomamos el primer elemento (el 74) contamos 5 lugares y tomamos también otro elemento (el 97) volvemos a contar 5 y tomamos otro (el 30) y acabamos porque se nos acaba el arreglo. El primer sub-arreglo con k=5 es el formado por 74, 97 y 30. Vamos a pintarlos en rojo
6. 74 , 14, 21, 44, 38, 97 , 11, 78, 65, 88, 30
7. Ahora, ordenaremos los elementos del sub-arreglo rojo pero sólo entre ellos, utilizando el algoritmo de Inserción directa.   30 , 14, 21, 44, 38, 74 , 11, 78, 65, 88, 97   Fíjate qué curioso. El 30, un elemento relativamente pequeño se ha ido hacia el principio y el 97 hacia el final... ¡pero dando saltos ( gap ) de 5 en 5 lugares! Cada uno ha avanzado en saltos de 5 hacia una posición cercana a su ubicación definitiva.
8. Fíjate qué curioso. El 30, un elemento relativamente pequeño se ha ido hacia el principio y el 97 hacia el final... ¡pero dando saltos ( gap ) de 5 en 5 lugares! Cada uno ha avanzado en saltos de 5 hacia una posición cercana a su ubicación definitiva. Formemos ahora otro sub-arreglo con salto k=5... partiendo del segundo elemento (el 14) y contando 5 (tomamos también el 11) y ya está, porque se acaba el arreglo.   30 , 14 , 21, 44, 38, 74 , 11 , 78, 65, 88, 97
9. Vamos a ordenarlos entre ellos con Inserción directa... el 11 primero y el 14 después.   30 , 11 , 21, 44, 38, 74 , 14 , 78, 65, 88, 97
10. Ahora a por otro... el 21 y el 78     30 , 11 , 21 , 44, 38, 74 , 14 , 78 , 65, 88, 97   Están en orden entre ellos, así que se quedan como están.
11. Ahora le toca al sub-arreglo formado por el 44 y el 65    30 , 11 , 21 , 44 , 38, 74 , 14 , 78 , 65 , 88, 97   Que también están en orden entre ellos... y finalmente el 38 y el 88, que también están en orden. 30 , 11 , 21 , 44 , 38 , 74 , 14 , 78 , 65 , 88 , 97
12. Hemos formado 5 sub-arreglos en los cuales los elementos están separados por 5 lugares (porque k=5). Hemos ordenado cada sub-arreglo por separado utilizando inserción directa, y hemos logrado que cada elemento se dirija hacia su ubicación definitiva en pasos de 5 lugares. Por supuesto, no hemos terminado todavía, pero resulta evidente que algunos elementos, como el 30, el 97 o el 11 han dado un gran salto y que no deben andar muy lejos de su sitio final.
13. Decimos ahora que el arreglo está 5-ordenado.   Para continuar con el algoritmo, debemos ir reduciendo progresivamente k dividiéndolo sucesivamente por 2 y k-ordenando los sub-arreglos que nos salgan (recuerda que nos salen k sub-arreglo). Cuando lleguemos a k=1 habremos terminado.   Pero de momento, nuestra k valía 5, así que ahora k←k/2=5/2=2   Nuestra nueva k vale 2. Repetimos todo el tinglado, pero ahora nos saldrán 2 sub-arreglo cuyos elementos están separados por 2 lugares.
14. El primero (en marrón) y el segundo (en verde): 30 , 11 , 21 , 44 , 38 , 74 , 14 , 78 , 65 , 88 , 97
15. Ordenamos por un lado los marrones entre ellos y los verdes entre ellos... es decir, 2-ordenamos el arreglo (curiosamente, los verdes ya están ordenados.... probablemente ha contribuido a ello la 5-ordenación que ya hemos hecho. En ese caso, la ordenación ha requerido muy poco esfuerzo)   14 , 11 , 21 , 44 , 30 , 74 , 38 , 78 , 65 , 88, 97
16. Ahora, cada número está mucho más cerca de su posición definitiva... El arreglo está 2-ordenado... pero sigue también 5-ordenado. No hemos perdido el trabajo que hicimos cuando k era 5.   Finalmente, calculamos un nuevo k dividiendo el que tenemos entre 2. k←k/2=2/2=1 Hemos llegado a k=1. Cuando k es 1 sólo podemos obtener 1 sub-arreglo cuyos elementos están separados 1 posición: el propio arreglo original. Dicho de otra manera... cuando k es 1, el algoritmo de Shell se comporta exactamente igual que el de inserción directa sobre todo el arreglo .
17. Sin embargo, las k-ordenaciones que hemos hecho (con k=5 y k=2) han hecho que cada elemento se aproximase con saltos de 5 y luego de 2 posiciones hacia su ubicación definitiva. Ahora que k=1 y que vamos a aplicar el algoritmo de inserción directa tal cual, haremos muchas menos comparaciones e intercambios que si lo hubiéramos aplicado con en arreglo tal como lo teníamos al empezar. El algoritmo de inserción directa se comporta tanto mejor cuanto más cerca está cada elemento de su sitio definitivo.   Finalmente, el arreglo queda de ésta manera:   11, 14, 21, 30, 38, 44, 65, 74, 78, 88, 97   Cada elemento descolocado ha tenido que moverse pocos lugares. Muchos de ellos ni siquiera se han movido.

Busqueda



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.

Busqueda Hash

Hasta ahora las técnicas de localización de registros vistas, emplean un proceso de búsqueda que implica cierto tiempo y esfuerzo. El siguiente método nos permite encontrar directamente el registro buscado.

 

    La idea básica de este método consiste en aplicar una función que traduce un conjunto de posibles valores llave en un rango de direcciones relativas. Un problema potencial encontrado en este proceso, es que tal función no puede ser uno a uno; las direcciones calculadas pueden no ser todas únicas, cuando R(k₁ )= R(k₂)

Pero : K₁ diferente de K₂ decimos que hay una colisión. A dos llaves diferentes que les corresponda la misma dirección relativa se les llama sinónimos.

 

A las técnicas de calculo de direcciones también se les conoce como :

·         Técnicas de almacenamiento disperso

·         Técnicas aleatorias

·         Métodos de transformación de llave - a- dirección

·         Técnicas de direccionamiento directo

·         Métodos de tabla Hash

·         Métodos de Hashing

    Pero el término mas usado es el de hashing. Al cálculo que se realiza para obtener una dirección a partir de una llave se le conoce como función hash.

 

 

Ventaja

1.      Se pueden usar los valores naturales de la llave, puesto que se traducen internamente a direcciones fáciles de localizar

2.      Se logra independencia lógica y física, debido a que los valores de las llaves son independientes del espacio de direcciones

3.      No se requiere almacenamiento adicional para los índices.

Desventajas

1.      No pueden usarse registros de longitud variable

2.      El archivo no esta clasificado

3.      No permite llaves repetidas

4.      Solo permite acceso por una sola llave

Costos

·         Tiempo de procesamiento requerido para la aplicación de la función hash

·         Tiempo de procesamiento y los accesos E/S requeridos para solucionar las colisiones.

La eficiencia de una función hash depende de:

1.      La distribución de los valores de llave que realmente se usan

2.      El numero de valores de llave que realmente están en uso con respecto al tamaño del espacio de direcciones

3.      El numero de registros que pueden almacenarse en una dirección dad sin causar una colisión

4.      La técnica usada para resolver el problema de las colisiones

Las funciones hash mas comunes son:

·         Residuo de la división

·         Medio del cuadrado

·         Pliegue