View All Pages

Övning 4: Sortering och heap:ar

Mål:

  • Kunna tillämpa algoritmer för sortering, samt räkna på tidskomplexiteten för ett givet problem
  • Kunna demonstrera hur en heap fungerar

Tabell över ungefärliga tvåpotenser:

-----------------------------------------------------------------------
1 2 3  4  5  6   7   8   9   10   11   12   13    14    15    16     17
-----------------------------------------------------------------------
2 4 8 16 32 64 128 250 500 1000 2000 4000 8000 16000 32000 64000 130000 ...
-----------------------------------------------------------------------

  1. LÖNAR SEJ SORTERING (Tildatenta 4 april 1997)

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

    För varje nummer måste hela listan 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 listan? (vi väljer heapsort istället för quicksort)

    lösning

  2. HOPPFULL SORTERING

    Höjdhoppsfederationens databas över världens alla höjdhoppstävlingsresultat består av objekt med bland annat fälten datum, plats, höjd (cm), hoppare och rivit/klarat. På skivminnet ligger objekten 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.

    lösning

  3. TJUGONDAG KNUT KASTAS JULEN UT (Tildtenta 16 januari 2001)

    För att kontrollera sanningen i detta talesätt har man i en fil samlat tre miljoner datum för svenska julgranars utkastning. Man vill veta mediandatum, alltså det datum då hälften av granarna slängts ut, ut, ut och hälften ännu står gröna och granna i stugan.

    Rangordna följande sex föreslagna metoder efter deras effektivitet. Binärsökning, hashning, insättningssortering, distributionsräkning, djupet-först-sökning, trappsortering (heap sort).

    lösning

  4. 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 heapsort? Hur många med den bästa metoden?

    lösning

  5. Cykel-tentan 2014-10-24, uppgift 3 (betyg E)

    Nu när det blir mörkare om kvällarna känns det extra viktigt att ha lysen till cykeln. Du har lagt in lamporna med priset som prioritet i en min-heap. På vektorform ser heapen ut så här: 
    10 40 30 42 41 48 50 49
    Rita upp heapen på trädform och visa sen hur det ser ut när man plockar ut två element (du vill ju inte köpa de allra billigaste). Visa minst fem steg. Skriv slutligen upp heapen på vektorform igen.