Video 7-10: Heapsort

0:02 Im nächsten ganz kurzen Abschnitt möchte ich einen einen Vorwärtszeiger geben auf Priority Cues, auf die wir dann noch mal zu sprechen kommen werden gegen Ende der der des Moduls. Ähm, die aber auch verwendet werden können, um einen Sortieralgorithmus zu äh konstruieren, der auch zu diesem äh klassischen bekannten Verfahren gehört. auch einer, der m quasi gegenüber von Quicksord erfunden wurde im Sinne von, dass die beiden Erfinder quasi nebeneinander Büros hatten zu der Zeit in der gleichen Institution.

0:36 Äh, das ist HEBSort. Dazu schauen wir uns den Selection Sort noch mal an. wie Sie sich erinnern, äh war das das allererste Sortierverfahren, das wir uns angeschaut haben und hat überhaupt nicht gut funktioniert im Sinne von der Anzahl Vergleichen, denn äh in jedem Schritt bin ich meine meine komplette Liste noch mal, die übrig war, durchgegangen und habe das Minimum gesucht. Dann habe ich das gefunden und hier hin getauscht und danach habe ich keinen rekursiven Aufruf, war eine Schleife, aber doch äh sozusagen das gleiche Problem noch mal angestoßen auf der eins kleineren Eingabe und habe da wieder das Minimum gesucht. Da die Suche, wenn ich das Minimum einzeln betrachte, muss ich jedes Element anschauen. Da komme ich nicht umhin, linear viele Vergleiche zu spendieren für eine Suche nach dem Minimum. Äh hier war noch mal der Code dazu. Ähm hier jetzt so formuliert, dass es eine Methode gibt, die die Position des Minimums in einem Array findet.

1:44 Also, die ist hier ausformuliert. Am Anfang vom Kapitel hatten wir das in einem großen Code Stück gehabt. Äh ist natürlich leicht rausz refaktorisieren. Wir kriegen ein Array und einen Bereich in dem Array und auch ein Sortierkriterium und suchen entsprechend die Position I. an der ein Vorkommen des Minimums ist. Das können auch können natürlich mehrmals vorkommen. Ähm eins reicht uns. Und dann äh tauschen wir wiederholt das Minimum an den linken Rand. Das war Selection Start, wie wir uns den angeschaut hatten. Und insbesondere in dieser Formulierung ist in Isolation diese Methode, um das Minimum zu finden, bestmöglich. Ich kann das nicht besser machen, wenn ich über eine Liste nichts weiß, als alle Elemente einmal anzugucken. Äh, könnte man auch so eine untere Schranke für beweisen. Angenommen, sie haben einen Algorithmus, der nicht jedes Element betrachtet, dann könnte ich dem eine andere Eingabe unterjubeln, die dieses nicht betrachtete Element entweder zum Minimum oder zum nicht Minimum macht. Und der Algorithmus hat aber dieses Element nicht angeschaut, würde also das gleiche Ergebnis liefern.

2:56 Das kann also nicht in beiden Fällen richtig sein. In Isolation ist diese diese Prozedur also bestmöglich, aber es ist natürlich ziemlich doof in diesem Kontext, weil wir gar nicht ausnutzen, dass wir über die Zeit Wissen gewinnen. Wir vergleichen immer und immer wieder oder suchen immer wieder das Minimum aus dem aus den fast gleichen Elementen wird wir nehmen ein Element heraus, aber doch haben wir viele dieser Vergleiche schon gemacht und daraus schlagen wir gar kein Kapital in Selection Sort. Das ist der Grund, warum Selection S da nicht vom Fleck kommt. Und ähm es gibt eine cleverere Methode, eine Datenstruktur, die binäre HEBS heißt, auf die wir im Grafkapitel mehr eingehen. Ähm, ich war ein bisschen hin und her gerissen, weil sie historisch zum Sortieren gehört, aber inhaltlich dann doch eigentlich eine fortgeschrittenere Datenstruktur ist, als jetzt was wir uns heute noch anschauen. Deswegen lieber als Vorgriff als Blackbox. Da gibt's so eine ähm so einem so eine magische Box, die tolle Eigenschaften hat, ohne dass wir jetzt wissen müssen, wie die aussieht.

4:06 Mal das mal als so ein Geschenk. Äh, okay. Vielleicht hät ich das Bild weglassen können. Was die unterstützt ist, ich kann Elemente einfügen und ich kann das Minimum rausziehen. Das ist natürlich auch nur interessant, wenn das schnell geht, aber äh wir werden sehen, dass beide in groß Ohr von Logend Zeit äh funktionieren. insbesondere das Minimum finden ist da da damit viel viel besser als was wir hier erreichen, wenn wir die einfach die Liste linear durchlaufen.

4:44 Wie gesagt, wenn wir uns im Detail anschauen, was dahinter steckt. Wenn ich diese diese Blackbox habe, dann kann ich die zum Sortieren verwenden und zwar auf genau die Art, wie Selection Sort das auch tun würde. Äh informell, ich stecke alle Elemente rein und hole sie nacheinander raus. Beim Entfernen bekomme ich immer das aktuelle Minimum aus den Elementen, die noch in der Datenstruktur gespeichert sind. Also sind die Elemente in der Reihenfolge, in der ich sie raushole, sortiert. Es gibt dann noch einen cleveren Trick, sodass man hier keinen Zusatzspeicher dafür braucht. Diese Datenstruktur kann zufälligerweise, möchte man fast sagen, das Array verwenden, in dem die Elemente schon drin stehen. Äh, da werden wir noch mal drauf zurückkommen, sozusagen nur als Vorgriff. Ich kann kein Sortierkapitel haben, ohne Hapsort, zumindest erwähnen zu müssen, aber ähm wir haben im Prinzip den spannenden Teil daran jetzt erstmal verlagert auf später.