Gäller för: HT23

Algoritmrapport 1

I den första algoritmrapporten ska ni kommentera koden för de två sorteringsalgoritmer som ni inte använde i er temauppgift. Om ni t.ex. hade shell-sort i temauppgiften, skriver ni om merge-sort och quick-sort. För varje sorteringsalgoritm ska ni också steg-för-steg, beskriva hur algoritmen sorterar av en lista med heltal.

Ladda ner koden ni ska kommentera nedan

Inlämning

Algoritmrapporten lämnas in via Lisam. Se Inlämningar

Ni kommer få en av bedömningarna komplettering, 1 poäng, 2 poäng eller 3 poäng på algoritmrapporten.

Om man får 1 eller 2 poäng vid första inlämningen får man lämna in en komplettering om man vill försöka få högre bedömning. Ta kontakt med den lärare som rättat er rapport så att hen kan låsa upp er inlämning i Lisam (genom att markera den för komplettering).
Om man får komplettering vid första inlämningen är det den första godkända bedömningen som gäller. Dvs. om ni vill ha 2 eller 3 poäng, se till att det ni skickar in som komplettering uppfyller kraven för detta.

Rapporten

Algoritmrapporten lämnas i som pargrupp. Följande information ska finnas med i början av rapporten:

Era namn, er pargrupp, kurskod och datum
Namnet på uppgiften (t.ex. Algoritmrapport 1)
Vilken nivå som ni satsar på (1, 2 eller 3 poäng).

Komplettering ges på inlämningen om något av ovanstående saknas.

Algoritmrapporten ska innehålla ett avsnitt med rubrik för varje sorteringsalgoritm. Varje avsnitt om en sorteringsalgoritm ska i sin tur innehålla följande två delar med rubrik:

Kommenterad kod
Steg för steg

Beskrivning av innehållet under dessa rubriker finner ni nedan.

1. Kommenterad kod

Klistra in er kommenterade kod här. Se till att ni använder ett typsnitt med fast teckenbredd (t.ex. Consolas, Courier New, Menlo eller Monaco). Tips: Ni kan kopiera koden med syntaxfärger från Visual Studio Code genom att trycka Ctrl+Shift+P (Linux/Windows) eller Cmd+Shift+P (Mac) och skriva “Copy”, välj sedan kommandot Copy With Syntax Highlighting (byt till ett ljust färgtema i VSCode om texten syns dåligt).

