Sortering af en hægtet liste

Det er selvfølgelig muligt at sortere en hægtet liste, ved at tage elementer ud og sætte dem ind det rigtige sted igen. Det tager selvfølgelig bare tid.

Du kan dog (måske) lave din hægtede liste om, så den sætter ny elementer ind sorteret istedet for enten forrest eller bagest.

Så vidt jeg kan se er der ikke en sorterings algortime til linkede lister.

Lav en .toArray() på din linkede liste.

Derefter kører du en Sort på dit array.

Bagefter ligger du dem ind i din linkede liste, efter du har tømt den for gamle data.

Disky: Hvordan bruger jeg så den der .toArray() på min linkede liste?

LinkedList list=new LinkedList()

Object array[]=list.toArray(); //sådanne her

Hvis du benytter en LInkedList der implementerer
List interfacet fra java.util er det let at sortere din liste.
Arrays klassen fra java.util har mange statiske metoder
til at sortere arrays, alle med navnet sort men med
forskellige signaturer (argumentlister). 
Arrays.sort( list, comparator );
hvor comparator implementerer Comparator, der
skal have en int compare(Object o1, Object o2)
og en equals metode.
Når du har en hægtet liste af heltal (Integer) er denne
let at skrive (så skal det også være heltal):
public int compart(Object o1, Object o2) {
  return ((Integer)o1).intValue()<((Integer)o2).intValue();
}

hej igen!

tak for hjælpen men kan i ikke lige skære det her lidt ud i pap?

jeg har lavet en hægtet liste der hedder sl denne liste vil jeg gerne lave om til et array således at jeg kan bruge metoderen instertionsort og mergesort (disse har jeg rimelig styr på, det er bare konverteringen mellem linked list til array)

Object data[]=sl.toArray();

Det er det hele, så har du et array af Object\'s som du så kan sortere på.
Men brug den sorteringsmetode som er indbygget i Java, kig under Array\'s under java.util, de klarer det for dig.

Jeg kan ikke lige teste men noget i retningen af:


Object data[]=sl.toArray();
Arrays.sort(data);

Nu er dit Array sorteret, ved brug af den meget hurtige Quicksort

Du må skrive lidt klarere hvad du mener:  dine arrays
er det int[] eller Object[] eller hvad?  Dine insertionsort
og mergesort metoder må have en argumentliste?
Hvad mener du med at du har lavet en hægtet liste?
Har du nedarvet fra LinkedList og hvilke interfacet har
du i så fald implementeret.  Med disse informationer
er der mange der hurtigt kan hjælpe dig med koden,
men uden at vide hvilke metoder du har til rådighed
er det ikke muligt at komme meget videre en indlægene
ovenfor.

disky: Det kræver at der benyttes de indbyggede
hægtede lister (LinkedList) eller at man har implementeret
de relevante interfaces, men det tyder ikke på at
det er tilfældet her, for i så fald var problemet nok løst.

Kasi:

Da du ikke har sagt om du bruger din egen hægtet liste, eller en af dem i Collection pakken, har jeg lavet et eksempel der bruger LinkedList.

p.s. det kan ikke betale sig at lave sin egen.

import java.util.*;

public class Liste extends java.lang.Object
{
   
    /** Creates new Liste */
    public Liste()
    {
        LinkedList sl=new LinkedList();
        sl.add(new Integer(2846));
        sl.add(new Integer(-28));
        sl.add(new Integer(0));
        sl.add(new Integer(55));
        sl.add(new Integer(2));
        sl.add(new Integer(85));
        sl.add(new Integer(17));
       
        Object data[]=sl.toArray();
        Arrays.sort(data);
       
        for(int x=0;x<data.length;x++)
        {
            System.out.println(data[x]);
        }
       
    }
   
    /**
    * @param args the command line arguments
    */
    public static void main (String args[])
    {
        new Liste();
    }
   
}

Og eksemplet virker.

vi har lavet en hægtet liste med 10 strings i disse strings er der tal som vi gerne vil have ændret til int, lagt over i et array således at vi kan sortere med insertionsort og mergesort.

vi har lavet den hægtede liste (hurra) og sorterings algoritmerne (atter hurra), men vores merge og insertionsort kan kun modtage et array af integers som argument og det er her vores probkem opstår, nemlig hvordan vi laver den hægtede liste om til et array.

Hvis du selv har lavet din linked liste.

skal du lave f.eks. lave en .toArray() metode som gør følgende:

SIZE = antal elementer i din linkede liste
sl = din linkedeliste

sl.data(x) skal returnere den String på plads x i din linkede liste

    public int[] toArray()
    {
        int data[]=new int[SIZE];
       
        for(int x=0;x<SIZE;x++)
        {
            data[x]=Integer.parseInt(sl.data(x)); //sl.data(x) skal returnere den string der er på pos x i din liste
        }
        return data;
    }

