Quick sort

Este sorting tiene complejidad $O (n^{2})$ , pero es uno de los mas usados aun asi. Esto tiene que ver con el hecho de que en los casos promedio la complejidad baja a $O (n \log (n))$ .

Primero partimos de una premisa algo exagerada, pero sirve para el ejemplo. Supongamos que conocemos el elemento mediano del arreglo (el que separa en dos mitades iguales, o casi). En ese caso podemos separar la lista en dos: por un lado los elementos que son menores a esa mediana, y por el otro los que son mayores. Una vez hecho esto, podemos repetir el proceso en cada mitad, buscando su mediana, y separando esas listas en dos mitades, a las cuales ordenamos, y asi sucesivamente. Finalmente, unimos todo y terminamos con una lista completamente ordenada.

Como podran imaginar, este algoritmo es buenisimo siempre que sepamos quien es la mediana. Ahora, supongamos que no conocemos la mediana (que es lo que va a pasar casi siempre). Entonces, vamos a tener que elegir a algun elemento como punto medio para partir la lista. Aca tenemos un problema grave, ya que la eleccion de este pivot es clave.

Supongamos que elegimos el elemento mas chico como pivot. Terminariamos por poner todos los elementos a su derecha, ya que al ser el minimo todos van a ser mayores a el. Esto no ordena nada, de hecho, deja todo como estaba.

Por eso, aunque parezca poco logico, lo mejor para elegir el pivote, es elegirlo al azar. La probabilidad de elegir justo el elemento minimo es $\frac{1}{n}$ , identica a la probabilidad de elegir al mayor. Por otro lado, la probabilidad de elegir cualquier elemento que no sea ni el maximo ni el minimo es de $\frac{n - 2}{n}$ , que es bastante.

Es por esto que se dice que, en el caso promedio, y bajo una buena eleccion de pivote, nuestros tiempos de ordenamiento no suben radicalmente.