3A. Reporte escrito. Experimentos y análisis de algoritmos de ordenamiento.

Lista de cambios:

Sin cambios. Versión original.

Introducción.

El ordenamiento es el proceso computacional de reorganizar una secuencia dada de elementos en orden ascendente o descendente. (Estivill-Castro & Wood, 1992).

En este reporte, se implementarán y analizarán varios algoritmos clásicos de ordenamiento por comparación, a saber: Heapsort, Mergesort, Quicksort, y Bubblesort. Cada uno de estos algoritmos se caracteriza por distintas complejidades de tiempo y estrategias de partición de los datos, lo que los hace más o menos eficientes según las características del conjunto de datos a ordenar.

Para hacerlo se usarán diferentes archivos proporcionados cuyos niveles de desorden son variables. Se realizará la métrica del número de comparaciones así como del tiempo necesario para ordenarlos.

El análisis se llevará a cabo utilizando archivos de entrada con niveles de desorden variados, lo que permitirá observar cómo se comportan los algoritmos en distintos tipos de distribuciones de los datos. Se emplearán tres métricas principales para evaluar el desempeño de cada algoritmo: el número de comparaciones realizadas, el número de intercambio y el tiempo total de ejecución.

Método heapsort.

De acuerdo con Cormen et al.(2022) Heapsort introduce el uso de una estructura de datos llamada heap (montículo), que no solo es útil para el algoritmo de ordenación. El algoritmo funciona construyendo el heap a partir de la lista y extrae repetidamente el elemento máximo (o mínimo) del montículo para construir la lista ordenada. Una de sus ventajas respecto a otros algoritmos de ordenamiento por comparación, es que realiza el mismo in situ lo que significa que solo requiere un número constante de elementos fuera del array de entrada en cualquier momento (Cormen et al. 2022).

Complejidad temporal:

\(O(n \log n)\) en todos los casos.

Esto significa que sin importar el orden preexistente en los arreglos, su complejidad permanecerá constante.

using JSON
using Dates

# Función para ajustar el montículo (heapify) - Índices basados en 1
function heapify!(arr, n, i, counters)
    largest = i
    left = 2 * i      # Hijo izquierdo (ajustado para base 1)
    right = 2 * i + 1 # Hijo derecho (ajustado para base 1)

    # Comparar con el hijo izquierdo
    counters[:comparisons] += 1
    if left <= n && arr[left] > arr[largest]
        largest = left
    end

    # Comparar con el hijo derecho
    counters[:comparisons] += 1
    if right <= n && arr[right] > arr[largest]
        largest = right
    end

    # Si el mayor no es la raíz, intercambiar y seguir ajustando
    if largest != i
        arr[i], arr[largest] = arr[largest], arr[i]
        counters[:swaps] += 1
        heapify!(arr, n, largest, counters)
    end
end

# Implementación de HeapSort - Índices basados en 1
function heapsort!(arr)
    n = length(arr)
    counters = Dict(:comparisons => 0, :swaps => 0)  # Contador de operaciones

    # Construir el max-heap
    for i in n ÷ 2:-1:1
        heapify!(arr, n, i, counters)
    end

    # Extraer elementos del heap uno por uno
    for i in n:-1:2
        arr[1], arr[i] = arr[i], arr[1]  # Mover la raíz al final
        counters[:swaps] += 1
        heapify!(arr, i - 1, 1, counters)
    end

    return counters
end

# Función para cargar y ordenar el archivo JSON con múltiples claves
function eval_heap(p::String)
    # Construir la ruta del archivo con el argumento p
    ruta_archivo = joinpath(homedir(),  raw"C:\Users\josea\Downloads\listas-posteo-con-perturbaciones", "listas-posteo-con-perturbaciones-p=" * p * ".json")

    # Cargar el archivo JSON
    datos = JSON.parsefile(ruta_archivo)
    contador = 0
    contador2= 0

    # Procesar cada clave del JSON
    for (clave, arr) in datos

        counters = heapsort!(arr)
        contador += counters[:comparisons]
        contador2 += counters[:swaps]
    end
println("Comparaciones: ", contador)
println("Intercambios: ", contador2)
end

eval_heap (generic function with 1 method)

using JSON
using Dates

