GRUDAT, ÖVNING 8

Sortering

1 LÖNAR SEJ SORTERING

En miljon dumbolotter säljs var månad. För varje lott sparas
lottnumret och köparen i en post. En array med en miljon poster finns
alltså i datorn vid dragningen, då tusen vinstnummer slumpas fram, ett
efter ett.

För varje nummer måste hela arrayen letas igenom, eftersom
den är osorterad. Hur många jämförelser får man räkna med totalt?
Lönar det sej att först sortera arrayen, en gång för alla?

2 BILLIG STANDARD SELECTION

Tilda och Totte skrev var sin sorteringsprocedur. Tilda valde en
utsökt merge sort medan Totte tog en standard selection sort.  När dom
provkörde med tusen poster gick ändå Tottes program lika fort,
eftersom han har superdator. Men med tiotusen poster vann Tilda. Med
hur mycket?

3 OSVENSK SORTERING

I laboration 4 använder man   if nyord<p.word:   när man
sorterar in ord i sökträdet. Denna funktion är avpassad för engelska
alfabetet, så när man skriver ut orden i sökträdet i inordning så
kommer bokstäverna å, ä och ö att sorteras som ä, å, ö (men dom ligger
i alla fall efter z).

Anta att du har en array med ord sorterade på detta sätt och
vill sortera om den i svensk bokstavsordning. Vilken sorteringsmetod
är bäst?  Motivera utförligt!

4 HOPPFULL SORTERING

Höjdhoppsfederationens databas över världens alla
höjdhoppstävlingsresultat består av poster med bland annat fälten
datum, plats, höjd (cm), hoppare och rivit/klarat. På skivminnet
ligger posterna i datumordning, men man vill sortera om dom i
resultatordning, nämligen klarade hopp före rivna och höga hopp före
låga.

Vilken sorteringsmetod är bäst? Motivera utförligt.

5 TJUGONDAG KNUT KASTAS JULEN UT

Tildatentan 010116 uppgift 1 frågar efter mediandatum för
svenska julgranaras utkastande.

6 FRUKTSORTERING

Tildatentan 000318, uppgift 1, gör bottenupp-mergesort med
abstrakt frukt i en abstrakt kö.

7 SKATTEREGISTRET

Riksskatteverkets databas med nio miljoner svenskar 
finns sorterad på efternamn. Man vill sortera om
den på personnummer. Hur många jämförelser krävs
med quicksort? Hur många med den bästa metoden?

8 KROGKÖN

Klubben Hip Bar är det häftigaste innestället i stan, och detta
medför naturligtvis att det bildas köer utanför. Eftersom ägaren
vill att Hip Bars status skall förbli hög, ger han dörrvakterna
order om att släppa in mycket kändisar. Han poängterar dock att
han i första hand är mån om klubbens trogna medlemmar, och att
dessa skall givas företräde.

Din uppgift går ut på att skriva en algoritm, med tillhörande
lämpliga datastrukturer, som vakterna kan använda för att
tillgodose ägarens önskemål. Du kan betrakta varje köande gäst
som objekt med instansvariablerna "medlemsår" och
"kändisfaktor". Observera att kändisar naturligtvis också kan
vara medlemmar.