BubbleSort auf beliebige Objekte

Pille456

Hi
Ich bin gerade dabei viele der nötigen Standardklassen (also Queue, Stacke, List etc.) selbst in Java zu implementieren. Nun möchte ich meiner Liste noch ein paar Sortier-Algorithmen geben (wahrscheinlich BubbleSort und QuickSort) nur frage ich mich gerade wie ich das möglichst allgemein angehen kann. Konkret sieht das bei mir gerade so aus:
Meine "Knotenklasse" (also die Klasse mit Vorgänger/Nachfolger) hat als eigentliches Objekt was in die Liste soll, ein Element vom Typ "Object". Da "Object" die Oberklasse für jede Java Klasse ist kann ich so jedes beliebige Objekt in meine Liste packen. Nun muss ich natürlich die Elemente irgendwie vergleichen können, nur wie mache ich das?
Ich hatte an eine abstrakte Klasse bzw. abstrakten Dienst oder leeren Dienst (der dann halt in der Oberklasse überschrieben wird) gedacht, aber irgendwie passt das nicht so in das Projekt rein. Vielleicht habt ihr da ne Idee?
So sehen die Klassen derzeit aus:

public class element {
    private Object object; //jede Klasse in Java ist eine Unterklasse von Object
    private element next;
    private element previous;
    /* Ganz viel Code */
}

public class List {
    private element pointer;
    private element first;
    private element last;
    private int len;
    /* Mehr Code */
    public void bubbleSort() {
        element temp = first;
        while (temp.next() != null) {
            //Hier nun etwas allgemeineres
            if (temp.object().toString().length() > temp.next().object().toString().length()) {
                swap(temp,temp.next());
                if (temp == first) first = temp.next();
                if (temp == last) last = temp;
                temp = first;
            }
            temp = temp.next();
        }
    }

Zu nächst nen Tipp nutze doch Generics.
Das mit element.object ist ne gute idee ist aber nicht typischer.
Also du müsstest das object jedesmal wieder casten.

Und für das Allgemeinhalten der Größenvergleiche würde ich dir ein Interface empfehlen.

interface IComparer {

public int compare(IComparer a,IComparer b);

}

Das übergibst deiner Methode Bubblesort und überprüfst damit die größe der beiden elemente.So kannst für jeden Typ einen eigenen Comparer erstellen.

Gruß

DEvent

Wir sind hier nicht bei C#, also lass diese haesslichen IComparable. Benutze einfach das Comparable interface:

interface Comparable<T> {
    int compareTo(T o);
}

Siehe http://java.sun.com/javase/6/docs/api/java/lang/Comparable.html

Also

public class element<T> implements Comparable<element<T>> {
    private T object;
    private element next;
    private element previous;

    public int compareTo(element<T> o) {
        // pseudocode
        if (this < o) return -1;
        if (this > o) return 1;
        return 0;
    }
    /* Ganz viel Code */
}

Entsprechend deine List Klasse:

public class List<T> {
    private element<T> pointer;
    private element<T> first;
    private element<T> last;
    private int len; 
// ...

Achja, Klassentypen werden in Java mit einem Grosbuchstaben geschrieben, also "Element".

Pille456

Ich habe gerade mal versucht das mit nem Interface zu implementieren, aber irgendwie will das nicht so fruchten. Folgendes Problem:

public class Element<T> implements Comparable<Element<T>> {
    private T object; 
    private Element<T> next;
    private Element<T> previous;

    public Element(T pObject) {
        object = pObject;
        next = previous = null;
    }

    public int compareTo(T pObject) {
      return object.compareTo(pObject);
    }
/* weiterer code*/
}

Irgendwie klar, dass der Compiler dann meckert, dass er compareTo in "object" nicht findet.
Folgendes ist mein Ziel: Wenn der Programmierer meine Klasse benutzen will, dann muss er für das sortieren eine Funktion (hier compareTo) implementieren.
Ungefähr das macht ja der Pseudecode oder:

public int compareTo(element<T> o) {
        // pseudocode
        if (this < o) return -1;
        if (this > o) return 1;
        return 0;
    }

Da sehe ich nur das Problem, dass der Programmiere dann doch für die Objekte "<" und ">" implementieren muss oder nicht?

2. Frage: Wie handhabt Java Vergleiche genau? Beispiel:

if (10 <= 9) // = false = 0 ?
if (10 >= 9) // = true = 1?
if (10 > 10) // = false = 0?

Weil diese compareTo-Funktion soll ja -1,0 und 1 zurückgeben, je nach ob ob es gleich, größer oder kleiner ist. Das passt dann irgendwie nicht so in das Schema für if-Abfragen. (ich hoffe ihr wisst nun was ich meine :D)

DEvent

Irgendwie klar, dass der Compiler dann meckert, dass er compareTo in "object" nicht findet.

hm, dann eben so:

public class Element<T extends Comparable<T>> {
    private T object;
    private Element<T> next;
    private Element<T> previous;

    public Element(T pObject) {
        object = pObject;
        next = previous = null;
    }

    public int compareTo(T pObject) {
      return object.compareTo(pObject);
    }
/* weiterer code*/
}

Weil diese compareTo-Funktion soll ja -1,0 und 1 zurückgeben, je nach ob ob es gleich, größer oder kleiner ist. Das passt dann irgendwie nicht so in das Schema für if-Abfragen. (ich hoffe ihr wisst nun was ich meine :D)

Immer diese C/C++ Programmierer.

if ( x < y ) return -1;
if ( x > y ) return 1;
return 0;

Pille456

Hm, das ist nun komisch:

public class List<T> {
    private Element<T> pointer; //Hier Fehler, Meldung siehe unten
/*...*/

public class Element<T extends Comparable <T>> {
    private T object; 
    private Element<T> next;
    private Element<T> previous;
/*...*/

Da bekomme ich folgenden Fehler (wobei google hier auch recht wenig zu sagt):

type parameter T is not within its bound

EDIT: Ah okay so gehts:

public class List<T> {
    private Element<T extends Compareable<T>> pointer; //Hier Fehler, Meldung siehe unten
/*...*/

public class Element<T extends Comparable <T>> {
    private T object; 
    private Element<T> next;
    private Element<T> previous;
/*...*/

Dasd

Würde dir empfehlen, die komplette Deklaration des Typparameters in die List-Klasse zu nehmen.

public class List<T extends Comparable <T>> {
    private Element<T> pointer; //Hier Fehler, Meldung siehe unten
/*...*/

public class Element<T> {
    private T object; 
    private Element<T> next;
    private Element<T> previous;
/*...*/

Tolpan

Dann muss er das aber auch bei Element eintragen damit dort bekannt ist das T Comparable ist sonst gibts ja wieder probleme mit dem compareTo

public class List<T extends Comparable <T>> { 
    private Element<T> pointer; //Hier Fehler, Meldung siehe unten 
/*...*/ 

public class Element<T extends Comparable <T>> { 
    private T object; 
    private Element<T> next; 
    private Element<T> previous; 
/*...*/

Pille456

Hm also ich bin nun bei meiner Variante geblieben und das rennt bisher ganz gut
Ich mach mich dann mal die Tage an QuickSort, vielleicht kommt der MergeSort auch noch dazu mal sehen.

Dasd

Tolpan schrieb:

Dann muss er das aber auch bei Element eintragen damit dort bekannt ist das T Comparable ist sonst gibts ja wieder probleme mit dem compareTo

Hmm... ich habe es so verstanden, dass Element eine innere Klasse von List ist. Dann bräuchte er das nicht. Wenn nicht, dann ist es natürlich nötig.