# Función para ajustar el montículo (heapify) - Índices basados en 1
function heapify!(arr, n, i, counters)
    largest = i
    left = 2 * i      # Hijo izquierdo (ajustado para base 1)
    right = 2 * i + 1 # Hijo derecho (ajustado para base 1)

    # Comparar con el hijo izquierdo
    counters[:comparisons] += 1
    if left <= n && arr[left] > arr[largest]
        largest = left
    end

    # Comparar con el hijo derecho
    counters[:comparisons] += 1
    if right <= n && arr[right] > arr[largest]
        largest = right
    end

    # Si el mayor no es la raíz, intercambiar y seguir ajustando
    if largest != i
        arr[i], arr[largest] = arr[largest], arr[i]
        counters[:swaps] += 1
        heapify!(arr, n, largest, counters)
    end
end

# Implementación de HeapSort - Índices basados en 1
function heapsort!(arr)
    n = length(arr)
    counters = Dict(:comparisons => 0, :swaps => 0)  # Contador de operaciones

    # Construir el max-heap
    for i in n ÷ 2:-1:1
        heapify!(arr, n, i, counters)
    end

    # Extraer elementos del heap uno por uno
    for i in n:-1:2
        arr[1], arr[i] = arr[i], arr[1]  # Mover la raíz al final
        counters[:swaps] += 1
        heapify!(arr, i - 1, 1, counters)
    end

    return counters
end

# Función para cargar y ordenar el archivo JSON con múltiples claves
function eval_heap(p::String)
    # Construir la ruta del archivo con el argumento p
    ruta_archivo = joinpath(homedir(),  raw"C:\Users\josea\Downloads\listas-posteo-con-perturbaciones", "listas-posteo-con-perturbaciones-p=" * p * ".json")

    # Cargar el archivo JSON
    datos = JSON.parsefile(ruta_archivo)
    contador = 0
    contador2= 0

    # Procesar cada clave del JSON
    for (clave, arr) in datos

        counters = heapsort!(arr)
        contador += counters[:comparisons]
        contador2 += counters[:swaps]
    end
println("Comparaciones: ", contador)
println("Intercambios: ", contador2)
end

eval_heap (generic function with 1 method)

# Ejecutar el programa para p=016

@time begin
    eval_heap("016")
end
# Se ejecuta dos veces para no considerar el tiempo de compilación 
@time begin
    eval_heap("016")
end

Comparaciones: 4830498
Intercambios: 2319348
  0.487989 seconds (254.80 k allocations: 10.922 MiB, 29.39% gc time, 23.16% compilation time)
Comparaciones: 4830498
Intercambios: 2319348
  0.207115 seconds (191.69 k allocations: 7.581 MiB, 5.55% gc time)

# Ejecutar el programa para p=032

@time begin
    eval_heap("032")
end
# Se ejecuta dos veces para no considerar el tiempo de compilación 
@time begin
    eval_heap("032")
end

Comparaciones: 4826432
Intercambios: 2317315
  0.181611 seconds (191.68 k allocations: 7.581 MiB)
Comparaciones: 4826432
Intercambios: 2317315
  0.245424 seconds (191.68 k allocations: 7.581 MiB, 1.72% gc time)

# Ejecutar el programa para p=064

@time begin
    eval_heap("064")
end
# Se ejecuta dos veces para no considerar el tiempo de compilación 
@time begin
    eval_heap("064")
end

Comparaciones: 4820024
Intercambios: 2314111
  0.214752 seconds (191.55 k allocations: 7.572 MiB, 2.19% gc time)
Comparaciones: 4820024
Intercambios: 2314111
  0.213742 seconds (191.67 k allocations: 7.580 MiB, 0.48% gc time)

# Ejecutar el programa para p=128

@time begin
    eval_heap("128")
end
# Se ejecuta dos veces para no considerar el tiempo de compilación 
@time begin
    eval_heap("128")
end

Comparaciones: 4805308
Intercambios: 2306753
  0.194435 seconds (191.55 k allocations: 7.572 MiB, 0.76% gc time)
Comparaciones: 4805308
Intercambios: 2306753
  0.180788 seconds (191.67 k allocations: 7.581 MiB, 0.63% gc time)

# Ejecutar el programa para p=256

@time begin
    eval_heap("256")
end
# Se ejecuta dos veces para no considerar el tiempo de compilación 
@time begin
    eval_heap("256")
end

