Introducción

Los algoritmos de ordenamiento permiten, como su nombre lo dice, ordenar. En este caso, funcionaran para ordenar vectores o matrices con valores asignados aleatoriamente, o mediante la utilización de ficheros, dependiendo de cual sea el tipo de clasificación de ordenamiento, si es interno o externo. Se destacaran los métodos más populares, analizando la cantidad de comparaciones que suceden y revisando el código, escrito en Pascal, de cada algoritmo.

Seguidamente se conocerán los métodos de búsqueda, entre los cuales se encuentran el Secuencial e Indexado. Estos métodos permitirán la manipulación de arreglos y/o ficheros para lograr con éxito su búsqueda.

Este informe permitirá conocer más a fondo cada método distinto de ordenamiento y búsqueda, desde uno simple hasta el más complejo. Se realizaran visualizaciones gráficas de la realización de cada algoritmo para su mejor entendimiento.

Algoritmos de clasificación interna

Ordenación por burbuja.

Es un método clásico y sencillo, aunque por desgracia poco eficiente. La ordenación por burbuja se basa en la comparación de elementos adyacentes de la lista (vector) e intercambiar sus valores si están desordenados. De este modo se dice que los valores mas pequeños burbujean hacia la parte superior d la lista (hacia el primer elemento), mientras que los valores más grandes se hunden hacia el fondo de la lista.El método burbuja es simple de implementar, pero es muy lento, por lo cual es sólo adecuado para pequeños conjuntos de números.

A continuación se muestra el Ordenamiento por Burbuja en lenguaje de programación pascal:

Var i,j,aux:integer; Begin

desordenado := true;

while desordenado do begin desordenado := false; for i:= 1 to 5 do if arre[ i ] > arre[ i + 1 ] then begin desordenado := true; aux := arre[ i ]; arre[ i ] := arre[ i + 1 ]; arre[ i + 1] := aux; end; end; end.

Ordenación por selección.

En este tipo de algoritmos se selecciona o se busca el elemento más pequeño (o más grande) de todo el conjunto de elementos y se coloca en su posición adecuada. Este proceso se repite para el resto de los elementos hasta que todos son analizados.

Su funcionamiento es el siguiente:

Buscar el mínimo elemento de la lista Intercambiarlo con el primero Buscar el mínimo en el resto de la lista Intercambiarlo con el segundo

Y en general:

Buscar el mínimo elemento entre una posición i y el final de la lista Intercambiar el mínimo con el elemento de la posición i.

A continuación se muestra el Ordenamiento por Selección en lenguaje de programación pascal:

Var i,j,aux:integer; Begin

for i:=1 to 5 do for j:= i+1 to 5 do

if arre[i] > arre[j] then begin aux:=arre[i]; arre[i]:=arre[j]; arre[j]:=aux; end; end.

Ordenamiento por Inserción Directa.

El método de ordenación por inserción consiste en dividir el conjunto de datos a ordenar en dos subconjuntos que corresponden, respectivamente, al subconjunto de datos ya ordenados y el subconjunto que contiene los datos pendientes de ordenar. Cada paso del algoritmo consiste en incrementar en un elemento el subconjunto ordenado y decrementar el desordenado, hasta que todos los elementos pertenezcan al subconjunto ordenado y el subconjunto desordenado esté vacío.

Este método está basado en la técnica utilizada por los jugadores de cartas para clasificar sus cartas. El jugador va colocando (insertando) cada carta en su posición correcta.

El método se basa en considerar una parte de la lista ya ordenada y situar cada uno de los elementos restantes insertándolo en el lugar que le corresponde por su valor.

A continuación se muestra el Ordenamiento por Inserción Directa en lenguaje de programación pascal:

Var i,j,aux:integer; Begin

aux:= arre[i]; encontrado:=false;

while (i >= 1) and (not encontrado) do if (arre[i-1] > aux) then begin

arre[i]:= arre[i-1]; i:=i-1 end; else encontrado:=true; nuevapos:=i; arre[nuevapos]:=aux;end.

Ordenamiento por el método Shell.

