Ordenamiento por fusión

Estructuras de datos y algoritmos en Python

Miriam Antona

Software engineer

Ordenamiento por fusión

Sigue el enfoque de divide y vencerás
- Dividir
  - divide el problema en subproblemas más pequeños
- Vencer
  - resuelve los subproblemas recursivamente
- Combinar
  - combina las soluciones para obtener la solución final

Ordenamiento por fusión: en acción

Representación esquemática de una lista con números desordenados.

Ordenamiento por fusión: en acción

Representación esquemática de una lista con números desordenados. La lista se ha dividido en dos partes.

Ordenamiento por fusión: en acción

Representación esquemática de una lista con números desordenados. La lista se ha dividido en dos partes. Hay dos listas nuevas, la primera con la mitad izquierda de la lista original y la segunda con la mitad derecha.

Ordenamiento por fusión: en acción

Representación esquemática de una lista con números desordenados. Las nuevas listas se han dividido en dos partes.

Ordenamiento por fusión: en acción

Representación esquemática de una lista con números desordenados. Hay listas nuevas con las divisiones de las últimas listas divididas.

Ordenamiento por fusión: en acción

Representación esquemática de una lista con números desordenados. Las nuevas listas se han dividido en dos partes.

Ordenamiento por fusión: en acción

Representación esquemática de una lista con números desordenados. Hay listas nuevas con las divisiones de las últimas listas divididas.

Ordenamiento por fusión: en acción

Representación esquemática de una lista con números desordenados. Las nuevas listas se han dividido en dos partes.

Ordenamiento por fusión: en acción

Representación esquemática de una lista con números desordenados. Las nuevas listas se han dividido en dos partes.

Ordenamiento por fusión: en acción

Representación esquemática de una lista con números desordenados. Los elementos de las últimas listas divididas se han ordenado.

Ordenamiento por fusión: en acción

Representación esquemática de una lista con números desordenados. Los elementos de las últimas listas divididas se han fusionado y ordenado.

Ordenamiento por fusión: en acción

Representación esquemática de una lista con números desordenados. Los elementos de las últimas listas divididas se han fusionado y ordenado.

Ordenamiento por fusión: en acción

Representación esquemática de una lista con números desordenados. Los elementos de las últimas listas divididas se han fusionado y ordenado. Todos los elementos están ordenados.

Ordenamiento por fusión: implementación

def merge_sort(my_list):
  if len(my_list) > 1:

    mid = len(my_list)//2
    left_half = my_list[:mid]
    right_half = my_list[mid:]

    merge_sort(left_half)
    merge_sort(right_half)


    i = j = k = 0

    while i < len(left_half) and j < len(right_half):

      if left_half[i] < right_half[j]:

        my_list[k] = left_half[i]

        i += 1

      else:

        my_list[k] = right_half[j]

        j += 1

      k += 1

    while i < len(left_half):

      my_list[k] = left_half[i]
      i += 1
      k += 1


    while j < len(right_half):
      my_list[k] = right_half[j]
      j += 1
      k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)

[1, 4, 20, 22, 30, 35, 40, 50, 90]

Ordenamiento por fusión: complejidad

Peor caso: $O(n\log{}n)$
- mejora notable sobre bubble sort, selection sort e insertion sort
- adecuado para listas grandes
Caso promedio: $\Theta(n\log{}n)$
Mejor caso: $\Omega(n\log{}n)$
- otros algoritmos (p. ej., bubble sort, insertion sort) tienen mejor mejor caso
Complejidad espacial: $O(n)$
- peor espacio que algoritmos con $O(1)$
Otras variantes reducen este espacio

¡Vamos a practicar!

Estructuras de datos y algoritmos en Python