Variado

Estudio y optimización del algoritmo de ordenamiento Shellsort
Benjamin Bustos Departamento de Ciencias de la Computación, Universidad de Chile bebustos@dcc.uchile.cl

Resumen
Este estudioanaliza, en forma empírica, el desempeño del algoritmo de ordenamiento Shellsort con diferentes series de pasos. Se estudian optimizaciones al algoritmo para evitar los peores casos y se compara surendimiento con algoritmos de ordenamiento eficientes (Quicksort, Mergesort y Heapsort), discutiéndose la utilidad del algoritmo para resolver el problema de ordenamiento de conjuntos de tamaño medio.

1.Introducción
El estudio de algoritmos de ordenamiento tiene una gran importancia dentro de la Ciencia de la Computación, pues una buena cantidad de los procesos realizados por medios computacionalesrequieren que sus datos estén ordenados. Además, el hecho de almacenar los datos de manera ordenada permite implementar algoritmos de búsqueda muy rápidos (por ejemplo: búsqueda binaria). Esta y muchasotras razones de fin práctico impulsaron el estudio y la búsqueda de algoritmos de ordenamiento eficientes.

Desde los comienzos del uso de computadores se conocían algoritmos que resolvían elproblema en tiempo cuadrático respecto del tamaño del problema, pero eran rutinas muy sencillas y lentas. El algoritmo de ordenamiento Shellsort fue publicado en 1959 por Donald L. Shell, y fue uno de losprimeros en romper la barrera del orden cuadrático, aunque esto en realidad se probó un par de años después de su publicación.

El objetivo de este estudio es demostrar empíricamente queimplementar Shellsort con series de pasos dependientes del tamaño del arreglo puede llegar a ser mucho más eficiente que con las series clásicas, las cuales son independientes del tamaño del arreglo, pero hayque aplicar una optimización sencilla para obtener buenos resultados: todos los pasos de la serie deben ser números impares. Además,

este estudio muestra que dada la simplicidad de programación...