Ordenación burbuja

Estructuras de datos y algoritmos en Python

Miriam Antona

Software engineer

Algoritmos de ordenación

  • Estudiados en profundidad
  • Resuelven cómo ordenar una colección desordenada en orden ascendente/descendente
  • Pueden reducir la complejidad de problemas
  • Algunos algoritmos de ordenación:
    • bubble sort
    • selection sort
    • insertion sort
    • merge sort
    • quicksort
Estructuras de datos y algoritmos en Python

Ordenación burbuja

Esquema de una lista con números desordenados. Un puntero apunta al primer elemento y otro al segundo.

  • Primer valor mayor que el segundo
Estructuras de datos y algoritmos en Python

Ordenación burbuja

Esquema de una lista con números desordenados. Un puntero apunta al primer elemento y otro al segundo. El primero y el segundo se han intercambiado.

  • Primer valor > segundo valor
    • Intercámbialos
  • Segundo valor > primer valor
    • Nada
Estructuras de datos y algoritmos en Python

Ordenación burbuja

Esquema de una lista con números desordenados. Un puntero apunta al segundo elemento y otro al tercero.

  • Primer valor > segundo valor
    • Intercámbialos
  • Segundo valor > primer valor
    • Nada
Estructuras de datos y algoritmos en Python

Ordenación burbuja

Esquema de una lista con números desordenados. Un puntero apunta al tercer elemento y otro al cuarto.

  • Primer valor > segundo valor
    • Intercámbialos
  • Segundo valor > primer valor
    • Nada
Estructuras de datos y algoritmos en Python

Ordenación burbuja

Esquema de una lista con números desordenados. Un puntero apunta al tercer elemento y otro al cuarto. El tercero y el cuarto se han intercambiado.

  • Primer valor > segundo valor
    • Intercámbialos
  • Segundo valor > primer valor
    • Nada
Estructuras de datos y algoritmos en Python

Ordenación burbuja

Esquema de una lista con números desordenados. Un puntero apunta al cuarto elemento y otro al quinto.

  • Primer valor > segundo valor
    • Intercámbialos
  • Segundo valor > primer valor
    • Nada
Estructuras de datos y algoritmos en Python

Ordenación burbuja

Esquema de una lista con números desordenados. Un puntero apunta al cuarto elemento y otro al quinto. El cuarto y el quinto se han intercambiado.

  • Primer valor > segundo valor
    • Intercámbialos
  • Segundo valor > primer valor
    • Nada
Estructuras de datos y algoritmos en Python

Ordenación burbuja

Esquema de una lista con números desordenados. Un puntero apunta al cuarto elemento y otro al quinto. El quinto está en azul porque está ordenado.

  • Primer valor > segundo valor
    • Intercámbialos
  • Segundo valor > primer valor
    • Nada
Estructuras de datos y algoritmos en Python

Ordenación burbuja

Esquema de una lista con números desordenados. Un puntero apunta al primer elemento y otro al segundo. El último elemento está en azul.

  • Primer valor > segundo valor
    • Intercámbialos
  • Segundo valor > primer valor
    • Nada
Estructuras de datos y algoritmos en Python

Ordenación burbuja

Esquema de una lista con números desordenados. Un puntero apunta al segundo elemento y otro al tercero. El último elemento está en azul.

  • Primer valor > segundo valor
    • Intercámbialos
  • Segundo valor > primer valor
    • Nada
Estructuras de datos y algoritmos en Python

Ordenación burbuja

Esquema de una lista con números desordenados. Un puntero apunta al segundo elemento y otro al tercero. El segundo y el tercero se han intercambiado. El último elemento está en azul.

  • Primer valor > segundo valor
    • Intercámbialos
  • Segundo valor > primer valor
    • Nada
Estructuras de datos y algoritmos en Python

Ordenación burbuja

Esquema de una lista con números desordenados. Un puntero apunta al tercer elemento y otro al cuarto. El último elemento está en azul.

  • Primer valor > segundo valor
    • Intercámbialos
  • Segundo valor > primer valor
    • Nada
