Insertion-sort besser als Bubble-sort?

Ich bin dabei meine revision für die Prüfung.

Würde gerne wissen, unter welcher Bedingung wird Insertion-sort besser als bubble-sort gegeben gleichen durchschnittlichen Fall Komplexität von O(N^2).

Ich fand einige ähnliche Beiträge, aber ich kann Sie nicht verstehen.

Würde jemand Verstand erklärt es in einer einfachen Art und Weise?

InformationsquelleAutor Jonathan | 2012-05-03
  1. 5

    Den Vorteil, bubblesort ist in der Geschwindigkeit der Erkennung einer bereits sortierten Liste:

    BubbleSort Best Case-Szenario: O(n)

    Jedoch auch in diesem Fall insertion sort bekam bessere/gleiche Leistung.

    Bubblesort ist, mehr oder weniger, nur gut für das Verständnis und/oder das unterrichten der Mechanismus von sortalgorithm, aber nicht finden, eine einwandfreie Nutzung in der Programmierung in diesen Tagen, weil seine Komplexität

    O(n2)

    bedeutet, dass seine Leistungsfähigkeit sinkt dramatisch auf Listen von mehr als einer kleinen Zahl von Elementen.

    • "bubblesort ist nur gut für das Verständnis und/oder das unterrichten der Mechanismus von sort-Algorithmus" - nicht einmal das, würde ich sagen. Insertion sort ist nicht schwerer zu verstehen, und nicht viel schwerer zu Programmieren. Bubble sort hat einen sehr speziellen Vorteil, dass es nachweislich die effizienteste Art für einen bestimmten Typ von Speicher, der nicht wahlfreien Zugriff. Trommel-Lagerung, denke ich, wo die Trommel dreht sich mit konstanter Geschwindigkeit in eine Richtung nur. Dann ist es beats einfügen Sortieren, weil insertion sort muss "nach hinten zu schauen", was sehr langsam ist. Dieser Vorteil wird nur selten von praktischem nutzen in diesen Tagen!
    InformationsquelleAutor Ben Win
  2. 3

    Folgende Dinge kamen mir in den Sinn:

    1. Bubble-sort braucht immer einen pass mehr über array, um festzustellen, ob es sortiert ist. Auf der anderen Seite, insertion sort nicht benötigen diesen-wenn die Letzte eingefügte element, Algorithmus garantiert, dass der array sortiert ist.

    2. Bubble-sort funktioniert n Vergleiche auf jedem pass. Insertion sort weniger als n Vergleiche: sobald der Algorithmus ermittelt die position, wo einfügen, Aktuelles element", es Stoppt Vergleiche an und nimmt das nächste element.

    3. Schließlich, Zitat aus wikipedia Artikel:

    Bubble-sort auch interagiert schlecht mit modernen CPU-hardware. Es
    benötigt mindestens doppelt so viele Schreibvorgänge wie insertion sort, doppelt so
    viele cache-misses, und asymptotisch weitere Niederlassung mispredictions.
    Experimente von Astrachan Sortieren von strings in Java-Karte bubble-sort zu
    etwa 5 mal langsamer als das einfügen, Sortieren und 40% langsamer als
    Auswahl Sortieren

    Finden Sie den link zur original-Studie gibt es.

    • Dank Victor. Ich fand die ersten 2 Punkte wirklich nützlich. Ich verstehe nun, einen grundlegenden Unterschied zwischen der 2-algorithmen ist die Anzahl der Vergleiche erforderlich. Cheers
    • 2. Punkt scheint zu sein, nicht korrigieren. Ja einige algorithmen, die das tut. Aber ich denke, in der richtigen bubble-sort-Algorithmus, die innere Schleife läuft n-1, n-2, n-3 .... mal bei jeder iteration der äußeren Schleife.
    InformationsquelleAutor Victor Sorokin
  3. 0

    Ich denke, die Antwort, die Sie suchen,hier:

    Bubble-sort kann auch effizient auf einer Liste, die bereits
    sortiert, außer für eine sehr kleine Anzahl von Elementen. Zum Beispiel, wenn
    nur ein element ist nicht in Ordnung, bubble-sort werden nur 2n mal.
    Wenn zwei Elemente sind nicht in Ordnung, bubble-sort werden nur bei den meisten
    3n Zeit...

    und

    Insertion sort ist ein einfacher Sortieralgorithmus ist relativ
    effizient für kleine Listen und meist sortierten Listen, und oft verwendet wird
    als Teil von komplexeren algorithmen

    • so zum Beispiel eine meist sortierte Liste: z.B. [ 2,3,4,5,1] bubble sort noch 4 swaps und 4 Vergleiche Insertion sort 4 swaps und 4 Vergleiche, wie gut. also, was ist der Unterschied?
    • in diesem spezifischen Beispiel gibt es keinen Unterschied 🙂
    InformationsquelleAutor MarcoS
  4. 0

    Könnten Sie links auf die entsprechenden Artikel, die Sie nicht verstehen? Ich bin mir nicht sicher, welche Aspekte Sie vielleicht ansprechen. Andere als das, es ist ein theoretischer Unterschied, das könnte sein, dass der bubble-sort ist besser geeignet für die Sammlungen vertreten, wie arrays (als es ist für diejenigen vertreten, die als verknüpfte Listen), während insertion sort ist geeignet für verknüpfte Listen.

    Die Argumentation wäre, dass der bubble-sort-immer vertauscht zwei Elemente zu einer Zeit, die trivial auf beide, array und verkettete Liste (effizienter auf arrays), während insertion sort Einsätze an einem Ort, in einer bestimmten Liste, das ist trivial für verknüpfte Listen, sondern umfasst das verschieben aller nachfolgender Elemente in einem array auf der rechten Seite.

    Dass gesagt wird, nehmen Sie es mit einem Körnchen Salz. Zuerst von allen, Sortieren von arrays ist, in der Praxis fast immer schneller als das Sortieren von verketteten Listen. Einfach aufgrund der Tatsache, dass das Scannen die Liste einmal hat ein enormen Unterschied schon. Davon abgesehen, bewegen n Elemente eines Arrays auf der rechten Seite, ist viel schneller als die Ausführung n (oder auch n/2) swaps. Dies ist der Grund, warum andere Antworten richtig behaupten, insertion sort, überlegen zu sein, im Allgemeinen, und warum ich mich über die Artikel, die Sie Lesen, weil ich nicht denke, dass eine einfache Art zu sagen, dies ist besser, in den Fällen Ein, und das ist besser in den Fällen B.

    • Bubble-sort ist möglicherweise besser geeignet, um arrays als bubble-sort ist es, verknüpfte Listen, aber die bubble-sort ist nicht mehr geeignet, um arrays als insertion sort für arrays.
    • Ja, vielleicht war ich nicht klar genug in dem letzten Absatz. Die Sache ist die, bubble-sort-Prinzip trivial auf arrays, während insertion sort nicht ("alles bewegen, was von x nach rechts"). Noch es ist wahr, dass dies nicht machen bubble-sort schneller.
    InformationsquelleAutor b.buchhold
  5. 0

    Im schlimmsten Fall beide sind in der Regel bei O(n^2)

    In der best-case-Szenario, D. H., wenn das array bereits sortiert, Bubble sort durchführen können O(n).

    • Bubble-sort kann so optimiert werden, laufen in O(n) - Laufzeit für die besten Fall.
    • Beide bubble und insertion die gleiche Komplexität für den worst/average/best case-Auftritte, die O(n^2) und auch räumliche Komplexität ist sowohl O(n) für Sie.
    • Im best-case-Szenario Bubble Sort durchführen können O(n). Wir können ändern, bubble-sort in einer solchen Weise, dass, wenn keine Swap-geschehen in der ersten iteration, dann können wir aufhören überprüft, wie denn die Liste ist bereits sortiert.
    InformationsquelleAutor Vineeth Chitteti
Schreibe einen Kommentar