Comparaciones: 4783464
Intercambios: 2295831
  0.181757 seconds (191.56 k allocations: 7.572 MiB, 0.87% gc time)
Comparaciones: 4783464
Intercambios: 2295831
  0.176678 seconds (191.68 k allocations: 7.581 MiB, 0.79% gc time)

# Ejecutar el programa para p=512

@time begin
    eval_heap("512")
end
# Se ejecuta dos veces para no considerar el tiempo de compilación 
@time begin
    eval_heap("512")
end

Comparaciones: 4752240
Intercambios: 2280219
  0.182473 seconds (191.55 k allocations: 7.572 MiB, 0.80% gc time)
Comparaciones: 4752240
Intercambios: 2280219
  0.182040 seconds (191.67 k allocations: 7.580 MiB, 0.72% gc time)

Mergesort

El algoritmo Mergesort se basa en una operación simple llamada mezcla (merging), que consiste en combinar dos arreglos ordenados para formar un único arreglo ordenado. Este proceso da lugar a un método recursivo sencillo: para ordenar un arreglo, se divide en dos mitades, se ordenan recursivamente ambas mitades y luego se combinan los resultados mediante la operación de mezcla (Sedgewick & Wayne, 2011). Uno de los principales atractivos de Mergesort es que garantiza ordenar cualquier arreglo de \(n\) elementos en un tiempo proporcional a \(O(n \log n)\) Sin embargo, su desventaja principal es que requiere espacio adicional proporcional a \(n\) (Sedgewick & Wayne, 2011).

Complejidad temporal:

\(O(n \log n)\) en todos los casos.

using JSON
using Dates

# Función para combinar dos subarreglos ordenados
function merge!(arr, left, mid, right, counters)
    # Tamaños de los subarreglos
    n1 = mid - left + 1
    n2 = right - mid

    # Crear arreglos temporales
    L = copy(arr[left:left+n1-1])
    R = copy(arr[mid+1:mid+n2])

    i = 1  # Índice para L
    j = 1  # Índice para R
    k = left  # Índice para arr

    # Combinar los subarreglos
    while i <= n1 && j <= n2
        counters[:comparisons] += 1
        if L[i] <= R[j]
            arr[k] = L[i]
            i += 1
        else
            arr[k] = R[j]
            j += 1
        end
        counters[:movements] += 1
        k += 1
    end

    # Copiar elementos restantes de L, si los hay
    while i <= n1
        arr[k] = L[i]
        counters[:movements] += 1
        i += 1
        k += 1
    end

    # Copiar elementos restantes de R, si los hay
    while j <= n2
        arr[k] = R[j]
        counters[:movements] += 1
        j += 1
        k += 1
    end
end

# Implementación de MergeSort
function mergesort!(arr, left, right, counters)
    if left < right
        mid = (left + right) ÷ 2
        mergesort!(arr, left, mid, counters)
        mergesort!(arr, mid + 1, right, counters)
        merge!(arr, left, mid, right, counters)
    end
end

# Wrapper para inicializar MergeSort con contadores
function mergesort_wrapper!(arr)
    counters = Dict(:comparisons => 0, :movements => 0)
    mergesort!(arr, 1, length(arr), counters)
    return counters
end

# Cargar y ordenar el archivo JSON con múltiples claves
function eval_merge(p::String)
    # Construir la ruta del archivo con el argumento p
    ruta_archivo = joinpath(homedir(),  raw"C:\Users\josea\Downloads\listas-posteo-con-perturbaciones", "listas-posteo-con-perturbaciones-p=" * p * ".json")

    # Cargar el archivo JSON
    datos = JSON.parsefile(ruta_archivo)
    contador = 0
    contador2= 0

    # Procesar cada clave del JSON
    for (clave, arr) in datos

        counters = mergesort_wrapper!(arr)
        contador += counters[:comparisons]
        contador2 += counters[:movements]
    end
println("Comparaciones: ", contador)
println("Intercambios: ", contador2)
end

eval_merge (generic function with 1 method)

# Ejecutar el programa para p=016

@time begin
    eval_merge("016")
end
# Se ejecuta dos veces para no considerar el tiempo de compilación 
@time begin
    eval_merge("016")
end

Comparaciones: 1572444
Intercambios: 2367713
  0.232683 seconds (1.39 M allocations: 77.256 MiB, 12.19% gc time, 26.26% compilation time)
