Quicksort

Estructuras de datos y algoritmos en Python

Miriam Antona

Software engineer

Quicksort

  • Sigue el principio de divide y vencerás
  • Implementado por muchos lenguajes de programación
  • Técnica de partición
    • Pivote
    • elementos menores que el pivote -> izquierda
    • elementos mayores que el pivote -> derecha
  • Los de la izquierda se ordenan recursivamente
  • Los de la derecha se ordenan recursivamente
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados.

Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El primer elemento está en azul.

  • Partición de Hoare
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El primer elemento está en azul. Hay dos punteros. El puntero izquierdo apunta al segundo elemento y el derecho al último.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El primer elemento está en azul. Hay dos punteros. El puntero izquierdo apunta al tercer elemento y el derecho al último.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El primer elemento está en azul. Hay dos punteros. El puntero izquierdo apunta al tercer elemento y el derecho al quinto.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
    • Mueve el puntero derecho hasta hallar un valor menor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El primer elemento está en azul. Hay dos punteros. El puntero izquierdo apunta al tercer elemento y el derecho al quinto. Hay dos flechas que indican que se intercambiarán el tercer y el quinto elementos.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
    • Mueve el puntero derecho hasta hallar un valor menor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El primer elemento está en azul. Hay dos punteros. El puntero izquierdo apunta al tercer elemento y el derecho al quinto. El tercer y el quinto elementos han sido intercambiados.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
    • Mueve el puntero derecho hasta hallar un valor menor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El primer elemento está en azul. Hay dos punteros. El puntero izquierdo apunta al cuarto elemento y el derecho al quinto.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
    • Mueve el puntero derecho hasta hallar un valor menor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El primer elemento está en azul. Hay dos punteros. El puntero izquierdo apunta al cuarto elemento y el derecho al cuarto.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
    • Mueve el puntero derecho hasta hallar un valor menor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El primer elemento está en azul. Hay dos punteros. El puntero izquierdo apunta al cuarto elemento y el derecho al tercero.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
    • Mueve el puntero derecho hasta hallar un valor menor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El primer elemento está en azul. Hay dos punteros. El puntero izquierdo apunta al cuarto elemento y el derecho al tercero. Hay dos flechas que indican que se intercambiarán el primer y el tercer elementos.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
    • Mueve el puntero derecho hasta hallar un valor menor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El tercer elemento está en azul. El primer y el tercer elementos han sido intercambiados.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
    • Mueve el puntero derecho hasta hallar un valor menor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El tercer elemento está en verde.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
    • Mueve el puntero derecho hasta hallar un valor menor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El tercer elemento está en verde y los dos primeros en naranja, representando la parte izquierda de la lista.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
    • Mueve el puntero derecho hasta hallar un valor menor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El primer elemento está en azul, el segundo en naranja y el tercero en verde. Los punteros izquierdo y derecho apuntan al segundo elemento.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
    • Mueve el puntero derecho hasta hallar un valor menor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El primer elemento está en azul, el segundo en naranja y el tercero en verde. Los punteros izquierdo y derecho apuntan al segundo elemento. Hay dos flechas que indican que se intercambiarán el primer y el segundo elementos.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
    • Mueve el puntero derecho hasta hallar un valor menor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El primer elemento está en azul, el segundo en naranja y el tercero en verde. Los punteros izquierdo y derecho apuntan al segundo elemento. El primer y el segundo elementos han sido intercambiados.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
    • Mueve el puntero derecho hasta hallar un valor menor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El primer elemento está en naranja y el segundo y tercero en verde.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
    • Mueve el puntero derecho hasta hallar un valor menor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El primero, segundo y tercer elementos están en verde.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
    • Mueve el puntero derecho hasta hallar un valor menor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El primero, segundo y tercer elementos están en verde. La parte derecha de la lista está en naranja.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
    • Mueve el puntero derecho hasta hallar un valor menor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El primero, segundo y tercer elementos están en verde. El primer elemento de la parte derecha está en azul. El puntero izquierdo apunta al segundo elemento de la parte derecha y el derecho al último de la parte derecha.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
    • Mueve el puntero derecho hasta hallar un valor menor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El primero, segundo y tercer elementos están en verde. El primer elemento de la parte derecha está en azul. Los punteros izquierdo y derecho apuntan al segundo elemento de la parte derecha.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
    • Mueve el puntero derecho hasta hallar un valor menor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El primero, segundo y tercer elementos están en verde. El primer elemento de la parte derecha está en azul. El puntero izquierdo apunta al primer elemento de la parte derecha y el derecho al segundo.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
    • Mueve el puntero derecho hasta hallar un valor menor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El primero, segundo, tercero y cuarto elementos están en verde, y el quinto y sexto en naranja.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
    • Mueve el puntero derecho hasta hallar un valor menor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El primero, segundo, tercero y cuarto elementos están en verde. El elemento está en azul. Los punteros izquierdo y derecho apuntan al último elemento.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
    • Mueve el puntero derecho hasta hallar un valor menor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El primero, segundo, tercero y cuarto elementos están en verde. El elemento está en azul. Los punteros izquierdo y derecho apuntan al último elemento. Hay dos flechas que indican que se intercambiarán el quinto y sexto elementos.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
    • Mueve el puntero derecho hasta hallar un valor menor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. El primero, segundo, tercero y cuarto elementos están en verde. El elemento está en azul. Los punteros izquierdo y derecho apuntan al último elemento. El quinto y sexto elementos han sido intercambiados.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
    • Mueve el puntero derecho hasta hallar un valor menor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort en acción

Esquema de una lista con números desordenados. Todos los elementos están en verde porque están ordenados.

  • Partición de Hoare
    • Mueve el puntero izquierdo hasta hallar un valor mayor que el pivote
    • Mueve el puntero derecho hasta hallar un valor menor que el pivote
Estructuras de datos y algoritmos en Python

Quicksort: implementación

def quicksort(my_list, first_index, last_index):

    if first_index < last_index:

        partition_index = partition(my_list, first_index, last_index)

        quicksort(my_list, first_index, partition_index)

        quicksort(my_list, partition_index + 1, last_index)
Estructuras de datos y algoritmos en Python

Quicksort: implementación

def partition(my_list, first_index, last_index):

    pivot = my_list[first_index]
    left_pointer = first_index + 1
    right_pointer = last_index

    while True: 
        while my_list[left_pointer] < pivot and left_pointer < last_index:
            left_pointer += 1

        while my_list[right_pointer] > pivot and right_pointer >= first_index:
            right_pointer -= 1

        if left_pointer >= right_pointer:
            break

        my_list[left_pointer], my_list[right_pointer] = my_list[right_pointer], my_list[left_pointer]

    my_list[first_index], my_list[right_pointer] = my_list[right_pointer], my_list[first_index]

    return right_pointer
Estructuras de datos y algoritmos en Python

Quicksort: implementación

my_list = [6, 2, 9, 7, 4, 8] 
quicksort(my_list, 0, len(my_list) - 1)
print(my_list)

[2, 4, 6, 7, 8, 9]
Estructuras de datos y algoritmos en Python

Quicksort: complejidad

  • Peor caso: $O(n^2)$
  • ¡Muy eficiente!
    • Caso medio: $\Theta(n\log{}n)$
    • Mejor caso: $\Omega(n\log{}n)$
  • Complejidad espacial: $O(n\log{}n)$
Estructuras de datos y algoritmos en Python

¡Vamos a practicar!

Estructuras de datos y algoritmos en Python

Preparing Video For Download...