Es una mejora del método de inserción directa, utilizado cuando el array tiene un gran número de elementos. En este método no se compara a cada elemento con el de su izquierda, como en el de inserción, sino con el que está a un cierto número de lugares (llamado salto) a su izquierda. Este salto es constante, y su valor inicial es N/2 (siendo N el número de elementos, y siendo división entera).

El Shell es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones:

1. El ordenamiento por inserción es eficiente si la entrada está "casi ordenada". 2. El ordenamiento por inserción es ineficiente, en general, porque mueve los

valores sólo una posición cada vez.

El algoritmo Shell sort 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 su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados.

A continuación se muestra el Ordenamiento por el método de Shell en lenguaje de programación pascal:

Var salto,i,aux,num:integer; cambios:boolean; Begin

salto:= 8 div 2; while salto <> 0 do begin cambios:=true;

while cambios do begin cambios:=false;

for i:= (salto+1) to 8 do begin if (arre[i-salto] > arre[i]) then begin aux:=arre[i]; arre[i]:=arre[i-salto]; arre[i-salto]:=aux; end; end; end; salto:= salto div 2; end;

end.

Ordenamiento por Quicksort.

El Ordenamiento por Quicksort o método de ordenamiento rápido, es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en una complejidad de n log n. Es la técnica de ordenamiento más rápida conocida.

El algoritmo fundamental es el siguiente:

Se elige un elemento del vector, puede ser cualquiera. Lo llamaremos elemento de división o pivote. La forma más efectiva es escoger como pivote el elemento intermedio

Se busca la posición que le corresponde en el vector al pivote y ordenamos los elementos de la lista de manera que a lado queden los menores y a otro los mayores.

Se realiza esto de forma recursiva para que cada “subvector” mientras este tengan un largo mayor que 1.

A continuación se muestra un ejemplo de Ordenamiento Quicksort:

PROCEDIMIENTO quicksort (a: tipo_vector (E/S), izq: entero (E), der: entero (E)); VAR

i,j: enterox,w: tipo_elemento

INICIOI:=izq

J:=derX:=a [(izq+der)/2]

Mientras (i<=j) hacer Mientras (a[i].clave<x.clave) hacer

I:=i+1Fin_mientrasMientras (x.clave<a[j].clave) hacer

J:=j-1Fin_mientrasSi (i<=j) entonces

W:=a[i]a[i]:=a[j]a[j]:=wi:=i+1j:=j-1

Fin_siFin_mientrasSi (izq<j) entonces

LLAMAR A quicksort (a,izq,j)Fin_siSi (i<der) entonces

LLAMAR A quicksort (a,i,der)Fin_si

FIN_PROCEDIMIENTO

Algoritmos de clasificación externa de datos basados en mezcla

Problema: Los datos a ordenar no entran todos en memoria principal, están almacenados en dispositivos periféricos de acceso secuencial:

Cinta: TDA secuencia

Disco: TDA archivo

Restricciones en el proceso de clasificación:

Acceso secuencial a cada uno de los elementos de una secuencia.

No permite aplicar los métodos de clasificación sobre arreglos en los que el acceso a cualquier elemento implicaba el mismo coste.

Tipos de técnicas de clasificación externa basadas en Mezcla

Mezcla directa

Mezcla directa de una fase

Mezcla natural

Mezcla balanceada múltiple

Clasificación polifásica Definiciones:

Mezcla:Tarea de combinar varias secuencias en una sola, mediante la selección repetida de los componentes accesibles en cada momento.

Es una operación auxiliar previa utilizada como estrategia para desarrollar la tarea de clasificación.

Fase:Cada operación que trata un conjunto completo de datos.Ejemplos: distribución, mezcla.

Pase (etapa):El proceso más corto que, por repetición, forma parte del proceso de clasificación. Ejemplo: distribución + mezcla.

Mezcla directa

Tomar como fuente la secuencia original c1

Dividir la fuente en dos mitades, en las cintas destino c2 y c3

Mezclar c2 y c3 combinando cada elemento accesible en pares ordenados, en c1Repetir el proceso:Se obtiene una cinta con cuádruplos ordenados.

