Algorithmen und Datenstrukturen #18 - Bubble Sort in Python

Algorithmen machen unsere digitale Welt. In dieser Serie erfahrt ihr, wie die Dinger eigentlich funktionieren.

Nicht vergessen: Liken, Abo und ein Kommentar helfen diesem Video sehr =)

Algorithmen machen unsere digitale Welt. In dieser Serie erfahrt ihr, wie die Dinger eigentlich funktionieren.

Nicht vergessen: Liken, Abo und ein Kommentar helfen diesem Video sehr =)

_Discord:_

_Unterstützt mich - Danke!:_

[paddicxhd]

Unser Dozent hat das viel inkompetenter und komplizierter erklärt und gemacht. Danke für die gute Erklärung.

[lars]

BubbleSort ist der erste Sortieralgorithmus, den ich kennengelernt hatte. Elegant ist er nicht, aber ich finde, er ist sehr einfach zu merken und sehr leicht zu implementieren. Das macht ihn z.B. an Stellen nützlich, wo keine guten Sortieralgorithmen vorgegeben sind, und man mal eben einen einfachen Algorithmus ohne viel Aufwand implementieren will.

[ParalyticAngel]

Habe das Fach gerade an der Uni und schaue mir Deine Videoreihe durch. Gut gemacht. Deine Beispiele sind sehr hilfreich und einige sehr wichtige Sätze zum Verständnis haust Du raus.
Aber zu diesem Video muss ich was sagen.^^ 😎 Auch für mich ist es irritierend das manche Sort-Algorithmen zwar die gleiche O(n²) Komplexität haben, aber in der Realität trotzdem Unterschiede aufweisen. Auch ich habe Zeiten in Millisekunden (ja sogar Pikosekunden) gemessen um jegliche Unterschiede herauszukristallisieren. Auch weil ich mich selbst an einen Algorithmus versucht habe neu zu entwickeln und demnach unbedingt ganz genau wissen wollte, welche der bekannten Algorithmen ich schlagen kann.^^
Daher meine so Pikosekunden genaue Messungen.^^ An sich ist mein Algorithmus sehr wohl durchdacht doch den Java Sortieralgorithmus schlägt niemand. 🤣
Irgendwann passe ich meinen Algorithmus noch an, aber das ist nicht das Thema. Sondern warum O(n²) tatsächlich = O(n²) ist.

Mit der Landau-Notation hebelt man ALLES was Unterschiede machen würde praktisch komplett aus. Oder besser gesagt, wir sind nur daran interessiert wie schnell der Algorithmus an sich ist und nicht wie beispielsweise auf Assembler-Ebene noch optimiert werden könnte bzw. mit einer erhöhten CPU-Taktrate man schneller durch diesen Algorithmus kommen könnte.
Beim Bubblesort, mit dem nicht mehr "anfassen" der letzteren Glieder, macht man tatsächlich einen Unterschied an der Zeit her, welches nicht auf die CPU oder auf gewisse Assembler-Optimierungen zurückzuführen ist. Doch auch diese darf man mit der Landau-Notation gepflegt umgehen. Zwar gehört das Weglassen zum Algorithmus dazu, doch bis zum Weglassen hat man definitiv O(n²).
Sprich, es gibt sehr viele Quellen die zu unterschiedlich schnellen Durchlaufzeiten führen können; und genau das ist der Grund der O-Notation, damit man diese feinen und dem Algorithmus gegenüber irrelevanten Unterschiede gepflegt raus lassen kann. Daher ist ein O(n²) Sort-Algorithmus gleich eines anderen O(n²) Sort-Algorithmusses. Das tatsächlich schneller gemessene ist nicht vom Algorithmus her schneller, sondern von Implementierungs- bis hin zu Assembler-Optimierung, CPU-Taktrate, Cache-Version, ja sogar vom Betriebssystem und von der benutzen Programmiersprache her abhängig und darauf geschuldet.^^

Sorry für die Länge, aber das ist mir zu Deinen Worten zum Ende hin aufgefallen und wollte es mal hier schreiben.
Trotzdem, Danke für Deine Videos und weiter so.^^

[Twntyyyy]

8:08 Nicht auszudenken was passieren würde wenn man's sogar mit 100.000 probiert :^)

[dennisjanvogt]

Hallo :)

Könntest du mir bitte sagen, ob:

def bubble_sort2(unsorted_list):
list_sorted = False
j = 1
while list_sorted == False:
list_sorted = True
for i in range(len(unsorted_list)-1):
if unsorted_list[i+1] < unsorted_list[i]:
unsorted_list[i+1], unsorted_list[i] = unsorted_list[i], unsorted_list[i+1]
list_sorted = False
j += 1
return unsorted_list

effizienter wäre? Weil ich ja sozusagen, da schon schneller rauskäme aus dem Algo, wenn die Sortierung bereits nach der Hälfte des For-Loops besteht ^^

[sumsumcity]

Hei morheus. Ich habe eine Frage zu meinen Wahlfähcher im nächsten Studienjahr. Ich interessiere mich sehr für KI und welche Auswirkung dies auf die Wirtschaft noch haben wird. Wenn ich mehr darüber lernen möchte, sollte ich dann mehr in die Richtung Data Science oder Software Systems gehen? Ich kann mir bis jetzt noch nicht so gut vorstellen was Data Scientist eigentlich machen

[ansgar]

In Java war bei der Sortierung eines Int Arrays mit Länge 10000 bei mir mit Selection Sort fast 40% schneller als Bubble Sort. Weiß einer warum?