PRÁCTICA 3A: REPORTE ESCRITO. EXPERIMENTOS Y ANÁLISIS DE ALGORITMOS DE ORDENAMIENTO.¶

PROFESOR: DR. ERIC SADIT TÉLLEZ AVILA

ESTUDIANTE: EDGAR SANTIAGO GONZALEZ MARTINEZ

Introducción¶

Esta práctica comparamos cinco algoritmos de ordenamiento (Bubble Sort, Quicksort, Heapsort, Mergesort y Skip List Sort) sobre los archivos p016, p032, p064, p128, p256 y p512, con el objetivo de contrastar la teoría con observaciones experimentales en datos reales. Los detalles de cada método se presentan más adelante.

Para cada algoritmo se registran tres métricas: número de comparaciones, movimientos y tiempo de ejecución. Estas medidas permiten evaluar no solo la complejidad asintótica, sino también las constantes ocultas y el impacto práctico.

Bajo el modelo de ordenamiento por comparación, todo algoritmo requiere al menos $\Omega(n \log n)$ comparaciones, pues ordenar $n$ elementos implica distinguir entre $n!$ permutaciones. Por la aproximación de Stirling, $\log_2(n!) \in \Theta(n \log n)$.

Conexión de Google Drive con Google Colab¶

Como primer procedimiento, se conecta Google Drive con Google Colab para poder acceder a los archivos almacenados en la nube.

La instrucción from google.colab import drive permite importar el módulo drive, el cual posibilita que Colab interactúe con Google Drive. El comando drive.mount('/content/drive') monta Google Drive en la carpeta /content/drive. Al ejecutarlo, Colab solicitará un permiso de acceso. Una vez concedido, los archivos estarán disponibles para lectura y escritura dentro del notebook.

In [4]:
# Cargar Google Drive
from google.colab import drive
drive.mount('/content/drive')

Drive already mounted at /content/drive; to attempt to forcibly remount, call drive.mount("/content/drive", force_remount=True).

Extracción de archivos desde Google Drive¶

En esta parte se extraen los identificadores de los archivos almacenado en Google Drive y se convierten en un arreglo de NumPy listo para los algoritmos de ordenamiento. Se define la ruta del JSON (path) y la clave KEY = "reunion" que, si el archivo está estructurado como diccionario, indica dónde está la lista de IDs.

El archivo se abre con codificación UTF-8 y se parsea con json.load, obteniendo un objeto de Python. A partir de ello se construye archivos con np.asarray.

El mismo procedimiento se realiza para todos los archivos (p=016, p=032, p=064, p=128, p=256, p=512), cambiando únicamente la ruta del archivo y generando los arreglos correspondientes.

In [9]:
# Extraer los datos del archivo p016
path = "/content/drive/MyDrive/MCDI/3A_AdA/listas-posteo-con-perturbaciones/listas-posteo-con-perturbaciones-p=016.json"
KEY = "reunion"  # la clave que contiene la lista en tu JSON
with open(path, encoding="utf-8") as f:
    d = json.load(f)
archive_016 = np.asarray(d[KEY] if isinstance(d, dict) else d, dtype=np.int64)

# Extraer los datos del archivo p032
path = "/content/drive/MyDrive/MCDI/3A_AdA/listas-posteo-con-perturbaciones/listas-posteo-con-perturbaciones-p=032.json"
KEY = "reunion"  # clave que contiene la lista en el JSON
with open(path, encoding="utf-8") as f:
    d = json.load(f)
archive_032 = np.asarray(d[KEY] if isinstance(d, dict) else d, dtype=np.int64)

# Extraer los datos del archivo p064
path = "/content/drive/MyDrive/MCDI/3A_AdA/listas-posteo-con-perturbaciones/listas-posteo-con-perturbaciones-p=064.json"
KEY = "reunion"  # clave que contiene la lista en el JSON
with open(path, encoding="utf-8") as f:
    d = json.load(f)
archive_064 = np.asarray(d[KEY] if isinstance(d, dict) else d, dtype=np.int64)

# Extraer los datos del archivo p128
path = "/content/drive/MyDrive/MCDI/3A_AdA/listas-posteo-con-perturbaciones/listas-posteo-con-perturbaciones-p=128.json"
KEY = "reunion"  # clave que contiene la lista en el JSON
with open(path, encoding="utf-8") as f:
    d = json.load(f)
archive_128 = np.asarray(d[KEY] if isinstance(d, dict) else d, dtype=np.int64)

# Extraer los datos del archivo p256
path = "/content/drive/MyDrive/MCDI/3A_AdA/listas-posteo-con-perturbaciones/listas-posteo-con-perturbaciones-p=256.json"
KEY = "reunion"  # clave que contiene la lista en el JSON
with open(path, encoding="utf-8") as f:
    d = json.load(f)
archive_256 = np.asarray(d[KEY] if isinstance(d, dict) else d, dtype=np.int64)

# Extraer los datos del archivo p512
path = "/content/drive/MyDrive/MCDI/3A_AdA/listas-posteo-con-perturbaciones/listas-posteo-con-perturbaciones-p=512.json"
KEY = "reunion"  # clave que contiene la lista en el JSON
with open(path, encoding="utf-8") as f:
    d = json.load(f)
archive_512 = np.asarray(d[KEY] if isinstance(d, dict) else d, dtype=np.int64)

