Divide y vencerás

1 Táctica de divide-y-vencerás

La táctica divide-y-vencerás resuelve problemas:

  • divide el problema en subproblemas
  • conquista, resolviendo los subproblemas
  • combina las soluciones

2 Problema de ordenar listas

Tenemos una lista de objetos, que son comparables dos a dos y los queremos ordenarlos de menor a mayor.

3 Método de QuickSort

El método de quicksort es un método para ordenar una lista:

  • Elige un elemento, llamado el pivote.
  • divide el problema, poniendo dos listas, una, la lista de elementos mayores que el pivote y otra con los elementos menores del pivote.
  • conquista ordenando estas sublistas.
  • combina las soluciones simplemente juntando las listas.

4 Dividir el array en dos

\[ 5\ \color{red}{3}\ 2\ 1\ 7\ 12\ 9\ 4\ \color{blue}{6} \]

5 Dividir el array en dos

\[ 5\ 3\ \color{red}{2}\ 1\ 7\ 12\ 9\ 4\ \color{blue}{6} \]

6 Dividir el array en dos

\[ 5\ 3\ 2\ \color{red}{1}\ 7\ 12\ 9\ 4\ \color{blue}{6} \]

7 Dividir el array en dos

\[ 5\ 3\ 2\ 1\ \color{red}{7}\ 12\ 9\ 4\ \color{blue}{6} \]

8 Dividir el array en dos

\[ 5\ 3\ 2\ 1\ \color{red}{7}\ 12\ 9\ \color{blue}{4}\ 6 \]

9 Dividir el array en dos

\[ 5\ 3\ 2\ 1\ \color{red}{4}\ 12\ 9\ \color{blue}{7}\ 6 \]

10 Dividir el array en dos

\[ 5\ 3\ 2\ 1\ 4\ \color{red}{12}\ \color{blue}{9}\ 7\ 6 \]

11 Dividir el array en dos

\[ 5\ 3\ 2\ 1\ \color{blue}{4}\ \color{red}{12}\ 9\ 7\ 6 \]

12 Dividir el array en dos

\[ 4\ 3\ 2\ 1\ \color{blue}{5}\ \color{red}{12}\ 9\ 7\ 6 \]

13 Resultado ordenado

\[ 1\ 2\ 3\ 4\ \color{blue}{5}\ 6\ 7\ 9\ 12 \]

14 Pregunta

Dado el siguiente array, \[ D\ \color{red}{C}\ A\ C\ J\ B\ B\ G\ \color{blue}{A}, \] decir cuales son los tres siguientes pasos que realiza el algoritmo quicksort.

15 Análisis de la complejidad

  • En el mejor caso: \(O(n\log n)\)
  • En el peor caso: \(n^2/2\)
  • Es un algoritmo que no necesita más de extra memoria (in-place)
  • No es estable.

16 Mejoras de quicksort

  • Utilizad otro algoritmo de ordenación cuando las listas son pequeñas.
  • Elegid el pivote lo más parecido al valor medio como sea posible.