El objectiu d’esta pràctica és l’implementació del TAD Pila i el seu us en la construcció d’una versió (acadèmica, no eficient) del algorisme d’ordenació per inserció.

Utilització correcta en un programa de les dos implementacions del TAD pila, de manera que, en el seu us, siga transparent el tipus d’implementació utilitzada.

L’algorisme d’ordenació per inserció és un algorisme directe, de cost mitja n² (on n és el número d’elements a ordenar) basat en la comparació d’elements entre sí.

L’idea és la següent: es tracta de mantindre un conjunt d’elements parcialment ordenat que va creixent de la següent manera:

• Donat un elemento k del conjunt a ordenar, es busca el lloc que l’hi correspon segons la relació d’orde en el conjunt parcialment ordenat.
• Es fica en el lloc escollit dins del conjunt parcialmente ordenat.
• Es repeteixen els dos pasos anteriors fins que s’acabe el conjunt a ordenar.

El algorisme eficient en espai, gasta com a estructura de dades el propi vector d’elements desordenats. Visualment l’algorisme podría funcionar de la següent manera:

En esta pràctica utilitzarem com a estructura auxiliar el TAD pila per a conseguir el mateix funcionament. L’idea és la següent:

Gastarem dos piles A i B per a obtindre en cada momento, el lloc que l’hi correspon a cada nou element dins del conjunt parcialment ordenat. La pila A no estarà en cap moment buida i va contenint el conjunt parcialment ordenat. La pila B servirà per a guardar temporalment els elements de la pila A que es desapilen de A per a deixar lloc per al nou element. Sense entrar en detalls, el algorisme consistiria en els següents punts. A partir d’un vector V d’elements desordenats:

1. Apile en A el primer element de V.
2. Pase al següent element de V mentre éste existisca.
3. Desapile de A tots els elements majors (o menors, segons si volem fer l’ordenació de major a menor o de menor a major) que el considerat i els apile en B.
4. Apile en A l’element.
5. Desapilo de B todos los elementos y los apilo nuevamente en A.
6. Vuelvo al paso 2 hasta que recorra todo el vector.

Al acabar el procés, en la pila A es troba el vector ordenat, sent el cim de la pila l’element major o menor (segons el criteri d’ordenació).

Per últim s’actualitza el vector V amb el contingut de la pila A.

En esta tercera pràctica, es deu implementar una clase en C++ que permitisca representar el TAD pila, asumint l’interficie estàndar vista en teoría:

class Pila
{
   public:
      Pila (void);                // Constructor por defecto
      bool Apilar (Valor);
      bool Desapilar (void);
      bool CimaPila (Valor &);
      bool PilaVacia (void);
   private:
      .??.
};