Métodos de Ordenamiento

REPBLICA BOLIVARIANA DE VENEZUELA MINISTERIO DEL PODER POPULAR PARA LA DEFENSA

UNIVERSIDAD NACIONAL EXPERIMENTAL POLITCNICA DE LA FUERZA ARMADA

UNEFA- NCLEO YARACUY- EXTENSIN NIRGUA

Emprendedor

Luis M. Hernndez

Facilitador

Ing. Luis Sequera

Mtodos De Ordenamiento

Es la operacin de arreglar los registros de una tabla en algn orden secuencial

de acuerdo a un criterio de ordenamiento. El ordenamiento se efecta con base en el

valor de algn campo en un registro. El propsito principal de un ordenamiento es el de

facilitar las bsquedas de los miembros del conjunto ordenado.

Ej. de Ordenamientos:

Dir. Telefnico, 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 numrico,

alfabtico o incluso alfanumrico, ascendente o descendente.

Cundo conviene usar un mtodo de ordenamiento?

Cuando se requiere hacer una cantidad considerable de bsquedas y es

importante el factor tiempo .

Tipos De Ordenamientos:

Los 2 tipos de ordenamientos que se pueden realizar son: los internos y los externos.

Los internos:

Son aquellos en los que los valores a ordenar estn 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 estn en memoria secundaria

(disco, cinta, cilindro magntico, etc), por lo que se asume que el tiempo que se requiere

para acceder a cualquier elemento depende de la ltima posicin accesada (posicin 1,

posicin 500, etc).

Algoritmos de ordenamiento:

Internos:

1. Internos

1. Insercin directa.

2. Insercin binaria.

2. Insercin directa.

1.

2. Seleccin directa.

3. Seleccin directa.

1. Burbuja.

2. Shake.

4. Intercambio directo.

1. Shell.

5. Insercin disminucin incremental.

1. Heap.

2. Tournament.

6. Ordenamiento de rbol.

1.

2. Quick sort.

7. Sort particionado.

8. Merge sort.

9. Radix sort.

10. Clculo de direccin.

Externos:

1. Straight merging.

2. Natural merging.

3. Balanced multiway merging.

4. Polyphase sort.

5. Distribution of initial runs.

Clasificacin de los algoritmos de ordenamiento de informacin:

El hecho de que la informacin est ordenada, nos sirve para poder encontrarla y

accesarla de manera ms eficiente ya que de lo contrario se tendra que hacer de manera

secuencial.

A continuacin se describirn 4 grupos de algoritmos para ordenar informacin:

1. Algoritmos de insercin:

En este tipo de algoritmo los elementos que van a ser ordenados son considerados

uno a la vez. Cada elemento es INSERTADO en la posicin apropiada con respecto al

resto de los elementos ya ordenados.

Entre estos algoritmos se encuentran el de INSERCION DIRECTA, SHELL SORT,

INSERCION BINARIA y HASHING.

2. Algoritmos de intercambio:

En este tipo de algoritmos se toman los elementos de dos en dos, se comparan y se

INTERCAMBIAN si no estn en el orden adecuado. Este proceso se repite hasta que se

ha analizado todo el conjunto de elementos y ya no hay intercambios.

Entre estos algoritmos se encuentran el BURBUJA y QUICK SORT.

3. Algoritmos de seleccin:

En este tipo de algoritmos se SELECCIONA o se busca el elemento ms pequeo (o

ms grande) de todo el conjunto de elementos y se coloca en su posicin adecuada. Este

proceso se repite para el resto de los elementos hasta que todos son analizados.

Entre estos algoritmos se encuentra el de SELECCION DIRECTA.

4. Algoritmos de enumeracin:

En este tipo de algoritmos cada elemento es comparado contra los dems. En la

comparacin se cuenta cuntos elementos son ms pequeos que el elemento que se est

analizando, generando as una ENUMERACION. El nmero generado para cada

elemento indicar su posicin.

A continuacin se mostrarn los mtodos de ordenamiento ms simples.

METODO DE INSERCIN.

Este mtodo toma cada elemento del arreglo para ser ordenado y lo compara con

los que se encuentran en posiciones anteriores a la de l dentro del arreglo. Si resulta

que el elemento con el que se est comparando es mayor que el elemento a ordenar, se

recorre hacia la siguiente posicin superior. Si por el contrario, resulta que el elemento

con el que se est comparando es menor que el elemento a ordenar, se detiene el

proceso de comparacin pues se encontr que el elemento ya est ordenado y se coloca

en su posicin (que es la siguiente a la del ltimo nmero con el que se compar).

Procedimiento Insertion Sort

Este procedimiento recibe el arreglo de datos a ordenar a[] y altera las posiciones

de sus elementos hasta dejarlos ordenados de menor a mayor. N representa el nmero de

elementos que contiene a[].

paso 1: [Para cada pos. del arreglo] For i

paso 6: [Intercambia los datos de la pos.

min y posicin i] Swap(a, min, j).

