Nabend,

Wollte mal fragen ob mir jemand sagen kann, was der Autor mit diesem falschen? Code Block erreichen möchte?
Seite 5 - 1. Kasten "Sortieren mit BubbleSort - Optimierung"
Habe das ganze in JS vorliegen und es machht einfach keinen Sinn.
Denn sobald die geprüfte Zahl größer ist, wie die mit jener sie verglichen wird, ist test = true und die innere Schleife wird abgebrochen.
Das ganze führt dazu das bei mir nichts mehr sortiert wird. Weiß jemand wie die Optimierung von Bubblesort richtig funktioniert?

Gruß Eistee

Warum willst du den BubbleSort optimieren, anstatt dass du einfach einen schnelleren Sortieralgorithmus verwendest?

hi,

sieht so aus als wäre die anweisung "if(test) break;" relativ sinnfrei, da wie du schon gesagt hast durch das break die schleife verlassen wird.
hast du es mal implementiert und ausprobiert ?

Eistee schrieb:

Weiß jemand wie die Optimierung von Bubblesort richtig funktioniert?

Das ist eine C&P Bremse

Kein Mensch optimiert ernsthaft BubbleSort. Es ist ein anschauliches Verfahren, aber jegliche Optimierung ist vollkommen sinnbefreit, da es immer in O(n^2) (für einen Sortieralgorithmus heißt das: elendig langsam) bleibt. Dieser Vorlesung würde ich nicht über den Weg trauen.

Renati schrieb:

Kein Mensch optimiert ernsthaft BubbleSort

Welchen anderen Algorithmus mit (praktisch) 0 Speicherverbrauch gibts denn?

quicksort?

Hm.
Das was ich aus dieser Präsentation lesen konnte ist das:


Hat das Problem, dass der innerste Teil (Liste.Count - 2) ^ 2 Mal durchlaufen wird.
Benötigt aber tatsächlich nur 3 * 4 Byte (Die beiden Zählervariablen und die Hilfsvariable).

Ich habe es mit 10000 Integer Werten von Integer.MinValue bis Integer.MaxValue getestet.
Herausgekommen sind immer zwischen 3 und 3.2 Sekunden.
Ob das jetzt viel oder wenig ist kann ich nicht beurteilen, weil ich selten mit sowas arbeite.

squisheemixxa schrieb:

quicksort?

Quicksort arbeitet mit Rekursion. Rekursion braucht immer "extra" Speicher. Deswegen kann man sich mit ner endlos-Rekursion ja auch blitzartig einen StackOverflow einbauen ...

abermalimernst: So knapp kann Speicher garnet sein, dass man deswegen tatsächlich Bubblesort nehmen täte.

Übrigens: HeapSort ist als In-Place-Sortierung möglich.

microsoft.com/germany/msdn/web…ibrary.aspx?id=1032454038
microsoft.com/germany/msdn/web…ibrary.aspx?id=1032454039
Kann ich jedem empfehlen.

nikeee13 schrieb:

Kann ich jedem empfehlen.

wozu?

einen Sortier-Algo selbst zu implementieren ist doch eine Fingerübung ohne jeden praktischen Nutzen.

Inne Praxis verwendet man die List.Sort()-Methode und gut ist.

(naja - einen theoretischen Nutzen hat das vlt. schon: man lernt das Rekursions-Prinzip kennen)

Niko Ortner schrieb:

Hm.
Das was ich aus dieser Präsentation lesen konnte ist das:

VB.NET-Quellcode

1. Dim SortiertCount As Integer = Sortiert.Count - 2
2. For i As Integer = 0 To SortiertCount
3. For j As Integer = 0 To SortiertCount
4. If Liste(j) > Liste(j + 1) Then
5. Dim H As Integer = Liste(j)
6. Liste(j) = Sortiert(j + 1)
7. Liste(j + 1) = H
8. End If
9. Next
10. Next

Hat das Problem, dass der innerste Teil (Liste.Count - 2) ^ 2 Mal durchlaufen wird.
Benötigt aber tatsächlich nur 3 * 4 Byte (Die beiden Zählervariablen und die Hilfsvariable).

Ich habe es mit 10000 Integer Werten von Integer.MinValue bis Integer.MaxValue getestet.
Herausgekommen sind immer zwischen 3 und 3.2 Sekunden.
Ob das jetzt viel oder wenig ist kann ich nicht beurteilen, weil ich selten mit sowas arbeite.

Deinen Code könnte man aber noch Optimieren, um ein paar Schleifendurchläufe, wenn man die äußere Schleife rückwärts laufen lässt und die Zählervariable als MaxWert der zweiten schleife nimmt. Denn gegen Ende muss ja nicht mehr geprüft werden ob das eine Item größer dem anderen ist. Da beim ersten Durchlauf das höchste Item bereits ganz hinten ist, muss nur noch bis zum vorletzten Item geprüft werden. Im Code sähe das dann so aus



