Oppgavesett 3 - Sortering

Oppgavene blir tema på øvingen fredag 3. februar. Innleveringen skal bestå av en pdf-fil med korte kommentarer og dokumentasjon (utskrifter etc.). Legg også ved godt dokumenterte java filer. Alt pakkes i en zipfil, med navn assignment03-*.zip der * er etternavnene til gruppemedlemmene. Javafilene skal tilhøre en pakke med navn package assignment03.

Fristen for innlevering er tirsdag 7.februar 09:00.

Oppgave 1

Oppgave 1.A

Redegjør for hovedprinsippet ved innsettingssortering, og beskriv algoritmen med presis pseudokode.

Oppgave 1.B

Illustrer hvert trinn i en innsettingssortering på følgende sekvens av heltall:
12 3 89 42 21 11 23

Oppgave 1.C

Er effektiviteten til innsettingssortering avhengig av strukturen på det som skal sorteres (dvs. om input er ferdig sortert, omvendt sortert, etc.)? Begrunn svaret.

Oppgave 1.D

Programmer metoden fra 1.A, med følgende signatur void insertionSort(int[] arr). Metoden skal inneholde passende utskrifter, slik at en kjøring også resulterer i en illustrasjon av trinnene. Test sorteringen på følgende sekvens:
12 3 89 42 21 11 23

Oppgave 1.E

Du skal nå teste hvor effektiv metoden din er i praksis. Kjør et passende antall sorteringer med økende input (tilfeldig distribuerte verdier), helt opp til en størrelse der det tar "urimelig" lang tid på din maskin. Ta tiden på hver sortering, og lag et plott med størrelsen på input langs x-aksen, og kjøretid på y-aksen. Prøv å bruke dette plottet til å bestemme algoritmens effektivitet i O-notasjon.

Oppgave 2

Oppgave 2.A

Forklar hvordan vi kan implementere innsettingssortering ved hjelp av en lenket liste, og beskriv algoritmen med presis pseudokode. Husk at en lenket liste også kan bygges opp med toveis lenker, der man bruker en referanse til forrige node. Her er det mange løsninger. Den kanskje enkleste er å ta ut ett og ett element fra den sorterte delen, finne den riktige plassen i den sorterte delen, og så ta en vanlig insert (altså ingen byttinger). Dette kan også fint gjøres med enveis referanser.

* Oppgave 2.B

Den følgende (ufullstendige) nodeklassen innkapsler et data objekt som implementerer interfacet Comparable:

package assignment03; public class Node { public String value; Node next; //... }

Dette gjør at man kan bruke nodeklassen til å implementere metoden du har beskrevet i oppgave 2.A...bruk malen under og gjør det!

package assignment03; public class Sort { public Node insertionSort(Node unsorted) { // Return first element in sorted list // unsorted is the first element in the unsorted input list //... } //... }

Du kan gjerne legge til ekstra funksjonalitet i Node-klassen hvis du trenger det. Dokmenter at metoden virker.

* Oppgave 2.C

Test metoden du har implementert i 2.B på samme måte som i 1 E.