Impresión de los archivos¶

Este fragmento recorre una lista de tuplas que asocia cada etiqueta de dataset con su arreglo correspondiente. En cada iteración el bucle for desempaqueta la tupla en label y var (el np.ndarray asociado) y, a partir de ahí, imprime un rótulo con la etiqueta y una vista del arreglo, por ejemplo, los primeros 12 elementos).

In [14]:
for label, var in [
    ("p=016", archive_016),
    ("p=032", archive_032),
    ("p=064", archive_064),
    ("p=128", archive_128),
    ("p=256", archive_256),
    ("p=512", archive_512),
]:
    print(f"Archivo {label}:", var[:12])

Archivo p=016: [260 275 294 296 314 317 341 384 457 529 616 630]
Archivo p=032: [260 275 294 296 314 317 341 384 457 529 616 630]
Archivo p=064: [  260   275   294   296   314   317   341  6773   457   529   616 37512]
Archivo p=128: [  260   275 25442   296   314   317 11580   384   457   529   616   630]
Archivo p=256: [  260 43024   294   296 17944   317 17991   384   457   529   616   630]
Archivo p=512: [  260   275   294   296   314 42610   341   384   457   529 15293   630]
In [13]:
print(len(archive_016))
print(len(archive_032))
print(len(archive_064))
print(len(archive_128))
print(len(archive_256))
print(len(archive_512))

3080
3080
3080
3080
3080
3080

Paqueterías usadas¶

Se importan: time, random, json, numpy as np y pandas as pd.

  • time — Cronometraje con perf_counter() en funciones *_count_timed; produce time_ms.
  • random — Aleatoriedad (con seed) para el pivote en quicksort_count y los niveles en skiplist_sort_count_timed.
  • json — Carga de datasets .json con json.load(...) y acceso por KEY antes de ejecutar los algoritmos.
  • numpy (np) — Interoperación con np.ndarray (convertir a lista y devolver np.array preservando dtype); verificación con np.sort y np.array_equal.
  • pandas (pd) — Consolidación de métricas en un DataFrame para comparar comparisons, swaps/writes y time_ms.
In [8]:
# Imports necesarios
import time
import random
import json
import numpy as np
import pandas as pd

Algoritmos de ordenamiento¶

Bubble sort¶

Tomado de Cormen et al. (2022), este procedimiento mantiene la lógica clásica de Bubble Sort y se añade mediciones. Primero copia la entrada a una lista a. Inicializa contadores de comparaciones (comps) e intercambios (swaps) y arranca el cronómetro con time.perf_counter(). Recorre el arreglo con dos bucles anidados: en cada iteración del interno incrementa comps y, si encuentra un par desordenado (a[j] > a[j+1]), realiza el swap y aumenta swaps. Al finalizar calcula el tiempo en milisegundos (ms) y devuelve la versión ordenada como np.array, junto con comps, swaps y ms. El comportamiento del algoritmo sigue siendo estable, opera in-place sobre la copia, usa espacio extra $O(1)$ y su costo temporal es $O(n^2)$; lo añadido es únicamente la instrumentación para comparar rendimientos.

In [ ]:
def bubble_sort_count(arr):
    a = arr.tolist() if isinstance(arr, np.ndarray) else list(arr)
    n = len(a)
    comps = swaps = 0
    t0 = time.perf_counter()
    for i in range(n - 1):
        for j in range(n - 1 - i):
            comps += 1
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swaps += 1
    ms = (time.perf_counter() - t0) * 1000
    return np.array(a, dtype=arr.dtype if isinstance(arr, np.ndarray) else None), comps, swaps, ms

Quick Sort¶

Tomado de Cormen et al. (2022), se parte de la variante con pivote aleatorio y partición tipo Lomuto: el pivote se mueve a A[high], se mantiene un índice i para los elementos menores que el pivote y se recorre j de low a high-1; cuando A[j] < piv se intercambia con A[i] y se avanza i. Al final el pivote se coloca en A[i] y se aplica recursión sobre los subarreglos izquierdo y derecho. En expectativa el tiempo es $O(n \log n)$; el peor caso es $O(n^2)$; el espacio extra es $O(1)$ (más el stack), y no es estable.

En esta práctica se utiliza quicksort_count(arr, seed=183), que añade instrumentación sin cambiar la lógica: fija una semilla para reproducibilidad, trabaja sobre una copia de la entrada, cuenta comparaciones (comps) y swaps (swaps) —incluyendo el swap al mover el pivote y los intercambios con la zona “menor”— y cronometra con time.perf_counter() (milisegundos, ms). Devuelve el arreglo ordenado (preservando dtype si la entrada era np.ndarray) junto con comps, swaps y ms.

In [ ]:
def quicksort_count(arr, seed=183):
    random.seed(seed)
    a = arr.tolist() if isinstance(arr, np.ndarray) else list(arr)
    comps = swaps = 0

    def partition(lo, hi):
        nonlocal comps, swaps, a
        piv_idx = random.randint(lo, hi)
        a[piv_idx], a[hi] = a[hi], a[piv_idx]; swaps += 1
        piv = a[hi]
        i = lo
        for j in range(lo, hi):
            comps += 1
            if a[j] < piv:
                a[i], a[j] = a[j], a[i]; swaps += 1
                i += 1
        a[i], a[hi] = a[hi], a[i]; swaps += 1
        return i

    def qs(lo, hi):
        if lo < hi:
            p = partition(lo, hi)
            qs(lo, p - 1)
            qs(p + 1, hi)

    t0 = time.perf_counter()
    qs(0, len(a) - 1)
    ms = (time.perf_counter() - t0) * 1000
    return np.array(a, dtype=arr.dtype if isinstance(arr, np.ndarray) else None), comps, swaps, ms