Comparaciones: 1572444
Intercambios: 2367713
  0.442377 seconds (1.34 M allocations: 75.157 MiB, 69.89% gc time)

# Ejecutar el programa para p=032

@time begin
    eval_merge("032")
end
# Se ejecuta dos veces para no considerar el tiempo de compilación 
@time begin
    eval_merge("032")
end

Comparaciones: 1669236
Intercambios: 2367713
  0.169852 seconds (1.34 M allocations: 75.146 MiB, 14.78% gc time)
Comparaciones: 1669236
Intercambios: 2367713
  0.184990 seconds (1.34 M allocations: 75.156 MiB, 10.29% gc time)

# Ejecutar el programa para p=064

@time begin
    eval_merge("064")
end
# Se ejecuta dos veces para no considerar el tiempo de compilación 
@time begin
    eval_merge("064")
end

Comparaciones: 1755354
Intercambios: 2367713
  0.188880 seconds (1.34 M allocations: 75.146 MiB, 23.22% gc time)
Comparaciones: 1755354
Intercambios: 2367713
  0.259645 seconds (1.34 M allocations: 75.155 MiB, 40.08% gc time)

# Ejecutar el programa para p=128

@time begin
    eval_merge("128")
end
# Se ejecuta dos veces para no considerar el tiempo de compilación 
@time begin
    eval_merge("128")
end

Comparaciones: 1844035
Intercambios: 2367713
  0.169888 seconds (1.34 M allocations: 75.146 MiB, 12.87% gc time)
Comparaciones: 1844035
Intercambios: 2367713
  0.193641 seconds (1.34 M allocations: 75.155 MiB, 24.28% gc time)

# Ejecutar el programa para p=256

@time begin
    eval_merge("256")
end
# Se ejecuta dos veces para no considerar el tiempo de compilación 
@time begin
    eval_merge("256")
end

Comparaciones: 1915028
Intercambios: 2367713
  0.281777 seconds (1.34 M allocations: 75.146 MiB, 41.46% gc time)
Comparaciones: 1915028
Intercambios: 2367713
  0.174015 seconds (1.34 M allocations: 75.155 MiB, 14.61% gc time)

# Ejecutar el programa para p=512

@time begin
    eval_merge("512")
end
# Se ejecuta dos veces para no considerar el tiempo de compilación 
@time begin
    eval_merge("512")
end

Comparaciones: 1975697
Intercambios: 2367713
  0.208104 seconds (1.34 M allocations: 75.146 MiB, 24.63% gc time)
Comparaciones: 1975697
Intercambios: 2367713
  0.261640 seconds (1.34 M allocations: 75.155 MiB, 40.85% gc time)

Quicksort

Quicksort es un algoritmo de ordenación ampliamente utilizado que, a pesar de tener un tiempo de ejecución en el peor caso de \(O(n^2)\) para un array de n elementos, es una de las opciones más eficientes en la práctica. Esto se debe a que su tiempo de ejecución promedio es \(O(n \log n)\), con constantes ocultas en la notación \(O(n \log n)\) muy pequeñas, lo que lo hace extremadamente rápido en la mayoría de los casos (Cormen et al. 2022). Además, Quicksort tiene la ventaja de ser un algoritmo in situ, es decir, ordena los elementos directamente en el array original sin requerir espacio adicional significativo. Esta característica lo hace especialmente adecuado para entornos de memoria virtual Funcionamiento (Cormen et al. 2022). Al igual que Mergesort, también utiliza un enfoque “divide y vencerás”. Selecciona un elemento pivote y reorganiza la lista de manera que los elementos menores que el pivote estén a su izquierda y los mayores a su derecha. Luego, repite el proceso recursivamente para las sublistas (Cormen et al. 2022).

Aunque Quicksort no es adaptativo por diseño (es decir, no aprovecha el orden existente en la entrada), se han desarrollado versiones adaptativas de Quicksort, como CKsort, que utiliza una técnica de división específica (Cook-Kim division) para mejorar su rendimiento en secuencias casi ordenadas(Estivill-Castro & Wood, 1992).

Complejidad temporal:

Peor caso:

\(O(n^2)\) ( depende del pivote)

Caso promedio:

\(O(n \log n)\)

using JSON
using Dates

