Labinstruktion. Ännu utkast.

Laboration 3: sortering

• Kod att börja med. (Testa med Test1.java.)
• Relevanta overheadbilder

Inför övningarna finns en färdig instickssortering för strängar InsertionSort. Den implementerar gränssnittet LinkedListOfStringsSorting som kräver att denna metod skall finnas: public LinkedList<String> sort(LinkedList<String> input);

(a) Befintlig InsertionSort skapar en helt ny sorterad LinkedList<String> och låter den gamla finnas kvar (med sin osorterade sekvens av element). Vi kan också göra instickssortering som bara använder den givna listan (sortering "in place"). För varje element vi sticker in frigörs en plats i den dittills osorterade delen av listan. På så sätt halveras behovet av att allokera minne för listor jämfört med given lösning. Gör en ny klass med samma metoder som InsertionSort, men som arbetar "in place". Modifiera Test1.java så att den testar din nya "in place" instickssortering.

Lite knepigt, kanske.

(b) Skapa en klass som implementerar gränssnittet LinkedListOfStringsSorting, men som bygger på någon annan (valfri) algoritm än instickssortering.

Mer krävande. Kräver eget val

VG-uppgift

(c) Skapa en ytterligare en klass som implementerar gränssnittet LinkedListOfStringsSorting, men som bygger på någon tredje (valfri) algoritm utöver dem i (a) och (b).

Ännu mer krävande. Kräver eget val