Svarene kan være korte. Svarene under er mer detaljert enn vi kan
forlange av kandidatene for å få 100%.

OPPGAVE 6.

Ja, det er mulig siden quicksortalgoritmen baserer seg på at man kan
løpe begge veier i listen (mot venster og mot høyre) og at man må kunne
bytte to elementer.

Følgende forandringer må gjøres:

Metoden som velger pivotelement må skrives om slik at den ikke bruker
indekser. Den returnerer (og kan evt. tau ut) pivotobjektet.

Istedet for indekser lar man en lm-peker (i) starte fra elemtentet lengst
til venstre og en annen (j) starter med objektet lengst til høyre.

Paramtrene fra og til er av type Listemedlem.

Finn og ta ut pivotelementet.


hvis fra.neste == til bytt de to elementene om "fra > til"
hvis fra == til gjør ingenting
    
     sett inn pivotelementet på rett plass og returner
     

Ellers

    Listemedlem i = fra;
    Listemedlem j = til;
    Listemedlem midl;
    while (true) {
      while ( i.sorteringsatributt < pivot.sorteringsatributt) {i = i.hentneste()}
      while ( j.sorteringsatributt > pivot.sorteringsatributt) {j = j.hentforrige()}

      if (i "til venstre for" j) {
	 bytt2listeMedlemmer(i,j);

        // obs i og j har byttet plass, mens algoritmen baserer seg på at i og j
        // peker ut "en plass" i listen, så nå må i og j bytte pekere

        midl = i;
	i = j;
	j = midl;

      } else {
	break;
      }
    }
    
    settInnTilVenstre(i, pivotelementet);
    quicksort(a, fra, pivotelement.hentforrige());
    quicksort(a, pivotelement, til);
  

OPPGAVE 7

Nei, det er lite hensiktsmessig fordi å bytte plass for to
listeelementer innebærer mange operasjoner.

Hvis apotekvarene ikke går inn og ut av lister hele tiden, er det mer
hensiktsmessig å lage en metode som setter et objekt inn på rett plass,
slik at varelisten er sortert til enhver tid.

Må man sortere, kan man spenne ut listen over en Listemedlem array og
bruke quicksort på indeksene i denne. Så omorganiserer man varelisten i
henhold til denne etter at sorteringen er gjort.


OPPGAVE 8

QUICKSORTALGORITME
o       -        -

EIICKOOGMALQSRUTRT
-    -    o 

EIICKAGLMOOQSRUTRT
o  -  -


Husk at kallrekkefølgen er slik at algoritmen partisjonerer venstre
delarray først og ikke slik vi tenker når vi skriver hvor vi først tar
venstre og så høyre delarray.