Ordenacion de arreglos

ORDENAMIENTO DE DATOS EN ARREGLOS.

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. La colocación en orden de una lista de valores se llama Ordenación.

Existen tres casos al ordenar información:

1) El peor caso es cuando la información que se tiene está ordenada al revés.

2) El Mejor es cuando la información está ordenada.

3) El caso Promedio es cuando la información está ordenada al azar.

Por ejemplo, se podría disponer una lista de valores numéricos en orden ascendente o descendente, o bien una lista de nombres en orden alfabético. La localización de un elemento de una lista se llama búsqueda. Tal operación se puede hacer de manera más eficiente después de que la lista ha sido ordenada.

Debido a que las estructuras de datos son utilizadas para almacenar información, para poder recuperar esa información de manera eficiente es deseable que aquella esté ordenada.

Para poder ordenar una cantidad determinada de números almacenadas en un vector o matriz, existen distintos métodos con distintas características y complejidad.

ORDENAMIENTOS INTERNOS Y EXTERNOS

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

EXTERNOS: 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…)

• MÉTODO DE BURBUJA
• MÉTODO DE SELECCIÓN
• MÉTODO DE INSERCIÓN
• MÉTODO QUICKSORT

MÉTODO DE BURBUJA

Es uno de los más simples, es tan fácil como comparar todos los elementos de una lista contra todos, si se cumple que uno es mayor o menor otro, entonces los intercambia de posición. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este método obtiene su nombre de la forma con la que suben o se mueven de izquierda a derecha por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". 

Por ejemplo, imaginemos que tenemos los siguientes valores:

Lo que haría una burbuja, seria comenzar recorriendo los valores de izquierda a derecha, comenzando por el 6. Lo compara con el 5, con el 3, con el 1, con el 8, con el 7, con el 2 y con el 4; si es mayor o menor (dependiendo si el orden es ascendiente o descendente) se intercambian de posición. Luego continua con el siguiente, con el 5, y lo compara con todos los elementos de la lista, esperando ver si se cumple o no la misma condición que con el primer elemento. Así, sucesivamente, hasta el último elemento de la lista.

BURBUJA SIMPLE

La burbuja más simple de todas es la que compara todos con todos, generando comparaciones extras, por ejemplo, no tiene sentido que se compare con sigo mismo o que se compare con los valores anteriores a él, ya que supuestamente, ya están ordenados.

BURBUJA MEJORADA

Una nueva versión del método de la burbuja seria limitando el número de comparaciones, dijimos que era inútil que se compare consigo misma. Si tenemos una lista de 10.000 elementos, entonces son 10.000 comparaciones que están sobrando. Imaginemos si tenemos 1.000.000 de elementos. El método sería mucho más óptimo con “n” comparaciones menos (n = total de elementos).

Ventajas:

Fácil implementación.
No requiere memoria adicional.

Desventajas:

Muy lento.
Realiza numerosas comparaciones.
Realiza numerosos intercambios.

Este método sigue el algoritmo en base a los procesos anteriormente descritos y su aplicación  a la programación se puede observar en el siguiente enlace:

Clic para presentar recorrido del algoritmo de BURBUJA