Selection Sort e Insertion Sort

Estructuras de datos y algoritmos en Python

Miriam Antona

Software engineer

Selection sort

Representación esquemática de una lista con números desordenados. Un puntero apunta al primer elemento.

  • Determina el valor más bajo
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. Un puntero apunta al primer elemento. El primer elemento está en naranja.

  • Determina el valor más bajo
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. Un puntero apunta al segundo elemento. El primer elemento está en naranja.

  • Determina el valor más bajo
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. Un puntero apunta al segundo elemento. El segundo elemento está en naranja.

  • Determina el valor más bajo
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. Un puntero apunta al tercer elemento. El segundo elemento está en naranja.

  • Determina el valor más bajo
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. Un puntero apunta al cuarto elemento. El segundo elemento está en naranja.

  • Determina el valor más bajo
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. Un puntero apunta al cuarto elemento. El cuarto elemento está en naranja.

  • Determina el valor más bajo
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. Un puntero apunta al quinto elemento. El cuarto elemento está en naranja.

  • Determina el valor más bajo
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. El cuarto elemento está en naranja. Dos flechas indican que se intercambiarán el primer y el cuarto elementos.

  • Determina el valor más bajo
  • Intercambia el más bajo con el primer elemento desordenado
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. El primer elemento está en naranja. Se han intercambiado el primero y el cuarto.

  • Determina el valor más bajo
  • Intercambia el más bajo con el primer elemento desordenado
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. El primer elemento está en azul y el segundo en naranja. Un puntero apunta al segundo elemento.

  • Determina el valor más bajo
  • Intercambia el más bajo con el primer elemento desordenado
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. El primer elemento está en azul y el segundo en naranja. Un puntero apunta al tercer elemento.

  • Determina el valor más bajo
  • Intercambia el más bajo con el primer elemento desordenado
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. El primer elemento está en azul y el segundo en naranja. Un puntero apunta al cuarto elemento.

  • Determina el valor más bajo
  • Intercambia el más bajo con el primer elemento desordenado
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. El primer y segundo elementos están en azul. Un puntero apunta al tercer elemento.

  • Determina el valor más bajo
  • Intercambia el más bajo con el primer elemento desordenado
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. El primer y segundo elementos están en azul. Un puntero apunta al tercer elemento.

  • Determina el valor más bajo
  • Intercambia el más bajo con el primer elemento desordenado
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. El primer y segundo elementos están en azul y el tercero en naranja. Un puntero apunta al tercer elemento.

  • Determina el valor más bajo
  • Intercambia el más bajo con el primer elemento desordenado
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. El primer y segundo elementos están en azul y el tercero en naranja. Un puntero apunta al cuarto elemento.

  • Determina el valor más bajo
  • Intercambia el más bajo con el primer elemento desordenado
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. El primer y segundo elementos están en azul y el cuarto en naranja. Un puntero apunta al cuarto elemento.

  • Determina el valor más bajo
  • Intercambia el más bajo con el primer elemento desordenado
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. El primer y segundo elementos están en azul y el cuarto en naranja. Un puntero apunta al quinto elemento.

  • Determina el valor más bajo
  • Intercambia el más bajo con el primer elemento desordenado
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. El primer y segundo elementos están en azul y el cuarto en naranja. Dos flechas indican que se intercambiarán el tercero y el cuarto.

  • Determina el valor más bajo
  • Intercambia el más bajo con el primer elemento desordenado
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. El primer y segundo elementos están en azul y el tercero en naranja. Se han intercambiado el tercero y el cuarto.

  • Determina el valor más bajo
  • Intercambia el más bajo con el primer elemento desordenado
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. El primer, segundo y tercer elementos están en azul. Un puntero apunta al cuarto elemento.

  • Determina el valor más bajo
  • Intercambia el más bajo con el primer elemento desordenado
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. El primer, segundo y tercer elementos están en azul, y el cuarto en naranja. Un puntero apunta al cuarto elemento.

  • Determina el valor más bajo
  • Intercambia el más bajo con el primer elemento desordenado
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. El primer, segundo y tercer elementos están en azul, y el cuarto en naranja. Un puntero apunta al quinto elemento.

  • Determina el valor más bajo
  • Intercambia el más bajo con el primer elemento desordenado
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. El primer, segundo y tercer elementos están en azul, y el quinto en naranja. Un puntero apunta al quinto elemento.

  • Determina el valor más bajo
  • Intercambia el más bajo con el primer elemento desordenado
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. El primer, segundo y tercer elementos están en azul, y el quinto en naranja. Dos flechas indican que se intercambiarán el cuarto y el quinto.

  • Determina el valor más bajo
  • Intercambia el más bajo con el primer elemento desordenado
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. El primer, segundo y tercer elementos están en azul, y el cuarto en naranja. Se han intercambiado el cuarto y el quinto.

  • Determina el valor más bajo
  • Intercambia el más bajo con el primer elemento desordenado
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. El primer, segundo, tercer y cuarto elementos están en azul.

  • Determina el valor más bajo
  • Intercambia el más bajo con el primer elemento desordenado
