Kmom05: Sorteringsalgoritmer och datastrukturer

By . Latest revision .

Vi ska titta på hur några av de vanligaste sorteringsalgoritmerna ser ut och fungerar. Samtidigt ska vi lära oss hur man skriver rekursiva funktioner.

Bild på algoritmen Merge-sort.

Bild på algoritmen Merge-sort.

(Detta är instruktionen för kursmomentet och omfattar det som skall göras inom ramen för kursmomentet. Momentet omfattar cirka 20 studietimmar inklusive läsning, arbete med övningar och uppgifter, felsökning, problemlösning, redovisning och eftertanke. Läs igenom hela kursmomentet innan du börjar jobba. Om möjligt – planera och prioritera var du vill lägga tiden.)

#Läsanvisningar

  1. Sorting algorithms and big-O. Visar inte kod men men visualiserar och förklarar bra hur sorterings algoritmerna fungerar.

#Kurslitteratur

Läs följande:

#Artiklar

Läs följande:

  1. visualgo. Interaktiv sida som visualiserar hur tal sorteras och även pseudo kod för olika algoritmer.

  2. Python thinking recursively. Intressant artikel som pratar om hur rekursion fungerar i Python.

#Video

Titta på följande:

  1. Videoserien Lär dig objektorienterad Python är tätt kopplat till kursmaterialet. Kika på de videor som börjar med 5.

  2. CS50 Algorithms kolla från tidstämpel fram till 55 min.

  3. What on Earth is Recursion? förklarar rekursion.

  4. Getting sorted visualiserar olika sorteringsalgoritmer och går igenom komplexitet.

  5. Quick Sort visualiserar quick sort.

#Lästips

Om du känner att du har tid och lust.

  1. Sorting algoritms - geeksforgeeks

#Övningar & Uppgifter

(ca: 8-10 studietimmar)

#Övningar

Genomför följande övning för att träna dig.

  1. Läs igenom artikeln “Rekursion”.

  2. Läs igenom artikeln “Klassiska sorteringsalgoritmer”.

#Uppgifter

Dessa uppgifter skall utföras och redovisas.

  1. Gör uppgiften “Python med rekursiva funktioner” (lab 3)

  2. Gör uppgiften “Terminalprogram med sortering av lista”. Spara din kod i mappen sort.

  3. Fyll på redovisning.html med kursmomentets redovisningstext.

# Ställ dig i kurskatalogen
dbwebb publish flask

#Extra

  1. Det finns ingen extrauppgift.

#Resultat & Redovisning

(ca: 1-2 studietimmar)

Läs instruktionen om hur du skall redovisa.

Se till att följande frågor besvaras i redovisningstexten.

  • Vad är rekursion?
  • Känner du att du har förståelse för hur sorteringsalgoritmerna fungerar?
  • Vad tycker du om VisuAlgo]?
  • Vad är big-O?
  • Gjorde du någon av extrauppgift?
  • Gick det bra att komma i gång med kursmomentet, var det lagom, för litet, för stort?

#Revision history

  • 2018-01-31: (A, aar) Första version v2.
  • 2017-11-10: (PF1, mos) Utkast till v2.

Document source.