Grundgebiete der Informatik 1 | RWTH | Bubble Sort
UniCourse Global
https://www.youtube.com/watch?v=ZcOWGEwInj4

Transkript (automatisch erstellt)

0:00 Dieses Video soll noch mal der Funktion gelten, euch Bubble Sort noch mal näher zu bringen und zu erklären. Noch mal ein kleine kleine Refresher. Und was euch da
0:11 natürlich in der Klausur begegnen kann, ist wie immer, wie sieht das Array nach dem weiß ich nicht vierten, fünften Schritt Bubblesort aus. Ähm Schritt ist
0:21 da natürlich dann müssen müssen gucken, wie sie das jetzt definieren, äh nach welcher Aktion die dann wirklich das Array haben wollen. Meistens äh wenn die
0:31 weiß ich nicht xte Bubble runtergekommen ist. Bubbles funktioniert ja so, dass wir hier ganz am Array Ende uns diese kleine Bubble nehmen und diese Bubble
0:41 geht dann einfach nach links ins Array runter und auf dem Weg vertauschen wir Elemente, die vertauscht werden sollen. Gut, bei dieser Bubble sehen wir jetzt
0:51 hier beim ersten Schritt, okay, die sind eigentlich schon auf der richtigen Seite voneinander. Drei ist links von der fünf und das soll auch so gut, dann babbelt
0:59 die Bubble weiter runter. 4 und 3. Ja, da sehen wir sofort, die müssten eigentlich vertauscht werden. Also schreiben wir hier hin. So, okay, die
1:11 Bubble wandert weiter und die müssen natürlich dann auch vertauscht werden. Zack, 3 4 5 Ich werde jetzt gleich nicht mehr
1:22 das da hinten mitschreiben, weil da dann ja aber eh nichts mehr passiert. Gut, Babble wegt sich weiter. 3 und 9. Es bubbelt weiter nach unten. Die müssen
1:33 natürlich auch getauscht werden, weil die neun größer ist als die drei. 2 3 9 6. Na, ich wollte es ja nicht mehr mitschreiben. Na, jetzt habe ich es do
1:42 noch einmal gemacht. Gut. Und unsere Bubble bewegt sich weiter. Die müssen natürlich auch getauscht werden. Sie nee, die müssen nicht
1:49 getauscht werden. Ich bin ja verrückt. Die stehen ja schon auf der richtigen Seite. Okay, also hier nichts tauschen. Zwei und sieben müssen aber getauscht
1:59 werden, wenn die Bubble dann nach ganz unten kommt. So, und dann haben wir hier 2 7 3 9 6 4 5 stehen. Da ist die erste Bubble runtergekommen.
2:09 Ja, ist also ganz links am Rand angekommen und die zwei ist jetzt fertig sortiert. Das könnte dann z.B. so wie die es wollen ein Schritt im Bubblesort
2:18 Algorithmus sein. Und so sieht das Radern danach aus. Gut, wenn wir jetzt hier weitermachen würden, würden wir wieder unsere Bubble nehmen und von
2:26 rechts nach links durchbubbeln, ne? Bzw. dann nur noch bis zu diesem Punkt hier, weil wir wissen ja von der zwei, dass die schon sortiert ist. 4 und F. Sie
2:34 scheinen auf der richtigen Seite voneinander zu sein. Alles gut. Dann kommt die vier und die 6. Die müssen allerdings vertauscht werden. Also 7 3 9
2:45 und die 4 und die 6 werden vertauscht. Gut, dann die 9 und die 4, die vertauschen wir auch. Alles klar. Die drei und die vier, die
2:57 sind schon auf der richtigen Seite voneinander. Nur die drei und die sieben, die sollten wir auch noch mal tauschen. So, und dann ist die drei hier
3:06 auch fertig sortiert. Ich werde hier noch mal das ganze Array hinschreiben. So. Und das könnte jetzt natürlich, ne, schon ganz gut das Ende sein. Da der
3:15 Bubblesund Algorithmus eigentlich auch relativ einfach ist, werden sie euch dafür nicht allzu viele Punkte geben. Sollte dann natürlich auch nicht allzu
3:21 viel Zeit in Anspruch nehmen. Deswegen ist es relativ realistisch, dass sie nach dem ersten oder zweiten runterbubabbeln, dann sagen: "Okay, dann
3:28 schreifen uns das Array noch mal hin, wie es jetzt aussieht." Damit ihr es verstanden habt, damit sie das prüfen können. Wir sortieren jetzt aber doch
3:34 noch mal einmal zum Ende. Einfach aus Prinzip. Und da machen wir natürlich hier am rechten Rand wieder unsere Bubble. Da
3:41 sehen wir sofort die Fünf und die sechs, die müssen getauscht werden. Also 4 9 5 6 die 5 und die 9 genauso.
3:54 Und die fün und die 4 da ist alles okay. Nur bei der 4 und der 7 müsste noch getauscht werden. Da sind wir dann auch wieder unten am Ende angekommen. Alles
4:05 klar. Und wir beginnen wieder von vorne, lassen es ein bisschen runterbubbeln. Aha,
4:15 okay. Bubble zieht weiter. Hier ist alles in Ordnung. Also tauschen wir hier nur noch unten 5 und 7 6 9. Die fünf ist sortiert. Unsere Bubble wird wieder von
4:28 rechts nach links. Hier ist alles in Ordnung, aber bei 6 und 7 da noch nicht. Also 6 7 9 und wir sehen jetzt natürlich schon ist alles gut. Hier ist alles
4:40 richtig. Der so Algorithmus muss hier aber am Ende auch noch einmal prüfen. Sind die wirklich in der richtigen Reihenfolge? Kann er ja nicht wissen.
4:48 Aber der sieht dann auch relativ schnell. Wenn er diese Bubble hier sieht, okay, alles richtig, dann wisst weiß er, dass die sieben hier auch am
4:54 richtigen Ort ist und dadurch natürlich auch automatisch die Numero 9. Dann können wir hier natürlich den Rest des Arrays auch noch hinschreiben. Na, was
5:03 haben wir da noch drin? Ah, da vorne war tatsächlich die zwei das kleinste. Okay, d mache ich noch mal Kästchen drum und dann sind wir fertig.