Hemtal 4
A) Hashning
Läs om
hashning (Hashing) i kursboken.
- Är hashning snabbare än binärsökning?
- Vad ska man tänka på när man skapar en hashfunktion?
- Kan man använda slumptal i en hashfunktion?
- Vad är en krock (collision)?
- Vad är skillnaden mellan krockhanteringsmetoderna linjär probning
och krocklistor? Rita och berätta!
B) Sortering
Läs om
sortering i kursboken.
- Gör en tabell över de sex sorteringsalgoritmer som tas upp i kapitlet ovan, med
algoritmernas namn och komplexitet.
- Jämför bokens implementationer av Selection Sort och
Insertion Sort. Vilken av funktionerna skulle du välja
om du ganska ofta fick data som redan var sorterade?
Förklara varför!
- Räkna ut hur många jämförelser som görs i urvalssortering (Selection Sort)
av 4 element.
- Visa hur Mergesort gör vid sortering av följande tal: 23 28 7 14 2
- Vad är ett pivot-värde i Quicksort? Förklara och visa ett exempel.
Hemtalet tas med till övningen och rättas där!
Den som gjort uppgiften ska skriva sitt namn
och personnummer överst till höger på alla blad.
Den som rättar ska skriva sitt namn och personnummer
längst ner till vänster på första bladet.
