Clasificación rápida en Python

Quicksort es uno de los algoritmos de clasificación más extendidos debido a la relativa simplicidad de implementación y rendimiento eficiente. En este artículo, implementaremos Quicksort en Python.

Introducción

Quicksort es un algoritmo de clasificación popular y se usa a menudo junto con Merge Sort. Es un buen ejemplo de un algoritmo de clasificación eficiente, con una complejidad promedio de O(nlogn). Parte de su popularidad también deriva de la facilidad de implementación.

Usaremos enteros simples en la primera parte de este artículo, pero daremos un ejemplo de cómo cambiar este algoritmo para ordenar objetos de una clase personalizada.

Quicksort es un representante de tres tipos de algoritmos de clasificación: divide y vencerás, in situ e inestable.

  • Divide y vencerás: Quicksort divide la matriz en matrices más pequeñas hasta que termina con una matriz vacía, o una que tiene solo un elemento, antes de ordenar recursivamente las matrices más grandes.
  • In situ: Quicksort no crea ninguna copia de la matriz ni de ninguna de sus subarreglas. Sin embargo, requiere memoria de pila para todas las llamadas recursivas que realiza.
  • Inestable: un algoritmo de ordenación estable es aquel en el que los elementos con el mismo valor aparecen en el mismo orden relativo en la matriz ordenada que antes de ordenar la matriz. Un algoritmo de clasificación inestable no garantiza esto, puede por supuesto suceder, pero no está garantizado.

Esto es algo que se vuelve importante cuando ordenas objetos en lugar de tipos primitivos. Por ejemplo, imagina que tienes varios objetos Persona que tienen la misma edad, es decir, Dave tiene 21 años y Mike tiene 21 años. Si tuvieras que usar Quicksort en una colección que contiene tanto a Dave como a Mike, ordenados por edad, hay no hay garantía de que Dave se presente antes que Mike cada vez que ejecute el algoritmo, y viceversa.

Ordenación rápida

La versión básica del algoritmo hace lo siguiente:

Divide la colección en dos partes (más o menos) iguales tomando un elemento pseudoaleatorio y usándolo como un pivote.

Los elementos más pequeños que el pivote se mueven a la izquierda del pivote y los elementos más grandes que el pivote a la derecha.

Este proceso se repite para la colección a la izquierda del pivote, así como para la matriz de elementos a la derecha del pivote hasta que se ordena toda la matriz.

Cuando describimos elementos como "más grandes" o "más pequeños" que otro elemento, no significa necesariamente números enteros más grandes o más pequeños, podemos ordenar por cualquier propiedad que elijamos.

Si tenemos una clase personalizada ‘Persona’, y cada persona tiene un ’nombre’ y una ’edad’, podemos ordenar por ’nombre’ (lexicográficamente) o por edad (ascendente o descendente).

Cómo funciona Quicksort

Quicksort, en la mayoría de los casos, no podrá dividir la matriz en partes iguales. Esto se debe a que todo el proceso depende de cómo elijamos el pivote. Necesitamos elegir un pivote para que sea aproximadamente más grande que la mitad de los elementos y, por lo tanto, más o menos más pequeño que la otra mitad de los elementos. Tan intuitivo como puede parecer este proceso, es muy difícil de hacer.

Piénselo por un momento: ¿cómo elegiría un pivote adecuado para su matriz? Se han presentado muchas ideas sobre cómo elegir un pivote en la historia de Quicksort: elegir un elemento al azar, lo que no funciona debido a lo “caro” que es elegir un elemento aleatorio sin garantizar un buen pivote. elección; escoger un elemento del medio; elegir una mediana del primer, medio y último elemento; e incluso fórmulas recursivas más complicadas.

El enfoque más directo es simplemente elegir el primer (o último) elemento. Esto lleva a que Quicksort, irónicamente, funcione muy mal en arreglos ya ordenados (o casi ordenados).

Así es como la mayoría de la gente elige implementar Quicksort y, dado que es simple y esta forma de elegir el pivote es una operación muy eficiente (y tendremos que hacerlo repetidamente), esto es exactamente lo que haremos.

Ahora que hemos elegido un pivote, ¿qué hacemos con él? Una vez más, hay varias formas de realizar la partición en sí. Tendremos un "puntero" a nuestro pivote, y un puntero a los elementos "más pequeños" y un puntero a los elementos "más grandes".

El objetivo es mover los elementos para que todos los elementos más pequeños que el pivote estén a su izquierda y todos los elementos más grandes estén a su derecha. Los elementos más pequeños y más grandes no terminan necesariamente ordenados, solo los queremos en el lado correcto del pivote. Luego pasamos recursivamente por el lado izquierdo y derecho del pivote.

