Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder einen alternativen Browser verwenden.
deine behauptung ist schlcihtweg falsch. insertion sort ist sowohl im avarage case und damit auch im worst case n^2. das muss man sich nicht einmal genauer anschauen um das zu sehen, mit ein kleinen wenig erfahrung.
kleiner nachtrag warum insertion sort auch im avarage case Theta(n^2) laufzeit hat:
die entscheidende beobachtung ist, dass bei einer zufälligen eingabe, zu jedem zeitpunkt während der ausführung die erwarte anzahl an schritten um das gerade neu einzusortierende element an seine richtige position zu setzten 1/2 mal Anzahl bereits vorhandenen elemente ist.
nein. das gilt NUR, wenn für die bestimmung der position binäre suche benutzt wird bzw. werden kann. insertion sort (ohne zusätzliche bemerkung) tut dies nicht.
implementierst du insertion sort auf einem array, so könntest du binäre suche nutzen, hast aber verdammt teuere einfügeoperationen (im erwartungsfall Theta(n) ).
nutzt du eine liste, dann kannst du nicht mehr ohne weiteres eine binäre suche in logarithmischer zeit durchführen. dieses dilemma kann man durch aus lösen, mit aber rel. großem aufwand. das resultät wäre dann ein verfahren, welches immer noch deutlich schlechter ist als ein schelchtprogrammiertes merge sort.
edit: haben wir das nun endlich mit insertion sort geklärt?
p.s. hab glatt vergessen dein "naja" zu kommentieren. ja, insertion sort ist so eines der einstiegsbeispiele zur laufzeitanalyse bevor man überhaupt andfängt den studenten die grundlagen zu erklären. wenn einer schon ein paar semester weiter ist und sich mit insertion sort abschätzung schwer tut, dann sollte er ganz ganz vorsichtig sein mit seinen vermutung zu laufzeiten.
edit2: aber du darfst mir gerne mal zeigen, wie du in log n schritten in einer liste (und nur mit hilfe dieser liste) die passende stelle findest.
die wiki seite die du gelesen hast hat dir das wohl nicht verraten...
@daemon777:
überschätzt diese beobachtung nicht. stell dir die frage, wie wahrscheinlich es ist, das so etwas passiert. bedenke bubble sort hat auch avarage case laufzeit von n^2, quick sort n log n.
Wenn man tatsächlich einfach nur beliebige Eingaben betrachtet gebe ich dir durchaus recht. Es ist mir aber schon passiert, dass ich bei einem Problem erst nicht erkannt habe, dass meine Zahlenfolgen eigentlich bereits vorsortiert vorliegen. Ich wollte nur nochmal darauf aufmerksam machen, dass so etwas eben auch vorkommen kann.
So wie es eben auch vorkommen kann, dass sich der Radix-Sort gut anwenden lässt. Das trifft ja längst nicht auf alle Anwendungen zu aber wenn man über so etwas stolpert ist es, denke ich, doch nützlich wenn man nicht nur an Quicksort, Mergesort, Heapsort und was weiß ich noch alles denkt
Wenn du feststellst, dass deine eingaben ohnehin sortiert kommen, wozu dann noch sortieren?
ich weiderhole noch mal:
quicksort ist AUCH bei höherer gefahr von teilsortieren folgen im allgemeinen schneller als Insertion Sort und co.
der grund ist, dass quicksort die n^2 laufzeit nur dann hat, wenn das pivot-element ungünstig gewählt wird. da es aber normalerweise zufällig gewählt wird kommt das nicht so zum tragen.
wenn ein großteil der eingaben vollsortiert sind, dann ist es besser einmal auf sortiert zu überprüfen und falls es das nicht isst dann quicksort zu nutzen.
mir fällt echt beim besten willen kein anwendungsszenario ein in dem ich insertion oder bubble sort nutzen würde. in der praxis sieht es so aus:
- quicksort
- mergesort, wenn große datenmengen vorhanden sind, die nicht alle in den arbeitsspeicher passen (dürfen) oder wenn eine garantie für die max. laufzeit benötigt wird.
es gibt noch andere szenarien, die für mergesort sprechen, die haben aber alle ähnliche gründe, wie das da soben bezüglich des arbeitspseichers beschriebene.
wenn man parallelisiert sortieren will, dann:
sample sort oder odd-even-transposition sort oder paar varianten von merge-sort.
unter umständen kann (bei geeigneter topologie) auch quicksort in einer speziellen parallelen variante sinnvoll sein.
bei sehr exotischen topoligien gibt es dann natürlich eigens dafür konzipierte verfahren.
edit2: aber du darfst mir gerne mal zeigen, wie du in log n schritten in einer liste (und nur mit hilfe dieser liste) die passende stelle findest.
die wiki seite die du gelesen hast hat dir das wohl nicht verraten...
Kein Problem, ich brauche halt eine Listenstruktur, die auch einen Zugriff über Index erlaubt. Zugegeben etwas exotisch, aber warum nicht.
Dann suche ich zuerst bei: Liste.getElement((int) (Liste.length/2)), und soweiter.
Beim einfügen muss sich die Liste dann entsprechend updaten. Das wäre halt eine Mischung aus Array und Liste.
Und bitte komme mir jetzt nicht mit irgendwelchen naiven Implementierungen bzw. dieses und jenes wäre nicht erlaubt. Wenn ich mir über die Laufzeit eines Algorithmus Gedanken mache, dann schon über die schlaueste bzw. mächtigste Variante. Dabei gilt: alle Tricks sind erlaubt.
Kein Problem, ich brauche halt eine Listenstruktur, die auch einen Zugriff über Index erlaubt. Zugegeben etwas exotisch, aber warum nicht.
Dann suche ich zuerst bei: Liste.getElement((int) (Liste.length/2)), und soweiter.
Beim einfügen muss sich die Liste dann entsprechend updaten. Das wäre halt eine Mischung aus Array und Liste.
Und bitte komme mir jetzt nicht mit irgendwelchen naiven Implementierungen bzw. dieses und jenes wäre nicht erlaubt. Wenn ich mir über die Laufzeit eines Algorithmus Gedanken mache, dann schon über die schlaueste bzw. mächtigste Variante. Dabei gilt: alle Tricks sind erlaubt.
binäre suche in listen funktioniert mit skiplists, wie ice-breaker schon angemerkt hat, dennoch würde mich interessieren, wie man die von dir vorgeschlagene datenstruktur konkret implementieren würde, das ist ja doch alles recht schwammig. kannst du da etwas mehr ins detail gehen?
das ist die oben angesprochene lösung, wenn man das obige dillemma lösen will.
Und bitte komme mir jetzt nicht mit irgendwelchen naiven Implementierungen bzw. dieses und jenes wäre nicht erlaubt. Wenn ich mir über die Laufzeit eines Algorithmus Gedanken mache, dann schon über die schlaueste bzw. mächtigste Variante. Dabei gilt: alle Tricks sind erlaubt.
ich weiß zwar nicht was du mir damit sagen willst. aber egal.
du hast meine frage jedenfalls nicht beantwortet. binäre suche in log(n) zeit in normalen listen bekommst du also auch nicht hin. die verwendung von listen sind aber nicht nur eine implementationsvariante sondern bestandteil der definition von insertion sort.
wie ich bereits schon schrieb, kann man listen und arrays geschickt kombinieren. ddamit könnte man das problem lösen. das war aber nicht gefragt, denn das so etwas möglich sit habe ich ja schon gesagt.
du hast aber im übrigen das eigentlich problem, wie man das denn nun sinnvoll verknüpft noch gar nicht angesprochen, geschweige denn gelöst.
ich helf mal bissle nach:
während die äussere schleife von insertion-sort läuft baust du am listen anfang ne sortierte teilfolge auf.
man betrachte einen zeitpunkt i:
- wir haben i sortierte elemente am anfang.
- nehmen wir mal an du hast wie von zauberhand einen sortierten index auf den du die binäre suche durchführen kannst (der index verweist auf die listenelemente und die sortierung beruht auf den wert des listenelements und nicht den index selber).
- du findest nun also in log(i) zeit die einfügestelle.
- du fügst das listenelemente korrekt in die neue position der liste ein
FRAGE: wie erstellst du daraus nun in MAXIMAL log(i) zeit einen neuen index, welcher die obigen bedingungen wieder erfüllt?
edit2:-----------------------
ich weiß nicht, irgenwie macht mir das den eindruck, dass du dich gerade bissle durch inet liest und hier dann schnippsel von ideen hinwirfst. denk doch mal dein verfahren zu ende und poste es erst dann.
dann können wir ja mal drüber reden, ob es funzt.
jedenfalls insertion sort wie es auf den seiten zuvor angesprochen wurde ist von der laufzeit so zu analysieren, wie ich es schrieb und für einen studenten der informatik, der schon ein paar semester fortgeschritten ist, sollte es kinderkram sein... sollte es, ist es leider sehr sehr oft nicht.
-----------------------------
edit:---------------------------------
hmm, hab jetzt mal bissle genauer drüber nachgedacht. ich denke nicht, dass das überhaupt geht, ohne insertion sort selbst völlig überflüssig zu machen.
--------------------------------------
@zum thema skiplisten: die helfen hier gar nicht. das was F_GXdx da meint sind indizierte listen. ich sehe auch nicht wie skip-listen hier hilfreich wären (bevor jemand meckert: ja mit skip lists inziert man auch listen).
man könnte allerdings mit skip-listen (wie auch mit allen suchbäumen) ein sortierverfahren aufbauen: baum bzw. skip-listen erzeugen (geht normalerweise in n log n zeit) und dann die blätter auslesen ( O(n) ) -> fertig.
kennt wer heap-sort?
wenn man die in insertion sort einbauen will, kann man sich gleich das ganze insertion sort sparen
Ergänzung ()
Nachtrag:
man kann natürlich während des aufbaus dieses sortierten präfixes parallel dazu über diese sortierten elemente einen selbst balancierenden suchbaum aufbauen und ihn mit jedem (in den präfix) eingefügten elment mit einer log(i) operations um dieses element erweitern. solche bäume gibt es.
dann kann man mithilfe dieses baums die binäre suche machen.
die frage ist heir aber (wie oben schon angedeutet) WOZU? man kann sich die liste, die insertion sort sortiert ganz sparen und nur diesen baum benutzen und wie oben gesagt bei einen geeigneten suchbaum einfach die blätter in reihe auslesen.
alles was mir einfällt um insertion sort auf n log n alufzeit zu drücken macht insertion sort selbst überflüssig.
gerne. bin mal gespannt. edit: ectl. kann cih heute nicht mehr drauf antworten (jeh nach dem wann du dich meldest). komme dann morgen oder so drauf zurück.
Weil ich - wie oben bereits genannt - keine komplett sortierte Folge habe, sondern eben nur eine Teilsortierte. Die Zahlenfolgen waren stets von der Form, dass Nachbarn maximal einmal vertauscht werden müssen. BubbleSort läuft hier also in O(n) während der QuickSort O(nlogn) benötigt.
Dass Quicksort in fast allen Fällen vorzuziehen ist ist mir auch klar. Nur sollte man eben trotzdem vorher prüfen für welche Problemstellung der Algorithmus denn überhaupt eingesetzt wird
Es handelte sich um eine Simulation von Verkehrsteilnehmern auf vorgeschriebenen Routen. Da diese unterschiedliche Geschwindigkeiten hatten konnten sich die Reihenfolge ändern aber die Wahrscheinlichkeit, dass innerhalb eines Frames 2 Autos überholt werden war nahe bei 0.
Details weiß ich jetzt leider auch nicht mehr, weil ich das Programm nicht selber geschrieben habe. Im Moment frage ich mich ein bisschen ob es denn wirklich notwendig war in jedem Frame zu Sortieren oder ob 1mal/Sekunde nicht ausgereicht hätte, wenn man dann QuickSort verwendet.
nun ja, jeh nachdem was für anforderungen gegeben waren/sind... also, warum wurde berhaupt sortiert? ich meine gab es zeitpunkte an denen eine sortierte folge verlangt war?
wenn ja wie oft? wieviele frames lagen da dazwischen. denn abhängig von der wkt der überholugnen und der anzahl der frames zwioschen zwei zeitpuntken an denen man die sortierte folge bracuh könnte man z.b. so was machen:
bei jedem oder jedem x-tenf rame einmal durch huschen und nur ganz naiv direkte nachbarn bei bedarf sortieren. das geht einmal linear. die resultierende folge ist hochwahrscheinlich sortiert, wenn 1. überholung sehr selten geschehen und 2. im allgemeinen nur ein auto überholt wird, bzw. wenige.
und dann halt wenn man die richtig sortierte folge brauch einmal richtig durchgehen mit etwas, das gut auf fast sortierte folgen reagiert. man muss aber aufpassen, denn wenn zwischen 2 solcher zeitpunkte bereits log n frames liegen mit n anzahlt der autos, dann kann mans ich das gleich sparen und nur zu diesen zeitpunkt mit quicksort sortieren.
ich nehme an, dass ist so ziemlich der gedanke der dir grad kam, klang zu mindest so
aber du hast vollkommen recht hier: das ist ne situation in der lohnt es sich genauer hinzu schauen. es gibt viele zusatzinfos die helfen ein auf dieses problem spezialiserite lösung zu basteln.
genau hier ist es gut nicht nur zu wissen standardalgo xy hat laufzeit vw und geeignet für bla blub. da man hier evtl. mit dem abweichen vom standardbrei was effizienteres schustern kann.
mir fällt da grad ne menge ein... aber dafür knnte man nen neuen thread aufmachen
ich vermiss ein wenig meine wimi stelle glaub ich... sorry
edit: aus dem n log n insertion sort oben ist wohl nichts mehr geworden... oder?
Ich hab die Simulation nur als Grundlage benutzen müssen. Deshalb kann ich mich leider nicht mehr daran erinnern was genau mit der sortierten Liste angestellt wurde. Ich bin mir mittlerweile auch ziemlich sicher, dass man das auch anders hätte lösen können.
[ZITAT]wenn ja wie oft?[/ZITAT]
Ich meine, dass tatsächlich in jedem Frame soritert wurde. Das ist zwar nicht sonderlich elegant, aber noch technisch möglich, da der BubbleSort eben in 2n durchgelaufen ist. Einmal zum Sortieren und noch einmal um zu überprüfen ob tatsächlich alles richtig ist (jedenfalls hätte ich es dann so gemacht).
[ZITAT]ich nehme an, dass ist so ziemlich der gedanke der dir grad kam, klang zu mindest so [/ZITAT]
Genau das war mein Gedanke
[ZITAT]ich vermiss ein wenig meine wimi stelle glaub ich... sorry [/ZITAT]
Hab ich auch so das Gefühl
Mich stört es nicht und ich hoffe, dass der Threadersteller hier auch das ein oder andere Nützliche rausziehen kann.
Btw: Da ich ejtzt mal angefangen habe einfach aus Spaß an der Freude ein bisschen mit den Algorithmen rumzuexperimentieren und in C++ auszuprobieren bin ich echt erstaunt wie schlecht BubbleSort tatsächlich ist und wie schnell QuickSort ausfällt
Ich bin mal gespannt wie das wird wenns dann ans Parallelisieren geht. Da sollte ja bei QuickSort ja auch noch einiges rauszuholen sein. Wobei ich auch bei BubbleSort gespannt bin wie weit man den beschleunigen kann.
bzgl. bubble sort uss ich sagen, keine ahnung. hab darüber noch nie nachgedacht und ich errinere mich nicht jeh davon gelesen zu haben, dass es jemand anders mal tat
aber zu quicksort kann ihc einiges sagen. da gibt es im grunde zwei prinzipielle ansätze (+ ne dritte triviale). über beide kann man aber eines sagen: quicksort ist im allgemeinen keine gute wahl als grundlage für eine parallelisierte sortierung.
aber dennoch ist quicksort parallelisiert eine interessante sache, weil es eben recht deutich die verschiedenen problematiken beim parallelisieren aufzeigt.
wenn dich die richtung interessiert, dann empfehle ich mal sich die parallelen verfahren odd-even-transposition sort und sample sort anzuschauen.
das erste ist elegant einfach. von der effizienz eher schlecht da es eine gesamt arbeit von n^2 bei n prozessen, also ein prozess pro element und n^2 log n wenn man jeder prozess eine menge von Theta(n) elementen enthält.
ABER, es hat einen sehr geringen kommunikationsaufwand, skaliert recht gut und ist sehr anspruchslos bei der netzwerktopoligie, denn es reicht, wenn alle prozess in reihe geschaltet sind, also 1 - 2 -...- (P-1) - P und ein prozess kann (billig) nur mit seinen direkten nachbarn reden.
sample sort hingegen ist mit quicksort verwand. es reduziert den kommunikationsaufwand indem mehr oder weniger eine dicke effzizient gestallte kommunikation nur ausgeführt wird (grob gesagt) und dann jeder prozess autonom für scih alleine arbeitet.
aber es brauch eine topolige welche effiziente broadcast und prefixsummenberechnung erlaubt (vso ungefähr wie ich mich erinnere).
in der praxis ist letzteres normalerweise die erste wahl. quicksort hab ich mal zu demonstrationszwecken von einem team in cuda implementiert gesehen, merkwürdigerweise aber die schlechtere der beiden oben genannten ansätzte gewählt.
beim parallelisieren ist im gegensatz zu squentiellen verfahren eben nicht nur die laufzeit zu beachten, sondern auch die gesamt arbeit. beides verändert sich ggf. stark jeh nach dem verhältnis zwischen anzahl elemente n und anzahl prozesse p. und wenn man das dann auch noch etwas realistisch modellieren will, dann kommen da noch komunikationskosten, selbst vereinfacht sind es dann noch faktoren wie bandbreite, latenz und overhead... da gibt einige analyse modelle, die versuchen einigermaßen sinnvolle prognosen für parallele algorithmen zu machen.
die theoretiker haben es sich da lange einfach gemacht mit dem pram modell, was so eigenschaften wie latenzen etc. ignoriert. in meiner diplomarbeit habe ich unter anderem das LOGP modell bewertet und verglichen was eben versucht die obigen faktoren der kommunikation zu berücksictigen.
edit: ein generelles problem beim parallelisierenwas merge sort und quicksort gemein haben ist, dass sie das problem baumartig in teilprobleme zerlegen. was im squenzitellen der clou ist, ist im parallelen genau das, was es schelcht skalieren läßt.
denn während du bei beiden mit den blätern quasi alle prozessoren auslasten kannst, kannst du auf der vorletzten ebene nur 2 unabhängig von einer ander arbeiten lassen, ausser du bezahlt mit verdammt hoheh kommunikationskosten
Aus irgendeinem Grund bereit es mir grad Freude mich mit dem Parallelisieren zu beschäftigen. Also werde ich mir die beiden Vorschläge von dir auch mal anschauen. Aber nicht bevor ich mir meine eigenen Gedanken dazu gemacht habe. Ich finde es immer ganz spannend sich erst selbst Gedanken zu einem Thema zu machen. Deswegen eben auch der parallele Bubblesort
Vielleicht ist parallel hier aber auch schon zu viel gesagt. Bei den Greedy-Algorithmen kann ich mir schwer vorstellen, dass man sie tatsächlich auf mehrere Rechner aufteilen könnte. Es geht also, denke ich, nur so lange gut, so lange alle Prozesse auf die gleiche Datenmenge zugreifen können und das auch in überschaubarer Zeit können. Auf einem Quadcore habe ich hier also 4 bzw. 8 Prozesse. Aber das sollte mir auch schon erlauben einen gewissen Geschwindigkeitsvorteil zu gewinnen.
Auch Cuda wäre ein interessanter Ansatz, weil die GPU für paralleles Arbeiten ja wunderbar geeignet ist. Aber bisher habe ich nur einmal im Studium was mit openCL basteln müssen und auch da wurde uns das mehr vorgesetzt, als dass ich mir das tatsächlich erarbeitet habe. Da würde ich also praktisch bei 0 anfangen.
Wenn man tatsächlich alles ausnutzen will was man bekommen kann wäre es vermutlich spannend Teilprobleme auf unterschiedliche Rechner zu verteilen und hier sowohl von CPU als auch von GPU berechnen zu lassen. Probleme entstehen hier aber, wie du ja auch gesagt hast, beim Mergen vor Allem gegen Ende.
verstehe. beim gedanken machen zur parallelisierung musst du dir um folgende primitiven mal geadnken machen:
1. wie sind die prozesse (cpus oder was acuh immer) genau vernetzt? d.h. kann jeder mit jedem zum gleichen preis reden? wenn nein wie genau?
2. welche primitiven funktionen sind mit welchen kostenv erubunden? broadcast? all-to-all, prefix-calculation etc. gemeint sind effiziente methoden werte von allen zusammeln, ggf. dabei gleichzeitig zu verarbeite
3. kann man das problem in unabhängig teilprobleme überhaupt aufteilen und dann nur am ende wieder alles zusammen tragen oder sind zwischendurch immer wieder kommunikationen nötig?
ich rate dir erstmal nicht verschiedene topoligien und netzwerke zu mischen, also bleib bei einem multi-core oder bei mehreren rechner mit einem genutzten core pro rechner, damit du überhaupt erstmal die auswirkungen nachvollziehen kannst und deine algorithmen optimieren kannst.
mischt du die architekturen verlierst du schnell den überblick für die zusammehänge. ist ja so schon schwer genug beim parallelisieren.
edit: 4. wie ist das verhältnis zwischen anzahl prozesse und anzahl zu bearbeitender elemente.
