QuickSort

Uno de los algoritmos de ordenación más populares es QuickSort. Es un método de divide-and-conquer (divide y vencerás) que de manera iterativa elige un elemento pivot del array, divide el array en 3 partes — los elementos más pequeños, los iguales y los más grandes que el pivot — y repite este proceso hasta llegar a un punto en el que todo el array está ordenado.

Entonces, en cada iteración:

Elegimos un pivot en el array

Movemos los elementos más pequeños a la parte izquierda del pivot

Movemos los elementos más grandes a la parte derecha del pivot

Agrupamos en el centro todos los elementos iguales al pivot

Repetimos este proceso con las partes izquierda y derecha

def quicksort(a):
    if len(a) <= 1:
        return a
    pivot = a[len(a) // 2]
    left = [x for x in a if x < pivot]
    middle = [x for x in a if x == pivot]
    right = [x for x in a if x > pivot]
    return quicksort(left) + middle + quicksort(right)

Esta implementación de QuickSort usa arreglos adicionales para las partes left, middle y right. Podemos hacerlo in-place modificando el código para usar índices y reacomodar los elementos directamente en el array.

def quicksort(a, start, end):
    if start >= end:                    # No hay elementos que ordenar
        return

    pivot = a[start]                    # Elegir un pivot
    l, r = start + 1, end               # Ordenar a[start+1 ... end]
    while l <= r:                       # Mientras queden elementos dentro del rango
        if a[l] < pivot:                # si a[l] < pivot => dejar a[i] sin cambios
            l += 1                      # Incrementar el puntero izquierdo
        else:                           # de lo contrario, mover a[l] al final
            a[l], a[r] = a[r], a[l]     # Intercambiar a[l] y a[r] -> mover al final
            r -= 1                      # Reducir el puntero derecho

    a[start], a[r] = a[r], a[start]     # Intercambiar pivot con a[r]
    quicksort(a, start, r - 1)          # Ordenar a[start ... r-1]
    quicksort(a, r + 1, end)            # Ordenar a[r+1 ... end]

Tal vez hayas notado que la manera de elegir el pivot fue diferente en estas dos implementaciones. El algoritmo QuickSort no impone restricciones específicas para escoger un pivot. Existen varias formas de hacerlo. A continuación, presentamos algunas ideas para seleccionar el pivot:

Primer elemento: a[start] como se ve en la segunda implementación

Último elemento: a[end]

Elemento medio: a[(start + end + 1) // 2]

Elemento aleatorio: elegir cualquier elemento en a[start ... end]

Elemento mediano: elegir la mediana del segmento actual. Esto garantiza que cada partición produzca partes left y right balanceadas, pero requiere una implementación más compleja.

Simulemos el algoritmo en varios arreglos:

[4, 1, -1, 0, 2, 8]

quicksort(a, 0, 5) → pivot = 4 [4, 1, -1, 0, 2, 8]

l=1, r=5 ⇒ a[l] = 1 < pivot ⇒ l += 1
l=2, r=5 ⇒ a[l] = -1 < pivot ⇒ l += 1
l=3, r=5 ⇒ a[l] = 0 < pivot ⇒ l += 1
l=4, r=5 ⇒ a[l] = 2 < pivot ⇒ l += 1
l=5, r=5 ⇒ a[l] = 8 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
swap a[start] and a[r] ⇒ [2, 1, -1, 0, 4, 8]
quicksort(a, 0, 3) and quicksort(a, 5, 5)

quicksort(a, 0, 3) → pivot = 2 [2, 1, -1, 0, 4, 8]

l=1, r=3 ⇒ a[l] = 1 < pivot ⇒ l += 1
l=2, r=3 ⇒ a[l] = -1 < pivot ⇒ l += 1
l=3, r=3 ⇒ a[l] = 0 < pivot ⇒ l += 1
swap a[start] and a[r] ⇒ [0, 1, -1, 2, 4, 8]
quicksort(a, 0, 2) and quicksort(a, 3, 3)

quicksort(a, 0, 2) → pivot = 0 [0, 1, -1, 2, 4, 8]

l=1, r=2 ⇒ a[l] = 1 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [0, -1, 1, 2, 4, 8]
l=1, r=1 ⇒ a[l] = -1 < pivot ⇒ l += 1
swap a[start] and a[r] ⇒ [-1, 0, 1, 2, 4, 8]
quicksort(a, 0, 0) and quicksort(a, 2, 2)

[-1, 0, 1, 2, 4, 8]

[4, 5, 3, 4, 4, 8, 4, 1, 2, 9, 7, 4, -1]

quicksort(a, 0, 12) → pivot = 4 [4, 5, 3, 4, 4, 8, 4, 1, 2, 9, 7, 4, -1]

l=1, r=12 ⇒ a[l] = 5 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [4, 5, 3, 4, 4, 8, 4, 1, 2, 9, 7, 4, -1]
l=1, r=11 ⇒ a[l] = -1 < pivot ⇒ l += 1
l=2, r=11 ⇒ a[l] = 3 < pivot ⇒ l += 1
l=3, r=11 ⇒ a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [4, -1, 3, 4, 4, 8, 4, 1, 2, 9, 7, 4, 5]
l=3, r=10 ⇒ a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [4, -1, 3, 4, 4, 8, 4, 1, 2, 9, 7, 4, 5]
l=3, r=9 ⇒ a[l] = 7 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [4, -1, 3, 7, 4, 8, 4, 1, 2, 9, 4, 4, 5]
l=3, r=8 ⇒ a[l] = 9 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [4, -1, 3, 9, 4, 8, 4, 1, 2, 7, 4, 4, 5]
l=3, r=7 ⇒ a[l] = 2 < pivot ⇒ l += 1
l=4, r=7 ⇒ a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [4, -1, 3, 2, 4, 8, 4, 1, 9, 7, 4, 4, 5]
l=4, r=6 ⇒ a[l] = 1 < pivot ⇒ l += 1
l=5, r=6 ⇒ a[l] = 8 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [4, -1, 3, 2, 1, 8, 4, 4, 9, 7, 4, 4, 5]
l=5, r=5 ⇒ a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [4, -1, 3, 2, 1, 4, 8, 4, 9, 7, 4, 4, 5]
swap a[start] and a[r] ⇒ [1, -1, 3, 2, 4, 4, 8, 4, 9, 7, 4, 4, 5]
quicksort(a, 0, 3) and quicksort(a, 5, 12)

quicksort(a, 0, 3) → pivot = 1 [1, -1, 3, 2, 4, 4, 8, 4, 9, 7, 4, 4, 5]

l=1, r=3 ⇒ a[l] = -1 < pivot ⇒ l += 1
l=2, r=3 ⇒ a[l] = 3 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [1, -1, 3, 2, 4, 4, 8, 4, 9, 7, 4, 4, 5]
l=2, r=2 ⇒ a[l] = 2 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [1, -1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
swap a[start] and a[r] ⇒ [-1, 1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
quicksort(a, 0, 0) and quicksort(a, 2, 3)

quicksort(a, 2, 3) → pivot = 2 [-1, 1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]

l=3, r=3 ⇒ a[l] = 3 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
swap a[start] and a[r] ⇒ [-1, 1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
quicksort(a, 2, 1) and quicksort(a, 3, 3)

quicksort(a, 5, 12) → pivot = 4 [-1, 1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]

l=6, r=12 ⇒ a[l] = 8 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
l=6, r=11 ⇒ a[l] = 5 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 5, 4, 9, 7, 4, 4, 8]
l=6, r=10 ⇒ a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 4, 9, 7, 4, 5, 8]
l=6, r=9 ⇒ a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 4, 9, 7, 4, 5, 8]
l=6, r=8 ⇒ a[l] = 7 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 7, 4, 9, 4, 4, 5, 8]
l=6, r=7 ⇒ a[l] = 9 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 9, 4, 7, 4, 4, 5, 8]
l=6, r=6 ⇒ a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 9, 7, 4, 4, 5, 8]
swap a[start] and a[r] ⇒ [-1, 1, 2, 3, 4, 4, 4, 9, 7, 4, 4, 5, 8]
quicksort(a, 5, 4) and quicksort(a, 6, 12)