Una mirada paso a paso a lo que estamos planeando hacer ayudará a ilustrar el proceso. Usando la matriz que se muestra a continuación, hemos elegido el primer elemento como el pivote (29), y el puntero a los elementos más pequeños (llamados "low") comienza justo después, y el puntero a los elementos más grandes (llamados \ “alto") comienza al final.

  • 29 es el primer pivote, low apunta a 99 y high apunta a 44

29 | 99 (bajo),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21,44 (alto)

  • Movemos high a la izquierda hasta que encontremos un valor más bajo que nuestro pivote.

29 | 99 (bajo),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21 (alto),44

  • Ahora que nuestra variable alta apunta a 21, un elemento más pequeño que el pivote, queremos encontrar un valor cerca del comienzo de la matriz con el que podamos intercambiarlo. No tiene ningún sentido intercambiar con un valor que también es más pequeño que el pivote, por lo que si bajo apunta a un elemento más pequeño, tratamos de encontrar uno que sea más grande.
  • Movemos nuestra variable baja hacia la derecha hasta encontrar un elemento más grande que el pivote. Afortunadamente, bajo ya estaba posicionado en 99.
  • Intercambiamos lugares de bajo y alto:

29 | 21 (bajo),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,99 (alto),44

  • Inmediatamente después de hacer esto, movemos high a la izquierda y low a la derecha (ya que 21 y 99 ahora están en sus lugares correctos)
  • De nuevo, nos movemos alto hacia la izquierda hasta llegar a un valor inferior al pivote, que encontramos enseguida - 12
  • Ahora buscamos un valor mayor que el pivote moviendo bajo a la derecha, y encontramos el primer valor en 41

Este proceso continúa hasta que los punteros bajo y alto finalmente se encuentran en un solo elemento:

29 | 21,27,12,19,28 (bajo/alto),44,78,87,66,31,76,58,88,83,97,41,99,44

  • Ya no tenemos más uso de este pivote, por lo que lo único que queda por hacer es intercambiar pivot y high y hemos terminado con este paso recursivo:

28,21,27,12,19,29,44,78,87,66,31,76,58,88,83,97,41,99,44

Como puede ver, hemos logrado que todos los valores menores de 29 estén ahora a la izquierda de 29, y todos los valores mayores de 29 estén a la derecha.

Luego, el algoritmo hace lo mismo para la colección 28,21,27,12,19 (lado izquierdo) y 44,78,87,66,31,76,58,88,83,97,41, Colección 99,44 (lado derecho).

Implementación

Clasificación de matrices {#clasificación de matrices}

Quicksort es un algoritmo naturalmente recursivo: divide la matriz de entrada en matrices más pequeñas, mueve los elementos al lado adecuado del pivote y repite.

Veamos cómo se verían algunas llamadas recursivas:

  • Cuando llamamos al algoritmo por primera vez, consideramos todos los elementos, desde los índices 0 hasta n-1, donde n es el número de elementos en nuestra matriz.
  • Si nuestro pivote terminara en la posición k, repetiríamos el proceso para los elementos de 0 a k-1 y de k+1 a n-1.
  • Al ordenar los elementos de k+1 a n-1, el pivote actual terminaría en alguna posición p. Luego ordenaríamos los elementos de k+1 a p-1 y de p+1 a n-1, y así sucesivamente.

Dicho esto, utilizaremos dos funciones: partition() y quick_sort(). La función quick_sort() primero particionará() la colección y luego se llamará recursivamente a sí misma en las partes divididas.

Empecemos con la función partition():

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def partition(array, start, end):
    pivot = array[start]
    low = start + 1
    high = end

    while True:
        # If the current value we're looking at is larger than the pivot
        # it's in the right place (right side of pivot) and we can move left,
        # to the next element.
        # We also need to make sure we haven't surpassed the low pointer, since that
        # indicates we have already moved all the elements to their correct side of the pivot
        while low <= high and array[high] >= pivot:
            high = high - 1

        # Opposite process of the one above
        while low <= high and array[low] <= pivot:
            low = low + 1

        # We either found a value for both high and low that is out of order
        # or low is higher than high, in which case we exit the loop
        if low <= high:
            array[low], array[high] = array[high], array[low]
            # The loop continues
        else:
            # We exit out of the loop
            break

    array[start], array[high] = array[high], array[start]

    return high

Y finalmente, implementemos la función quick_sort():

1
2
3
4
5
6
7
def quick_sort(array, start, end):
    if start >= end:
        return

    p = partition(array, start, end)
    quick_sort(array, start, p-1)
    quick_sort(array, p+1, end)

Con ambos implementados, podemos ejecutar quick_sort() en una matriz simple:

1
2
3
4
array = [29,99,27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21,44]

quick_sort(array, 0, len(array) - 1)
print(array)

Producción:

1
[12, 19, 21, 27, 28, 29, 31, 41, 44, 44, 58, 66, 76, 78, 83, 87, 88, 97, 99]

Dado que el algoritmo es inestable, no hay garantía de que estos dos 44 estuvieran en este orden entre sí. Tal vez originalmente se cambiaron, aunque esto no significa mucho en una matriz de enteros.

Clasificación de objetos personalizados

Hay algunas formas de reescribir este algoritmo para ordenar objetos personalizados en Python. Una forma muy pythonica sería implementar los operadores de comparación para una clase dada, lo que significa que en realidad no necesitaríamos cambiar la implementación del algoritmo ya que >, ==, <=, etc. trabajar en nuestro objeto de clase.

Otra opción sería permitir que la persona que llama proporcione un método a nuestro algoritmo que luego se usaría para realizar la comparación real de los objetos. Reescribir el algoritmo de esta manera para usarlo con objetos personalizados es bastante sencillo. Sin embargo, tenga en cuenta que el algoritmo no es estable.

Empecemos con una clase Persona:

1
2
3
4
5
6
7
class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __str__(self):
        return self.name

Esta es una clase bastante básica con solo dos propiedades, ’nombre’ y ’edad’. Queremos usar age como nuestra clave de clasificación, lo que haremos proporcionando una función lambda personalizada al algoritmo de clasificación.

Pero primero, veamos cómo se usa esta función proporcionada dentro del algoritmo. En lugar de hacer una comparación directa con los operadores <= o >=, llamamos a la función para decir qué Persona tiene mayor edad:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def partition(array, start, end, compare_func):
    pivot = array[start]
    low = start + 1
    high = end

    while True:
        while low <= high and compare_func(array[high], pivot):
            high = high - 1

        while low <= high and not compare_func(array[low], pivot):
            low = low + 1

        if low <= high:
            array[low], array[high] = array[high], array[low]
        else:
            break

    array[start], array[high] = array[high], array[start]

    return high
1
2
3
4
5
6
7
def quick_sort(array, start, end, compare_func):
    if start >= end:
        return

    p = partition(array, start, end, compare_func)
    quick_sort(array, start, p-1, compare_func)
    quick_sort(array, p+1, end, compare_func)

Y ahora, ordenemos una colección de estos objetos. Puede ver que la comparación de objetos se proporciona a la llamada quick_sort a través de una lambda, que hace la comparación real de la propiedad age:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
p1 = Person("Dave", 21)
p2 = Person("Jane", 58)
p3 = Person("Matthew", 43)
p4 = Person("Mike", 21)
p5 = Person("Tim", 10)

array = [p1,p2,p3,p4,p5]

quick_sort(array, 0, len(array) - 1, lambda x, y: x.age < y.age)
for person in array:
    print(person)

La salida es:

1
2
3
4
5
Tim
Dave
Mike
Matthew
Jane

Al implementar el algoritmo de esta manera, se puede usar con cualquier objeto personalizado que elijamos, siempre que proporcionemos una función de comparación adecuada.

Optimizaciones de Quicksort

Dado que Quicksort ordena las "mitades" de una matriz dada de forma independiente, es muy conveniente para la paralelización. Podemos tener un subproceso separado que ordene cada "mitad" de la matriz, e idealmente podríamos reducir a la mitad el tiempo necesario para ordenarlo.

Sin embargo, Quicksort puede tener una pila de llamadas recursivas muy profunda si tenemos mala suerte en nuestra elección de un pivote, y la paralelización no es tan eficiente como lo es con Merge Sort.

Se recomienda utilizar un algoritmo simple y no recursivo para clasificar matrices pequeñas. Incluso algo simple como la ordenación por inserción es más eficiente en arreglos pequeños que la ordenación rápida. Entonces, idealmente, podríamos verificar si nuestro subarreglo tiene solo una pequeña cantidad de elementos (la mayoría de las recomendaciones dicen alrededor de 10 o menos), y si es así, lo ordenaríamos con Ordenación por inserción.

Una variación popular de Quicksort es Multi-pivot Quicksort, que divide el arreglo original en n arreglos más pequeños, usando n-1 pivotes. Sin embargo, la mayoría de las veces solo se utilizan dos pivotes, no más.

Dato curioso: en la implementación de clasificación de Java 7 se utilizó Quicksort de doble pivote, junto con Insertion Sort para arreglos más pequeños.

Conclusión

Como mencionamos anteriormente, la eficiencia de Quicksort depende en gran medida de la elección del pivote: puede "hacer o deshacer" la complejidad del tiempo (y el espacio de pila) del algoritmo. La inestabilidad del algoritmo también es algo que puede ser un factor decisivo cuando se usan objetos personalizados.

Sin embargo, a pesar de todo esto, la complejidad de tiempo promedio de Quicksort de O(n*log~n~) y su uso de espacio relativamente bajo y su implementación simple, lo convierten en un algoritmo muy eficiente y popular.

Si desea obtener más información, consulte nuestro otro artículo, Clasificación de algoritmos en Python, que cubre más algoritmos de clasificación en Python, pero no tan en profundidad. rofundidad.