Ni ska både skriva docstrings för funktionerna (enligt PEP257), samt block-kommentarer (rader som börjar med #) på de ställen som markerats i koden som ni laddade ner (högst upp på denna sida). Observera att block-kommentarer skrivs innan den kod de kommenteras medan funktionskommentaren skrivs efter funktionshuvudet.

De existerande block-kommentarerna i koden beskriver vad ni ska kommentera.Lämna kvar dessa i er kod (som i exemplet nedan). Block-kommentarerna ni skriver ska

vara formulerade som kommentarer, inte som “svar på frågor”
förklara koden som block-kommentaren hör ihop med för programmerare som läser koden, inte bara vara en innantilläsning av koden

Ett exempel på en innantillläsning (som ni alltså inte ska skriva) av kodraden for i in range(len(a_list)-1, 0, -1): är “för varje i mellan längden på a_list minus ett och ett”.

Nedan är ett exempel för Bubbel Sort.

def bubble_sort(a_list):
    """Sortera listan a_list i stigande ordning med Bubble Sort."""
    # Kommentera for-loopen. Vad är syftet med loopen (vad har hänt när
    # loopen är klar)? Vad händer varje varv?
    #
    # Sortera listan genom att iterera över minskande delar av listan. Vi
    # börjar med hela listan och krymper den aktuella delen från höger.
    #
    # Efter varje iteration är värdet på den sista platsen i del-listan,
    # dvs a_list[i] på sin slutgiltiga plats.
    for i in range(len(a_list)-1, 0, -1):
        # Kommentera for-loopen. Vad är syftet med loopen (vad har hänt när
        # loopen är klar)? Vad händer varje varv?
        #
        # Flytta det högsta värdet i a_list mellan index 0 och i till
        # a_list[i]. Varje iteration går vi ett steg åt höger i
        # listan och ser till att a_list[i] och a_list[i+1] står i stigande
        # ordning.
        for j in range(i):
            # Kommentera villkorssatsen. Vad dess syfte?
            #
            # Se till att värdena a_list[j] och a_list[j+1] står i stigande
            # ordning (byt plats på värdena om de inte är det).
            if a_list[j] > a_list[j+1]:
                temp = a_list[j]
                a_list[j] = a_list[j+1]
                a_list[j+1] = temp

När ni skriver kommentarerna, lämna funktionskommentarerna (docstrings för funktionern) till sist. Ni kommer behöva hoppa mellan de olika nivåerna av algoritmen, men det är förmodligen lättast om ni börjar skriva kommentarerna på den lägsta (innersta) nivån först och arbeta er utåt.

Era kommentarer kommer innehålla viss redundans (kommententarer på högre nivå kommer ibland beskriva t.ex. vad en loop på lägre nivå gör). Detta behövs inte alltid när man kommenterar kod “på riktigt”, men finns med här av pedagogiska skäl.

2. Steg-för-steg

Ett exempel på de steg som en specifik lista går igenom när man sorterar den med hjälp av algoritmen. Här är det viktiga att beskriva

vilka förflyttningar och jämförelser som görs av algoritmen,
vilken ordning detta sker, samt
vilken/vilka delar av listan som bearbetas för tillfället

Nedan är ett exempel med Selection Sort (OBS! Koden i exemplet ovan var för Bubble Sort):

Listan [54,26,93,17,77,23,88] ska sorteras genom att tillämpa Selection Sort.
Det största talet i listan mellan index 0 och 6, dvs 93 (index 2) byter plats med värdet på index 6 (värdet 88) → [54,26,88,17,77,23,93]
Det största talet i listan mellan index 0 och 5, dvs 88 (index 2), byter plats värdet på index index 5 (värdet 23) → [54,26,23,17,77,88,93]
Det största talet i listan mellan index 0 och 4, dvs 77 (index 4), byter plats med värdet med index 4 (värdet 77) → [54,26,23,17,77,88,93] (ingen förändring)
Det största talet i listan mellan index 0 och 3, dvs 54 (index 0), byter plats med värdet som har index 3, (värdet 17) → [17,26,23,54,77,88,93].
Det största talet i listan mellan index 0 och 2, dvs 26 (index 1), byter plats med värdet som har index 2 (värdet 23) → [17,23,26,54,77,88,93].
Det största talet i listan mellan index 0 och 1, dvs 23 (index 1) byter plats med värdet som har index 1, (värdet 23) → [17,23,26,54,77,88,93] (ingen förändring)
Algoritmen har kommit till det sista värdet och listan är sorterad.

Ni kan summera flera saker som händer i ett steg, så länge stegbeskrivningen är tydlig. T.ex. “indexvariabeln x minskar tills y händer och får då värdet z”. Om innehållet i listan ändras bör den förändrade listan skrivas ut.

Använd listorna nedan för era två Steg-för-steg-avsnitt (samma lista i båda Steg-för-steg).

A.1: [6, 10, 13, 24, 94, 27, 50]
A.2: [57, 27, 87, 41, 84, 25, 53]
A.3: [43, 77, 13, 88, 22, 11, 17]
B.1: [31, 20, 8, 74, 49, 56, 63]
B.2: [2, 2, 40, 30, 53, 26, 43]
B.3: [80, 54, 69, 63, 64, 60, 69]
C.1: [18, 58, 8, 62, 56, 17, 79]
C.2: [5, 60, 49, 20, 4, 73, 37]
C.3: [10, 42, 94, 99, 96, 42, 63]
D.1: [55, 85, 71, 27, 16, 65, 79]
D.2: [43, 17, 36, 22, 53, 15, 42]
D.3: [93, 17, 76, 20, 4, 27, 93]
E.1: [29, 16, 45, 23, 12, 85, 74]
E.2: [71, 35, 28, 100, 34, 25, 65]
E.3: [100, 46, 3, 15, 18, 38, 5]
F.1: [59, 89, 56, 7, 88, 21, 85]
F.2: [16, 17, 71, 96, 26, 51, 19]
F.3: [40, 35, 59, 10, 9, 19, 98]
G.1: [93, 2, 63, 57, 15, 87, 17]
G.2: [96, 35, 68, 65, 81, 63, 64]
G.3: [49, 46, 57, 87, 27, 19, 26]
H.1: [14, 33, 58, 67, 97, 45, 52]
H.2: [63, 29, 53, 47, 60, 95, 3]
H.3: [13, 49, 99, 76, 59, 50, 94]
I.1: [57, 16, 45, 94, 32, 30, 47]
I.2: [94, 46, 39, 18, 60, 36, 93]
I.3: [5, 33, 74, 83, 74, 24, 96]
J.1: [65, 27, 4, 79, 47, 35, 59]
J.2: [64, 16, 86, 97, 83, 64, 33]
J.3: [13, 24, 49, 13, 42, 83, 35]

Poäng

1 poäng: Majoriteten av kodkommentarerna är godkända. Steg-för-steg-beskrivningen följer algoritmen, men kan ha något enstaka detaljfel.
2 poäng: Majoriteten av kodkommentarerna är godkända. Steg-för-steg-beskrivningen följer algoritmen och har inga fel.
3 poäng: Alla kodkommentarer är godkända. Steg-för-steg-beskrivningen följer algoritmen och har inga fel.