Algoritmo Quicksort en Python para Ordenar Playlists por BPM y Energía

Algoritmos de Ordenamiento Quicksort para Listas de Reproducción

A continuación se presentan diferentes variantes e implementaciones del algoritmo Quicksort en Python, diseñadas para ordenar listas de canciones (tracks) considerando el flujo musical mediante el tempo (BPM) de forma ascendente y la energía de forma descendente.

Implementación 1: Partición de Lomuto con Copia Segura de Lista

Esta variante utiliza el esquema clásico de partición de Lomuto y genera una copia defensiva del arreglo para preservar los datos de la lista original intactos.

def sort_playlist_by_flow(tracks, use_energy):
    # Comparador del DJ (devuelve True si a < b)
    def less(a, b):
        bpm_a = a[1]
        bpm_b = b[1]
        if bpm_a != bpm_b:
            return bpm_a < bpm_b
        if use_energy:
            energy_a = a[2]
            energy_b = b[2]
            if energy_a != energy_b:
                return energy_a > energy_b # energy descendente
        return False # considera iguales → no mover

    def partition(arr, left, right):
        pivot = arr[right] # pivote = último elemento
        i = left - 1 # índice del menor
        for j in range(left, right):
            if less(arr[j], pivot): # arr[j] < pivot
                i += 1
                arr[i], arr[j] = arr[j], arr[i] # swap
        # colocar pivote en su posición final
        arr[i+1], arr[right] = arr[right], arr[i+1]
        return i + 1

    def quicksort(arr, left, right):
        if left < right:
            p = partition(arr, left, right)
            quicksort(arr, left, p - 1)
            quicksort(arr, p + 1, right)

    arr = tracks[:] # copiar para no modificar el original
    quicksort(arr, 0, len(arr)-1)
    # devolver solo títulos
    return [t[0] for t in arr]

Implementación 2: Partición Bidireccional In-Place con Validación de Atributos

Esta solución aplica una partición bidireccional (estilo Hoare) directamente sobre la lista pasada por parámetro, comprobando la longitud de los registros para evitar errores si la propiedad de energía no está presente.

def sort_playlist_by_flow(tracks, use_energy):
    def comparar_dj_simple(a, b):
        bpm_a = a[1]
        bpm_b = b[1]
        if bpm_a != bpm_b:
            return bpm_a < bpm_b
        if use_energy:
            energy_a = a[2] if len(a) > 2 else 0
            energy_b = b[2] if len(b) > 2 else 0
            if energy_a != energy_b:
                return energy_a > energy_b
        return False

    def partition(arr, left, right):
        pivot = arr[right]
        i = left
        j = right - 1
        while True:
            while i <= j and comparar_dj_simple(arr[i], pivot):
                i += 1
            while i <= j and comparar_dj_simple(pivot, arr[j]):
                j -= 1
            if i >= j:
                break
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
            j -= 1
        arr[i], arr[right] = arr[right], arr[i]
        return i

    def quicksort_recursivo(arr, left, right):
        if left < right:
            p = partition(arr, left, right)
            quicksort_recursivo(arr, left, p - 1)
            quicksort_recursivo(arr, p + 1, right)

    if not tracks:
        return []
    quicksort_recursivo(tracks, 0, len(tracks) - 1)
    return [t[0] for t in tracks]

Implementación 3: Réplica de Partición Bidireccional

Segunda instancia del método in-place bidireccional con validación de elementos nulos y control de longitud por tupla.

def sort_playlist_by_flow(tracks, use_energy):
    def comparar_dj_simple(a, b):
        bpm_a = a[1]
        bpm_b = b[1]
        if bpm_a != bpm_b:
            return bpm_a < bpm_b
        if use_energy:
            energy_a = a[2] if len(a) > 2 else 0
            energy_b = b[2] if len(b) > 2 else 0
            if energy_a != energy_b:
                return energy_a > energy_b
        return False

    def partition(arr, left, right):
        pivot = arr[right]
        i = left
        j = right - 1
        while True:
            while i <= j and comparar_dj_simple(arr[i], pivot):
                i += 1
            while i <= j and comparar_dj_simple(pivot, arr[j]):
                j -= 1
            if i >= j:
                break
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
            j -= 1
        arr[i], arr[right] = arr[right], arr[i]
        return i

    def quicksort_recursivo(arr, left, right):
        if left < right:
            p = partition(arr, left, right)
            quicksort_recursivo(arr, left, p - 1)
            quicksort_recursivo(arr, p + 1, right)

    if not tracks:
        return []
    quicksort_recursivo(tracks, 0, len(tracks) - 1)
    return [t[0] for t in tracks]

Implementación 4: Esquema Compacto de Lomuto con Copia de Seguridad

Variación simplificada de la ordenación por Lomuto preservando inmutabilidad en la entrada original.

def sort_playlist_by_flow(tracks, use_energy):
    def less(a, b):
        bpm_a = a[1]
        bpm_b = b[1]
        if bpm_a != bpm_b:
            return bpm_a < bpm_b
        if use_energy:
            energy_a = a[2]
            energy_b = b[2]
            if energy_a != energy_b:
                return energy_a > energy_b
        return False # considera iguales → no mover

    def partition(arr, left, right):
        pivot = arr[right] # pivote = último elemento
        i = left - 1 # índice del menor
        for j in range(left, right):
            if less(arr[j], pivot): # arr[j] < pivot
                i += 1
                arr[i], arr[j] = arr[j], arr[i] # swap
        arr[i+1], arr[right] = arr[right], arr[i+1]
        return i + 1

    def quicksort(arr, left, right):
        if left < right:
            p = partition(arr, left, right)
            quicksort(arr, left, p - 1)
            quicksort(arr, p + 1, right)

    arr = tracks[:] # copiar para no modificar el original
    quicksort(arr, 0, len(arr)-1)
    return [t[0] for t in arr]