Ir al contenido principal

TAD de las pilas - Ordenación de pilas por inserción

Utilizando el tipo abstracto de datos de las pilas, definir la función

   ordenaInserPila :: Ord a => Pila a -> Pila a

tal que ordenaInserPila p es la pila obtenida ordenando por inserción los los elementos de la pila p. Por ejemplo,

   λ> ordenaInserPila (apila 4 (apila 1 (apila 3 vacia)))
   1 | 3 | 4

Comprobar con QuickCheck que la pila (ordenaInserPila p) está ordenada.

Soluciones

Se usarán las funciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila)
import Transformaciones_pilas_listas (listaApila, pilaAlista)
import OrdenadaPila (ordenadaPila)
import Test.QuickCheck

-- 1ª solución
-- ===========

ordenaInserPila1 :: Ord a => Pila a -> Pila a
ordenaInserPila1 p
  | esVacia p = p
  | otherwise = insertaPila cp (ordenaInserPila1 dp)
  where cp = cima p
        dp = desapila p

insertaPila :: Ord a => a -> Pila a -> Pila a
insertaPila x p
  | esVacia p = apila x p
  | x < cp    = apila x p
  | otherwise = apila cp (insertaPila x dp)
  where cp = cima p
        dp = desapila p

-- 2ª solución
-- ===========

ordenaInserPila2 :: Ord a => Pila a -> Pila a
ordenaInserPila2  =
  listaApila . reverse . ordenaInserLista . pilaAlista

ordenaInserLista :: Ord a => [a] -> [a]
ordenaInserLista []      = []
ordenaInserLista (x: xs) = insertaLista x (ordenaInserLista xs)

insertaLista :: Ord a => a -> [a] -> [a]
insertaLista x [] = [x]
insertaLista x (y:ys) | x < y = x : y : ys
                      | otherwise = y : insertaLista x ys

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_ordenaInserPila :: Pila Int -> Bool
prop_ordenaInserPila p =
  ordenaInserPila1 p == ordenaInserPila2 p

-- La comprobación es
--    λ> quickCheck prop_ordenaInserPila
--    +++ OK, passed 100 tests.

-- Comprobación de la propiedad
-- ============================

-- La propiedad es
prop_ordenadaOrdenaInserPila :: Pila Int -> Bool
prop_ordenadaOrdenaInserPila p =
  ordenadaPila (ordenaInserPila1 p)

-- La comprobación es
--    λ> quickCheck prop_ordenadaOrdenaInserPila
--    +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given

from src.ordenadaPila import ordenadaPila
from src.TAD.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria,
                          vacia)
from src.transformaciones_pilas_listas import listaApila, pilaAlista

A = TypeVar('A', int, float, str)

# 1ª solución
# ===========

def insertaPila(x: A, p: Pila[A]) -> Pila[A]:
    if esVacia(p):
        return apila(x, p)
    cp = cima(p)
    if x < cp:
        return apila(x, p)
    dp = desapila(p)
    return apila(cp, insertaPila(x, dp))

def ordenaInserPila1(p: Pila[A]) -> Pila[A]:
    if esVacia(p):
        return p
    cp = cima(p)
    dp = desapila(p)
    return insertaPila(cp, ordenaInserPila1(dp))

# 2ª solución
# ===========

def insertaLista(x: A, ys: list[A]) -> list[A]:
    if not ys:
        return [x]
    if x < ys[0]:
        return [x] + ys
    return [ys[0]] + insertaLista(x, ys[1:])

def ordenaInserLista(xs: list[A]) -> list[A]:
    if not xs:
        return []
    return insertaLista(xs[0], ordenaInserLista(xs[1:]))

def ordenaInserPila2(p: Pila[A]) -> Pila[A]:
    return listaApila(list(reversed(ordenaInserLista(pilaAlista(p)))))

# 3ª solución
# ===========

def ordenaInserPila3Aux(p: Pila[A]) -> Pila[A]:
    if p.esVacia():
        return p
    cp = p.cima()
    p.desapila()
    return insertaPila(cp, ordenaInserPila3Aux(p))

def ordenaInserPila3(p: Pila[A]) -> Pila[A]:
    q = deepcopy(p)
    return ordenaInserPila3Aux(q)

# Comprobación de equivalencia de las definiciones
# ================================================

# La propiedad es
@given(p=pilaAleatoria())
def test_ordenaInserPila(p: Pila[int]) -> None:
    r = ordenaInserPila1(p)
    assert ordenaInserPila2(p) == r
    assert ordenaInserPila3(p) == r

# La comprobación es
#    src> poetry run pytest -q ordenaInserPila.py
#    1 passed in 0.31s

# Comprobación de la propiedad
# ============================

# La propiedad es
@given(p=pilaAleatoria())
def test_ordenadaOrdenaInserPila(p: Pila[int]) -> None:
    ordenadaPila(ordenaInserPila1(p))

# La comprobación es
#    src> poetry run pytest -q ordenaInserPila.py
#    2 passed in 0.47s