# Función para particionar el arreglo usando el último elemento como pivote
function partition!(arr, low, high, counters)
    pivot = arr[high]
    i = low - 1  # Índice del elemento menor

    for j in low:high-1
        counters[:comparisons] += 1
        if arr[j] <= pivot
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
            counters[:swaps] += 1
        end
    end

    # Colocar el pivote en su posición correcta
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    counters[:swaps] += 1
    return i + 1
end

# Implementación de QuickSort
function quicksort!(arr, low, high, counters)
    if low < high
        # Obtener el índice de partición
        pi = partition!(arr, low, high, counters)
        
        # Ordenar las particiones recursivamente
        quicksort!(arr, low, pi - 1, counters)
        quicksort!(arr, pi + 1, high, counters)
    end
end

# Wrapper para inicializar QuickSort con contadores
function quicksort_wrapper!(arr)
    counters = Dict(:comparisons => 0, :swaps => 0)
    quicksort!(arr, 1, length(arr), counters)
    return counters
end

# Cargar y ordenar el archivo JSON con múltiples claves
function eval_quick(p::String)
    # Construir la ruta del archivo con el argumento p
    ruta_archivo = joinpath(homedir(),  raw"C:\Users\josea\Downloads\listas-posteo-con-perturbaciones", "listas-posteo-con-perturbaciones-p=" * p * ".json")

    # Cargar el archivo JSON
    datos = JSON.parsefile(ruta_archivo)
    contador = 0
    contador2= 0

    # Procesar cada clave del JSON
    for (clave, arr) in datos

        counters = quicksort_wrapper!(arr)
        contador += counters[:comparisons]
        contador2 += counters[:swaps]
    end
println("Comparaciones: ", contador)
println("Intercambios: ", contador2)
end

eval_quick (generic function with 1 method)

# Ejecutar el programa para p=016

@time begin
    eval_quick("016")
end
# Se ejecuta dos veces para no considerar el tiempo de compilación 
@time begin
    eval_quick("016")
end

Comparaciones: 238991206
Intercambios: 132394039
  8.545927 seconds (219.99 k allocations: 8.957 MiB, 0.11% gc time, 0.43% compilation time)
Comparaciones: 238991206
Intercambios: 132394039
  8.226709 seconds (191.67 k allocations: 7.581 MiB, 0.07% gc time)

# Ejecutar el programa para p=032

@time begin
    eval_quick("032")
end
# Se ejecuta dos veces para no considerar el tiempo de compilación 
@time begin
    eval_quick("032")
end

Comparaciones: 155831691
Intercambios: 109338692
  5.753984 seconds (191.55 k allocations: 7.572 MiB, 0.09% gc time)
Comparaciones: 155831691
Intercambios: 109338692
  5.646577 seconds (191.67 k allocations: 7.581 MiB, 0.01% gc time)

# Ejecutar el programa para p=064

@time begin
    eval_quick("064")
end
# Se ejecuta dos veces para no considerar el tiempo de compilación 
@time begin
    eval_quick("064")
end

Comparaciones: 100831274
Intercambios: 78513669
  3.923298 seconds (191.56 k allocations: 7.572 MiB, 2.24% gc time)
Comparaciones: 100831274
Intercambios: 78513669
  3.760600 seconds (191.68 k allocations: 7.581 MiB)

# Ejecutar el programa para p=128

@time begin
    eval_quick("128")
end
# Se ejecuta dos veces para no considerar el tiempo de compilación 
@time begin
    eval_quick("128")
end

Comparaciones: 28777425
Intercambios: 16890882
  1.128812 seconds (191.55 k allocations: 7.572 MiB, 0.28% gc time)
Comparaciones: 28777425
Intercambios: 16890882
  1.055082 seconds (191.68 k allocations: 7.581 MiB, 0.42% gc time)

# Ejecutar el programa para p=256

@time begin
    eval_quick("256")
end
# Se ejecuta dos veces para no considerar el tiempo de compilación 
@time begin
    eval_quick("256")
end

Comparaciones: 18675607
Intercambios: 6596669
  0.638336 seconds (191.68 k allocations: 7.580 MiB)
Comparaciones: 18675607
Intercambios: 6596669
  0.625922 seconds (191.67 k allocations: 7.581 MiB, 0.29% gc time)

# Ejecutar el programa para p=512

@time begin
    eval_quick("512")
