Esercizio 6ordinare una pila con pile ausiliarie

Esame

In questa pagina 4

Testo (tema d'esame del 13 settembre 2018, Fondamenti di Informatica, Ingegneria dell'Informazione UniPD; adattato da un tema d'esame in Java: lì la pila era java.util.Stack, qui è una lista Python usata con append e pop).

Si vuole costruire una classe OS ("ordina stack") il cui costruttore riceve una pila di oggetti confrontabili e il cui metodo ordina() la riordina in modo che l'elemento più piccolo si trovi in testa (in cima) alla pila.

Scrivere OS. È consentito copiare la pila in un array, ordinare l'array e ricopiarlo, ma la soluzione ottima usa una o più pile ausiliarie e non array. In un commento all'inizio di ordina() indicare quale algoritmo noto si è scelto (inserzione, selezione, mergesort, bubblesort...).
Scrivere un programma che legge dallo standard input un testo, una stringa per riga, lo inserisce in una pila, la ordina con OS e svuota la pila stampando le righe: devono comparire in ordine alfabetico crescente.

Teoria: Pila e coda, Algoritmi di ordinamento, Complessità computazionale.

Idea

Con una pila si può leggere solo la cima, quindi non si può indicizzare. Si usa una seconda pila aux che si mantiene sempre ordinata con l'elemento più grande in cima (quindi crescente dal fondo alla cima). È l'ordinamento per inserzione: si prende un elemento x dalla pila originale e lo si inserisce al posto giusto in aux; per farlo si spostano temporaneamente su p gli elementi di aux più grandi di x, poi si mette x e questi elementi verranno riesaminati dal ciclo esterno.

Alla fine aux contiene tutto in ordine con il massimo in cima; travasandola in p elemento per elemento il massimo arriva per primo, e quindi finisce in fondo, mentre il minimo arriva per ultimo e resta in cima: è l'ordine richiesto.

p = [c, a, b]  (cima = b)         aux = []
estrai b                           aux = [b]
estrai a: b > a, b torna su p      p = [c, b]      aux = [a]
estrai b                           aux = [a, b]
estrai c                           aux = [a, b, c]
travaso: c, poi b, poi a su p      p = [c, b, a]   (cima = a, il minimo)

Codice

python

import io

class OS:
    """Ordina una pila (lista usata con append/pop) in modo che la cima sia il minimo."""

    def __init__(self, pila):
        self._p = pila
        self.mosse = 0                       # solo per contare il lavoro svolto

    def ordina(self):
        # Algoritmo scelto: ordinamento per INSERZIONE con una pila ausiliaria.
        p, aux = self._p, []
        while p:
            x = p.pop()
            while aux and aux[-1] > x:       # gli elementi di aux più grandi di x
                p.append(aux.pop())          # tornano temporaneamente su p
                self.mosse += 1
            aux.append(x)                    # aux resta ordinata (massimo in cima)
        while aux:                           # travaso: il massimo va in fondo, il minimo in cima
            p.append(aux.pop())
            self.mosse += 1


def main(f):
    pila = [riga.rstrip("\n") for riga in f]
    OS(pila).ordina()
    while pila:
        print(pila.pop())


if __name__ == "__main__":
    # con la tastiera o un file:  python main.py < dati.txt
    # qui, per provare, un file simulato
    main(io.StringIO("pera\nmela\nuva\nbanana\narancia\n"))

Stampa: arancia, banana, mela, pera, uva.

La pila originale è una list con la cima in fondo: pop() toglie l'ultimo elemento inserito. Per questo pila = [riga ...] mette l'ultima riga in cima, e dopo ordina() la cima è la riga alfabeticamente minore; pop() ripetuto le restituisce in ordine crescente.

Verifica e costo

python

import random

for _ in range(500):
    v = [random.randint(-20, 20) for _ in range(random.randint(0, 30))]
    p = v[:]
    OS(p).ordina()
    uscita = []
    while p:
        uscita.append(p.pop())
    assert uscita == sorted(v)
print("500 prove ok")

for n in (100, 200, 400):
    caso_peggiore = OS(list(range(1, n + 1)))      # cima = massimo
    caso_peggiore.ordina()
    caso_migliore = OS(list(range(n, 0, -1)))      # cima = minimo
    caso_migliore.ordina()
    print(n, caso_peggiore.mosse, caso_migliore.mosse)    # 100 5050 100 / 200 20100 200 / 400 80200 400

Caso peggiore (la cima è il massimo e la pila è già "al contrario"): $1 + 2 + \dots + n = n(n+1)/2$ spostamenti, $\Theta(n^2)$ (5050, 20 100, 80 200: raddoppiando $n$ il lavoro quadruplica).
Caso migliore (cima = minimo e già ordinata): $n$ spostamenti, solo il travaso finale, $\Theta(n)$ .
Spazio: una pila ausiliaria, $O(n)$ .

La versione "con array" è più breve ma usa $\Theta(n)$ memoria in più e non rispetta il vincolo di usare solo operazioni di pila:

python

def ordina_con_array(pila):
    v = []
    while pila:
        v.append(pila.pop())
    v.sort(reverse=True)               # il minimo deve finire per ultimo, cioè in cima
    for x in v:
        pila.append(x)

Errori comuni

Ordinare in senso contrario: ricordare che la cima deve essere il minimo, quindi l'ultimo inserito.
Dimenticare di rimettere su p gli elementi tolti da aux per fare posto, perdendoli.
Indicizzare la pila (pila[i]): con la pila come ADT si usano solo push, pop e top.
Scrivere nel commento "mergesort" o "quicksort": con una sola pila ausiliaria l'algoritmo è inserzione (o selezione).

Versione ripasso

Tema d'esame del 13 settembre 2018 (UniPD, in Java con java.util.Stack; adattato a Python: lista con append/pop). Teoria: Pila e coda, Algoritmi di ordinamento.

Obiettivo: dopo ordina() la cima è l'elemento minimo (leggendo con pop() si ottiene l'ordine crescente); soluzione ottima con pile ausiliarie, non array.

Algoritmo: inserzione con una pila ausiliaria aux (sempre ordinata, massimo in cima):

x = p.pop();
finché aux[-1] > x: p.append(aux.pop()) (tornano su p, saranno rivisti);
aux.append(x);
alla fine si travasa aux su p: il massimo arriva per primo (in fondo), il minimo per ultimo (in cima).

Costo: caso peggiore (cima = massimo) $n(n+1)/2$ spostamenti, $\Theta(n^2)$ ; caso migliore $n$ ; spazio $O(n)$ . main: legge le righe in una pila, OS(pila).ordina(), poi pop() fino a svuotarla.

Errori comuni: cima = massimo invece del minimo; elementi tolti da aux non rimessi su p; indicizzare la pila; dichiarare mergesort/quicksort.

Esercizio 6ordinare una pila con pile ausiliarie

Idea

Codice

Verifica e costo

Errori comuni

Teoria collegata