{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "provenance": [], "authorship_tag": "ABX9TyMDqmBneRctAxeH6IqwMHZe", "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 TERCERO\n", "* Existe una pila PRINCIPAL y una pila AUXILIAR\n", "* Si hacemos el procedimiento PRIMERO:\n", " - La pila PRINCIPAL siempre es la pila A\n", " - La pila AUXILIAR siempre es la pila B\n", "* Si hacemos el procedimiento SEGUNDO:\n", " - establecemos ```s``` que es el número de tramos\n", " * por ejemplo, si n = 100 y s=5 tenemos 5 tramos de 20 números cada uno\n", " * el primer tramo se pasa de A a B y se ordena en B de forma decreciente\n", "* Si hacemos el procedimiento TERCERO:\n", " - definimos s tramos y luego \n", " - sobre cada uno de ellos definimos t subtramos\n", " * por ejemplo:\n", " * n = 100\n", " * s = 5\n", " * t = 4\n", " * así, terminaremos manejando subtramos de 5 elementos (100/5/4)\n", " \n" ], "metadata": { "id": "O6IgPZrOuiMR" } }, { "cell_type": "code", "source": [ "# FUNCIONES\n", "from random import sample, seed\n", "seed()\n", "\n", "def lista_ordenada(lis, orden_inverso=False): # la función da True si ponemos lista_ordenada([4,3,2,1], orden_inverso=True)\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\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", " while max(b) != b[0]: # buscamos el máximo y vamos haciendo ra o rra hasta que quede el primero\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", " 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" ], "metadata": { "id": "epQAIlYhumzC" }, "execution_count": null, "outputs": [] } ] }