Repetir el proceso hasta que toda la cinta esté ordenada Cada pase o etapa consta de dos fases, Una de división y

Otra de mezcla, por ello se denomina mezcla de dos fases o mezcla de tres cintas.

Análisis de clasificación por mezcla directa

En las mezclas el número de comparaciones es de poco interés práctico frente a la penalización de tiempo que supone el realizar movimientos.La complejidad es parecida a la de los algoritmos avanzados de clasificación en memoria principal. Mezcla Directa de una Fase(Mezcla directa balanceada)

Debemos observar que la fase de división no aporta nada a la clasificación y sin embargo tiene un coste computacional significativo

Las fases de división de la mezcla directa pueden eliminarse combinando la fase de división con la de mezcla mejora el método de mezcla directa

En vez de mezclar en una sola cinta,que posteriormente será dividida, puede irse directamente separando en dos, de manera que en el siguiente pase ya estarán divididas (se elimina la distribución).

Análisis

Se producen el entero mayor de log n pases, por tanto el número de Movimientos es:

Mezcla natural

Aprovecha el hecho de que entre los elementos de la secuencia original, algunos elementos consecutivos ya se encontrarán ordenados entre sí.

La mezcla natural se basa en la combinación de subsecuencias ordenadas. Las subsecuencias ordenadas de la cinta fuente, se distribuyen en dos cintas destino auxiliares a y b. Seguidamente se mezcla una subsecuencia ordenada de cada cinta auxiliar.Fuente c

Distribuir las subsecuencias ordenadas de la fuente en las cintas destino a y b

Mezclar a y b en c, combinando subsecuencias ordenadas de cada cinta auxiliar.

Cada pase en la mezcla natural consta de dos fases, una de distribución y otra de mezcla.

Análisis mezcla natural

En el peor caso el número de movimientos es de orden nlog n, e inferior en el caso promedio.

El número de comparaciones es mucho mayor, pero al ser el coste de una comparación muy inferior al de un movimiento, este incremento no resulta significativo. Mezcla Balanceada Múltiple

Persigue reducir el número de movimientos (copias) para reducir el número de pases.

Se consigue:

Realizando la distribución entre más de dos cintas (mezcla múltiple)

En la mezcla se combinan más de dos subsecuencias ordenadas (una por cinta)

La mezcla se realiza en una sola fase, sobre varias cintas auxiliares

Se elimina la fase de distribución, salvo la inicial.

Análisis balanceada múltiple

Hay una cinta inicial con m subsecuencias ordenadas

Supóngase que se utilizan N cintas destino en la fase de distribución.

Una vez hecha la primera distribución, hay que mezclar las m subsecuencias ordenadas que están distribuidas uniformemente en N cintasEn una primera fase de mezcla, una subsecuencia ordenada de m/N subsecuencias ordenadas, en la segunda de m/N2 y en la k-ésima m/Nk.El número total de pases necesarios para clasificar n subsecuencias ordenadas con

N cintas será, en el peor de los casos Como cada pase necesita n copias, el número total de copias vendrá dado por

Clasificación polifásica

Mejora el rendimiento de la mezcla balanceada.

Las cintas fuente y destino no son establecidas a priori, sino como consecuencia de la mezcla realizada.

En el proceso de mezcla, dos hacen de fuente y la tercera de destino,

Al finalizar las combinaciones hará de cinta destino aquella que se haya agotado, la cual sólo podrá ser identificada tras la mezcla.

La clasificación polifásica aprovecha al máximo las cintas ya que con N cintas

realiza mezclas de N-1 subsecuencias ordenadas.

Lo que se pretende es que al final haya una sola subsecuencia ordenada en una cinta y las demás estén agotadas. Esto no siempre es posible.

En el ejemplo hay dos cintas vacías y a otra todavía le quedan dos subsecuencias.

Construcción de la clasificación Polifásica satisfactoria de tres cintas

Conclusión:

La clasificación polifásica con 3 cintas será satisfactoria si la distribución inicial de subsecuencias ordenadas entre las cintas fuentes es tal que son números consecutivos de Fibonacci.

Métodos de Búsqueda

Búsqueda Secuencial.