end
# Se ejecuta dos veces para no considerar el tiempo de compilación 
@time begin
    eval_quick("512")
end

Comparaciones: 11725369
Intercambios: 7020554
  0.445251 seconds (191.55 k allocations: 7.572 MiB, 0.18% gc time)
Comparaciones: 11725369
Intercambios: 7020554
  0.461213 seconds (191.68 k allocations: 7.581 MiB, 0.42% gc time)

Bubblesort

Funcionamiento: Compara pares de elementos adyacentes y los intercambia si están en el orden incorrecto. Este proceso se repite hasta que no se necesiten más intercambios. Es un algortimo adaptativo ya que es sensible al orden preexistente del arreglo.

Complejidad temporal:

Peor caso:

\(O(n^2)\)

Mejor caso:

\(O(n)\) (si la lista ya está ordenada)

using JSON
using Dates

# Implementación de BubbleSort
function bubblesort!(arr)
    n = length(arr)
    counters = Dict(:comparisons => 0, :swaps => 0)  # Contador de operaciones
    swapped = false

    for i in 1:n-1
        swapped = false
        for j in 1:n-i
            counters[:comparisons] += 1
            if arr[j] > arr[j+1]
                arr[j], arr[j+1] = arr[j+1], arr[j]
                counters[:swaps] += 1
                swapped = true
            end
        end
        # Si no hubo intercambios en esta pasada, el arreglo ya está ordenado
        if !swapped
            break
        end
    end

    return counters
end

# Cargar y ordenar el archivo JSON con múltiples claves
function eval_bubble(p::String)
    # Construir la ruta del archivo con el argumento p
    ruta_archivo = joinpath(homedir(),  raw"C:\Users\josea\Downloads\listas-posteo-con-perturbaciones", "listas-posteo-con-perturbaciones-p=" * p * ".json")

    # Cargar el archivo JSON
    datos = JSON.parsefile(ruta_archivo)
    contador = 0
    contador2= 0

    # Procesar cada clave del JSON
    for (clave, arr) in datos

        counters = bubblesort!(arr)
        contador += counters[:comparisons]
        contador2 += counters[:swaps]
    end
println("Comparaciones: ", contador)
println("Intercambios: ", contador2)
end

eval_bubble (generic function with 1 method)

# Ejecutar el programa para p=016

@time begin
    eval_bubble("016")
end
# Se ejecuta dos veces para no considerar el tiempo de compilación 
@time begin
    eval_bubble("016")
end

Comparaciones: 1239423690
Intercambios: 1951394
 35.737679 seconds (217.12 k allocations: 8.829 MiB, 0.01% gc time, 0.08% compilation time)
Comparaciones: 1239423690
Intercambios: 1951394
 35.802825 seconds (191.68 k allocations: 7.581 MiB, 0.02% gc time)

# Ejecutar el programa para p=032

@time begin
    eval_bubble("032")
end
# Se ejecuta dos veces para no considerar el tiempo de compilación 
@time begin
    eval_bubble("032")
end

Comparaciones: 1230370900
Intercambios: 4024541
 35.331065 seconds (191.56 k allocations: 7.572 MiB, 0.02% gc time)
Comparaciones: 1230370900
Intercambios: 4024541
 34.921086 seconds (191.69 k allocations: 7.581 MiB, 0.00% gc time)

# Ejecutar el programa para p=064

@time begin
    eval_bubble("064")
end
# Se ejecuta dos veces para no considerar el tiempo de compilación 
@time begin
    eval_bubble("064")
end

Comparaciones: 1290738623
Intercambios: 7686291
 36.387142 seconds (191.56 k allocations: 7.572 MiB, 0.00% gc time)
Comparaciones: 1290738623
Intercambios: 7686291
 40.992388 seconds (191.68 k allocations: 7.581 MiB, 0.00% gc time)

# Ejecutar el programa para p=128

@time begin
    eval_bubble("128")
end
# Se ejecuta dos veces para no considerar el tiempo de compilación 
@time begin
    eval_bubble("128")
end

Comparaciones: 1302028794
Intercambios: 14702835
 37.817800 seconds (191.56 k allocations: 7.572 MiB, 0.00% gc time)
Comparaciones: 1302028794
Intercambios: 14702835
 37.637456 seconds (191.68 k allocations: 7.581 MiB, 0.00% gc time)

