Unidad V Y VI MÉTODOS DE ORDENAMIENTO Y DE BÚSQUEDA.

                                  MÉTODOS DE ORDENAMIENTO. 

Es la operación de arreglar los registros de una tabla en algún orden secuencial de acuerdo a un criterio de ordenamiento. El ordenamiento se efectúa con base en el valor de algún campo en un registro.

El propósito principal de un ordenamiento es el de facilitar las búsquedas de los miembros del conjunto ordenado.

Ej. De ordenamientos: 

Dir. Telefónico, tablas de contenido, bibliotecas y diccionarios, etc.

El ordenar un grupo de datos significa mover los datos o sus referencias para que queden en una secuencia tal que represente un orden, el cual puede ser numérico, alfabético o incluso alfanumérico, ascendente o descendente. 

¿Cuándo conviene usar un método de ordenamiento? 

Cuando se requiere hacer una cantidad considerable de búsquedas y es importante el factor tiempo. 

Tipos de ordenamientos:

Los 2 tipos de ordenamientos que se pueden realizar son:

ü  Los internos: 

Son aquellos en los que los valores a ordenar están en memoria principal, por lo que se asume que el tiempo que se requiere para acceder cualquier elemento sea el mismo (a[1], a[500], etc). 

ü  Los externos: 

Son aquellos en los que los valores a ordenar están en memoria secundaria (disco, cinta, cilindro magnético, etc), por lo que se asume que el tiempo que se requiere para acceder a cualquier elemento depende de la última posición accesada (posición 1, posición 500, etc).

MÉTODOS DE BÚSQUEDA.

La búsqueda es la operación más importante en el procesamiento de información, ya que permite recuperar datos previamente almacenados. El resultado de una búsqueda puede ser un éxito, si se encuentra la información o un fracaso, si no la encuentra.

 La búsqueda se puede aplicar sobre elementos previamente ordenados o sobre elementos desordenados, en el primer caso la búsqueda es más fácil, en cambio en el segundo se dificulta un poco más el proceso, sobre todo cuando de se trata de encontrar una cantidad de elementos similares.

Los métodos de búsqueda se clasifican en:

Búsqueda interna.

Búsqueda externa.

Búsqueda interna.

La búsqueda interna es aquella en la que todos los elementos de la estructura estática (arreglo) o dinámica (lista ligada o árbol) se encuentran almacenados en la memoria principal de la computadora.

Los métodos de búsqueda interna más importantes son:

ü  Secuencial o lineal.

ü  Binaria.

ü  Hash (transformación de claves).

Búsqueda externa.

La búsqueda externa es aquella en la que todos los elementos se encuentran almacenados en un archivo, el cual se encuentra en un dispositivo de almacenamiento secundario como un disco duro, una cinta o una memoria usb.

Los métodos de búsqueda externa más importantes son:

ü  Secuencial.

ü  Binaria.

ü  Hash (transformación de claves).

• Algoritmo Burbuja
• Algoritmo Quicksort
• Algoritmo Shellsort
• Algoritmo Radix

Algoritmo Burbuja.

El método de ordenación por intercambio directo o método de la burbuja, es el más simple y consiste en comparar dos elementos adyacentes para determinar si se realiza un intercambio entre los mismos, esto en caso de que el primero sea mayor que el segundo (forma ascendente) o el caso de que el primero sea menor que el segundo (forma descendente).

El primer procedimiento del método de la burbuja es:

ü  Generar un ciclo que inicie desde uno hasta el número de elementos del arreglo.

ü  Generar un segundo ciclo dentro del anterior que inicie desde cero hasta el número de elementos del arreglo menos dos.

Dentro del segundo ciclo debe existir una comparación que determina el tipo de ordenamiento (ascendente o descendente) entre el primer elemento (posición generado por el segundo ciclo) y el segundo elemento (el que le  sigue), si la respuesta a la condición es verdadera se realiza un intercambio entre los dos elementos.

