Opgaver - Modul 12 - Programmeringsopgaver

Til opgaverne herunder er der lavet en projektskabelon der indeholder test. Skabelonen findes på GitHub-repositoriet under / modul12 / Sortering /.

I skabelonen kan du bruge følgende kommandoer:

$ dotnet test
$ dotnet run

Med “dotnet test” kører alle testene, og du kan se hvad der fejler.

Med “dotnet run” kører du filen “Program.cs” som laver performance-test af alle fem sorterings-algoritmer. Den giver kun et retvisende resultat for de algoritmer er implementerede.

Opgave 1 - Lav BubbleSort

Filen BubbleSort.cs indeholder en skabelon til “bubble sort”. Tilføj den manglende implementation. Du kan fx finde den i dagens præsentation. Test den efterfølgende med dotnet test og dotnet run.

Du skal anvende Swap-metoden som allerede findes i klassen.

Opgave 2 - Lav InsertionSort og Selection

Lav nu også InsertionSort og SelectionSort og test at de virker. Du kan tilpasse koden fra dagens præsentation.

Opgave 3 - Performancetest

Prøv at køre performancetest af de tre algoritmer med

$ dotnet run

Hvilken er hurtigst? Hvor stor skal testSize være før at BubbleSort er ubrugelig?

Opgave 4 - Lav en fletning til MergeSort

Tiden er kommet til at færdiggøre MergeSort. Selve algoritmen er simpel nok, men fletning (Merge-metoden) er lidt mere omstændig.

Du skal tænke på den lidt som et spil kort delt op i to sorterede bunker. Opgaven er at flette dem samme til en bunke, som stadig er sorteret. Du skal kode denne fletning i følgende metode:

private static void Merge(int[] array, int low, int middle, int high) {
    // TODO: Implement		
}

array indeholder så at sige begge bunker. Første bunke ligger fra index low til middle. Sidste bunke er fra middle + 1 til high. Metoden har ingen return. Den skal lave “in place” sortering på input-arrayet.

Som en hjælp er her en god skabelon til fletning. Det kan være en fordel lige at køre den igennem med papir og blyant før man koder den.

Algoritme: totalFlet
Input: s1: sorteret sekvens, s2: sorteret sekvens
Returnerer result: sorteret sekvens

Metode:
result = den tomme sekvens
while (der er elementer i s1 && der er elementer i s2) {
	e1 = det element man er kommet til i s1
	e2 = det element man er kommet til i s2
	if (e1 <= e2) {
		tilføj e1 bagest i resultat
		gå videre i s1
	}
	else {
		tilføj e2 bagest i resultat
		gå videre i s2
	}
}

while (der er elementer i s1) {
	tilføj det element man er kommet til i s1 til resultat
	gå videre i s1
}

while (der er elementer i s2) {
	tilføj det element man er kommet til i s2 til resultat
	gå videre i s2
}

return result

Opgave 5 - Lav partition til QuickSort

Som en ekstra lille udfordring skal du lave partitions-delen til QuickSort færdig. Du kan finde algoritmen beskrevet på præsentationen.

Bemærk også, at der findes bedre måder at vælge “pivot” på end den beskrevne (fx kan man vælge et random index i stedet for 0).

Lav performance-test af alle algoritmerne. Prøv med forskellige “testSizes”. Hvis du har mod på det, kan du også prøve at tweake QuickSort ved fx at vælge pivot på en bedre måde.

Opgave 6 - Andre algoritmer

Der er mange andre sorteringsalgoritmer end de klassiske.

Har du mod på at implementere en af de andre efter eget valg, og teste dem op imod resten? Du kan altid prøve BogoSort 😊