# Ejecutar el programa para p=256

@time begin
    eval_bubble("256")
end
# Se ejecuta dos veces para no considerar el tiempo de compilación 
@time begin
    eval_bubble("256")
end

Comparaciones: 1306702501
Intercambios: 26925715
 37.682648 seconds (191.55 k allocations: 7.572 MiB, 0.00% gc time)
Comparaciones: 1306702501
Intercambios: 26925715
 37.965850 seconds (191.68 k allocations: 7.581 MiB, 0.00% gc time)

# Ejecutar el programa para p=512

@time begin
    eval_bubble("512")
end
# Se ejecuta dos veces para no considerar el tiempo de compilación 
@time begin
    eval_bubble("512")
end

Comparaciones: 1308817164
Intercambios: 48656147
 38.155156 seconds (191.54 k allocations: 7.572 MiB, 0.00% gc time)
Comparaciones: 1308817164
Intercambios: 48656147
 38.810830 seconds (191.67 k allocations: 7.581 MiB, 0.00% gc time)

Resultados y discusión

Tabla 1. Número de comparaciones por algoritmo de ordenamiento

\[\begin{array}{|c|c|c|c|c|} \hline \textbf{Perturbación} & \textbf{Heapsort} & \textbf{Mergesort} & \textbf{Quicksort} & \textbf{Bubblesort} \\ \hline 16 & 4,830,498 & 1,572,444 & 238,991,206 & 1,239,423,690 \\ 32 & 4,826,432 & 1,669,236 & 155,831,691 & 1,230,370,900 \\ 64 & 4,820,024 & 1,755,354 & 100,831,274 & 1,290,738,623 \\ 128 & 4,805,308 & 1,844,035 & 28,777,425 & 1,302,028,794 \\ 256 & 4,783,464 & 1,915,028 & 18,675,607 & 1,306,702,501 \\ 512 & 4,752,240 & 1,975,697 & 11,725,369 & 1,308,817,164 \\ \hline \end{array}\]

De la tabla 1 podemos observar que tanto Mergesort como Heapsort, mantuvieron números de comparaciones muy similares, debemos recordar que estos dos algoritmos de ordenamiento tienen complejidades de \(O(n \log n)\) en todos los casos, por lo que sin importar el nivel de perturbación en cada archivo las comparaciones que realizó el algoritmo fueron prácticamente iguales en cada caso.

En el caso de Quicksort, su complejidad depende del pivote seleccionado, para el experimento se eligió el último elemento de cada lista de tal forma que durante la partición, el arreglo se reorganiza de manera que los elementos menores que el pivote queden a la izquierda y los elementos mayores queden a la derecha, por lo que si el arreglo está casi ordenado, el pivote será el elemento más grande. Como resultado, la partición no será eficiente y hará que la complejidad del algortimo tienda a \(O(n^2)\). Esto es verificable en la tabla de resultados donde se muestra que mientras menos desordenados estaban los arreglos el número de comparaciones fue mayor.

Finalmente para Bubblesort, se puede apreciar que de todos los algoritmos fue el que mayor número de comparaciones requirió, debemos también recordar que su complejidad varía entre \(O(n)\) y \(O(n^2)\), y al ser un algortimo adaptativo se vuelve sensible al orden preexistente en los arreglos a ordenar. Esto se puede verificar en la tabla en la que podemos apreciar la tendencia clara a aumentar el número de comparaciones conforme aumenta el desorden

Tabla 2. Número de intercambios por algoritmo de ordenamiento

\[\begin{array}{|c|c|c|c|c|} \hline \textbf{Perturbación} & \textbf{Heapsort} & \textbf{Mergesort} & \textbf{Quicksort} & \textbf{Bubblesort} \\ \hline 16 & 2,319,348 & 2,367,713 & 132,394,039 & 1,951,394 \\ 32 & 2,317,315 & 2,367,713 & 109,338,692 & 4,024,541 \\ 64 & 2,314,111 & 2,367,713 & 78,513,669 & 7,686,291 \\ 128 & 2,306,753 & 2,367,713 & 16,890,882 & 14,702,835 \\ 256 & 2,295,831 & 2,367,713 & 6,596,669 & 26,925,715 \\ 512 & 2,280,219 & 2,367,713 & 7,020,554 & 48,656,147 \\ \hline \end{array}\]

