-
-
Save parzibyte/883d44cd3f55149581279df67fb9ddb5 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
https://parzibyte.me/blog | |
""" | |
def merge_sort(arreglo): | |
longitud = len(arreglo) | |
mitad = longitud//2 # El doble / es para dividir y redondear hacia abajo | |
# Condición de salida de recursividad es que el arreglo mida 1 o 0 | |
if longitud <= 1: | |
return arreglo | |
mitad_izquierda = arreglo[:mitad] | |
mitad_derecha = arreglo[mitad:] | |
mitad_izquierda = merge_sort(mitad_izquierda) | |
mitad_derecha = merge_sort(mitad_derecha) | |
return merge(mitad_izquierda, mitad_derecha) | |
def merge(izquierda, derecha): | |
print(f"Recibo {izquierda} y {derecha}") | |
arreglo_ordenado = [] | |
indice_de_izquierda = 0 | |
indice_de_derecha = 0 | |
indice_arreglo_ordenado = 0 | |
# Recorremos ambos arreglos y vamos colocando los elementos ordenados. Colocamos siempre el que sea menor | |
while indice_de_izquierda < len(izquierda) and indice_de_derecha < len(derecha): | |
valor_izquierda = izquierda[indice_de_izquierda] | |
valor_derecha = derecha[indice_de_derecha] | |
if valor_izquierda <= valor_derecha: | |
# El de la izquierda es menor, entonces lo ponemos primero | |
arreglo_ordenado.append(valor_izquierda) | |
# Y aumentamos en 1 el valor de la izquierda | |
indice_de_izquierda += 1 | |
else: | |
arreglo_ordenado.append(valor_derecha) | |
indice_de_derecha += 1 | |
# Sin importar lo que hayamos movido, aumentamos el índice del actual | |
indice_arreglo_ordenado += 1 | |
# Hasta aquí puede que el índice izquierdo o derecho hayan llegado a su fin, pero no ambos. Entonces | |
# nos aseguramos de recorrerlos a ambos hasta el final | |
while indice_de_izquierda < len(izquierda): | |
arreglo_ordenado.append(izquierda[indice_de_izquierda]) | |
indice_de_izquierda += 1 | |
while indice_de_derecha < len(derecha): | |
arreglo_ordenado.append(derecha[indice_de_derecha]) | |
indice_de_derecha += 1 | |
print(f"Los ordeno y combino. Resultado: {arreglo_ordenado}.") | |
return arreglo_ordenado | |
arreglo = [6, 5, 3, 1, 8, 7, 2, 4] | |
print(f"Arreglo original: {arreglo}") | |
print("Ordenando con merge sort y recursividad...") | |
arreglo_ordenado = merge_sort(arreglo) | |
print(f"Arreglo ordenado: {arreglo_ordenado}") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment