Ordenación QuickSort en Python

Para ordenar listas o valores de un array existen varios métodos. Son bastante conocidos los dos siguientes.

• BubbleSort. El método de ordenación de la burbuja (bubble sort)
• QuickSort. El método rápido de ordenación (quick sort)

El método de la burbuja realiza una ordenación comparando todos los elementos por parejas. Es un buen método pero si el número de elementos a ordenar es muy grande este procedimiento se relentiza que ya el tiempo de cálculo crece con el cuadrado de n, del número de elementos. Por ejemplo, para ordenar un millón de valores no sería adecuado.

Para un elevado número de elementos a ordenar se aconseja el método QuickSort que se basa en dividir los elementos de la lista en dos subgrupos, los menores y los mayores a un elemento dado que se usa como pivote. Existen diferentes método para elegir el pivote óptimo, pero nosotros por simplicidad utilizaremos como pivote el primer elemento de la lista. De esta forma, los elementos inferiores al pivote los situaremos en una sublista que hemos denominado Izquierda, y los elementos superiores al pivote los situaremos una sublista denominada Derecha. Luego reconstruiremos la lista concatenando la lista de la izquierda, con el pivote que llamaremos centro, y con la lista de la derecha.

A su vez para cada una de las sublistas se repite este proceso de forma recursiva, hasta que la sublista más profunda únicamente tiene un elemento.

La filosofía de este algoritmo para llegar a ordenar listas largas es "Divide y vencerás".

• https://repl.it/@valoro/QuickSortPython

Código

miLista = [34,93,19,58,12,28,95,37,23,80,57,82,55,48,21,39,53,65,30,32,84,64,44,68,36]

def sort(lista):
    izquierda = []
    centro = []
    derecha = []
    if len(lista) > 1:
        pivote = lista[0]
        for i in lista:
            if i < pivote:
                izquierda.append(i)
            elif i == pivote:
                centro.append(i)
            elif i > pivote:
                derecha.append(i)
        #print(izquierda+["-"]+centro+["-"]+derecha)
        return sort(izquierda)+centro+sort(derecha)
    else:
      return lista

print(miLista)
print(sort(miLista))

El resultado obtenido es el de la siguiente imagen. Primero se imprime la lista original que deseamos ordenar, y luego se imprime la lista ya ordenada.

Existe una línea con un comentario en el código, si quitamos la almohadilla (#) del comentario y convertimos esa línea en ejecutable, obtendremos el siguiente resultado.

En la imagen anterior vemos el resultado de las diferentes iteraciones. Se ve que el método de ordenación va actuando por sublistas colocando el elemento pivote en el centro.

Vamos a ordenar una lista grande de elementos para ver que se realiza en un tiempo razonable.

• https://repl.it/@valoro/ordenaListaGrande