Para realizar el intercambio se genera un almacenamiento temporal, el cual guarda el dato del primer elemento, el segundo elemento toma el lugar del primero y en el lugar del segundo se coloca lo que contiene el almacenamiento temporal. Una vez que los ciclos terminan la estructura debe quedar ordenada de forma ascendente o descendente, pero este procedimiento es considerado como el peor de los casos ya que si el número de elementos de la estructura es de 100, se tienen que realizar 9900 comparaciones entes de terminar la ejecución del método.

Un segundo procedimiento del método de la burbuja es:

ü  Generar un ciclo que inicie desde cero hasta el número de elementos menos dos.

ü  Generar un segundo ciclo desde el valor del ciclo anterior más uno hasta el número de elementos menos uno;

Dentro del segundo ciclo debe existir una comparación que determina el tipo de ordenamiento (ascendente o descendente) entre el primer elemento (posición generada por el primer ciclo) y el segundo elemento (posición generada por el segundo ciclo), si la respuesta a la condición es verdadera se realiza un intercambio entre los dos elementos.

Para realizar el intercambio se genera un almacenamiento temporal, el cual guarda el dato del primer elemento, el segundo elemento toma el lugar del primero y en el lugar del segundo se coloca lo que contiene el almacenamiento temporal.

Una vez que los ciclos terminan la estructura debe quedar ordenada, la diferencia con el procedimiento anterior radica en el número de comparaciones y posibles intercambios que se presentan, en este segundo procedimiento, es menor ya que cada pasada que se le da al arreglo se realiza una comparación menos que en la pasada anterior.

Un tercer procedimiento del método de la burbuja es el siguiente:

ü  Generar un ciclo que inicie desde uno hasta el número de elementos menos uno.

ü  Generar un segundo ciclo que inicie desde el número de elementos menos uno y mientras que ese valor sea mayor o igual al del ciclo anterior (con decrementos).

Dentro del segundo ciclo debe existir una comparación que determina el tipo de ordenamiento (ascendente o descendente) entre el primer elemento (posición generada por el segundo ciclo) y el segundo elemento (posición generada por el segundo ciclo menos uno), si la respuesta a la condición es verdadera se realiza un intercambio entre los dos elementos.

Para realizar el intercambio se genera un almacenamiento temporal, el cual guarda el dato del primer elemento, el segundo elemento toma el lugar del primero y en el lugar del segundo se coloca lo que contiene el almacenamiento temporal. Este tercer procedimiento es muy similar al anterior con la diferencia que el elemento que va quedando es su lugar el primero no el último como en el caso anterior.

Algoritmo QuickSort.

El método de ordenamiento rápido o método quicksort, es una técnica basada en otra conocida con el nombre divide y vencerás, que permite ordenar una cantidad de elementos en un tiempo proporcional a n2 en el peor de los casos o a n log n en el mejor de los casos. El algoritmo original es recursivo, como la técnica en la que se basa.

La descripción del algoritmo para el método de ordenamiento quicksort es la siguiente:

ü  Debe elegir uno de los elementos del arreglo al que llamaremos pivote.

ü  Debe acomodar los elementos del arreglo a cada lado del pivote, de manera que del lado izquierdo queden todos los menores al pivote y del lado derecho los mayores al pivote; considere que en este momento, el pivote ocupa exactamente el lugar que le corresponderá en el arreglo ordenado.

Colocado el pivote en su lugar, el arreglo queda separado en dos subarreglos, uno formado por los elementos del lado izquierdo del pivote, y otro por los elementos del lado derecho del pivote.

Repetir este proceso de forma recursiva para cada subarreglo mientras éstos contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

 Para elegir un pivote se puede aplicar cualquiera de las siguientes tres opciones:

ü  El pivote será el primer elemento del arreglo,

ü  El pivote será el elemento que está a la mitad del arreglo, o

ü  Que el pivote se elija de entre tres elementos del arreglo (cualesquiera), los cuales se deben comparar para seleccionar el valor intermedio de los tres y considerarlo como el pivote.

