Ich habe eine kurze Frage, und zwar kann man seine Liste ja mit Collections.sort(..); sortieren lassen. Gibt es auch methoden, um eine bestimmtes Element in einer sortierten Liste zu finden, bzw. ein weiteres Elemnt einzufügen, ohne dass die Sortierung dafür aufgehoben werden muss? Weil bei den Funktionen von Collections finde ich diese Merhoden nicht, zumindest nicht unter Namen die ich erwarten würde.
Natürlich kann man die auch selber schreiben, aber da ich diese Methoden relativ häufig brauche wäre eine fertige Methode wahrscheinlich besser, da hofffentlich schneller.
In Collections nicht, liegt dann aber auch an dem Typ der Liste, auf einer ArrayList ist eine Binäre Suche gut (aber es muss verschoben werden), auf einer LinkedList durchgehen, bis Ende oder das nächste Element > dem aktuellen Element. Vielleicht umschwenken auf eine Sorted-Datenstruktur (edit: oder in vielen Zwischenschritten erst mal sammeln und dann sortieren).
Ja glaube so was habe ich gesucht, probiere das mal aus ob ich damit kalr komme, sonst melde ich mich nochmal
Wah :eek: Es muss doch einen Grund geben, warum Collections#binarySearch so einen merkwürdigen Wert zurückgibt, wenn das gesuchte Element nicht enthalten ist:
Returns:
the index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list
Das kann man ausnutzen, um in O(logn) die Einfügeposition für neue Elemente zu finden. (Das Einfügen selbst ist dann was anderes, aber … vom Prinzip her…)
package bytewelt;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class SortedListInsert
{
public static void main(String[] args)
{
List<String> list = new ArrayList<String>();
list.add("C");
list.add("E");
list.add("G");
list.add("I");
list.add("K");
Comparator<String> comparator = comparableComparator();
System.out.println("Before "+list);
sortedInsert(list, comparator, "F");
sortedInsert(list, comparator, "A");
sortedInsert(list, comparator, "Z");
System.out.println("After "+list);
}
private static <T extends Comparable<? super T>> Comparator<T> comparableComparator()
{
return new Comparator<T>()
{
@Override
public int compare(T t0, T t1)
{
return t0.compareTo(t1);
}
};
}
private static <T> void sortedInsert(List<T> list, Comparator<? super T> comparator, T element)
{
int index = Collections.binarySearch(list, element, comparator);
if (index < 0)
{
index = -(index + 1);
}
list.add(index, element);
}
}
Das klingt nach genau dem was ich gesucht hatte. Vielen dank
@Marco13 : bin. search macht nur Sinn, wenn eine ArrayList vorliegt. Außerdem hast du bei dem Einfügen “in der Mitte” von AL keinen Spaß. Außerdem ist die bin. search auf LinkedList langsam. Es gibt nur zwei richtige Wege: In vielen Zwischenschritten erst mal alles unsortiert sammeln/einfügen und anschließend sortieren oder von Beginn an eine sortierte DS verwenden. Laufzeit in O: gleich.
Naja bis jetzt habe ich eine normale ArrayList verwendet, daher ist das bei mir bis jetzt gegeben, wusste nicht, dass die Sort-methode von Collections für viele verscheidene Listentypen funktioniert, sosnt hätte ich geschrieben, was ich bisher verwende.
Wie ich schon angedeutet und CyborgBeta nochmal betont hat: Einfügen in eine ArrayList hat im schlechtesten Fall O(n). (Wenn man z.B. ganz vorne einfügt, müssen alle weiteren Elemente um 1 verschoben werden). Meine Antwort war die technische Antwort auf deine Frage: Man kann den Index für’s Sortierte Einfügen bestimmen (in O(logn)). Ob das in deinem Fall Sinn macht, ist eine andere Frage. Dazu müßtest du eine Abstraktionsebene höher beschreiben, was du vorhast… Welche Operation wird wie oft durchgeführt, und wann muss die Liste sortiert vorliegen?