Procedimiento mejorado segundo¶

Tomemos n=100 siendo a

a = [82, 14, 53, 81, 34, 40, 25, 52, 22, 91, 93, 80, 79, 5, 8, 17, 99, 96, 16, ......]

Se basa en dividir los n números de la pila A inicial en s tramos.
Por ejemplo, para n=100 dividimos en s=5 tramos.
Posteriormente tendremos que hacer pruebas para determinar el s óptimo para cada n, y también en función del grado de complejidad de la pila A.

El primer tramo son los números 1 a 20, que se buscan en A y se pasan a B, con la función separa.
Para ordenar esos 20 números en B de forma creciente (del 20 al 1) usamos la pila A como pila auxiliar, con la función ordena.
Cuando ya tengamos el priemer tramo ordenado de forma creciente en B vamos a por el segundo tramo
Esto se hace con todos los tramos salvo el último
En el último tramo, en la pila B, vemos que deben haber quedado ordenados de forma decreciente los números de 80 a 1, así 80,79,78,...,1.
En el úlitmo tramo, en la pila A, quedaran los últimos 20 números desordenados.
Estos 20 últimos números se ordenan en A de forma creciente: 81,82,...,100, para ello se usa la pila B como pila auxiliar.
Finalmente se pasan los números de B a A.

In [43]:

# FUNCIONES
from random import sample, seed
seed()

# la función da True si ponemos lista_ordenada([4,3,2,1], orden_inverso=True)
def lista_ordenada(lis, orden_inverso=False):
    ordenada = False
    aux = lis[:]
    aux.sort(reverse=orden_inverso)
    if aux == lis:
        ordenada = True
    return ordenada

def sa(a,b):
    if len(a) > 1: a[0],a[1] = a[1],a[0]
    return a,b
def sb(a,b):
    if len(b) > 1: b[0],b[1] = b[1],b[0]
    return a,b
def ss(a,b):
    sa(a,b)
    sb(a,b)
    return a,b
def pa(a,b):
    if len(b) > 0:
        a.insert(0, b[0])
        b.pop(0)
    return a,b
def pb(a,b):
    if len(a) > 0:
        b.insert(0, a[0])
        a.pop(0)
    return a,b
def ra(a,b):
    if len(a) > 1: a.append(a.pop(0))
    return a,b
def rb(a,b):
    if len(b) > 1: b.append(b.pop(0))
    return a,b
def rr(a,b):
    ra(a,b)
    rb(a,b)
    return a,b
def rra(a,b):
    if len(a) > 1: a.insert(0, a.pop())
    return a,b
def rrb(a,b):
    if len(b) > 1: b.insert(0, b.pop())
    return a,b
def rrr(a,b):
    rra(a,b)
    rrb(a,b)
    return a,b

In [48]:

# PROCEDIMIENTO MEJORADO SEGUNDO
# dividiendo los n=100 valores aleatorios en s=5 grupos de n/s=20 números cada uno
# si no es divisible se toma un ancho=int(n/s) y se ajusta el último para que finalice en n
def separa(tramo, n, s, a, b):   # se llevan de la pila A a la B los números del tramo que toca
    contador = 0
    ancho = int(n/s)
    fin = tramo * ancho          # fin del tramo
    inicio = (tramo-1)*ancho+1   # inicio del tramo
    pasados = 0   # cuenta cuantos números se han pasado de la pila A a la B
    while pasados < fin-inicio+1: # recorremos los elementos de la plia A hasta que pasemos todos los números de este tramo
        if inicio <= a[0] <= fin:
            pb(a,b)
            contador += 1
            pasados += 1
        else:
            ra(a,b)
            contador += 1
    return a, b, contador