paso 7: [Fin] End.

MTODO BURBUJA.

El bubble sort, tambin conocido como ordenamiento burbuja, funciona de la

siguiente manera: Se recorre el arreglo intercambiando los elementos adyacentes que

estn desordenados. Se recorre el arreglo tantas veces hasta que ya no haya cambios.

Prcticamente lo que hace es tomar el elemento mayor y lo va recorriendo de posicin

en posicin hasta ponerlo en su lugar.

Procedimiento Bubble Sort

paso 1: [Inicializa i al final de arreglo] For i

subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor ms

pequeo de K.

Eventualmente el valor de K llega a ser 1, de tal manera que el subgrupo

consiste de todo el arreglo ya casi ordenado.

Al principio del proceso se escoge la secuencia de decrecimiento de

incrementos; el ltimo valor debe ser 1.

"Es como hacer un ordenamiento de burbuja pero comparando e intercambiando

elementos."

Cuando el incremento toma un valor de 1, todos los elementos pasan a formar

parte del subgrupo y se aplica insercin directa.

El mtodo se basa en tomar como salto N/2 (siendo N el nmero de elementos) y

luego se va reduciendo a la mitad en cada repeticin hasta que el salto o distancia vale

1.

Mtodos De Bsqueda

Un algoritmo de busqueda es un algoritmo que acepta un argumento a y trata de

encontrar un registro cuya llave sea a. El algoritmo puede dar como resultado el registro

entero o, lo que es mas comun, un apuntador a dicho registro.

Si la bsqueda es infructuosa, con mucha frecuencia, es deseable agregar un

nuevo registro con dicho argumento como llave. Un algoritmo que haga esto se le

llama tabla busqueda o diccionario.

La bsqueda en la cual toda la tabla esta de manera frecuente en la memoria

principal se le llama busqueda interna, mientras que la busqueda en la que la mayor

parte de la table esta en la memoria auxiliar se llama busqueda externa.

Tcnica Secuencial Ordenada/Desordenada:

Normalmente un archivo secuencial se almacena en bloques, en un orden

secuencial simple de los registros. La organizacin fsica del archivo en una cinta o

disco se corresponde exactamente con la ubicacin lgica del archivo. En este caso, el

procedimiento para ubicar los nuevos registros en un archivo de pila separado, llamado

archivo de registro (log file) o archivo de transacciones. Peridicamente, se realiza una

actualizacin por lotes que mezcla el archivo de registro con el archivo maestro para

producir un nuevo archivo en secuencia correcta de claves.

Bsqueda secuencial, tambin se le conoce como bsqueda lineal. Supongamos

una coleccin de registros organizados como una lista lineal. El algoritmo bsico de

bsqueda secuencial consiste en empezar al inicio de la lista e ir a travs de cada

registro hasta encontrar la llave indicada (k), o hasta al final de la lista.

Ventajas de la tcnica

Es el algoritmo ms simple de bsqueda y no requiere ningn proceso previo de la

tabla, ni ningn conocimiento sobre la distribucin de las llaves. La bsqueda

secuencial es el rea del problema donde previamente existan mejores algoritmos.

Es el mejor metodo de busqueda para registros desordenados y revisa nodo por nodo

sin brincar ninguno ( es muy seguro)

Desventajas de la tcnica

Este mtodo de bsqueda es muy lento, pero si los datos no estn en orden es el

nico mtodo que puede emplearse para hacer las bsquedas. Si los valores de la

llave no son nicos, para encontrar todos los registros con una llave particular, se

requiere buscar en toda la lista.

Si los registros a los que se accede con frecuencia no estan al principio del archivo,

la cantidad promedio de comparaciones aumenta notablemente dado que se requiere

mas tiempo para recuperar dichos regisros.

Tcnica de Bsqueda Secuencial Indexada:

Un mtodo popular para superar las desventajas de los archivos secuenciales es

el del archivo secuencias indexado; pero implica un aumento en la cantidad de espacio

requerida.

Funciona de la siguiente manera:

Se reserva una taba auxiliar llamada indice ademas del archivo ordenado mismo.

Cada elemento en el indice consta de una llave kindex y un apuntador al registro en el

archivo que corresponde a kindex. Los elementos en el indice al igual que los elementos

en el archivo, deben estar ordenados en la llave. Si el indice es de un octavo del tamao

del archivo, se representa en el indice cada octavo registra el archivo.

Si el indice comienza a crecer tanto que se vuelve ineficaz se puede usar un

indice secundario que funciona casi de la misma forma que el indice principal, solo que

apunta a este, no a la tabla principal la busqueda empieza con una exploracion por el

indice secundario; esto nos lleva a un subarreglo en el indice principal; despues el

procesamiento continua normalmente.


Permite procesar el archivo secuencialmente por orden lgico y tambin procesarlo

al azar

La ventaja real del mtodo secuencial indexado es que los elementos en la tabla

pueden ser examinados en forma secuencial si todos los registros en el archivo