In wieweit sich das auf Geschwindikeit auswirkt weiß ich allerdings nicht.

ErfinderDesRades schrieb:

wozu?

Falls mal jemand auf die Idee kommt, Bubblesort zu optimieren.
Hintergrundwissen ist immer praktisch.

nikeee13 schrieb:

Falls mal jemand auf die Idee kommt, Bubblesort zu optimieren.

Du meinst also zum Abgewöhnen
Weil die Idee, Bubblesort optimieren zu wollen, ist ziemlich abwegig.

Hintergrundwissen ist immer praktisch.

Im engeren Sinne ist Hintergrundwissen niemals praktisch, denn praktisch anwendbares Wissen täte ich nicht als "Hintergrundwissen" bezeichnen.
Häufig (nicht immer) ists aber aber durchaus nützlich - da machich einen Unterschied.

(sorry - ich bin grad Wortklauberisch drauf - nimms nicht zu ernst ;))

picoflop schrieb:

Welchen anderen Algorithmus mit (praktisch) 0 Speicherverbrauch gibts denn?

Ein korrekt implementierter (gut, da scheitern dann die meisten dran), iterativer MergeSort zum Beispiel. Abgesehen davon kenne ich keine Anwendung, bei der man den Speicherplatzverbrauch einer logarithmischen Rekursion nicht verschmerzen könnte oder in die Nähe der maximalen Rekursionstiefe käme. Dafür kenne ich dann aber genug Anwendungen, bei denen man Milliarden Datenpunkte zu sortieren hat und O(n^2) extrem lange dauert. Wobei man da natürlich auch keinen herkömmlichen Sortieralgorithmus wie MergeSort nehmen würde, aber das ist wieder was anderes...

@Dodo: Das bringt einiges. Die Sortierzeit ist auf 2.1 bis 2.2 Sekunden runtergegangen.

Moment, ich simuliere das mal.
Ich benötige eine Variable für i, eine für j, eine Hilfsvariable und für jeden Arrayeintrag eine Variable (Plus eine Variable zum Zwischenspeichern, weil Hardwaremäßig Arrays nicht unterstützt werden).

Fazit: Wenn der Speicher wirklich begrenzt ist ist Bubblesort hifreich.

irrtum - dann nehmeman Heapsort

ein Heap ist eine sog. Vorrang-Warteschlange.
Also man kann sortierbare Dinge hineinwerfen, und immer den "besten" abrufen (immer nur einen, immer nur den Besten).
Das Sortieren damit ist garnet so interessant, denn da gibts List(Of T).Sort, die sortiert mit IntroSort, und IntroSort schaltet ggfs von QuickSort auf HeapSort um.

Interessant isses als Vorrangwarteschlange, etwa wenn Jobs verschiedener Wichtigkeit abzuarbeiten sind, dass wichtige Jobs sich quasi vordrängeln können.

Oder, eine kleine Erweiterung: "LimitedHeap".
So einer nimmt nur eine begrenzte Anzahl Items auf - wenn du also unter 100000 Daten die 100 besten suchst, ist LimitedHeap dein Froind.

Sollichmal klein Tut machen? - weil die Heap-Struktur ist schwierig zu verstehen, und AFAIK enthält Framework noch keine Heap-Auflistung.

Ich blicke bei HeapSort nicht mehr durch.
Muss man am Anfang das größte Element mit dem ersten vertauschen und dann das erste mit dem letzten?
Kannst Du das bitte kurz erklären?

Oha so viele Antworten, also erstmal zu "Warum willst du den BubbleSort optimieren": Es ist eine aufgabe vom Lehrer, ich selber würde von mir aus Boublesort nicht benutzen.
Da gibt es eig. überall fertige/bessere sortier Algos, wie bereits auch schon hier genannt (Quicksort).

@fraju: "Das ist eine C&P Bremse ;)" Habe aber schon beim 1. mal lesen des Kastens gemerkt, das es so auf keinen Fall funktionieren kann. Und irgendwie fehlte da eine Erklärung zu.

Den MS Webcast hör ich mir später mal an, eventuell versteht man dadruch ja mal wie Quicksort eig. funktioniert.

@Dodo: bzw. @Niko Ortner: Genau so habe ich das in meinem aktuellen JScript stehen (mit einer rückwertslaufenden Schlefe wobei die grenze der Inneren immer kleiner wird).
Doch das soll "angeblich" noch nicht die Lösung sein.

Danke an alle, Gruß Eistee