Hemtal 4

A) Sortering

Läs om sortering i kursboken.

1. Räkna ut hur många jämförelser som görs i bubbelsortering av n element (i värsta fallet).

2. 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!

3. Vad är den rekursiva tanken och basfallet i Mergesort?

4. Vad är ett pivot-värde i Quicksort? Förklara och visa ett exempel.

5. Gör en tabell över de sex sorteringsalgoritmer som tas upp i kapitlet ovan, med algoritmernas namn och komplexitet.

B) Prioritetsköer och bästaförstsökning

Läs om prioritetsköer och Dijkstras algoritm i kursboken.

1. Vad är heapvillkoret?

2. Visa med fem bilder hur det ser ut när man i tur och ordning puttar in talen 15 8 12 3 20 i en min-heap.

3. Visa sen vad som händer när man plockar ut ett element ur heapen ovan.

4. Vad är komplexiteten för Heapsort?

5. I labb 4 används breddenföstsökning för att hitta kortaste vägen från fan till gud. Skulle det gå lika bra att använda bästaförstsökning med en prioritetskö? Motivera ditt svar!

---

Hemtalet tas med till övning 4 (20 september) 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.