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.
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.
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).
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.
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.
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.