Herapsort¶

Tomado de la exposición estándar en CLRS (Cormen et al., 2022) y del trabajo original de Williams (1964), este Heapsort ordena in-place en dos fases: primero construye un max-heap con llamadas ascendentes a _heapify desde i = n//2 - 1 hasta 0, dejando el máximo en A[0]; después extrae el máximo iterativamente intercambiando A[0] con A[end], reduciendo el tamaño lógico y restaurando la propiedad de heap con _heapify(A, end, 0). La construcción cuesta $O(n)$; cada extracción $O(\log n)$, para un total $O(n \log n)$. Usa memoria $O(1)$, no es estable y la recursión de _heapify tiene profundidad $O(\log n)$.

La función heapsort_count_timed(arr) añade instrumentación sin cambiar la lógica: trabaja sobre una copia de la entrada, cuenta comparisons (una por cada evaluación > con los hijos en heapify) y swaps (tanto en heapify como en cada extracción A[0] ↔ A[end]), y cronometra el cuerpo del algoritmo con time.perf_counter() (milisegundos). Devuelve (arreglo_ordenado, comparisons, swaps, time_ms); se conservan la complejidad $O(n \log n)$, el uso extra de espacio $O(1)$ y el carácter no estable.

In [ ]:
def heapsort_count_timed(arr):
    a = arr.tolist() if isinstance(arr, np.ndarray) else list(arr)
    n = len(a)
    comparisons = 0
    swaps = 0
    def heapify(n, i):
        nonlocal comparisons, swaps, a
        largest = i
        l = 2*i + 1
        r = 2*i + 2
        if l < n:
            comparisons += 1
            if a[l] > a[largest]:
                largest = l
        if r < n:
            comparisons += 1
            if a[r] > a[largest]:
                largest = r

        if largest != i:
            a[i], a[largest] = a[largest], a[i]
            swaps += 1
            heapify(n, largest)
    t0 = time.perf_counter()
    for i in range(n//2 - 1, -1, -1):
        heapify(n, i)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        swaps += 1
        heapify(end, 0)
    ms = (time.perf_counter() - t0) * 1000
    return np.array(a, dtype=arr.dtype if isinstance(arr, np.ndarray) else None), comparisons, swaps, ms

Mergesort¶

Basado en la presentación estándar (von Neumann, 1945; CLRS; Knuth), Merge Sort ordena por divide y vencerás: divide en mitades y luego fusiona en un paso lineal usando un búfer auxiliar. Es estable, cuesta $O(n \log n)$ en promedio/peor caso y requiere $O(n)$ de memoria adicional.

En esta práctica se usa mergesort_count_timed(A), que añade instrumentación sin cambiar la lógica: cuenta comparisons durante la fusión (cada comparación aux[i] vs aux[j]), cuenta writes por cada escritura en la salida a[k] (se reporta como “swaps” para comparabilidad) y cronometra con time.perf_counter() (milisegundos). Devuelve (arreglo_ordenado, comparisons, writes, time_ms) y preserva el dtype si la entrada era np.ndarray.

In [ ]:
def mergesort_count_timed(A):
    a = A.tolist() if isinstance(A, np.ndarray) else list(A)
    n = len(a)
    aux = [None] * n
    comparisons = 0
    writes = 0
    def sort(lo, hi):
        nonlocal comparisons, writes, a, aux
        if lo >= hi:
            return
        mid = (lo + hi) // 2
        sort(lo, mid)
        sort(mid + 1, hi)
        # conteo
        aux[lo:hi+1] = a[lo:hi+1]
        i, j, k = lo, mid + 1, lo
        while i <= mid and j <= hi:
            comparisons += 1
            if aux[i] <= aux[j]:
                a[k] = aux[i]; i += 1
            else:
                a[k] = aux[j]; j += 1
            writes += 1
            k += 1
        while i <= mid:
            a[k] = aux[i]; i += 1; k += 1
            writes += 1
        while j <= hi:
            a[k] = aux[j]; j += 1; k += 1
            writes += 1
    t0 = time.perf_counter()
    sort(0, n - 1)
    ms = (time.perf_counter() - t0) * 1000
    return np.array(a, dtype=A.dtype if isinstance(A, np.ndarray) else None), comparisons, writes, ms

Skip list¶

Basado en Pugh (1990) y exposiciones modernas, este método ordena insertando cada elemento en una Skip List y luego recorriendo el nivel 0 para emitirlos en orden. La altura esperada es $O(\log n)$, cada inserción cuesta $O(\log n)$ en expectativa y el total resulta $O(n \log n)$ con espacio $\Theta(n)$. Al usar <= en la búsqueda, el resultado es estable.

En esta práctica se emplea skiplist_sort_count_timed(A, p=0.5, max_level=32, seed=162), que añade instrumentación sin cambiar la lógica: fija una semilla (seed) para reproducibilidad, copia la entrada, y contabiliza comparaciones (comparisons) al descender por niveles comparando x.next[i].key con la clave, además de escrituras (writes) al re-enlazar punteros (dos por nivel). Se cronometra todo el proceso con time.perf_counter() (milisegundos, time_ms). Devuelve el arreglo ordenado (preservando dtype si la entrada era np.ndarray) junto con comparisons, writes y time_ms. El comportamiento esperado $O(n \log n)$ y la estabilidad se mantiene.

In [ ]:
def skiplist_sort_count_timed(A, p=0.5, max_level=32, seed=162):
    rng = random.Random(seed)
    def random_level():
        lvl = 0
        while rng.random() < p and lvl < max_level:
            lvl += 1
        return lvl

    class _SkipNode:
        __slots__ = ("key", "next")
        def __init__(self, key, level):
            self.key = key
            self.next = [None] * (level + 1)
    head = _SkipNode(None, max_level)
    level = 0
    a = A.tolist() if isinstance(A, np.ndarray) else list(A)
    comparisons = 0
    writes = 0

    t0 = time.perf_counter()

    for key in a:
        update = [None] * (max_level + 1)
        x = head
        for i in range(level, -1, -1):
            while x.next[i] is not None:
                comparisons += 1
                if x.next[i].key <= key:
                    x = x.next[i]
                else:
                    break
            update[i] = x

        lvl = random_level()
        if lvl > level:
            for i in range(level + 1, lvl + 1):
                update[i] = head
            level = lvl

        node = _SkipNode(key, lvl)
        for i in range(lvl + 1):
            node.next[i] = update[i].next[i]; writes += 1
            update[i].next[i] = node;          writes += 1
    out = []
    x = head.next[0]
    while x is not None:
        out.append(x.key)
        x = x.next[0]
    ms = (time.perf_counter() - t0) * 1000
    return np.array(out, dtype=A.dtype if isinstance(A, np.ndarray) else None), comparisons, writes, ms

Evaluación de algoritmos con el Archivo p=016¶

Este bloque se ejecuta las evaluaciones. Primero fija la entrada A como archive_016 y prepara una lista rows para acumular las métricas. Define una batería de algoritmos como pares (nombre, función); en el caso de Skip List usa una lambda para fijar la semilla y asegurar reproducibilidad. En el bucle, cada fn(A) devuelve la salida ordenada (out) y las métricas (comps, swaps_or_writes, ms). Se valida la corrección con assert np.array_equal(out, np.sort(A)), comparando contra la referencia de NumPy. Luego se agrega un renglón a rows con: el dataset ("p016"), el nombre del algoritmo, el tamaño n, el número de comparaciones, los movimientos y el tiempo en milisegundos. Finalmente, pd.DataFrame(rows) construye la tabla df que resume los resultados de todos los algoritmos sobre el mismo arreglo A.

In [ ]:
A = archive_016
rows = []
for name, fn in [
    ("bubblesort", bubble_sort_count),
    ("quicksort",  quicksort_count),
    ("heapsort",   heapsort_count_timed),
    ("mergesort",  mergesort_count_timed),
    ("skiplist",   lambda X: skiplist_sort_count_timed(X, seed=123)),
]:
    out, comps, swaps_or_writes, ms = fn(A)
    assert np.array_equal(out, np.sort(A)), f"{name} no coincide con np.sort"
    rows.append({
        "dataset": "p016",
        "algo": name,
        "n": len(A),
        "comparisons": comps,
        "swaps": swaps_or_writes,
        "time_ms": ms
    })
df = pd.DataFrame(rows)
df
Out[ ]:
dataset algo n comparisons swaps time_ms
0 p016 bubblesort 3080 4741660 25392 794.521485
1 p016 quicksort 3080 41893 22193 14.305161
2 p016 heapsort 3080 64787 35252 24.546448
3 p016 mergesort 3080 23867 35944 15.373446
4 p016 skiplist 3080 47219 12168 23.731101

En p016 (n = 3080), Bubble Sort realiza 4,741,660 comparaciones, 25,392 swaps y tarda ≈0.795 s, confirmando su costo cuadrático. Entre los métodos $O(n \log n)$, Quicksort es el más rápido con ≈14.3 ms y 41,893 comparaciones, seguido de Mergesort con ≈15.4 ms, 23,867 comparaciones y 35,944 writes (reportados en “swaps”). Heapsort queda detrás con ≈24.5 ms, 64,787 comparaciones y 35,252 swaps, y Skip List Sort con ≈23.7 ms, 47,219 comparaciones y 12,168 writes. En conjunto, los $O(n \log n)$ dominan; las diferencias se explican por constantes y modelo de memoria. El gráfico inferior reproduce estos mismos valores de la tabla.

In [ ]:
import matplotlib.pyplot as plt
from matplotlib.ticker import FuncFormatter
import numpy as np

order = ['bubblesort', 'quicksort', 'heapsort', 'mergesort', 'skiplist']
agg = (df.groupby('algo', as_index=False)
         .agg(comparisons=('comparisons','mean'),
              swaps=('swaps','mean'),
              time_ms=('time_ms','mean')))
agg['algo'] = pd.Categorical(agg['algo'], categories=order, ordered=True)
agg = agg.sort_values('algo')

def abbr(x):
    if x >= 1_000_000:
        return f'{x/1_000_000:.1f}M'
    if x >= 1_000:
        return f'{x/1_000:.1f}k'
    return f'{x:.1f}'

fig, axes = plt.subplots(1, 3, figsize=(12, 4), constrained_layout=True)

# Comparaciones
bars = axes[0].bar(agg['algo'], agg['comparisons'])
axes[0].set_title('Comparaciones')
axes[0].yaxis.set_major_formatter(FuncFormatter(lambda v, _: f'{int(v):,}'))
axes[0].tick_params(axis='x', rotation=30)
axes[0].bar_label(bars, labels=[abbr(v) for v in agg['comparisons']], padding=2)
# Intercambios
bars = axes[1].bar(agg['algo'], agg['swaps'])
axes[1].set_title('Intercambios')
axes[1].yaxis.set_major_formatter(FuncFormatter(lambda v, _: f'{int(v):,}'))
axes[1].tick_params(axis='x', rotation=30)
axes[1].bar_label(bars, labels=[abbr(v) for v in agg['swaps']], padding=2)
# Tiempo en ms
bars = axes[2].bar(agg['algo'], agg['time_ms'])
axes[2].set_title('Tiempo')
axes[2].tick_params(axis='x', rotation=30)
axes[2].bar_label(bars, labels=[abbr(v) for v in agg['time_ms']], padding=2)

plt.show()

Evaluación de algoritmos con el Archivo p=032¶

Para el archivo p=032 (n = 3080), Bubble Sort realiza 4,741,660 comparaciones, 80,866 swaps y tarda ≈456.30 ms. Entre los métodos $O(n \log n)$, Quicksort es el más rápido (≈6.72 ms; 39,005 comparaciones), seguido de Mergesort (≈7.84 ms; 24,791 comparaciones y 35,944 writes). Heapsort queda detrás (≈12.87 ms; 64,715 comparaciones) y Skip List Sort (≈13.17 ms; 53,135 comparaciones y 12,168 writes) se ve penalizado por el overhead de punteros. En conjunto, dominan los $O(n \log n)$; las diferencias se explican por constantes y modelo de memoria. El gráfico inferior reproduce estos mismos valores de la tabla.

In [ ]:
A = archive_032
rows = []
for name, fn in [
    ("bubblesort", bubble_sort_count),
    ("quicksort",  quicksort_count),
    ("heapsort",   heapsort_count_timed),
    ("mergesort",  mergesort_count_timed),
    ("skiplist",   lambda X: skiplist_sort_count_timed(X, seed=123)),
]:
    out, comps, swaps_or_writes, ms = fn(A)
    assert np.array_equal(out, np.sort(A)), f"{name} no coincide con np.sort"
    rows.append({
        "dataset": "p032",
        "algo": name,
        "n": len(A),
        "comparisons": comps,
        "swaps": swaps_or_writes,
        "time_ms": ms
    })
df = pd.DataFrame(rows)
df
Out[ ]:
dataset algo n comparisons swaps time_ms
0 p032 bubblesort 3080 4741660 80866 456.298937
1 p032 quicksort 3080 39005 20983 6.721965
2 p032 heapsort 3080 64715 35202 12.872209
3 p032 mergesort 3080 24791 35944 7.839713
4 p032 skiplist 3080 53135 12168 13.170960
In [ ]:
order = ['bubblesort', 'quicksort', 'heapsort', 'mergesort', 'skiplist']
agg = (df.groupby('algo', as_index=False)
         .agg(comparisons=('comparisons','mean'),
              swaps=('swaps','mean'),
              time_ms=('time_ms','mean')))
agg['algo'] = pd.Categorical(agg['algo'], categories=order, ordered=True)
agg = agg.sort_values('algo')

def abbr(x):
    if x >= 1_000_000:
        return f'{x/1_000_000:.1f}M'
    if x >= 1_000:
        return f'{x/1_000:.1f}k'
    return f'{x:.1f}'

fig, axes = plt.subplots(1, 3, figsize=(12, 4), constrained_layout=True)

# Comparaciones
bars = axes[0].bar(agg['algo'], agg['comparisons'])
axes[0].set_title('Comparaciones')
axes[0].yaxis.set_major_formatter(FuncFormatter(lambda v, _: f'{int(v):,}'))
axes[0].tick_params(axis='x', rotation=30)
axes[0].bar_label(bars, labels=[abbr(v) for v in agg['comparisons']], padding=2)
# Intercambios
bars = axes[1].bar(agg['algo'], agg['swaps'])
axes[1].set_title('Intercambios')
axes[1].yaxis.set_major_formatter(FuncFormatter(lambda v, _: f'{int(v):,}'))
axes[1].tick_params(axis='x', rotation=30)
axes[1].bar_label(bars, labels=[abbr(v) for v in agg['swaps']], padding=2)
# Tiempo en ms
bars = axes[2].bar(agg['algo'], agg['time_ms'])
axes[2].set_title('Tiempo')
axes[2].tick_params(axis='x', rotation=30)
axes[2].bar_label(bars, labels=[abbr(v) for v in agg['time_ms']], padding=2)

plt.show()

Evaluación de algoritmos con el Archivo p=064¶

Para el archivo p=064 (n = 3080), Bubble Sort realiza 4,741,660 comparaciones, 124,486 swaps y tarda ≈465.9 ms, manteniéndose como el más lento. Entre los $O(n \log n)$, Quicksort es el más rápido (≈10.85 ms; 40,073 comparaciones), seguido de Mergesort (≈13.62 ms; 26,917 comparaciones y 35,944 writes) y Skip List Sort (≈14.58 ms; 51,285 comparaciones y 12,168 writes). Heapsort queda detrás (≈23.27 ms; 64,654 comparaciones y 35,160 swaps). El gráfico inferior reproduce estos mismos valores de la tabla para comparación visual.

In [ ]:
A = archive_064
rows = []
for name, fn in [
    ("bubblesort", bubble_sort_count),
    ("quicksort",  quicksort_count),
    ("heapsort",   heapsort_count_timed),
    ("mergesort",  mergesort_count_timed),
    ("skiplist",   lambda X: skiplist_sort_count_timed(X, seed=123)),
]:
    out, comps, swaps_or_writes, ms = fn(A)
    assert np.array_equal(out, np.sort(A)), f"{name} no coincide con np.sort"
    rows.append({
        "dataset": "p064",
        "algo": name,
        "n": len(A),
        "comparisons": comps,
        "swaps": swaps_or_writes,
        "time_ms": ms
    })

df = pd.DataFrame(rows)
df
Out[ ]:
dataset algo n comparisons swaps time_ms
0 p064 bubblesort 3080 4741660 124486 465.892737
1 p064 quicksort 3080 40073 20819 10.847561
2 p064 heapsort 3080 64654 35160 23.265947
3 p064 mergesort 3080 26917 35944 13.616630
4 p064 skiplist 3080 51285 12168 14.575142
In [ ]:
order = ['bubblesort', 'quicksort', 'heapsort', 'mergesort', 'skiplist']
agg = (df.groupby('algo', as_index=False)
         .agg(comparisons=('comparisons','mean'),
              swaps=('swaps','mean'),
              time_ms=('time_ms','mean')))
agg['algo'] = pd.Categorical(agg['algo'], categories=order, ordered=True)
agg = agg.sort_values('algo')

def abbr(x):
    if x >= 1_000_000:
        return f'{x/1_000_000:.1f}M'
    if x >= 1_000:
        return f'{x/1_000:.1f}k'
    return f'{x:.1f}'

fig, axes = plt.subplots(1, 3, figsize=(12, 4), constrained_layout=True)

# Comparaciones
bars = axes[0].bar(agg['algo'], agg['comparisons'])
axes[0].set_title('Comparaciones')
axes[0].yaxis.set_major_formatter(FuncFormatter(lambda v, _: f'{int(v):,}'))
axes[0].tick_params(axis='x', rotation=30)
axes[0].bar_label(bars, labels=[abbr(v) for v in agg['comparisons']], padding=2)
# Intercambios
bars = axes[1].bar(agg['algo'], agg['swaps'])
axes[1].set_title('Intercambios')
axes[1].yaxis.set_major_formatter(FuncFormatter(lambda v, _: f'{int(v):,}'))
axes[1].tick_params(axis='x', rotation=30)
axes[1].bar_label(bars, labels=[abbr(v) for v in agg['swaps']], padding=2)
# Tiempo en ms
bars = axes[2].bar(agg['algo'], agg['time_ms'])
axes[2].set_title('Tiempo')
axes[2].tick_params(axis='x', rotation=30)
axes[2].bar_label(bars, labels=[abbr(v) for v in agg['time_ms']], padding=2)

plt.show()

Evaluación de algoritmos con el Archivo p=128¶

Para el archivo p=128 (n = 3080), Bubble Sort realiza 4,741,660 comparaciones, 260,888 swaps y tarda ≈485.85 ms, confirmando su desventaja práctica frente a los $O(n \log n)$. Entre estos, Quicksort es el más rápido (≈7.35 ms; 40,527 comparaciones), seguido de Mergesort (≈8.79 ms; 28,882 comparaciones y 35,944 writes). Heapsort queda detrás (≈22.44 ms; 64,536 comparaciones) y Skip List Sort se sitúa en medio (≈13.80 ms; 60,073 comparaciones y 12,168 writes). El gráfico inferior reproduce estos mismos valores para comparación visual.

In [ ]:
A = archive_128
rows = []
for name, fn in [
    ("bubblesort", bubble_sort_count),
    ("quicksort",  quicksort_count),
    ("heapsort",   heapsort_count_timed),
    ("mergesort",  mergesort_count_timed),
    ("skiplist",   lambda X: skiplist_sort_count_timed(X, seed=123)),
]:
    out, comps, swaps_or_writes, ms = fn(A)
    assert np.array_equal(out, np.sort(A)), f"{name} no coincide con np.sort"
    rows.append({
        "dataset": "128",
        "algo": name,
        "n": len(A),
        "comparisons": comps,
        "swaps": swaps_or_writes,
        "time_ms": ms
    })
df = pd.DataFrame(rows)
df
Out[ ]:
dataset algo n comparisons swaps time_ms
0 128 bubblesort 3080 4741660 260888 485.852285
1 128 quicksort 3080 40527 21263 7.354733
2 128 heapsort 3080 64536 35040 22.439370
3 128 mergesort 3080 28882 35944 8.787886
4 128 skiplist 3080 60073 12168 13.803144
In [ ]:
order = ['bubblesort', 'quicksort', 'heapsort', 'mergesort', 'skiplist']
agg = (df.groupby('algo', as_index=False)
         .agg(comparisons=('comparisons','mean'),
              swaps=('swaps','mean'),
              time_ms=('time_ms','mean')))
agg['algo'] = pd.Categorical(agg['algo'], categories=order, ordered=True)
agg = agg.sort_values('algo')

def abbr(x):
    if x >= 1_000_000:
        return f'{x/1_000_000:.1f}M'
    if x >= 1_000:
        return f'{x/1_000:.1f}k'
    return f'{x:.1f}'

fig, axes = plt.subplots(1, 3, figsize=(12, 4), constrained_layout=True)

# Comparaciones
bars = axes[0].bar(agg['algo'], agg['comparisons'])
axes[0].set_title('Comparaciones')
axes[0].yaxis.set_major_formatter(FuncFormatter(lambda v, _: f'{int(v):,}'))
axes[0].tick_params(axis='x', rotation=30)
axes[0].bar_label(bars, labels=[abbr(v) for v in agg['comparisons']], padding=2)
# Intercambios
bars = axes[1].bar(agg['algo'], agg['swaps'])
axes[1].set_title('Intercambios')
axes[1].yaxis.set_major_formatter(FuncFormatter(lambda v, _: f'{int(v):,}'))
axes[1].tick_params(axis='x', rotation=30)
axes[1].bar_label(bars, labels=[abbr(v) for v in agg['swaps']], padding=2)
# Tiempo en ms
bars = axes[2].bar(agg['algo'], agg['time_ms'])
axes[2].set_title('Tiempo')
axes[2].tick_params(axis='x', rotation=30)
axes[2].bar_label(bars, labels=[abbr(v) for v in agg['time_ms']], padding=2)

plt.show()

Evaluación de algoritmos con el Archivo p=256¶

Para el archivo p=256 (n = 3080), Bubble Sort realiza 4,741,660 comparaciones, 452,612 swaps y tarda ≈501.74 ms, quedando muy por detrás de los $O(n \log n)$. Entre estos, Quicksort es el más rápido (≈7.26 ms; 40,946 comparaciones), seguido de Mergesort (≈8.36 ms; 29,803 comparaciones y 35,944 writes). Heapsort viene después (≈12.64 ms; 64,315 comparaciones) y Skip List Sort cierra el grupo (≈14.22 ms; 54,320 comparaciones y 12,168 writes).

In [ ]:
A = archive_256
rows = []
for name, fn in [
    ("bubblesort", bubble_sort_count),
    ("quicksort",  quicksort_count),
    ("heapsort",   heapsort_count_timed),
    ("mergesort",  mergesort_count_timed),
    ("skiplist",   lambda X: skiplist_sort_count_timed(X, seed=123)),
]:
    out, comps, swaps_or_writes, ms = fn(A)
    assert np.array_equal(out, np.sort(A)), f"{name} no coincide con np.sort"
    rows.append({
        "dataset": "256",
        "algo": name,
        "n": len(A),
        "comparisons": comps,
        "swaps": swaps_or_writes,
        "time_ms": ms
    })
df = pd.DataFrame(rows)
df
Out[ ]:
dataset algo n comparisons swaps time_ms
0 256 bubblesort 3080 4741660 452612 501.743030
1 256 quicksort 3080 40946 22140 7.256318
2 256 heapsort 3080 64315 34920 12.643787
3 256 mergesort 3080 29803 35944 8.356604
4 256 skiplist 3080 54320 12168 14.218479
In [ ]:
order = ['bubblesort', 'quicksort', 'heapsort', 'mergesort', 'skiplist']
agg = (df.groupby('algo', as_index=False)
         .agg(comparisons=('comparisons','mean'),
              swaps=('swaps','mean'),
              time_ms=('time_ms','mean')))
agg['algo'] = pd.Categorical(agg['algo'], categories=order, ordered=True)
agg = agg.sort_values('algo')

def abbr(x):
    if x >= 1_000_000:
        return f'{x/1_000_000:.1f}M'
    if x >= 1_000:
        return f'{x/1_000:.1f}k'
    return f'{x:.1f}'

fig, axes = plt.subplots(1, 3, figsize=(12, 4), constrained_layout=True)

# Comparaciones
bars = axes[0].bar(agg['algo'], agg['comparisons'])
axes[0].set_title('Comparaciones')
axes[0].yaxis.set_major_formatter(FuncFormatter(lambda v, _: f'{int(v):,}'))
axes[0].tick_params(axis='x', rotation=30)
axes[0].bar_label(bars, labels=[abbr(v) for v in agg['comparisons']], padding=2)
# Intercambios
bars = axes[1].bar(agg['algo'], agg['swaps'])
axes[1].set_title('Intercambios')
axes[1].yaxis.set_major_formatter(FuncFormatter(lambda v, _: f'{int(v):,}'))
axes[1].tick_params(axis='x', rotation=30)
axes[1].bar_label(bars, labels=[abbr(v) for v in agg['swaps']], padding=2)
# Tiempo en ms
bars = axes[2].bar(agg['algo'], agg['time_ms'])
axes[2].set_title('Tiempo')
axes[2].tick_params(axis='x', rotation=30)
axes[2].bar_label(bars, labels=[abbr(v) for v in agg['time_ms']], padding=2)

plt.show()

Evaluación de algoritmos con el Archivo p=512¶

Para el archivo p=512 (n = 3080), Bubble Sort realiza 4,741,660 comparaciones, 796,239 swaps y tarda ≈550.29 ms, confirmando su desventaja práctica. Entre los $O(n \log n)$, Quicksort es el más rápido (≈8.04 ms; 41,467 comparaciones), seguido muy de cerca por Mergesort (≈8.48 ms; 30,845 comparaciones y 35,944 writes). Heapsort queda después (≈12.83 ms; 63,936 comparaciones) y Skip List Sort cierra el grupo (≈13.08 ms; 60,772 comparaciones y 12,168 writes). En conjunto, los $O(n \log n)$ dominan; las diferencias responden a constantes y efectos de memoria.

In [ ]:
A = archive_512
rows = []
for name, fn in [
    ("bubblesort", bubble_sort_count),
    ("quicksort",  quicksort_count),
    ("heapsort",   heapsort_count_timed),
    ("mergesort",  mergesort_count_timed),
    ("skiplist",   lambda X: skiplist_sort_count_timed(X, seed=123)),
]:
    out, comps, swaps_or_writes, ms = fn(A)
    assert np.array_equal(out, np.sort(A)), f"{name} no coincide con np.sort"
    rows.append({
        "dataset": "512",
        "algo": name,
        "n": len(A),
        "comparisons": comps,
        "swaps": swaps_or_writes,
        "time_ms": ms
    })
df = pd.DataFrame(rows)
df
Out[ ]:
dataset algo n comparisons swaps time_ms
0 512 bubblesort 3080 4741660 796239 550.291931
1 512 quicksort 3080 41467 22721 8.036600
2 512 heapsort 3080 63936 34603 12.833832
3 512 mergesort 3080 30845 35944 8.477739
4 512 skiplist 3080 60772 12168 13.080908
In [ ]:
order = ['bubblesort', 'quicksort', 'heapsort', 'mergesort', 'skiplist']
agg = (df.groupby('algo', as_index=False)
         .agg(comparisons=('comparisons','mean'),
              swaps=('swaps','mean'),
              time_ms=('time_ms','mean')))
agg['algo'] = pd.Categorical(agg['algo'], categories=order, ordered=True)
agg = agg.sort_values('algo')

def abbr(x):
    if x >= 1_000_000:
        return f'{x/1_000_000:.1f}M'
    if x >= 1_000:
        return f'{x/1_000:.1f}k'
    return f'{x:.1f}'

fig, axes = plt.subplots(1, 3, figsize=(12, 4), constrained_layout=True)

# Comparaciones
bars = axes[0].bar(agg['algo'], agg['comparisons'])
axes[0].set_title('Comparaciones')
axes[0].yaxis.set_major_formatter(FuncFormatter(lambda v, _: f'{int(v):,}'))
axes[0].tick_params(axis='x', rotation=30)
axes[0].bar_label(bars, labels=[abbr(v) for v in agg['comparisons']], padding=2)
# Intercambios
bars = axes[1].bar(agg['algo'], agg['swaps'])
axes[1].set_title('Intercambios')
axes[1].yaxis.set_major_formatter(FuncFormatter(lambda v, _: f'{int(v):,}'))
axes[1].tick_params(axis='x', rotation=30)
axes[1].bar_label(bars, labels=[abbr(v) for v in agg['swaps']], padding=2)
# Tiempo en ms
bars = axes[2].bar(agg['algo'], agg['time_ms'])
axes[2].set_title('Tiempo')
axes[2].tick_params(axis='x', rotation=30)
axes[2].bar_label(bars, labels=[abbr(v) for v in agg['time_ms']], padding=2)

plt.show()

Conclusión¶

En todos los conjuntos, los resultados confirman la teoría: los métodos $O(n \log n)$ superan con claridad a Bubble Sort ($O(n^2)$). En promedio, Quicksort resulta el más rápido gracias a su localidad de memoria y ejecución in-place (aunque no es estable y su peor caso sigue siendo $O(n^2)$, mitigado con pivote aleatorio). Mergesort es igual de competitivo, realiza menos comparaciones y es estable, pero requiere memoria $O(n)$ y más escrituras. Heapsort garantiza $O(n \log n)$ in-place y sin memoria extra, pero suele quedar detrás por mayor número de swaps y peor localidad; Skip List Sort mantiene el orden esperado $O(n \log n)$, aunque el overhead de punteros lo hace más lento que quick/merge.

Referencias¶

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4.ª ed.). MIT Press.

Knuth, D. E. (1998). The Art of Computer Programming, Vol. 3: Sorting and Searching (2.ª ed.). Addison–Wesley.

Pugh, W. (1990). Skip lists: A probabilistic alternative to balanced trees. Communications of the ACM, 33(6), 668–676.

Sadit. (s. f.). 4 Algoritmos de ordenamiento. En Curso Introductorio al Análisis de Algoritmos con Julia. Recuperado de https://sadit.github.io/ALGO-IR/cap4-ordenamiento.html

Wikipedia contributors. (s. f.). Merge sort. En Wikipedia, The Free Encyclopedia. Recuperado el 8 de octubre de 2025, de https://en.wikipedia.org/wiki/Merge_sort

Williams, J. W. J. (1964). Algorithm 232: Heapsort. Communications of the ACM, 7(6), 347–348.