0Pricing
Coding Interview Prep · Lección

Ordenaciones sin comparación y sort() de Python

Explore counting sort y radix sort para arrays de enteros, y comprenda cómo funciona internamente el Timsort de Python en las llamadas al sort integrado.

Ordenaciones sin comparación y sort() de Python es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.

Cota inferior de O(n log n) para las comparaciones

Cualquier algoritmo de ordenamiento que determine el orden solo mediante comparaciones entre elementos requiere al menos Ω(n log n) comparaciones en el peor caso. Esto se demuestra mediante el argumento del árbol de decisión: ordenar n elementos requiere distinguir entre n! posibles ordenamientos. Un árbol de decisión binario (cada nodo es una comparación) necesita al menos log₂(n!) ≈ n log₂(n) niveles. Para superar este límite, se necesita información adicional sobre los elementos, como que sean enteros acotados.

import math

for n in [5, 10, 100, 1000]:
    lower_bound = n * math.log2(n)
    factorial_log = sum(math.log2(i) for i in range(1, n+1))
    print(f'n={n}: n*log2(n)={lower_bound:.1f}, log2(n!)={factorial_log:.1f}')

# n log n is a tight bound on comparison-based sorting

Counting Sort: ordenar por frecuencia

Counting sort funciona contando la frecuencia de cada valor y reconstruyendo después el arreglo ordenado a partir de los conteos. Requiere conocer de antemano el rango [0, k) de los valores. Complejidad temporal: O(n + k); complejidad espacial: O(k). Cuando k es pequeño en relación con n (por ejemplo, al ordenar edades de 0 a 120 o dígitos individuales), counting sort supera a todos los ordenamientos basados en comparaciones. Para valores grandes de k, el costo espacial O(k) lo vuelve poco práctico.

def counting_sort(arr, k=None):
    if not arr: return []
    if k is None: k = max(arr) + 1
    count = [0] * k
    for n in arr:
        count[n] += 1
    result = []
    for val, freq in enumerate(count):
        result.extend([val] * freq)
    return result

arr = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(arr))  # [1, 2, 2, 3, 3, 4, 8]
# O(n + k) where k = 9 (max value + 1)

Ordenamiento estable por conteo con conteos acumulados

Para realizar un ordenamiento estable por conteo (importante al ordenar objetos por una clave), calcule los conteos acumulados de modo que cum[v] indique la posición inicial del valor v en la salida. Recorra el arreglo de entrada de derecha a izquierda, coloque cada elemento en la posición cum[key] - 1 y disminuya esa posición. Esto produce un ordenamiento estable: los elementos con la misma clave aparecen en el mismo orden relativo que tenían originalmente.

def counting_sort_stable(arr, k):
    count = [0] * k
    for n in arr: count[n] += 1
    # Cumulative counts: count[v] = first position for value v
    for i in range(1, k): count[i] += count[i-1]
    output = [0] * len(arr)
    # Fill from right to maintain stability
    for n in reversed(arr):
        count[n] -= 1
        output[count[n]] = n
    return output

print(counting_sort_stable([4,2,2,8,3,3,1], 9))
# [1, 2, 2, 3, 3, 4, 8]

Ordenamiento radix: ordenar dígito a dígito

Radix sort ordena los enteros dígito a dígito, desde el dígito menos significativo (LSD) hasta el más significativo (MSD), utilizando un ordenamiento estable (como el ordenamiento por conteo) en cada posición de dígito. Después de d pasadas (una por cada dígito), el arreglo queda completamente ordenado. Complejidad temporal: O(d × (n + k)), donde d = número de dígitos y k = base (normalmente 10). Para n enteros acotados por W, d = log_k(W), lo que da un total de O(n log_k(W)).

def radix_sort(arr):
    if not arr: return []
    max_val = max(arr)
    exp = 1  # current digit position (1, 10, 100, ...)
    while max_val // exp > 0:
        arr = counting_sort_by_digit(arr, exp)
        exp *= 10
    return arr

