Merge sort

 Merge sort

Recursivo:

Código:


def merge_sort(a):
    if len(a) <= 1:
        return a

    mid = len(a) // 2
    l = a[:mid]
    r = a[mid:]

    l = merge_sort(l)
    r = merge_sort(r)

    return merge(l, r)

def merge(l, r):
    merged = []
    lI, rI = 0, 0

    while lI < len(l) and rI < len(r):
        if l[lI] < r[rI]:
            merged.append(l[lI])
            lI += 1
        else:
            merged.append(r[rI])
            rI += 1

    merged.extend(l[lI:])
    merged.extend(r[rI:])
    
    return merged

# Example usage:
a = [11,88,33,44,999,2,5,8,9,6,6]
sorted_a = merge_sort(a)
print(sorted_a)


Ejecucion:






Iterativo:
Código:


def merge_sort(a):
    if len(a) <= 1:
        return a

    sortedL = [[x] for x in a]

    while len(sortedL) > 1:
        mergedL = []
        for i in range(0, len(sortedL), 2):
            l = sortedL[i]
            r = sortedL[i + 1] if i + 1 < len(sortedL) else []

            merged = merge(l, r)
            mergedL.append(merged)

        sortedL = mergedL

    return sortedL[0]

def merge(l, r):
    merged = []
    lI, rI = 0, 0

    while lI < len(l) and rI < len(r):
        if l[lI] < r[rI]:
            merged.append(l[lI])
            lI += 1
        else:
            merged.append(r[rI])
            rI += 1

    merged.extend(l[lI:])
    merged.extend(r[rI:])
    
    return merged

a = [84,587,4,77,3,3,4,5]
sortedA = merge_sort(a)
print(sortedA)


Ejecucion:



Comentarios

Publicar un comentario

Entradas más populares de este blog

Limitaciones del Metodo Maestro

Imagen
El teorema maestro es una herramienta útil para resolver recurrencias que ocurren en muchos algoritmos recursivos, como los algoritmos de "divide y vencerás". Sin embargo, hay algunas limitaciones a tener en cuenta: 1. No monotonía: El teorema maestro no se puede utilizar si la función de tiempo de ejecución no es monótona. 2. No polinomio: Si la función de tiempo de ejecución no es un polinomio, el teorema maestro no se puede aplicar. 3. No constante: Si el número de subproblemas no es una constante, el teorema maestro no se puede utilizar. En este ejemplo, tenemos una función suma_lista que toma una lista de números como entrada y devuelve la suma de todos los elementos de la lista. No se aplica el método maestro aquí porque no estamos tratando con un algoritmo recursivo dividir y conquistar que requiera análisis de complejidad en términos de T(n). En su lugar, simplemente estamos iterando a través de la lista una vez, por lo que la complejidad es O(n), donde "n" ...
Read more »