sheel

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 medioscomputacionales requieren
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 muchas otras
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 queresolvían el problema
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, yfue uno de los
primeros 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íricamenteque implementar 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 delarreglo, pero hay que 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...