Aplica las Técnicas de Ordenamientos de Datos.

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.

Existen varios métodos para ordenamiento, clasificados en tres formas:

Intercambio

El método de intercambio se basa en comparar los elementos del arreglo e intercambiarlos si su posición actual o inicial es contraria inversa a la deseada. Pertenece a este método el de la burbuja clasificada como intercambio directo. Aunque no es muy eficiente para ordenar listas grandes, es fácil de entender y muy adecuado para ordenar una pequeña lista de unos 100 elementos o menos.
Una pasada por la ordenación de burbujeo consiste en un recorrido completo a través del arreglo, en el que se comparan los contenidos de las casillas adyacentes, y se cambian si no están en orden. La ordenación por burbujeo completa consiste en una serie de pasadas (“burbujeo”) que termina con una en la que ya no se hacen cambios porque todo está en orden.

Burbuja

La idea básica de este método de ordenamiento es la de comparar pares de valores de llaves e intercambiarlos si no están en sus posiciones relativas correctas.

Como los métodos de selección e inserción vistos anteriormente, el método de burbuja requiere O(n^2) comparaciones. No obstante, el método de la burbuja es frecuentemente usado.
La idea de este método es la de permitir que cada llave flote a su posición adecuada a través de una serie de pares de comparaciones e intercambios con los valores adyacentes. Cada paso haces que una llave suba a su posición final, como una burbuja, en la lista ordenada.
Consideremos otra vez nuestro ejemplo de lista de llaves no ordenadas:

Cada llave se compara con la llave que está encima de ella (en nuestro caso al lado derecho de ella) y se intercambia, si la llave de arriba es más pequeña. Cuando una llave mayor que la llave sujeto se encuentra, la llave sujeto queda encima, y el proceso continúa. Después de la pasada, todas las llaves arriba de la última por intercambiar deberán estar en su posición final. No necesitarán examinarse en pasos posteriores.

Selección.

Los métodos de ordenación por selección se basan en dos principios básicos:
Seleccionar el elemento más pequeño (o más grande) del arreglo.
Colocarlo en la posición más baja (o más alta) del arreglo.

A diferencia del método de la burbuja, en este método el elemento más pequeño (o más grande) es el que se coloca en la posición final que le corresponde.
La idea básica de un ordenamiento por selección es la selección repetida de la llave menor restante en una lista de datos no clasificados, como la siguiente llave (dato o registro), en una lista de datos ordenada que crece.

La totalidad de la lista de llaves no ordenadas, debe estar disponible, para que nosotros podamos seleccionar la llave con valor mínimo en esa lista. Sin embargo, la lista ordenada, podrá ser puesta en la salida, a medida que avancemos.
Por ejemplo, consideremos la siguiente lista de llaves no ordenadas:


El primer paso de selección identifica el 2 como valor mínimo, lo saca de dicha lista y lo agrega como primer elemento en una nueva lista ordenada.


El segundo paso identifica el 3 como el siguiente elemento mínimo y lo retira de la lista para incluirlo en la nueva lista de elementos ordenados.


Después del sexto paso, tenemos la siguiente lista.

Para una lista de n registros, este algoritmo requiere n pasadas sobre la lista no ordenada. En la i-ésima pasada, se habrán hecho n-i comparaciones de llaves. Por lo tanto, el número total de comparaciones será:

La cual da n(n-1)/2. Esta ordenación se dice que requiere O(n^2) comparaciones, porque el término n^2 domina a la expresión. El número de comparaciones es proporcional al cuadrado del número de llaves en el conjunto. Así que, duplicar el número de llaves, significará que el proceso tomará cuatro veces más tiempo.

Vemos que este método de ordenamiento implementado como lo está, requiere dos veces más espacio del necesario, debido al uso de dos listas. Una modificación a este método de selección puede ser un método por selección con intercambio, en el cual la llave seleccionada es movido a su posición final por intercambio con la llave que inicialmente ocupaba esa posición. Consideremos otra vez la lista no clasificada:

Después del primer paso, 2 es seleccionado,


Después del segundo paso, 3 es el seleccionado,


Después del sexto paso,



El ordenamiento por selección con intercambio tiene esencialmente los mismos requerimientos de comparaciones que el ordenamiento por selección original, es de O(n^2).

Intercalación Balanceada

Una intercalación balanceada de m vías utiliza m archivos de entrada y m archivos de salida.
Las k listas ordenadas se distribuyen en forma uniforme en los m archivos de entrada.

Se intercalan las listas de cada uno de los archivos, distribuyendo en forma uniforme las listas resultantes en los archivos de salida (de mayor tamaño que las iniciales).
Se repite el último paso hasta que un archivo de salida contiene una lista ordenada.

Las m vías a las que se hace mención, son las que limitarán el número de archivos que podremos utilizar para nuestro proceso de ordenamiento. El tamaño de las listas estará dado por la capacidad del Buffer, con ello obtendremos el número de listas que tendremos que distribuir entre los m archivos de entrada.

Por ejemplo: Se desea ordenar un archivo con 6000 registros. Se cuenta con 2 vías para lograrlo y se sabe que el Buffer soporta un tamaño de listas de 1000 registros. Con todo, sabemos que tenemos que distribuir 6 listas (6000/1000) entre los 2 archivos de entrada (2 vías). Luego, dividiendo 6 por 2 no da 3 listas para cada archivo, las cuales tendrán un tamaño de 1000 registros (los que soporta el Buffer).

Intercalación Polifásica

Una intercalación polifásica de m vías utiliza 2*m-1 archivos de entrada y 1 archivo de salida.

Las k listas se distribuyen en forma no uniforme en los 2*m-1 archivos de entrada.

Se intercalan las listas (de mayor tamaño) en el archivo de salida. El archivo de entrada que primero queda vacío pasa a ser archivo de salida y el archivo de salida pasa a ser de entrada. Se repiten los 2 últimos pasos hasta que un archivo de salida contenga las lista ordenada.
Por ejemplo: Se tiene un archivo de datos que contiene 129.000 registros. Las listas son de tamaño 1000 registros (los que soporta el Buffer) y el grado de la intercalación es 3 (m=3 vías).

Tipos de Tipos de Ordenamientos Óptimos según la estructura de Datos

Los 2 tipos de ordenamientos óptimos según la estructura de datos a utilizar son: los internos y los externos.

Los internos: Son aquellos en que los valores a ordenar están en memoria principal, por lo que se asume que el tiempo que se requiere para acceder a cualquier elemento sea el mismo, este ordenamiento se aplican cuando el conjunto de datos a clasificar es lo suficientemente pequeño.

Externos: Es cuando los datos a clasificar se encuentran almacenados en archivos, en soportes de almacenamiento masivo (cintas o discos) el tiempo de acceso a lectura y escritura influye en la eficiencia del ordenamiento, por lo que se asume que el tiempo que se requiere para acceder a cualquier elemento depende de la última posición accesada.