deben ser accesados, pero sin embargo, el tiempo de bsqueda para algn elemento

en particular se reduce considerablemente. La bsqueda secuencial se realiza en la

tabla de ndices que es ms pequea en lugar de la tabla ms grande. Una vez que se

ha encontrado un ndice correcto, se hace una segunda bsqueda secuencial

nicamente en la parte reducida de la tabla que contiene los registros.

Las eliminaciones de una tabla secuencial indexada se pueden hacer fcilmente

mediante la asignacin de banderas a las entradas que son eliminadas. Durante la

bsqueda secuencial a travs de la tabla, se ignoran las entradas que han sido

eliminadas.


Implica un aumento en la cantidad de espacio requerida, porque se ocupa un indice

y se pone a un lado adems del fichero clasificado a s mismo.

La insercin en una tabla secuencial indexada es un poco ms difcil debido a que

puede que no exista espacio entre dos entradas en la tabla, siendo necesario mover

un gran nmero de elementos en la tabla.

El uso de una lista ligada (indice) da una gran sobrecarga de espacio y tiempo para

los apuntadores que se utilizan en la busqueda de registros.

Tcnica de Bsqueda Binaria.

La bsqueda binaria utiliza un mtodo de `divide y vencers'para localizar el valor

deseado. Con este mtodo se examina primero el elemento central de la lista; si ste es

el elemento buscado, entonces la bsqueda ha terminado.

En caso contrario, se determinar si el elemento buscado ser en la primera o la

segunda mitad de la lista y a continuacin se repite este porceso, utilizando el elemento

central de esa sublista.

Algoritmo

o Se compara la llave buscada con la llave localizada al centro del arreglo.

o Si la llave analizada corresponde a la buscada fin de bsqueda si no.

o Si la llave buscada es menor que la analizada repetir proceso en mitad superior, sino

en la mitad inferior.

o El proceso de partir por la mitad el arreglo se repite hasta encontrar el registro o

hasta que el tamao de la lista restante sea cero , lo cual implica que el valor de la

llave buscada no esta en la lista.


La bsqueda binaria es un mtodo eficiente siempre que el vector est ordenado. En

la prctica, esto suele suceder, pero no siempre. Por esta razn la bsqueda binaria

exige una ordenacin previa del archivo.

La bsqueda binaria proporciona un medio para reducir el tiempo requerido para

buscar en una lista. Este mtodo, sin embargo, exige que los datos estn ordenados.

Es mas rapido por su recursividad, su mayor ventaja es con los archivos extensos.

El codigo del procedimiento de esta busqueda es corto en comparacion con las

demas tecnicas de busqueda.


La bsqueda binaria tiene, sin embargo, inconvenientes a resaltar:

No revisa todos los elementos del archivo, requiere que todos los elementos esten

ordenados

Esta busqueda mas de uno o dos accesos si el archivo es enorme;y mantener ese

archivo ordenado es muy costoso.

Tcnica de Bsqueda por Interpolacin

Este mtodo se puede aplicar solamente a tablas o archivos ordenados. Como su

nombre lo indica se trata de llegar al elemento buscado por medio de la

interpolacin lineal. El procedimiento es recursivo; como en el caso de la bsqueda

binaria, en cada paso se van modificando los lmites, disminuyendo el intervalo,

hasta llegar al elemento buscado.

El funcionamiento de la bsqueda de la interpolacin depende no solamente de

la talla de la secuencia, pero tambin de la entrada de informacin misma. Hay

entradas de informacin para los chequeos de la bsqueda de interpolacin del

deseado en cada nmero en la secuencia. Sin embargo, la bsqueda de la

interpolacin es muy eficiente para las entradas de informacin que consisten en

elementos relativamente uniformemente distribuidos (las paginaciones de un libro,

por supuesto, se distribuyen uniformemente). Puede ser mostrado que el nmero

medio de comparaciones se realiz por la bsqueda de interpolacin, donde el

promedio asume el control todas las secuencias posibles, es 0 (logn del registro).

Aunque ste se parece ser un orden de la mejora magnitud concluda de el

funcionamiento de la bsqueda binaria (debido al logaritmo adicional)


La bsqueda de interpolacin, es una bsqueda mucho mejor que la binaria en la

prctica porque, a menos que no sea muy grande, el valor de log2n es bastante

pequeo que el logaritmo de l no es mucho ms pequeo.

Incluso a pesar de qe el calclo es de algun modo mas complejo, una busqueda con

interpolacion puede proporcionar una mejoria importante a nuestra busqueda binaria

en grandes conjuntos de datos con claves distribuidas de modo uniforme.


La bsqueda de la interpolacin requiere una aritmtica ms elaborada, a parte que

los calculos que se necesitan para esta busqueda son muy lentos.

Para lograr esta busqueda se requieren llaves, multiplicaciones y divisiones

complejas, es decir, calculos de nivel alto.

Documents

Métodos de Ordenamiento