/**
 *   Løsning til eksamen i AlgMet, august 2022, oppgave 1.
 *
 *   @file     EX_S22_1.TXT
 *   @author   Frode Haug, NTNU
 */



OPPGAVE A:
==========

    Infix-uttrykket:       ((( 5 + 7 ) * (( 4 * 3 ) * ( 8 + 2 ))) * ( 3 + 6 ))

    skrevet POSTFIX blir:   5  7  +  4  3  *  8  2  +  *  *  3  6  +  *

                                                +
                                       *     *  *  *           +
    Stakken underveis:     _  +  _  *  *  *  *  *  *  *  _  *  *  *  _

                           ('_' betyr at stakken er tom)





OPPGAVE B:
==========

    "BANANBILDE" sorteres vha. Quicksort.
    Oversikten/tabellen for hver rekursive sortering blir da:
    (NB: Partisjonselementet er skrevet med STOR bokstav,
         mens resten er skrevet med små bokstaver.)


                1  2  3  4  5  6  7  8  9 10
    Initielt:   B  A  N  A  N  B  I  L  D  E

                b  a  d  a  b  E  i  l  n  n
                a  a  B  b  d
                A  a
                         b  D
                                  i  l  N  n
                                  i  L
               




OPPGAVE C:
==========

    Bottom Up Heap-konstruksjon:   
	  1  2  3  4  5  6  7  8  9 10
          B  A  N  A  N  B  I  L  D  E
                      n              e
                   L           A  d
                n        b  i
             N     l  E              A
          N  L  n  D  e        a  B  

    Dvs:  n  l  n  d  e  b  i  a  b  a

 
    Heapsort:
	  1  2  3  4  5  6  7  8  9 10
          N  l  I  d  e  b  A  a  b  N
          L  E  i  d  B  b  a  a  N  n
          I  e  B  d  b  A  a  L  n  n
          E  D  b  A  b  a  I  l  n  n
          D  B  b  a  A  E  i  l  n  n
          B  A  b  a  D  e  i  l  n  n
          B  a  A  B  d  e  i  l  n  n
          A  a  B  b  d  e  i  l  n  n
          A  A  b  b  d  e  i  l  n  n

    Svar: A  A  B  B  D  E  I  L  N  N