Runtimes

Question 1

QuickSort

Answer 1

Best case Θ(n log n) - Om pivotelementet altid delar exakt på mitten, med andra ord om vi alltid väljer att sätta medianen som pivot element.

Worst case Θ(n^2) - Om pivotelementet alltid är det minsta eller största elementet, då kommer listan delas ojämnt.

Question 2

HeapSort

Answer 2

Best case Θ(n log n) - Kommer alltid vara det, spelar ingen roll vilken input man har.

Worst case Θ(n log n).
HeapSort bygger på en heap struktur som alltid balanserar sig, vilket ger en konsekvent körtid

Question 3

MergeSort

Answer 3

Best case - Θ(n log n), även om listan redan är sorterad behöver algoritmen fortfarande dela upp och sedan slå ihop allt.

Worst case - Θ(n log n), MergeSort utför alltid samma operationer oavsett input.

Question 4

InsertionSort

Answer 4

Best case - Θ(n), vilket inträffar om listan redan är sorterad

Worst case - Θ(n^2), vilket sker om listan är sorterad i omvänd ordning. Varje nytt element kräver att alla tidigare element flyttas för att sätta in den på rätt plats.

Question 5

SelectionSort

Answer 5

Best case - Θ(n^2), även om arrayen redan är sorterad måste vi ändå göra n-1 jämförelser för att hitta det minsta elementet i hela arrayen och detta görs n gånger.

Worst case - Θ(n^2), i sämsta fall är det omvänd sorterad lista, men algoritmen gör ändå lika många jämförelse som i best case.