Du må fortælle hvilke metoder jeres hægtede liste klasse har,
så er det hurtigt at skrive koden til at ekstrahere jeres
int\'s. Fra en streng (String) får i en int ud som følger:
String s = \"1234\";
int i = Integer.parseInt(s);
Hvis ikke strengen repræsenterer kastes dog
en NumberFormatException.  Den er dog ikke en
checked exception så I behøver ikke at bekymre
jer om den (hvis I ved jeres strenge har det rette
format).

disky: nu blev det hele lidt forvirrende.... men om vi bruger del af din kode foroven:
*************************************************
import Sorts;  // her importerer vi vores Sorts-klasse som indeholder vores insertionsort-metode.

public class Liste extends java.lang.Object
{
   
    /** Creates new Liste */
    public Liste()
    {
        LinkedList sl=new LinkedList();
        sl.add(new Integer(2846));
        sl.add(new Integer(-28));
        sl.add(new Integer(0));
        sl.add(new Integer(55));
        sl.add(new Integer(2));
        sl.add(new Integer(85));
        sl.add(new Integer(17));
       
        Object data[]=sl.toArray();
       
        Sorts.insertionSort(data);
       
        for (int index = 0; index < data.length; index++)
        System.out.print (data[index] + \"  \");

}
}

***********************************************
Sorts-klassen:

public class Sorts
{
public static void insertionSort (int[] numbers)
  {
      for (int index = 1; index < numbers.length; index++)
      {
        int key = numbers[index];
        int position = index;
       
        //Skift stoerre vaerdier til hoejre
        while (position > 0 && numbers[position-1] > key)
        {
            numbers[position] = numbers[position-1];
            position--;
        }
       
        numbers[position] = key;
      }
  }
}
****************************************

Problemet er nu at vi ikke kan få sorteret vores ellers dejlige array med den ønskede insertionSort-algoritme.

Øh er det ikke en bobble sort du har lavet ?

øh har den metode nogensinde virket ?

Har lige kigget efter det er ikke en bobble sort

Nej, det mener jeg ikke - men det er i så fald ikke det væsentlige, som er at få dem til at \"tale sammen\".

Har i en toArray metode? Af ovenstående er det
ikke klart hvordan i får et element ud af jeres liste
og før i kan det kan i heller ikke sortere den.

kasi: husk du skal bruge den toArray() jeg har lavet. (læs kommentarene)

Ja, den virker her:

import Sorts;

public class SortGrades
{
  public static void main(String[] args)
  {
      int[] grades = {45, 56, 89, 12, 65, 33, 91, 6};
     
      Sorts.selectionSort (grades);
     
      for (int index = 0; index < grades.length; index++)
        System.out.print (grades[index] + \"  \");
  }
}

************************************

Men vi skal altså have den der hægtede liste med ind i billedet .... :-)

Vi kan godt se at den sorterer fint med Arrays.sort(data); - men vi SKAL altså bruge insertionSort....

i dit eksempel kalder du \'selectionSort\' men foroven er det insertionSort :-)

ups ... min fejl ... det skal selvfølgelig være: Sorts.insertionSort (grades);

Er jo også ved at blive lidt rundtosset her .... :)

Problemmet er arrayet skal castes fra Integer til int.

Følgende virker:

import java.util.*;

public class Liste extends java.lang.Object
{
   
    /** Creates new Liste */
    public Liste()
    {
        LinkedList sl=new LinkedList();
        sl.add(new Integer(2846));
        sl.add(new Integer(-28));
        sl.add(new Integer(0));
        sl.add(new Integer(55));
        sl.add(new Integer(2));
        sl.add(new Integer(85));
        sl.add(new Integer(17));
       
        Object data[]=sl.toArray();
        Arrays.sort(data);
       
        int grades[]=new int[data.length];
        for(int y=0;y<data.length;y++)
        {
            grades[y]=((Integer)data[y]).intValue();
        }
       
        insertionSort (grades);
       
        for (int index = 0; index < grades.length; index++)
            System.out.print (grades[index] + \"  \");
       
    }
   

    /**
    * @param args the command line arguments
    */
    public static void main (String args[])
    {
                new Liste();
    }

    public void insertionSort (int[] numbers)
    {
        for (int index = 1; index < numbers.length; index++)
        {
            int key = numbers[index];
            int position = index;
           
            //Skift stoerre vaerdier til hoejre
            while (position > 0 && numbers[position-1] > key)
            {
                numbers[position] = numbers[position-1];
                position--;
            }
           
            numbers[position] = key;
        }
    }
       
}

Det virker!!

Tak for hjælpen!!

det var skam så lidt :)