Comparación empírica del número de operaciones de diferentes algoritmos de ordenamiento

Abstract

En este trabajo se revisan las complejidades algorítmicas de los métodos de Burbuja (bubble), Mezcla (merge sort), Shell, ordenamiento rápido (quicksort), Comb y Stooge. Se realizan corridas con cada uno de los métodos mencionados con arreglos con diferentes tamaños que son generados aleatoriamente. En cada corrida de cuentan las cantidades de comparaciones y de intercambios de números que le toma a cada algoritmo para ordenar las listas de números. Se realizan 30 corridas de cada algoritmo con listas de diferentes tamaños, comenzando con 500 elementos y hasta 10000 elementos, con incrementos de 500 números. De las 30 corridas por método y por tamaño de arreglo, se obtiene el promedio y posteriormente se grafica. Se comparan los resultados de cada algoritmo con respecto a la cantidad de intercambios y de comparaciones. Las graficas obtenidas se comparan con las funciones de complejidad que se obtuvieron de forma teórica y se comprueba que el comportamiento que se observo durante las corridas coincide con el análisis teórico de complejidad de cada algoritmo.