Nada

DATALOGIÖVNING 10 - SORTERING

KÖNSSORTERING

Jämställdhetsombudsmannen beställde ett utdrag ur SPAR, personregistret över alla svenskar. För att få damerna först begärde hon sortering på nionde siffran i personnumret. Resultatet blev en vektor med nio miljoner poster, först alla kvinnor med niondesiffran noll, sedan alla män med niondesiffran ett, sedan alla kvinnor med niondesiffran två etc. Förklara för JÄMO hur hon ska göra för att sortera om vektorn så att damerna verkligen kommer först. Det måste gå fort och får inte kräva just något extra minnesutrymme! Ungefär hur många poster kommer att flyttas?

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?

SNABBSORTERING

Tilda och Totte skrev var sin sorteringsprocedur. Tilda valde en utsökt quicksort 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?

OSVENSK SORTERING

I labbarna använder man metoden compareTo 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 vektor med ord sorterade på detta sätt och vill sortera om den i svensk bokstavsordning. Vilken sorteringsmetod är bäst? Motivera utförligt!

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.