quicksort(a, 6, 12) → pivot = 4 [-1, 1, 2, 3, 4, 4, 4, 9, 7, 4, 4, 5, 8]

l=7, r=12 ⇒ a[l] = 9 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 9, 7, 4, 4, 5, 8]
l=7, r=11 ⇒ a[l] = 8 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 8, 7, 4, 4, 5, 9]
l=7, r=10 ⇒ a[l] = 5 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 5, 7, 4, 4, 8, 9]
l=7, r=9 ⇒ a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 4, 7, 4, 5, 8, 9]
l=7, r=8 ⇒ a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 4, 7, 4, 5, 8, 9]
l=7, r=7 ⇒ a[l] = 7 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 7, 4, 4, 5, 8, 9]
swap a[start] and a[r] ⇒ [-1, 1, 2, 3, 4, 4, 4, 7, 4, 4, 5, 8, 9]
quicksort(a, 6, 5) and quicksort(a, 7, 12)

quicksort(a, 7, 12) → pivot = 7 [-1, 1, 2, 3, 4, 4, 4, 7, 4, 4, 5, 8, 9]

l=8, r=12 ⇒ a[l] = 4 < pivot ⇒ l += 1
l=9, r=12 ⇒ a[l] = 4 < pivot ⇒ l += 1
l=10, r=12 ⇒ a[l] = 5 < pivot ⇒ l += 1
l=11, r=12 ⇒ a[l] = 8 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 7, 4, 4, 5, 8, 9]
l=11, r=11 ⇒ a[l] = 9 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 7, 4, 4, 5, 9, 8]
swap a[start] and a[r] ⇒ [-1, 1, 2, 3, 4, 4, 4, 5, 4, 4, 7, 9, 8]
quicksort(a, 7, 9) and quicksort(a, 11, 12)