La forma o técnica de reacomodo de los elementos del lado izquierdo y derecho del pivote, aplica el siguiente procedimiento que es muy efectivo. Se utilizan dos índices: izq, al que llamaremos índice inicial, y der, al que llamaremos índice final. Conociendo estos elementos el algoritmo quedaría de la siguiente manera:

Recorrer el arreglo simultáneamente con izq y der: por la izquierda con izq (desde el primer elemento), y por la derecha con der (desde el último elemento).

ü  Mientras el arreglo en su posición izq (arreglo[izq]) sea menor que el pivote, continuamos el movimiento a la derecha.

ü  Mientras el arreglo en su posición der (arreglo[der]) sea mayor que el pivote, continuamos el movimiento a la izquierda.

Terminando los movimientos se compara los índices y si izq es menor o igual al der, se intercambian los elementos en esas posiciones y las posiciones se cambian izq a la derecha y der a la izquierda.

Repetir los pasos anteriores hasta que se crucen los índices (izq sea menor o igual a der).

El punto en que se cruzan los índices es la posición adecuada para colocar el pivote, porque sabemos que a un lado los elementos son todos menores y al otro son todos mayores (o habrían sido intercambiados).

Algoritmo ShellSort.

El método de ordenación shellsort es una versión mejorada del método de ordenación por inserción directa, que se utiliza cuando el número de elementos es grande. Este método recibe su nombre gracias a su creados Donald L. Shell, también se conoce con el nombre inserción con incrementos decrecientes.

En el método de ordenación por inserción directa, cada elemento se compara con los elementos contiguos de su izquierda de uno por uno, para lograr su ordenamiento; si por ejemplo, el elemento a comparar  es el más pequeño y se encuentra en la última posición del arreglo, hay que ejecutar muchas comparaciones antes de colocar el elemento en su lugar de forma definitiva.

El método de ordenación shellsort 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 la posición que debe ocupar. Los pasos múltiples sobre los elementos se hacen con tamaños de espacio cada vez más pequeños y el último paso del método es un simple ordenamiento por inserción directa, pero para entonces, los elementos de arreglo ya casi están ordenados.

Para determinar el tamaño de los incrementos (saltos) constantes, el primero debe ser generado a partir del tamaño del arreglo entre dos, obteniendo solo su parte entera de la división o redondeando el resultado de la misma, y posteriormente ir reduciendo a la mitad el incremento en cada repetición, hasta que el incremento sea un uno.

El procedimiento para aplicar el algoritmo de shellsort es el siguiente:

ü  Generar un ciclo que se encargue de controlar el tamaño que deben tener los incrementos.

Este ciclo debe iniciar con la división del tamaño del arreglo entre dos.

ü  Mientras que el incremento sea mayor a cero debe continuar.

ü  Y el cambio de incremento se elige de entre dos opciones: un uno o la división del incremento anterior entre dos.

Un segundo ciclo dentro del anterior, controla el número de comparaciones que se deben hacer según el tamaño del incremento.

ü  El control de este ciclo debe iniciar con el incremento generado anteriormente.

ü  Mientras el control del ciclo sea menor que el tamaño del arreglo.

ü  El control debe cambiar de uno en uno.

Un tercer ciclo dentro del segundo controla en qué momento se detienen las comparaciones o se hacen los posibles intercambios entre los elementos.

ü  El control de este ciclo debe iniciar con el valor del ciclo anterior.

ü  Mientras que el control sea mayor o igual al incremento del primer ciclo y el elemento del arreglo de la posición del control de este ciclo menos el incremento, sea mayor que el elemento del arreglo de la posición control de este ciclo, realice los intercambios entre estas posiciones.

Y el control se decremente con el valor del incremento.

 Algoritmos de ordenamiento por distribución.

