Kmom05: Sorteringsalgoritmer och datastrukturer

By . Latest revision .

Kursutveckling pågår inför vt18.

Vi ska titta på hur några av de vanligaste sorteringsalgoritmerna ser ut och fungerar. Inbyggda sorteringsfunktioner baseras på en eller flera av de klassiska algoritmerna.

Vi ska även titta på några datastrukturer och implementera en egen som vi använder i ett terminalprogram.

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

(ca: 8-10 studietimmar)

#Kurslitteratur

Läs följande:

Python 3 Object-oriented Programming
* Ch 7 - Queues

#Artiklar

Läs följande:

Det finns inga extra artiklar.

#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. What on Earth is Recursion? förklarar rekursion.

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

  4. Quick Sort visualiserar quick sort.

  5. Data Structures: Queue visualiserar en Queue.

  6. Data Structures: Stack visualiserar en Stack.

#Lästips

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

  1. Datastructures - geeksforgeeks

  2. Sorting algoritms - geeksforgeeks

  3. Kolla på Abstract Data Type (ADT)

#Ö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”.

  3. Läs igenom artikeln “Datastrukturer”.

#Uppgifter

Dessa uppgifter skall utföras och redovisas.

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

  2. Gör uppgiften “Terminalprogram med sortering av lista

  3. Skapa din me-sida version 5. Fördjupa dig i Bootstrap och Flask. Gör uppdateringar som du själv bestämmer. Du måste även dokumentera vad du gjort i din redovisningstext.

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

#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 gjorde du för uppdatering av me-sidan?
  • Har du fått mer förståelse för datastrukturer?
  • Gick det bra att komma igång med rekursion?
  • Känner du att du har förståelse för hur sorteringsalgoritmerna fungerar?
  • Gick det bra att komma i gång med kursmomentet, var det lagom, för litet, för stort?
  • Vilken del av kursmaterialet (böcker, artiklar, videor, etc) uppskattade du mest?

#Revision history

  • 2017-11-10: (PF1, mos) Utkast till v2.
  • 2016-12-16: (E, lew) Updated flask structure.
  • 2016-06-09: (D, aar) Fler ändringar.
  • 2016-06-01: (C, lew) Ändrade något.
  • 2016-05-25: (B, aar) wow such change.
  • 2016-04-12: (A, lew) Första utgåva.

Document source.