Java Generic Insertionsort

[MR34L]

Hey Leute,
kurz zum meinem Problem.

Habe 2 Supertypen welche beide das Interface Comparable implementieren,
nun möchte ich mir einen Insertionsort bauen (bzw eine insert Methode um Objekte in die richtige Position einer Liste einzufügen).
Mir wäre es jetzt recht, wenn ich nicht für jede von den beiden Supertypen abgeleitete Klasse, die Methode insert überladen müsste, sonder alles mit einer generic Version machen könnte.

Mit Hilfe von eclipse bin ich dann hier drauf gekommen:

	@SuppressWarnings("unchecked")
	public static <T> void insert(List<Comparable<T>> objs, Comparable<T> obj) {

		int ix = 0;

		for (Comparable<T> o : objs) {
			if (o.compareTo((T) obj) < 0) {
				ix++;
			}
		}
		objs.add(ix, element);
	}

Leider funktioniert die Methode nicht. Eclipse zeigt mir folgendes an.

The method insert(List<Comparable<T>>, Comparable<T>) in the type Insert is not applicable for the arguments (List<Bike>, Bike)

Ich hoff das war alles verständlich & danke schonmal für die Hilfe

 

[Shagg]

du kannst deine objekte einfach in die liste einfügen und wenn deine supertypen comparable implementieren, dann kannst du im Anschluss darauf Collections.sort(Liste); aufrufen, was deine liste aufsteigend sortiert.

 

[1668mib]

	public static <T extends Comparable<? super T>> void insert(List<T> objs, T element) {

		int ix = 0;

		for (Comparable<T> o : objs) {
			if (o.compareTo(element) < 0) {
				ix++;
			} else {
				break;
			} 
		}
		objs.add(ix, element);
	}

Alternativ (würde ich wohl bevorzugen, aber schenkt sich nicht wirklich was...)

	public static <T extends Comparable<? super T>> void insert(final List<T> list, final T element) {
		for (int i = 0; i < list.size(); i++) {
			if (element.compareTo(list.get(i)) < 0) {
				list.add(i, element);
				return;
			}
		}

		list.add(element);
	}

 

[MR34L]

Ja, das weiß ich auch. Ich hätte hier vll noch erwähnen sollen, dass es mir um Performance geht.
Ich will nicht jedes mal die ganze Liste sortieren, sondern mir scheint es performanter die Objekte gleich
an die richtige Position zu setzen.
Okay, ich weiß jetzt nicht wie Collections.sort intern arbeitet.
Aber da Collections.sort ja nicht weiß, dass die Liste vorsortiert ist (und das ist sie ja, wenn ich jedes Element immer richtig einfüge) wird es daher das Element, welches ich einfügen will, mit allen anderen vergleichen müssen.

 

[1668mib]

AFAIK nutzt Collecitons.sort den Algorithmus Mergesort

Edit:
wäre für eine vorsortierte Liste kein solcher Ansatz denkbar:

	public static <T extends Comparable<? super T>> void insert(final List<T> list, final T element, int first, int last) {
		if (first >= last) {
			list.add(first, element);
			return;
		}
		
		final int middle = (first + last) / 2;
		final T middleElement = list.get(middle);
		
		if (middleElement.compareTo(element) < 0) {
			insert(list, element, middle + 1, last);
		} else {
			insert(list, element, first, middle - 1);
		}
	}
	
	public static <T extends Comparable<? super T>> void insert(final List<T> list, final T element) {
		insert(list, element, 0, list.size() - 1);
	}

Die Betonung liegt bei Ansatz, hab den Code nicht getestet... auf jeden Fall ist deine Schleife nicht wirklich schnell... im Mittel muss die Hälfte der Elemente geprüft werden bis der richtige Index gefunden wurde...

Bei einer Liste mit 1000 Einträgen wären das 500...
Wenn man immer die Mitte nimmt und schaut ob man größer oder kleiner liegt sinds nur noch 10 Vergleiche... (2-er Logarithmus von 1000)

 

[MR34L]

Den zweiten Post bischen zu spät gesehn.
Das will auch nicht jetzt bekomm ich den hier:

Bound mismatch: The generic method insert(List<T>, T) of type Insert is not applicable for the arguments (List<Bike>, Bike). The inferred type Bike is not a valid substitute for the bounded parameter <T extends Comparable<T>>

Bike erbt übrigens von Vehicle und Vehicle implementiert Comparable<Vehicle> die andre Oberklasse ist Building, davon erben dann auch paar Klassen.
Jap, ein optimierter Mergesort log n * n also oder bestcase linear. Ist jetzt auch egal, muss das so hinkriegen, sonst lern ich ja nichts dabei^^

 

[1668mib]

Dann könnte man noch rumspielen mit dem

<T extends Comparable<T>>

mal das hier machen

<T extends Comparable<? super T>>

 

[MR34L]

Macht es ja implizit, also es erbt von Vehicle und Überschreiben war nicht notwendig, da nur ein String Attribut verglichen wird. Also mit Collections.sort geht es, ich denk also nicht, dass es Probleme mit dem Interface Comparable gibt.

 

[1668mib]

Habs mein Post nochmal aktualisiert... da steht die Lösung.
und ich denke meine rekursive Variante dürfe kein allzu schlechtes Ergebnis liefern (hab die Änderungen reingemacht)

Edit:
Und nur mal so am Rande... "Insertionsort" ist ein Sortier-Algorithmus und keine Variante, Elemente in eine (vorsortierte) Liste einzufügen...

 

[MR34L]

Yeees, genau das hab ich gesucht. Danke!!
Könntest mir evtl noch paar Worte dazu sagen?

 

[1668mib]

The syntax ? super T denotes an unknown type that is a supertype of T (or T itself; remember that the supertype relation is reflexive)

D.h. der Ausdruck <T extends Comparable<? super T>> heißt du erwartest einen Typen T der das Comparable-Interface für T oder eine seiner Basisklassen implementiert. Vehicle ist Basisklasse von Bike.

Übrigens sieht die statische sort-Methode aus java.util.Collections so aus:
static <T extends Comparable<? super T>> void sort( List<T> list )

hat doch eine gewisse Ähnlichkeit (nicht dass du diese Methode verwenden sollst)

 

[MR34L]

Danke nochmal
Werde wahrscheinlich doch Collections.sort verwenden, da die Liste ja immer sortiert ist,
sollte es ja best case laufen^^ Oh man, aber immerhin was gelernt

 

[1668mib]

Gerade wenn die Liste vorsortiert ist lohnt es sich ja, einen darauf abgestimmten Algorithmus zu verwenden...

Warum die Sortierung über die ganzen vorsortierten Bereiche drüber laufen lassen? Wenn du weißt dass die Liste vorsortiert ist, kannst du schnell große Bereiche ausschließen - das wird Collections.sort nicht machen, weil es nicht wissen kann, in welchem Zustand sich die Liste befindet..

Wie gesagt, bei 1000 Listeneinträgen kannst du es mit 10 Vergleichen schaffen, auch Mergesort wird hier deutlich mehr brauchen...
Mergesort: Θ(nlog(n)) (für natural nur Θ(n) )
selbst nachgedacht: Θ(log(n))
wenn das kein Unterschied macht... oder hab ich dein Posting bzgl. der Leistung falsch interpretiert?