QuickSort

📖

Este es un algoritmo de ordenación el cual sigue el esquema de Divide y Vencerás

El algoritmo consiste en tomar un valor del array como referencia (usualmente el primero), luego recorremos el resto del array creando dos sub-arrays, uno para contener los números menores que el pivote, y otro para los mayores. De esta manera acabaremos con dos arrays desordenados, pero se garantiza que los de un array y los del otro son menores o mayores que el pivote respectivamente.

Dividir
A continuación procederemos a hacer una llamada recursiva por cada uno de estos arrays.

Vencer
Hemos llegado al caso base, pudiendo ser este, un array suficientemente pequeño para ser ordenado por otro método, o un array de tamaño 1

Combinar
Finalmente concatenaremos el resultado de el array de menores, el pivote y el array de mayores en un nuevo array

ℹ️

Este algoritmo podemos programarlo de dos manera una más sencilla pero menos eficiente que la otra

Opción 1 (facil pero menos eficiente)
Creamos arrays auxiliares para los elementos menores y mayores combinando el resultado concatenando los array con el pivote en medio

Opción 2 (dificil pero más eficiente)
Operaremos sobre el array original, utilizaremos puntero para ir seleccionando los objectos mayores y menores. Sabiendo que el pivote toma la posición $0$ , el puntero $i =1$ y el puntero $j=n-1$ (último elemento). Si el valor en la posición $i$ es menor que el pivote, entonces se hace incrementa el valor de $i$ (se selecciona el siguiente elemento) este paso continúa hasta que encontremos un elemento mayor que el pivote. A continuación haremos un proceso similar en $j$ retrocediendo el puntero cuando encontremos valores mayores que el pivote.
Cuando $j$ encuentre un valor menor que el pivote, moverá el valor apuntado por $i$ a $j$ y viceversa.
Cuando $i$ y $j$ se hayan cruzado, movemos el pivote a $j$ y veceversa

Código opción 1

from random import randint

# This version of quick_sort makes a copy of the array on each recursive call
# The main advantage of this implementation is that it is easier to understand
# The main disadvantage is that it uses more memory
# This implementation differs from the v2 in the way that the pivot is chosen and and that in this implementation we are not swapping with another element in the other side of the pivot

def quick_sort(arr):
    # Base case
    if len(arr) <= 1:
        return arr
    # Recursive case
    else:
        # Choose a pivot
        pivot = arr[0]
        left = []
        right = []
        
        # Divide the array in three parts
        for i in range(1, len(arr)):
            if arr[i] <= pivot:
                left.append(arr[i])
            else:
                right.append(arr[i])
        # Recursive call
        return quick_sort(left) + [pivot] + quick_sort(right)


if __name__ == "__main__":
    n = 20
    # Generate a random unsorted array
    arr1 = [randint(0, 100) for _ in range(n)]

    res1 = quick_sort(arr1)
    print(res1)

Código opción 2

from random import randint

# This version of quick_sort does not make a copy of the array on each recursive call, it will swap elements in place
# The main advantage is that it uses less memory
# The main disadvantage is that it is harder to understand
# This implementation differs from the v1 in the way that the pivot is chosen and that in this implementation we are swapping elements with the pivot

def quick_sort(arr, i, j):
    # Base case
    if i >= j:
        return arr
    # Recursive case
    else:
        # Choose a pivot
        pivot = arr[i]  # Choose the first element as the pivot
        left = i + 1    # The left pointer starts at the second element
        right = j       # The right pointer starts at the last element
        
        # Divide the array in two parts using the pivot, elements smaller than the pivot will be on the left and elements greater than the pivot will be on the right
        # We use the <= operator since we want to include the pivot in the left part
        while left <= right:
            # Find an element greater than the pivot
            while left <= right and arr[left] <= pivot:
                left += 1
            # Find an element smaller than the pivot
            while left <= right and arr[right] > pivot:
                right -= 1
                
            # > At this point we have found an element greater than the pivot on the left and an element smaller than the pivot on the right
                
            # Swap the elements
            if left < right:
                arr[left], arr[right] = arr[right], arr[left]
                
        # Swap the pivot with the element in the right position
        arr[i], arr[right] = arr[right], arr[i]
        # Recursive call
        quick_sort(arr, i, right - 1)
        quick_sort(arr, right + 1, j)
        return arr

if __name__ == "__main__":
    n = 20
    # Generate a random sorted array
    arr1 = [randint(0, 100) for _ in range(n)]

    res1 = quick_sort(arr1, 0, len(arr1) - 1)
    print(res1)