Algoritmos De Ordenamiento

Algoritmos de ordenamiento

Introducción.

Uno de los problemas fundamentales en la ciencia de la computación es ordenar una lista de ítems. Existen una infinidad de métodos de ordenamiento, algunos son simples e intuitivos, como el bubble sort, y otros como son extremadamente complicados, pero producen los resultados mucho más rápido. Se presentan los algoritmos de ordenamiento más comunes,entre los cuales están los siguientes: Bubble sort, Heap sort, Insertion sort, Merge sort, Quick sort, Selection sort y Shell sort. Los algoritmos de ordenamiento pueden ser divididos en dos clases de acuerdo a la complejidad de los mismos. La complejidad del algoritmo se denota según la notación Big-O.

Por ejemplo, O(n) significa que el algoritmo tiene una complejidad lineal. En otraspalabras, toma 10 veces más tiempo en operar un set de 100 datos que en hacerlo con un set de 10 ítems. Si la complejidad fuera O (n2) entonces tomaría 100 veces más tiempo en operar 100 ítems que en hacerlo con 10. Adicionalmente a la complejidad de los algoritmos, la velocidad de ejecución puede cambiar de acuerdo al tipo de dato a ordenar, es por ello que es conveniente comprar los algoritmos contradatos empíricos. Estos datos empíricos se deben elaborar tomando la media de tiempo de ejecución en un conjunto de corridas y con datos del mismo tipo.

En este trabajo se ejecutaron 10 veces cada algoritmo de ordenamiento con un set de 10000 datos de tipo entero de c++. Se realiza también una comparativa con otros tipos de datos como ser el long y el char para todos los algoritmos y luego se loscompara entre cada uno de ellos. En el gráfico siguiente se puede ver el tiempo de ejecución del algoritmo en función de la cantidad de elementos, se puede observar que si los elementos a ordenar son pocos, menos de 1000 casi todos los tienen el mismo tiempo de respuesta, pero si la cantidad de datos aumenta los tiempos de respuesta van cambiando drásticamente entre cada uno de los ellos, y parauna cantidad de datos de 8000 ya se puede determinar que el peor algoritmo es el bubble sort, mientras que el mejor es el Heap sort.

El siguiente trabajo desarrolla el tema de la performance del algoritmo de ordenamiento insertion sort asi como también el orden de complejidad del mismo.

Insertión Sort
El insertión sort trabaja insertando el ítem en su lugar correspondiente al final de lalista. Como el bubble sort, éste algoritmo se comporta como O(n2), pero a pesar de tener el misma complejidad, este algoritmo es casi el doble más eficiente que el bubble sort.

Como funciona.

En este método lo que se hace es tener una sublista ordenada de elementos del array e ir insertando el resto en el lugar adecuado para que la sublista no pierda el orden. La sublista ordenada se vahaciendo cada vez mayor, de modo que al final la lista entera queda ordenada.
Para el ejemplo {40, 21, 4, 9, 10, 35}, se tiene:

{40, 21, 4, 9, 10, 35} <-- La primera sublista ordenada es {40}.
Insertamos el 21:
{40, 40, 4, 9, 10, 35} <-- aux=21;
{21, 40, 4, 9, 10, 35} <-- Ahora la sublista ordenada es {21,40}.
Insertamos el 4:
{21, 40, 40, 9, 10, 35} <-- aux=4;
{21, 21, 40, 9,10, 35} <-- aux=4;
{4, 21, 40, 9, 10, 35} <-- Ahora la sublista ordenada es {4, 21, 40}.
Insertamos el 9:
{4, 21, 40, 40, 10, 35} <-- aux=9;
{4, 21, 21, 40, 10, 35} <-- aux=9;
{4, 9, 21, 40, 10, 35} <-- Ahora la sublista ordenada es {4,9,21,40}.
Insertamos el 10:
{4, 9, 21, 40, 40, 35} <-- aux=10;
{4, 9, 21, 21, 40, 35} <-- aux=10;
{4, 9, 10, 21, 40, 35} <-- Ahora lasublista ordenada es {4, 9, 10, 21, 40}.
Y por último insertamos el 35:
{4, 9, 10, 21, 40, 40} <-- aux=35;
{4, 9, 10, 21, 35, 40} <-- El array está ordenado.

En el peor de los casos, el número de comparaciones que hay que realizar es de N*(N+1)/2-1, lo que nos deja un tiempo de ejecución en O (n2). En el mejor caso (Cuando la lista ya estaba ordenada), el número de comparaciones es...