Estructuras de datos y algoritmos en Python

Selection sort

Representación esquemática de una lista con números desordenados. Todos los elementos están en azul.

  • Determina el valor más bajo
  • Intercambia el más bajo con el primer elemento desordenado
Estructuras de datos y algoritmos en Python

Selection sort: implementación

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

    lowest = my_list[i]

    index = i

    for j in range(i + 1, list_length):

      if my_list[j] < lowest:

        index = j

        lowest = my_list[j]

    my_list[i] , my_list[index] = my_list[index] , my_list[i]

  return my_list
Estructuras de datos y algoritmos en Python

Selection sort: complejidad

  • Peor caso: $O(n^2)$
  • Caso medio: $\Theta(n^2)$
  • Mejor caso: $\Omega(n^2)$
Estructuras de datos y algoritmos en Python

Insertion sort

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

Estructuras de datos y algoritmos en Python

Insertion sort

Representación esquemática de una lista con números desordenados. El primer elemento está en azul y el segundo se ha elevado por encima del resto.

Estructuras de datos y algoritmos en Python

Insertion sort

Representación esquemática de una lista con números desordenados. El primer elemento está en azul y el segundo se ha elevado por encima del resto. El primer elemento se ha desplazado a la derecha.

Estructuras de datos y algoritmos en Python

Insertion sort

Representación esquemática de una lista con números desordenados. El segundo elemento está en azul. El elemento elevado ahora está en la primera posición.

Estructuras de datos y algoritmos en Python

Insertion sort

Representación esquemática de una lista con números desordenados. El primer y segundo elementos están en azul.

Estructuras de datos y algoritmos en Python

Insertion sort

Representación esquemática de una lista con números desordenados. El primer y segundo elementos están en azul. El tercer elemento se ha elevado por encima del resto.

Estructuras de datos y algoritmos en Python

Insertion sort

Representación esquemática de una lista con números desordenados. El primer, segundo y tercer elementos están en azul.

Estructuras de datos y algoritmos en Python

Insertion sort

Representación esquemática de una lista con números desordenados. El primer, segundo y tercer elementos están en azul. El tercer elemento se ha elevado por encima del resto.

Estructuras de datos y algoritmos en Python

Insertion sort

Representación esquemática de una lista con números desordenados. El primer, segundo y tercer elementos están en azul. El tercer elemento se ha elevado por encima del resto. El tercer elemento se ha desplazado a la derecha.

Estructuras de datos y algoritmos en Python

Insertion sort

Representación esquemática de una lista con números desordenados. El primer, segundo y tercer elementos están en azul. El tercer elemento se ha elevado por encima del resto. El tercero y el segundo se han desplazado a la derecha.

Estructuras de datos y algoritmos en Python

Insertion sort

Representación esquemática de una lista con números desordenados. El primer, segundo y tercer elementos están en azul. El tercer elemento se ha elevado por encima del resto. El tercero, el segundo y el tercero se han desplazado a la derecha.

Estructuras de datos y algoritmos en Python

Insertion sort

Representación esquemática de una lista con números desordenados. El primer, segundo y tercer elementos están en azul. El tercer elemento se ha elevado por encima del resto. El tercero, el segundo y el tercero se han desplazado a la derecha. El elemento elevado ahora está en la primera posición.

Estructuras de datos y algoritmos en Python

Insertion sort

Representación esquemática de una lista con números desordenados. El primer, segundo, tercer y cuarto elementos están en azul.

Estructuras de datos y algoritmos en Python

Insertion sort

Representación esquemática de una lista con números desordenados. El primer, segundo, tercer y cuarto elementos están en azul. El quinto elemento se ha elevado por encima del resto.

Estructuras de datos y algoritmos en Python

Insertion sort

Representación esquemática de una lista con números desordenados. El primer, segundo, tercer y cuarto elementos están en azul. El quinto elemento se ha elevado por encima del resto. El cuarto elemento se ha desplazado a la derecha.

Estructuras de datos y algoritmos en Python

Insertion sort

Representación esquemática de una lista con números desordenados. El primer, segundo, tercer y cuarto elementos están en azul. El quinto elemento se ha elevado por encima del resto. El elemento elevado ahora está en la cuarta posición.

Estructuras de datos y algoritmos en Python

Insertion sort: implementación

def insertion_sort(my_list):
  for i in range(1, len(my_list)):

      number_to_order = my_list[i]

      j = i - 1

      while j >= 0 and number_to_order < my_list[j]:

          my_list[j + 1] = my_list[j]

          j -= 1

      my_list[j + 1] = number_to_order

  return my_list
Estructuras de datos y algoritmos en Python

Insertion sort: complejidad

  • Peor caso: $O(n^2)$
  • Caso medio: $\Theta(n^2)$
  • Mejor caso: $\Omega(n)$
Estructuras de datos y algoritmos en Python

¡Vamos a practicar!

Estructuras de datos y algoritmos en Python

Preparing Video For Download...