def counting_sort_by_digit(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    for n_ in arr: count[(n_ // exp) % 10] += 1
    for i in range(1, 10): count[i] += count[i-1]
    for n_ in reversed(arr):
        d = (n_ // exp) % 10
        count[d] -= 1
        output[count[d]] = n_
    return output

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]

Bucket sort: distribuir en cubetas

Bucket sort distribuye los elementos en un número fijo de cubetas según su rango de valores, ordena cada cubeta (con ordenamiento por inserción para cubetas pequeñas) y concatena sus contenidos. Para datos distribuidos uniformemente en [0, 1), n cubetas producen un tiempo promedio de O(n). Complejidad temporal: O(n + k) en promedio y O(n²) en el peor caso (cuando todos los elementos están en una sola cubeta). Es especialmente útil cuando se conoce la distribución de los datos y esta es aproximadamente uniforme.

def bucket_sort(arr):
    if not arr: return []
    n = len(arr)
    min_v, max_v = min(arr), max(arr)
    if min_v == max_v: return arr[:]
    buckets = [[] for _ in range(n)]
    # Map each value to a bucket index
    for v in arr:
        idx = int((v - min_v) / (max_v - min_v + 1e-9) * n)
        idx = min(idx, n - 1)
        buckets[idx].append(v)
    result = []
    for bucket in buckets:
        bucket.sort()  # insertion sort for small buckets
        result.extend(bucket)
    return result

print(bucket_sort([0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21]))
# sorted list

Timsort de Python por dentro

sorted() y list.sort() de Python utilizan Timsort, diseñado por Tim Peters en 2002. Timsort es un algoritmo híbrido de ordenamiento por mezcla y ordenamiento por inserción. Busca «secuencias naturales» (subsecuencias ya ordenadas) y utiliza el ordenamiento por inserción para construir secuencias de hasta 64 elementos. Después mezcla las secuencias mediante ordenamiento por mezcla con varias optimizaciones: galloping (omitir elementos en bloque cuando una secuencia predomina) y apilamiento de secuencias por longitud.

# Timsort properties:
# - Stable
# - O(n log n) worst case
# - O(n) best case (data already sorted)
# - O(n) auxiliary space
# - Highly optimised for real-world data with runs

import time

# Nearly sorted data: Timsort is extremely fast
nearly_sorted = list(range(10000))
nearly_sorted[-1] = 0  # one mis-placed element

t = time.perf_counter()
not_used = sorted(nearly_sorted)
elapsed = time.perf_counter() - t
print(f'Timsort on nearly-sorted n=10000: {elapsed*1000:.3f} ms')

Python: sort() frente a sorted(): diferencias clave

list.sort() ordena en el mismo lugar, devuelve None y solo funciona con listas. sorted(iterable) funciona con cualquier iterable (tuplas, generadores y diccionarios) y devuelve una lista nueva. Ambos aceptan los parámetros key y reverse. Un error común consiste en asignar el resultado de lst.sort() a una variable y preguntarse por qué es None. Utilice siempre sorted() cuando necesite la versión ordenada y quiera conservar el original.

nums = [3, 1, 4, 1, 5, 9]

# in-place: returns None
result = nums.sort()
print(result)  # None  (common bug!)
print(nums)    # [1, 1, 3, 4, 5, 9]  (modified)

nums2 = [3, 1, 4, 1, 5, 9]
# out-of-place: returns new list
result2 = sorted(nums2)
print(result2)  # [1, 1, 3, 4, 5, 9]
print(nums2)    # [3, 1, 4, 1, 5, 9]  (unchanged)

Claves de ordenamiento personalizadas en entrevistas

El método sort de Python acepta una función key que se evalúa una vez por elemento (a diferencia del comparador de C, que se llama para cada par). Claves de ordenamiento habituales en entrevistas: len para obtener la longitud de una cadena, lambda x: -x para ordenar de forma descendente, lambda x: (x[1], x[0]) para ordenar por varias claves y str.lower para ignorar mayúsculas y minúsculas. El ordenamiento de Python tiene estabilidad garantizada, por lo que los ordenamientos por varias claves funcionan correctamente.

# Sort by length, then alphabetically
words = ['banana', 'fig', 'apple', 'date', 'kiwi']
print(sorted(words, key=lambda w: (len(w), w)))
# ['fig', 'date', 'kiwi', 'apple', 'banana']

# Sort integers as strings (largest concatenation first)
nums = [3, 30, 34, 5, 9]
print(sorted(map(str, nums), key=lambda a: a*10, reverse=True))
# ['9', '5', '34', '3', '30']  => '9534330'

# Descending sort
print(sorted([3,1,4,1,5], reverse=True))  # [5,4,3,1,1]

Cuándo usar cada algoritmo de ordenamiento en entrevistas

Elija el ordenamiento adecuado según el contexto:

  • Use Python's sorted()/list.sort(): opción predeterminada para todos los problemas de entrevistas; Timsort es óptimo
  • Ordenamiento por conteo: cuando los valores son enteros pequeños acotados (de 0 a k, con k pequeño)
  • Radix sort: cuando se ordenan muchos enteros con un ancho de bits o una cantidad de dígitos conocidos
  • Bucket sort: cuando los datos son números de coma flotante distribuidos uniformemente dentro de un rango conocido
  • Implemente ordenamiento por mezcla: cuando se le pida programar desde cero un ordenamiento estable de O(n log n)

# Problem: sort array of 0s, 1s, 2s efficiently
# Counting sort: O(n), O(1) space  (k=3 is tiny)

def sort_012(arr):
    count = [0, 0, 0]
    for n in arr:
        count[n] += 1
    i = 0
    for val in range(3):
        for _ in range(count[val]):
            arr[i] = val; i += 1

arr = [2, 0, 2, 1, 1, 0]
sort_012(arr)
print(arr)  # [0, 0, 1, 1, 2, 2]

Ordenar sin ordenar: top-k con un heap

Muchos problemas de entrevistas solicitan resultados «similares a ordenar» sin requerir un ordenamiento completo. Para encontrar los k elementos principales, un min-heap de tamaño k se ejecuta en O(n log k), que es más rápido que O(n log n) cuando k << n. Para encontrar el k-ésimo elemento más grande, quickselect tiene un tiempo promedio de O(n). Para encontrar la mediana, el enfoque de dos heaps requiere O(log n) por inserción. Conviene conocer estos enfoques de ordenamiento parcial como alternativas más rápidas que ordenar por completo.

import heapq

# Top-k with heap: O(n log k)
def top_k(nums, k):
    return heapq.nlargest(k, nums)  # uses heap of size k internally

print(top_k([3,2,1,5,6,4], 2))    # [6, 5]

# kth largest: quickselect O(n) average
import random
def kth_largest(nums, k):
    def _select(lo, hi, target):
        if lo >= hi: return nums[lo]
        rand_i = random.randint(lo, hi)
        nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
        pivot = nums[hi]; i = lo - 1
        for j in range(lo, hi):
            if nums[j] >= pivot: i+=1; nums[i],nums[j]=nums[j],nums[i]
        nums[i+1],nums[hi]=nums[hi],nums[i+1]
        p = i + 1
        if p == target: return nums[p]
        return _select(lo, p-1, target) if target < p else _select(p+1, hi, target)
    return _select(0, len(nums)-1, k-1)

print(kth_largest([3,2,1,5,6,4], 2))  # 5

Estabilidad del ordenamiento con varias claves

La estabilidad permite ordenar correctamente por varias claves: ordene primero por la clave secundaria (de forma estable) y después por la clave primaria (también de forma estable). El orden secundario se conserva cuando hay empates en la clave primaria. Esta técnica se utiliza en bases de datos (ORDER BY col1, col2) y en radix sort (cada pasada por un dígito debe ser estable para que el algoritmo completo sea correcto). El ordenamiento de Python siempre es estable, por lo que este patrón funciona de manera fiable.

data = [
    ('Alice', 'Math',    90),
    ('Bob',   'Science', 85),
    ('Carol', 'Math',    90),
    ('Dave',  'Science', 90),
]
# Sort by score DESC, then by subject ASC (for ties)
# Step 1: sort by subject (secondary)
data.sort(key=lambda x: x[1])
# Step 2: sort by score DESC (primary, stable)
data.sort(key=lambda x: x[2], reverse=True)
for row in data:
    print(row)
# All score=90 rows: Math before Science (preserved from step 1)

Comprobación rápida

Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.

Repaso de la lección

En esta lección aprendió que: los algoritmos de ordenamiento basados en comparaciones tienen una cota inferior de O(n log n); para superar esta cota se necesita información que no dependa de comparaciones, como enteros acotados; el ordenamiento por conteo alcanza O(n + k) al contabilizar frecuencias, radix sort procesa los dígitos con un total de O(d × (n + k)) y bucket sort aprovecha la distribución uniforme para obtener O(n) en promedio; y Timsort de Python es la opción práctica predeterminada: estable, O(n log n) en el peor caso, O(n) en el mejor caso y más rápido que cualquier alternativa programada manualmente para datos reales. A continuación, dominará la búsqueda binaria clásica.

Preguntas frecuentes

¿La lección «Ordenaciones sin comparación y sort() de Python» es gratis?

Sí — el texto completo de «Ordenaciones sin comparación y sort() de Python» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.

¿Qué aprenderé en «Ordenaciones sin comparación y sort() de Python»?

Explore counting sort y radix sort para arrays de enteros, y comprenda cómo funciona internamente el Timsort de Python en las llamadas al sort integrado. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.

¿Necesito experiencia previa para empezar Coding Interview Prep?

No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.

¿Cuánto tiempo toma la lección «Ordenaciones sin comparación y sort() de Python»?

La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.

¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?

Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.

Todas las lecciones de este curso

  1. Bubble sort e insertion sort
  2. Merge sort: dividir, ordenar y combinar
  3. Quick sort y selección del pivote
  4. Ordenaciones sin comparación y sort() de Python
← Volver a Coding Interview Prep