Pivotando con Quicksort

Introducción

Estuve interesado por un tiempo sobre los algoritmos mas famosos, tales como el algoritmo de Euclides, Simplex, Montecarlo y algunos otros, pero el que me dejo con las ganas fue Quicksort!😍 esta es la razón por la que toco este tema espero que lo disfruten y entiendan...

Divide y Vencerás

Quicksort es un algoritmo de ordenamiento rápido, muy seco verdad😕, pongamos un ejemplo imagina que tienes una lista de variables desordenadas supongamos:

 lista = [3, 6, 1, 5, 2, 7, 4]

la función de este algoritmo sería procesar la lista y devolver la lista ordenada:

 lista = [1, 2, 3, 4, 5, 6, 7]

Quicksort es muy conocido por su velocidad y porque además no necesita pasos complejos para lograr ordenar gran cantidad de datos.

Pasos:

1. Elige un elemento de la lista, que llamaras pivote.

 lista = [3, 6, 1, 5, 2, 7, 4]
 # pivot = 4

2. Dividir la lista en tres, en la primera irán los números menores al pivote elegido el pivote y en la tercera los mayores a el.

 lista = [3, 6, 1, 5, 2, 7, 4]
 # pivot = 4
 menores = [3, 1, 2]
 iguales = [4]
 mayores = [6, 5, 7]

3. Repetir este procedimiento recursivamente en la lista de mayores y menores.

y por último...

4. Concatenamos todas las listas.

Rendimiento...

Si deseas ponerte algo mas matemático puedes medir la complejidad del algoritmo. Para esto te adelanto que... Quicksort tiene dos casos especiales y un tercero que no hace falta mencionarlo.. 🤔

• El Mejor Caso 👍: Cuando el pivote queda en el medio de la lista, con una ejecución promedio de O(nlog(n)).







• El Peor Caso 👎: Cuando el pivote se inclina consecuentemente hacia un lado, generando una lista de una solo elemento y la otra con el resto de ellos lo que hace que demore mas el tiempo de ejecución, su ejecución promedio es de O(n²).

¿Cómo mejoramos el tiempo de ejecución del algoritmo?

La respuesta descansa en la elección del pivote, siempre tratar que el pivote se encuentre en el medio del arreglo, una de las mejores técnicas que he visto es "a tres bandas", consiste en escoger tres números aleatorios y dividirlo entre 3 el resultado (num₁ + num₂ + num₃)/3. Por ejemplo:

 lista = [3, 6, 1, 5, 2, 7, 4]
 # Elegimos los 3 números aleatoriamente
 # num1 = 3, num2 = 4, num = 2
 # pivot = (num1 + num2 + num3)/3
 # pivot = 3

Que pasa si el control del pivote se te va de las manos, ¿Cómo podrías reposicionarla? o ¿Cómo podrías optimizar el posicionamiento del pivote, para que tome la forma del caso 1?

Esto sería muy complicado pero existe una manera de mantener al pivote en un lugar clave en donde se encuentre lo mas centrado posible, consiste en tener dos indices en la lista.

• j = indice que ira recorriendo la lista.
• i = indice del menor elemento.

Paso Total:

Condición: lista[j] <= pivot

• Si es verdad(True), entonces i = i + 1 y cambias lista(i) por lista(j) y lista(j) por lista(i)...
• Si es falsa(False), entonces no haces nada.

Totalmente Perdido?😖 no te preocupes, vamos por los ejemplos:

Tenemos una lista:

 lista = [2, 9, 4, 10, 5, 6, 8]

• 2 < 8 = True,
  j ++,
  i ++



• 9 <= 8 = False,
  j ++



• 4 <= 8 = True,
  j ++,
  i ++



• 10 <= 8 = False,
  j ++



• 5 <= 8 = True,
  j ++,
  i ++



• 6 <= 8 = True,
  j ++,
  i ++



• 8 <= 8 = True,
  j ++,
  i ++.
  Resumiendo sumas al indice i + 1 y lo cambias por el pivot

Y por último aplicamos Quicksort a ambos lados del pivote para que quede totalmente ordenado.

Y te quedara así..!

Si te gusto el pequeño tutorial no olvides suscribirte al blog, compartirlo en las redes y dejar tu comentario! Buena Suerte! 💩

Referencias: Wikipedia Quicksort, Video Optimización de Quicksort