Estructuras de datos y algoritmos en Python

Ordenación burbuja

Esquema de una lista con números desordenados. Un puntero apunta al tercer elemento y otro al cuarto. Los dos últimos elementos están en azul.

  • Primer valor > segundo valor
    • Intercámbialos
  • Segundo valor > primer valor
    • Nada
Estructuras de datos y algoritmos en Python

Ordenación burbuja

Esquema de una lista con números desordenados. Un puntero apunta al primer elemento y otro al segundo. Los dos últimos elementos están en azul.

  • Primer valor > segundo valor
    • Intercámbialos
  • Segundo valor > primer valor
    • Nada
Estructuras de datos y algoritmos en Python

Ordenación burbuja

Esquema de una lista con números desordenados. Un puntero apunta al primer elemento y otro al segundo. El primero y el segundo se han intercambiado. Los dos últimos elementos están en azul.

  • Primer valor > segundo valor
    • Intercámbialos
  • Segundo valor > primer valor
    • Nada
Estructuras de datos y algoritmos en Python

Ordenación burbuja

Esquema de una lista con números desordenados. Un puntero apunta al segundo elemento y otro al tercero. Los dos últimos elementos están en azul.

  • Primer valor > segundo valor
    • Intercámbialos
  • Segundo valor > primer valor
    • Nada
Estructuras de datos y algoritmos en Python

Ordenación burbuja

Esquema de una lista con números desordenados. Un puntero apunta al segundo elemento y otro al tercero. Los tres últimos elementos están en azul.

  • Primer valor > segundo valor
    • Intercámbialos
  • Segundo valor > primer valor
    • Nada
Estructuras de datos y algoritmos en Python

Ordenación burbuja

Esquema de una lista con números desordenados. Un puntero apunta al primer elemento y otro al segundo. Los tres últimos elementos están en azul.

  • Primer valor > segundo valor
    • Intercámbialos
  • Segundo valor > primer valor
    • Nada
Estructuras de datos y algoritmos en Python

Ordenación burbuja

Esquema de una lista con números desordenados. Un puntero apunta al primer elemento y otro al segundo. Los cuatro últimos elementos están en azul.

  • Primer valor > segundo valor
    • Intercámbialos
  • Segundo valor > primer valor
    • Nada
Estructuras de datos y algoritmos en Python

Ordenación burbuja

Esquema de una lista con números desordenados. Un puntero apunta al primer elemento y otro al segundo. Todos los elementos están en azul.

  • Primer valor > segundo valor
    • Intercámbialos
  • Segundo valor > primer valor
    • Nada
Estructuras de datos y algoritmos en Python

Ordenación burbuja: implementación

def bubble_sort(my_list):
  list_length = len(my_list)
  for i in range(list_length-1):
    for j in range(list_length-1-i):

      if my_list[j] > my_list[j+1]:

        my_list[j] , my_list[j+1] = my_list[j+1] , my_list[j]

  return my_list

print(bubble_sort([4,3,7,1,5]))

[1, 3, 4, 5, 7]
Estructuras de datos y algoritmos en Python

Ordenación burbuja: implementación

def bubble_sort(my_list):
  list_length = len(my_list)
  is_sorted = False

  while not is_sorted:

    is_sorted = True

    for i in range(list_length-1):

      if my_list[i] > my_list[i+1]:

        my_list[i] , my_list[i+1] = my_list[i+1] , my_list[i]

        is_sorted = False

    list_length -= 1

  return my_list
Estructuras de datos y algoritmos en Python

Ordenación burbuja: complejidad

  • Peor caso: $O(n^2)$
  • Mejor caso - versión no mejorada: $\Omega(n^2)$
  • Mejor caso - versión mejorada: $\Omega(n)$
  • Caso medio: $\Theta(n^2)$
  • Rinde mal con listas grandes muy desordenadas
  • Rinde bien:
    • listas grandes ordenadas/casi ordenadas
    • listas pequeñas
Estructuras de datos y algoritmos en Python

¡Vamos a practicar!

Estructuras de datos y algoritmos en Python

Preparing Video For Download...