quicksort(a, 7, 9) → pivot = 5 [-1, 1, 2, 3, 4, 4, 4, 5, 4, 4, 7, 9, 8]

l=8, r=9 ⇒ a[l] = 4 < pivot ⇒ l += 1
l=9, r=9 ⇒ a[l] = 4 < pivot ⇒ l += 1
swap a[start] and a[r] ⇒ [-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 9, 8]
quicksort(a, 7, 8) and quicksort(a, 10, 9)

quicksort(a, 7, 8) → pivot = 4 [-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 9, 8]

l=8, r=8 ⇒ a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 9, 8]
swap a[start] and a[r] ⇒ [-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 9, 8]
quicksort(a, 7, 6) and quicksort(a, 8, 8)

quicksort(a, 11, 12) → pivot = 9 [-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 9, 8]

l=12, r=12 ⇒ a[l] = 8 < pivot ⇒ l += 1
swap a[start] and a[r] ⇒ [-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 8, 9]
quicksort(a, 11, 11) and quicksort(a, 13, 12)

[-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 8, 9]

El tiempo de ejecución promedio del algoritmo QuickSort es . Sin embargo, dependiendo de cómo se elija el pivot, el rendimiento puede caer a cuadrático .

🤔 ¿Puedes pensar en un ejemplo donde el algoritmo haría operaciones si siempre elegimos start como el pivot?

Challenge

Dada una lista de n enteros y q pivots, se pide mover todos los elementos más pequeños que el pivot a su izquierda, y todos los elementos más grandes a su derecha, dejando todos los iguales juntos (contiguos, a la derecha de los más pequeños y a la izquierda de los más grandes).

Entrada

La primera línea de la entrada contiene un único entero n (1 ≤ n ≤ 100 000).

La siguiente línea contiene una lista de n enteros separados por espacios ( ≤ ≤ ).

La tercera línea contiene un único entero q (1 ≤ q ≤ 10).

La siguiente línea contiene q pivots, cada uno representado por un índice (1 ≤ ≤ n), que indica la posición del elemento pivot.

Salida

Para cada uno de los q pivots, el programa debe imprimir el array resultante tras hacer el reacomodo. Si hay varias respuestas posibles, se puede imprimir cualquiera de ellas.

Ejemplos

Entrada	Salida
7 1 8 0 3 4 -2 4 3 4 2 5	1 0 -2 3 4 4 8 -2 0 1 3 4 4 8 -2 0 1 3 4 4 8

Challenge

Entrada

Salida

Ejemplos

Constraints

To check your solution you need to sign in

Sign in to continue