/**
 *   Løsning til eksamen i AlgMet, desember 2024, oppgave 1.
 *
 *   @file     EX_H24_1.TXT
 *   @author   Frode Haug, NTNU
 */



OPPGAVE A:
==========
          
   Postfix-uttrykket:   7   3   +   3   2   +   *   5   6   *   8   5   *   +   +

                     ( skrevet Infix: ((( 7 + 3 ) * ( 3 + 2 )) + (( 5 * 6 ) + ( 8 * 5 ))) )

   har svaret: 120          

                                                                     5
                                         2               6       8   8  40
                             3       3   3   5       5   5  30  30  30  30  70
   Stakken underveis:  -  7  7  10  10  10  10  50  50  50  50  50  50  50  50  120





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

   "SJOKOMELK" 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
    Initielt:   S  J  O  K  O  M  E  L  K
                           
                e  j  k  K  o  m  s  l  o
                e  j  K
                e  J
                            l  m  O  o  s
                            l  M
                                     o  S





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

   Bottom Up Heap-konstruksjon:   
         1  2  3  4  5  6  7  8  9
         S  J  O  K  O  M  E  L  K
                  L           K  k
               o        m  e
            O     l  J
         s  o  o

   Dvs:  s  o  o  l  j  m  e  k  k
              

   Heapsort:
         1  2  3  4  5  6  7  8  9
         O  L  o  K  j  m  e  k  S
         O  l  M  k  j  K  e  O  s
         M  l  K  k  j  E  O  o  s
         L  K  k  E  j  M  o  o  s
         K  J  k  e  L  m  o  o  s
         K  j  E  K  l  m  o  o  s
         J  E  K  k  l  m  o  o  s
         E  J  k  k  l  m  o  o  s