def ordena(tramo, n, s, a, b):   # Pasamos de B a A los del tramo que toca, comenzando por el nº mayor, que para el tramo 1 es 5.
    # ordena los números recientemente separados y llevados a B
    # el objetivo es que esos números queden en B ordenados de forma decreciente: 5,4,3,2,1
    contador = 0
    ancho = int(n/s)
    fin = tramo * ancho          # fin del tramo
    inicio = (tramo-1)*ancho+1   # inicio del tramo
    while not lista_ordenada(b, orden_inverso=True): # se repite hasta que B quede ordenada decrecientemente. Si solo queda un elemento en B es que está ordenada
        # buscamos el máximo y vamos haciendo ra o rra hasta que quede el primero
        while max(b) != b[0]:
            #print("max(b):", max(b))
            if b.index(max(b)) <= int(len(b)/2):
                rb(a,b)
            else:
                rrb(a,b)
            contador += 1
        if not lista_ordenada(b, orden_inverso=True):
            pa(a,b); contador += 1
    while len(a) > n-fin:   # llevamos de A a B los números del tramo que toca
        pb(a,b); contador += 1
    return a, b, contador

def ordena_final(tramo, n, s, a, b):    # ordena los números del úlitmo tramo que están en "A" y el objetivo es que queden crecientes: ...,18,19,20.
    contador = 0
    ancho = int(n/s)
    fin = n           # en el último tramo se ajusta para que el último nº sea igual a n
    inicio = (tramo-1)*ancho+1   # inicio del tramo
    while not lista_ordenada(a): # se repite hasta que A quede ordenada en orden creciente. Si solo queda un elemento en A es que está ordenada
        while min(a) != a[0]:
            #print("max(b):", max(b))
            if a.index(min(a)) <= int(len(a)/2):
                ra(a,b)
            else:
                rra(a,b)
            contador += 1
        if not lista_ordenada(a):
            pb(a,b); contador += 1
    while len(b) > 0:   # llevamos de B a A todos los números que hay en B
        pa(a,b); contador += 1
    return a, b, contador

if __name__ == "__main__":
    # Generación de la pila A
    n = 100   # número de elementos de la pila
    #a = sample(range(1, n+1), n)
    a = [82, 14, 53, 81, 34, 40, 25, 52, 22, 91, 93, 80, 79, 5, 8, 17, 99, 96, 16, 65, 72, 18, 94, 66, 43, 44, 2, 3, 97, 86, 6, 32, 77, 35, 68, 61, 45, 63, 24, 83, 37, 48, 28, 95, 39, 60, 64, 85, 56, 12, 89, 92, 26, 70, 78, 55, 19, 98, 29, 88, 1, 69, 47, 71, 4, 10, 30, 59, 11, 15, 31, 75, 33, 7, 90, 27, 62, 36, 42, 58, 13, 41, 50, 23, 20, 38, 49, 76, 73, 57, 84, 100, 54, 21, 51, 87, 9, 46, 67, 74]
    #a = [14,3,15,12,16,13,2,5,11,18,17,4,8,1,6,20,10,7,19,9]
    a_original = a[:]
    n = len(a)
    b = []
    s = 4   # número de grupos
    ### PROCEDIMIENTO
    contador = 0
    for tramo in range(1, s):   # tramo=1,2,...,s-1. El último tramo se trata de forma diferente
        a, b, contador_separa = separa(tramo,n,s,a,b)   # lleva de A a B los números correspondientes a ese tramo
        contador += contador_separa
        a, b, contador_ordena = ordena(tramo,n,s,a,b)   # ordena los números recientemente separados y llevados a B
        contador += contador_ordena
        #print("ordenado:", a, b, contador)
    # tramo final donde los números de A ya se ordenan en A, ya no se usa la función separa
    # la pila de trabajo es "A" y el objetivo es que sea creciente: ...,18,19,20.
    a, b, contador_ordena_final = ordena_final(tramo,n,s,a,b)
    contador += contador_ordena_final
    print("="*60)
    print("Al final:", a, b)
    print("contador: ", contador)

============================================================
Al final: [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, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100] []
contador:  845