---

jeg er stødt på et lille problem, jeg kan ikke helt finde ud af java.. jeg
skulle implementerere en "Insertionsort" på en simpel hægtede liste... og
jeg ved kun hvordan man gør det på et array.. der skulle vel ikke være nogen
der kunne hjælpe mig med problemet.

på arrayet ser det sådan ud:

public void sort()
{
int j, temp;

for (int i = 1; i < tal.length; i++)
{
if (tal[ i ] < tal[ i-1 ])
{
temp = tal[ i ];
for (j = i; j >0 && temp < tal[ j-1 ]; j--)
tal[ j ] =temp;
}
}
}

---

steen svensson wrote:

> jeg er stødt på et lille problem, jeg kan ikke helt finde ud af java.. jeg
> skulle implementerere en "Insertionsort" på en simpel hægtede liste... og
> jeg ved kun hvordan man gør det på et array.. der skulle vel ikke være nogen
> der kunne hjælpe mig med problemet.
>
> på arrayet ser det sådan ud:
>
> public void sort()
> {
> int j, temp;
>
> for (int i = 1; i < tal.length; i++)
> {
> if (tal[ i ] < tal[ i-1 ])
> {
> temp = tal[ i ];
> for (j = i; j >0 && temp < tal[ j-1 ]; j--)
> tal[ j ] =temp;
> }
> }
> }

du kan vel bare udskifte tildeling og hentning med get() og set()
og length med size(): (ikke testet)

public void sort()
{
int j, temp;

for (int i = 1; i < tal.size(); i++)
{
if (((Integer)tal.get( i )).intValue() < ((Integer)tal.get( i-1
)).intValue())
{
temp = ((Integer)tal.get( i )).intValue();
for (j = i; j >0 && temp < ((Integer)tal.get( j-1 ).intValue());
j--)
tal.set( j , new Integer(temp) );
}
}
}

Dette er dog en afsindig brug af en hægtet liste, og et bedre
bud er nok at at konvertere listen til et array (fx med toArray())
og sortere dette. Eller, hvis du har adgang til de enkelte elementer
i listen med previous pegere, kan du udskifte get og set med
manipulation af disse - hold dog tungen lige i munden - her et
ukomplet forsøg på en illustration (sikkert overhovedet ikke korrekt):

class Node{ Node previous; Node next; int value; }

Node j;
int temp;

// list indeholder Node objekter, som findes med get(index)
for (Node i = list.get(1); i != null; i = i.next)
{
Node j, i;
if ( i.value < i.previous )
{
for (j = i; j.previous != null && temp < j.previous.value; j =
j.previous )
{
j.value = temp;
}
}
}

Ulrik Magnusson

---

steen svensson skrev

> jeg er stødt på et lille problem, jeg kan ikke helt finde ud af java.. jeg
> skulle implementerere en "Insertionsort" på en simpel hægtede liste... og
> jeg ved kun hvordan man gør det på et array.. der skulle vel ikke være
nogen
> der kunne hjælpe mig med problemet.

I insertion sort indsætter man det "næste element" på den korrekte plads i
den allerede sorterede del. Hvis man bruger arrays kan man kun gøre dette
ved at skifte elementerne en plads til højre, mens man med hægtede lister
kan nøjes med at hægte elementet ind der hvor det passer. For at finde
pladsen i en enkelt-hægtet liste er søgning fra første element nødvendig (i
modsætning til array-eksemplet hvor man i stedet går baglæns).

Følgende *uafprøvet* kode skulle gerne illustrere princippet (lad nu være
med at bruge koden direkte, lav i stedet din egen version):


class Node {
int number;
Node next;
}

public Node sort(Node first)
{
Node head = new Node(); // hjælpeknude for at gøre det nemt
head.next = first; // at indsætte i starten af listen
for (Node i = first; i != null && i.next != null; i = i.next) {
Node j = i.next; // j er det element der evt. skal flyttes
if (j.number < i.number) { // kriteriet for at j skal indsættes
i.next = j.next; // hægt j ud af listen ved i
Node k = head; // find hvor j skal indsættes
while(j.number < k.next.number) k = k.next;
j.next = k.next; // indsæt j efter k
k.next = j;
}
}
return head.next;
}




Mvh,
--
Filip Larsen <filip.larsen@mail.dk>

---

Filip Larsen skrev

> Følgende *uafprøvet* kode skulle gerne illustrere princippet ...

Der har (selvfølgelig af klart pædagogiske grunde :) indsneget sig mindst en
fejl i koden. Et sted skal "<" erstattes med ">=", find selv hvor.


Mvh,
--
Filip Larsen <filip.larsen@mail.dk>