Kmom05: Sorteringsalgoritmer och datastrukturer

By . Latest revision .

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.

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:

Det finns inget kapitel för det här kursmomentet.

#Artiklar

Läs följande:

  1. Sorting algorithms and big-O. Visar inte kod men är tydlig med bilder och förklarar hur de fungerar.

  2. visualgo. Interaktiv sida som visualiserar hur tal sorteras och hur koden exekveras med olika algoritmer.

#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 ä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.