El proceso de búsqueda secuencial es una de las operaciones más comunes en la manipulación de arreglos. Puede definirse como el proceso de determinar el elemento, o u posición, que cumple una condición, comparando con cada uno de los elementos en forma secuencial. Es el método de búsqueda recomendado cuando se tiene un arreglo en el cual no se conoce la relación entre sus elementos, es decir estos están desordenados.

A continuación se muestra un ejemplo del método de Búsqueda Secuencial:

POS := 0; I := 1; { Recorrido del arreglo buscando VALOR } While ( ( I< = N ) and ( A[ I ] <> VALOR ) ) do I := I + 1;

If I <= N then { Determinar si encontró o no }

POS := I;

Búsqueda Indexada.

Un método 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 índice además del archivo ordenado mismo. Cada elemento en el índice consta de una llave kindex y un apuntador al registro en el archivo que corresponde a kindex. Los elementos en el índice al igual que los elementos en el archivo, deben estar ordenados en la llave. Si el índice es de un octavo del tamaño del archivo, se representa en el índice cada octavo registra el archivo.

Si el índice comienza a crecer tanto que se vuelve ineficaz se puede usar un índice secundario que funciona casi de la misma forma que el índice principal, solo que apunta a este, no a la tabla principal la búsqueda empieza con una exploración por el índice secundario; esto nos lleva a un subarreglo en el índice principal; después el procesamiento continua normalmente. Un ejemplo de lo anterior es la siguiente figura.

Ventajas de la técnica. 

Permite procesar el archivo secuencialmente por orden lógico y también procesarlo al azar.

La ventaja real del método 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 búsqueda para algún elemento en particular se reduce considerablemente. La búsqueda secuencial se realiza en la tabla de índices que es más pequeña en lugar de la tabla más grande. Una vez que se ha encontrado un índice correcto, se hace una segunda búsqueda secuencial únicamente en la parte reducida de la tabla que contiene los registros.

La organización secuencial indexado es conveniente para archivos con mediana volatilidad, actividad variable y tamaño relativamente estable.

Las eliminaciones de una tabla secuencial indexada se pueden hacer fácilmente mediante la asignación de banderas a las entradas que son eliminadas. Durante la búsqueda secuencial a través de la tabla, se ignoran las entradas que han sido eliminadas.

Desventajas de la técnica.

Pero implica un aumento en la cantidad de espacio requerida, porque se ocupa un índice y “se pone a un lado además del fichero clasificado a sí mismo”.

La inserción en una tabla secuencial indexada es un poco más difícil debido a que puede qe no exista espacio entre dos entradas en la tabla, siendo necesario mover un gran número 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.

Los registros deben ser de longitud fija. El archivo debe estar soportado por una memoria de masa tal como el disco; no se utiliza en cinta magnética. A veces todo el archivo debe estar presente en línea.

Principales Aplicaciones.

Un uso en la cual esta búsqueda se aplica, es donde se presenta el ingreso de datos (registros) sin ningún tipo de orden especifico; pero en cada determinado momento su campo llave es almacenado en un índice, en el cual esas llaves están ordenadas de menor a mayor o de mayor a menor dependiendo el uso que se le de. De esta manera, para agilizar la búsqueda de un registro en particular se acceso a ese registro por medio de su campo llave alacenado en el índice.

Un ejemplo de nuestra vida diaria y donde se aplica esta búsqueda es en un negocio mediano (negocio de carnes frás , refaccionaria), ya que aquí se necesita una búsqueda eficiente con una sola clave de acceso y otorgándonos la información requerida.

Codificación.

Algoritmo de Búsqueda Secuencial Indexada:

PROCEDURE B_S_INDEXADA(llave:integer; var pocis:integer);vari,n:integer;f:boolean;beginf:=false;i:=1;while (i<llave) thenf:= true;elseinc(i);if i=1 thenlinf:=1elselinf:=pindex[i-1];if f thenlsup:=pindex[i]-1elselsup:=n;j:=linf; f:=false;while(j<=lsup) ands (not f) do if k[j]="llave" then f:="true" else inc(j); if f then posic:="j" elseposic:="0;"

end;