La tabla 2 se puede interpretar bajo la misma lógica de la tabla anterior los algoritmos de complejidad constante \(O(n \log n)\), Heapsort y Mergesort manttuvieron valores de intercambios constantes, en particular Mergesort que mantuvo exactamente el mismo número para cada caso. Quicksort al haber elegido el último elemento como pivote muestra un descenso de los intercambios necesarios conforme las entradas son más desordenadas. Finalmente Bubblesort al ser un algoritmo adaptativo muestra un marcado incremento en el número de intercambios necesarios conforme las entradas se tienen un mayor grado de perturbación.

Tabla 3. Tiempos de ejecución por algoritmo de ordenamiento en segundos

\[\begin{array}{|c|c|c|c|c|} \hline \textbf{Perturbación} & \textbf{Heapsort} & \textbf{Mergesort} & \textbf{Quicksort} & \textbf{Bubblesort} \\ \hline 16 & 0.207115 & 0.442377 & 8.226709 & 35.802825 \\ 32 & 0.245424 & 0.184990 & 5.646577 & 34.921086 \\ 64 & 0.213742 & 0.259645 & 3.760600 & 40.992388 \\ 128 & 0.180788 & 0.193641 & 1.055082 & 37.637456 \\ 256 & 0.176678 & 0.174015 & 0.625922 & 37.965850 \\ 512 & 0.182040 & 0.261640 & 0.461213 & 38.810830 \\ \hline \end{array}\]

Finalmente de la tabla 3 podemos observar que los mejores tiempos de ejecución fueron para los algortimos de complejidad constante; Heapsort y Mergesort. Quicksort mostró tiempos de ejecución de un orden superior e la mayoría de los casos, pero en los casos de mayor desorden los tiempos son comparables. Finalmente Bubblesort mostró tiempos de ejecución de hasta dos ordenes de magnitud mayores, lo que lo convierte en el algoritmo menos eficiente para este experimento.

Conclusiones

En conclusión, los resultados obtenidos y expresados en las tablas comparativas ofrecen una visión clara del rendimiento de los algoritmos evaluados en términos de comparaciones, intercambios y tiempos de ejecución. Tanto Mergesort como Heapsort mostraron un rendimiento bastante constante en cuanto al número de comparaciones, dado que son de complejidad constante \(O(n \log n)\) esto refleja su eficiencia al manejar diferentes niveles de desorden en los datos. Esta eficiencia también se refleja en los tiempos de ejecución observados en la tabla 3, donde ambos algoritmos demostraron ser los más rápidos, con tiempos de ejecución estables y comparables a lo largo de los distintos niveles de desorden.

Por otro lado, Quicksort mostró una mayor variabilidad en su número de comparaciones, especialmente cuando los arreglos estaban casi ordenados. En estos casos, debido a la elección del último elemento como pivote, la partición resultó ineficiente para los casos en los que los arreglos estaaban más ordenados, pero eficiente para aquellos más desordenados, esto también se vio reflejado en sus tiempos de ejecución. Aunque en los casos con mayor desorden, los tiempos de ejecución de Quicksort fueron comparables a los de Mergesort y Heapsort, su desempeño sigue siendo menos predecible y más dependiente del estado inicial de los datos.

Finalmente, Bubblesort fue el algoritmo que requirió el mayor número de comparaciones en todos los casos, lo que también se reflejó en sus tiempos de ejecución. En los experimentos, Bubblesort mostró tiempos de ejecución de hasta dos órdenes de magnitud mayores que los de los otros algoritmos, lo que lo convierte en el algoritmo menos eficiente de todos en este experimento.

En resumen, los resultados destacan la superioridad de Mergesort y Heapsort tanto en términos de eficiencia en el número de comparaciones como en tiempos de ejecución, mientras que Quicksort, aunque competitivo en ciertos escenarios, puede ser sensible al desorden inicial de los datos, y Bubblesort sigue siendo el menos eficiente en especial para entradas con con mucho desorden preexistente.

Bibliografía

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022). Introduction to Algorithms (2nd ed.). MIT Press.

Estivill-Castro, V., & Wood, D. (1992). A survey of adaptive sorting algorithms. ACM Computing Surveys, 24(4), 441-476. https://doi.org/10.1145/146370.146381

Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Pearson Education, Inc.