Folgendes Problem:
ich habe eine schon geordnete Liste von
reellen Zahlen.
Jetzt wird zu jeder Zahl eine im Verhältnis
zur Gesamtausdehnung der Zahlenmenge kleine
Zufallszahl hinzuaddiert, so dass relativ
wenige benachbarte Einträge ihre Reiheinfolge
vertauschen.
Diese fast geordnete Liste wuerde ich gerne
wieder ordnen.
Das ist fast der Worst-Case von Baum-Algorithmen
die sonst meistens optimal sind.
Was koennte fuer diesen speziellen Fall
ein optimaler Algorithmus sein?
Gruss, Marco
Bubblesort
Hallo,
unter den Bedingungen (ich nehme mal an es können unterschiedliche Zufallszahlen addiert werden, ansonsten ist ja überhaupt keine Neusortierung notwendig) würde ich Bubblesort verwenden. Ob Du theoretisch dem quadratischen Worst-Case entkommst, hängt davon ab wie genau sich die „wenigen notwendigen lokalen Vertauschungen“ fassen lassen.
Gruss
Enno
Hallo Marco,
Eventuell kannst du auch das Sortieren in einem Durchgang mit dem Addieren machen, das spart auch Zeit. Einfach den Bubblesort in die Addier-Schleife einbauen.
Grüße, Robert
Danke!
Vielen Dank für
die Hinweise.
Mit Bubble-Sort komme ich dann auf
eine komplexität von O(N mal Erwartungswert der Maximalen
Verschiebung eines Elements).
Es scheint aber bei großen N die Zeitdauer überproportional
zu wachsen.
Gruss, Marco
hallo
bubble sort wird bei grossen N’s langsam. dafür eignet sich quicksort viel besser. einfach nach quicksort googeln.
gruss, giuseppe
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]