{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "provenance": [], "authorship_tag": "ABX9TyOqcz5bfmMSmp60W62BhUuW", "include_colab_link": true }, "kernelspec": { "name": "python3", "display_name": "Python 3" }, "language_info": { "name": "python" } }, "cells": [ { "cell_type": "markdown", "metadata": { "id": "view-in-github", "colab_type": "text" }, "source": [ "\"Open" ] }, { "cell_type": "markdown", "source": [ "# Procedimiento mejorado segundo\n", "Tomemos n=100 siendo a\n", "\n", "a = [82, 14, 53, 81, 34, 40, 25, 52, 22, 91, 93, 80, 79, 5, 8, 17, 99, 96, 16, ......] \n", "\n", "* Se basa en dividir los ```n``` números de la pila A inicial en s tramos. \n", "* Por ejemplo, para n=100 dividimos en ```s=5``` tramos.\n", "* 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. \n", " - 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```.\n", " - 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```.\n", " - Cuando ya tengamos el priemer tramo ordenado de forma creciente en B vamos a por el segundo tramo\n", " - Esto se hace con todos los tramos salvo el último\n", " - 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.\n", " - En el úlitmo tramo, en la pila A, quedaran los últimos 20 números desordenados.\n", " - 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.\n", " - Finalmente se pasan los números de B a A." ], "metadata": { "id": "cPv9Xr_y_P49" } }, { "cell_type": "code", "source": [ "# FUNCIONES\n", "from random import sample, seed\n", "seed()\n", "\n", "# la función da True si ponemos lista_ordenada([4,3,2,1], orden_inverso=True)\n", "def lista_ordenada(lis, orden_inverso=False):\n", " ordenada = False\n", " aux = lis[:]\n", " aux.sort(reverse=orden_inverso)\n", " if aux == lis:\n", " ordenada = True\n", " return ordenada\n", "\n", "def sa(a,b):\n", " if len(a) > 1: a[0],a[1] = a[1],a[0]\n", " return a,b\n", "def sb(a,b):\n", " if len(b) > 1: b[0],b[1] = b[1],b[0]\n", " return a,b\n", "def ss(a,b):\n", " sa(a,b)\n", " sb(a,b)\n", " return a,b\n", "def pa(a,b):\n", " if len(b) > 0:\n", " a.insert(0, b[0])\n", " b.pop(0)\n", " return a,b\n", "def pb(a,b):\n", " if len(a) > 0:\n", " b.insert(0, a[0])\n", " a.pop(0)\n", " return a,b\n", "def ra(a,b):\n", " if len(a) > 1: a.append(a.pop(0))\n", " return a,b\n", "def rb(a,b):\n", " if len(b) > 1: b.append(b.pop(0))\n", " return a,b\n", "def rr(a,b):\n", " ra(a,b)\n", " rb(a,b)\n", " return a,b\n", "def rra(a,b):\n", " if len(a) > 1: a.insert(0, a.pop())\n", " return a,b\n", "def rrb(a,b):\n", " if len(b) > 1: b.insert(0, b.pop())\n", " return a,b\n", "def rrr(a,b):\n", " rra(a,b)\n", " rrb(a,b)\n", " return a,b" ], "metadata": { "id": "aoo1oYYjBzcm" }, "execution_count": 43, "outputs": [] }, { "cell_type": "code", "source": [ "# PROCEDIMIENTO MEJORADO SEGUNDO\n", "# dividiendo los n=100 valores aleatorios en s=5 grupos de n/s=20 números cada uno\n", "# si no es divisible se toma un ancho=int(n/s) y se ajusta el último para que finalice en n\n", "def separa(tramo, n, s, a, b): # se llevan de la pila A a la B los números del tramo que toca\n", " contador = 0\n", " ancho = int(n/s)\n", " fin = tramo * ancho # fin del tramo\n", " inicio = (tramo-1)*ancho+1 # inicio del tramo\n", " pasados = 0 # cuenta cuantos números se han pasado de la pila A a la B\n", " while pasados < fin-inicio+1: # recorremos los elementos de la plia A hasta que pasemos todos los números de este tramo\n", " if inicio <= a[0] <= fin:\n", " pb(a,b)\n", " contador += 1\n", " pasados += 1\n", " else:\n", " ra(a,b)\n", " contador += 1\n", " return a, b, contador\n", "\n", "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.\n", " # ordena los números recientemente separados y llevados a B\n", " # el objetivo es que esos números queden en B ordenados de forma decreciente: 5,4,3,2,1\n", " contador = 0\n", " ancho = int(n/s)\n", " fin = tramo * ancho # fin del tramo\n", " inicio = (tramo-1)*ancho+1 # inicio del tramo\n", " 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\n", " # buscamos el máximo y vamos haciendo ra o rra hasta que quede el primero\n", " while max(b) != b[0]:\n", " #print(\"max(b):\", max(b))\n", " if b.index(max(b)) <= int(len(b)/2):\n", " rb(a,b)\n", " else:\n", " rrb(a,b)\n", " contador += 1\n", " if not lista_ordenada(b, orden_inverso=True):\n", " pa(a,b); contador += 1\n", " while len(a) > n-fin: # llevamos de A a B los números del tramo que toca\n", " pb(a,b); contador += 1\n", " return a, b, contador\n", "\n", "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.\n", " contador = 0\n", " ancho = int(n/s)\n", " fin = n # en el último tramo se ajusta para que el último nº sea igual a n\n", " inicio = (tramo-1)*ancho+1 # inicio del tramo\n", " 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\n", " while min(a) != a[0]:\n", " #print(\"max(b):\", max(b))\n", " if a.index(min(a)) <= int(len(a)/2):\n", " ra(a,b)\n", " else:\n", " rra(a,b)\n", " contador += 1\n", " if not lista_ordenada(a):\n", " pb(a,b); contador += 1\n", " while len(b) > 0: # llevamos de B a A todos los números que hay en B\n", " pa(a,b); contador += 1\n", " return a, b, contador\n", "\n", "if __name__ == \"__main__\":\n", " # Generación de la pila A\n", " n = 100 # número de elementos de la pila\n", " #a = sample(range(1, n+1), n)\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]\n", " #a = [14,3,15,12,16,13,2,5,11,18,17,4,8,1,6,20,10,7,19,9]\n", " a_original = a[:]\n", " n = len(a)\n", " b = []\n", " s = 4 # número de grupos\n", " ### PROCEDIMIENTO\n", " contador = 0\n", " for tramo in range(1, s): # tramo=1,2,...,s-1. El último tramo se trata de forma diferente\n", " a, b, contador_separa = separa(tramo,n,s,a,b) # lleva de A a B los números correspondientes a ese tramo\n", " contador += contador_separa\n", " a, b, contador_ordena = ordena(tramo,n,s,a,b) # ordena los números recientemente separados y llevados a B\n", " contador += contador_ordena\n", " #print(\"ordenado:\", a, b, contador)\n", " # tramo final donde los números de A ya se ordenan en A, ya no se usa la función separa\n", " # la pila de trabajo es \"A\" y el objetivo es que sea creciente: ...,18,19,20.\n", " a, b, contador_ordena_final = ordena_final(tramo,n,s,a,b)\n", " contador += contador_ordena_final\n", " print(\"=\"*60)\n", " print(\"Al final:\", a, b)\n", " print(\"contador: \", contador)" ], "metadata": { "id": "UmUYfJz4Dlun", "outputId": "2898f579-cf25-4843-def9-68961c331797", "colab": { "base_uri": "https://localhost:8080/" } }, "execution_count": 48, "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "============================================================\n", "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] []\n", "contador: 845\n" ] } ] } ] }