Ordenamiento de datos

CONCEPTO
La ordenación de datos es un proceso muy frecuente en programación. Esta operación es también un proceso que las personas encuentran comúnmente en sus rutinas diarias.
Por ejemplo, cada elemento de la colección de datos de una agenda telefónica tiene un campo nombre, dirección, y un número de teléfono.

Cuando los datos están almacenados en vectores, tablas (arrays), listas enlazadas o árboles, la ordenación se denomina ordenación interna.

Cuando los datos a clasificar se encuentran almacenados en archivos, en soportes de almacenamiento masivo (cintas o discos)

TIPOS DE METODOS DE ORDENAMIENTO

ORDENAMIENTO POR 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.
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.

EJEMPLO GRAFICO DEL ORDENAMIENTO POR BURBUJA

QUICKSORT

El ordenamiento rápido  es un algoritmo que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

El algoritmo consta de los siguientes pasos:

• Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
• Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores.
• La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
• Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

La eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.

• En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n·log n).

EJEMPLO GRAFICO DEL ORDENAMIENTO POR QUICKSORT

SHELL SORT

ordenamiento Shell es un algoritmo de ordenamiento.

Aunque es fácil desarrollar un sentido intuitivo de cómo funciona este algoritmo, es muy difícil analizar su tiempo de ejecución.

El Shell sort 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.
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.

EJEMPLO GRAFICO DE SHELL SORT

INSERCION

El ordenamiento por inserción es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria.
Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor.
 En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.

EJEMPLO GRAFICO DE ORDENAMIENTO POR INSERCION

AQUI ALGUNOS VIDEOS