Los algoritmos de ordenamiento por distribución, ordenan el arreglo tomando cada número e insertándolo en la posición que toma su valor, es decir, si se tiene un cinco se coloca en la posición cinco del arreglo, algo así como: “lo que valgas en esa posición te pongo”. Esto indica que no se podrán ordenar los arreglos que tengan valores repetidos y el arreglo necesita el tamaño del número más grande que se encuentre en él.

Lo que debemos hacer cuando se repitan los datos es incrementar la capacidad de la posición (urna). Para lograrlo podemos hacer lo siguiente:

Definir un arreglo en el que cada posición puede ser ocupada por más de un elemento (arreglo bidimensional) puede darse la situación de ser insuficiente la cantidad de posiciones adicionales o de existir demasiado desperdicio de memoria.

Definir el tamaño de la urna variable a través del uso de estructuras de datos como las listas simples enlazadas.

Los algoritmos de ordenamiento por distribución se clasifican en:

ü  CountingSort.

ü  RadixSort.

ü  BucketSort.

Algoritmo Radix.

El método de ordenación radix es un algoritmo que ordena datos procesando sus elementos de forma individual, según la posición que ocupan dentro del dato. Los datos numéricos los por dígitos y los datos alfabéticos por letras.

El método radix se clasifica en dos tipos según el orden en el que procesan los datos:

ü   De derecha a izquierda y

ü   De izquierda a derecha.

Si aplicamos este método solo a enteros, el método se clasificaría de la siguiente manera:

ü   El digito menos significativo (LSD, Least Significat Digit) y

ü   El digito más significativo (MSD, More Significat Digit).

El radix LSD procesa los enteros iniciando por el digito menos significativo y moviéndose al digito más significativo (de derecha a izquierda).

El radix MSD procesa los enteros iniciando por el digito más significativo y moviéndose al digito menos significativo (de izquierda a derecha).

El método más aplicado de radix, es el LSD, y se encarga de colocar los números en una de las 10 colas que representan un digito cada una de ella, iniciando desde la cola que controla el digito 0 hasta la cola que controla el digito 9, en estas colas se colocan los números dependiendo del digito que se esté analizando en ese momento, hasta que termine con el número que contenga la mayor cantidad de dígitos, en cada cambio de digito los elementos se integran al arreglo nuevamente desde la cola 0 hasta la cola 9, para elegir el siguiente digito de ordenamiento. Cuando se efectúa este proceso para cada dígito  al arreglo  está ordenado.

El procedimiento para aplicar el algoritmo de radix es el siguiente:

Determinar cuál es la mayor cantidad de dígitos del elemento mayor del arreglo.

Crear un arreglo de colas, que permita almacenar cana uno de los dígitos del 0 al 9.

Crear cada posición del arreglo como un objeto que permita almacenar los elementos en cada cola, según el índice que le corresponde.

Generar un ciclo que determine el número de digito que se está procesando y el factor que permite encontrar el digito.

Inicializar el número de digito y el factor en uno;

Mientras el digito sea menor o igual a la cantidad de dígitos encontrados en el paso uno.

El número de digito se debe incrementar de uno en uno.

Crear un segundo ciclo que se encuentra dentro del anterior y que se encarga de recorrer todo el arreglo desde la posición inicial hasta la final del arreglo.

Iniciar el control del ciclo en cero.

Mientras el control sea menor al tamaño del arreglo, continuamos en el ciclo.

El control del ciclo se cambia de uno en uno.

 Generar un segundo ciclo que se encuentra dentro del primero, al igual que el anterior y este controla el paso de los elementos de las colas al arreglo nuevamente.

El control de este ciclo inicia desde la cola cero, al igual que el índice que controla el arreglo de los elementos.

Mientras el control sea menor a diez continua dentro del ciclo.

El control del ciclo se incrementa de uno en uno.

Dentro del ciclo anterior se genera otro ciclo que se encarga de colocar el contenido de cada cola dentro del arreglo original y su condición es que mientras la cola no este vacía retire los elementos guardándolos en el arreglo e incrementar el índice que controla el arreglo.