Algorithmus

Ein Algorithmus is eine Abfolge von Befehlen die eine spezielle Aufgabe lösen soll und mithilfe von Code darstellbar ist. Dabei ist wichtig:

• Möglichst wenig Ressourcen zu benötigen

• Gleiche Eingabedaten führen bei einem Algorithmus stets zu gleichen Ergebissen

die big -O Notation ist ein mathematisches Hilfsmittel um die Laufzeitkomplexität eines Algorithmus zu beschreiben. Im Wesentlichen hängt die Laufzeit eines Algorithmus von dessen Eingabedaten ab (z.B. Liste an Daten bei einem Suchalgorithmus). Die O Notation gibt an wie sich die Laufzeit eines algorithmus verändert wenn die Menge an Eingabedaten sich ändern.

Grundsätzlich unterscheidet man.

O(1): Bedeutet die Laufzeit ist immer gleich unabhängig von den Eingabedaten

0(N): Die Laufzeit ist proportional zu den Eingabedaten

O(log(N)): Ein logarithmisches Verhältnis

O(N^2): ein quadratisches Verhältnis

Ausgehend davon dass er jeden Wert überprüfen muss und somit alle indizes des Arrays durchforsten muss ist es O(N) weil im schlimmsten Fall liegt der gesuchte Wert am letzten Index des Arrays.

Eine "Linked List" und ein "Array" sind zwei grundlegende Datenstrukturen, die in der Programmierung verwendet werden. Hier sind die wichtigsten Unterschiede zwischen den beiden:

1. Speicherstruktur:

   • Linked List: Eine Linked List besteht aus Knoten, die miteinander verknüpft sind. Jeder Knoten enthält Daten und einen Verweis auf den nächsten Knoten.

   • Array: Ein Array ist eine geordnete Sammlung von Elementen, die unter einem einzigen Namen gespeichert sind und über einen Index zugänglich sind.

2. Zugriff auf Elemente:

   • Linked List: Der Zugriff auf Elemente in einer Linked List erfolgt sequenziell, beginnend beim ersten Knoten und durch Traversieren der Liste bis zum gewünschten Element.

   • Array: Der Zugriff auf Elemente in einem Array erfolgt direkt über den Index, was bedeutet, dass das Element an einer bestimmten Position sofort abgerufen werden kann.

3. Einfügen und Löschen:

   • Linked List: Einfügen und Löschen von Elementen in einer Linked List kann effizient sein, da es nur notwendig ist, die Verknüpfungen zwischen den Knoten anzupassen.

   • Array: Das Einfügen und Löschen von Elementen in einem Array kann ineffizient sein, insbesondere wenn es in der Mitte des Arrays geschieht, da alle nachfolgenden Elemente verschoben werden müssen.

4. Größe und Flexibilität:

   • Linked List: Die Größe einer Linked List kann dynamisch wachsen oder schrumpfen, da sie Elemente hinzufügen oder entfernen kann, ohne den Speicherplatz zu verändern.

   • Array: Die Größe eines Arrays ist in der Regel festgelegt und muss im Voraus festgelegt werden. Es ist schwieriger, die Größe zu ändern.

5. Speicherplatzanforderungen:

   • Linked List: Linked Lists benötigen zusätzlichen Speicherplatz für die Verknüpfungen zwischen den Knoten.

   • Array: Arrays benötigen weniger Speicherplatz, da sie nur den Speicherplatz für die Daten selbst benötigen.

6. Zugriffszeit:

   • Linked List: Der Zugriff auf ein bestimmtes Element in einer Linked List kann länger dauern, da er sequenziell durchlaufen werden muss.

   • Array: Der Zugriff auf ein bestimmtes Element in einem Array ist schnell, da es direkt über den Index abgerufen werden kann.

7. Verwendungszweck:

   • Linked List: Linked Lists sind besonders nützlich, wenn häufig Einfüge- und Löschoperationen durchgeführt werden müssen, da sie in solchen Szenarien effizienter sein können.

   • Array: Arrays sind gut geeignet, wenn schneller, direkter Zugriff auf die Elemente erforderlich ist und die Größe im Voraus bekannt ist.

Die Wahl zwischen einer Linked List und einem Array hängt von den spezifischen Anforderungen des Problems ab. Beide haben ihre Vor- und Nachteile und sind für unterschiedliche Anwendungsfälle geeignet.

Ein Stack funktioniert nach dem LIFO-Prinzip (Last in, First Out), was bedeutet, dass das zuletzt hinzugefügte Element als erstes wieder entfernt wird. Es gibt drei grundlegende Operationen, die auf einem Stack ausgeführt werden können:

1. top: Diese Operation gibt den Wert zurück, der zuletzt auf den Stack gelegt wurde, ohne ihn tatsächlich zu entfernen.

2. pop: Diese Operation entfernt das zuletzt gespeicherte Element vom Stack.

3. push: Diese Operation fügt ein neues Element oben auf den Stack hinzu.

Diese Operationen sind grundlegend für die Verwaltung von Daten auf einem Stack und werden in vielen Programmiersprachen und Algorithmen verwendet.

Eine Queue ist ein Pufferspeicher der nach dem FIFO Prinzip (First in First out) funktioniert demnach werden Elemente die zuerst in die Queue gelegt wurden auch zuerst wieder aus der Queue genommen.

peep(): gibt das element zurück das als erstes in die Queue gelegt wurde bzw am Ende der Queue liegt

enqueue(): legt ein neues Element am Anfang der Queue ein

dequeue(): löscht das element ganzen hinten in der Queue

Kann als auch als Ringspeicher konzipiert werden sodass bei einem Overflow an Elementen wieder vorne Angefangen wird

Eine rekursive Funktion ist eine Funktion, die sich selbst aufruft, entweder direkt oder indirekt über eine oder mehrere Zwischenfunktionen. Dabei wird das Problem in kleinere, leichter zu lösende Teile aufgeteilt, bis eine Basisfall erreicht ist, für den eine direkte Lösung bekannt ist.

Eine rekursive Funktion besteht typischerweise aus zwei Teilen:

1. Basisfall: Dies ist der Punkt, an dem die Funktion keinen rekursiven Aufruf mehr benötigt. Die Lösung wird direkt zurückgegeben. Ohne einen Basisfall würde die rekursive Funktion in einer endlosen Schleife enden.

2. Rekursiver Fall: Dieser Teil der Funktion ruft sich selbst mit einem modifizierten oder verkleinerten Problem auf. Dadurch wird das Problem nach und nach in Richtung des Basisfalls reduziert.

Ein binärer Baum ist eine Datenstruktur, die aus Knoten besteht, wobei jeder Knoten höchstens zwei Kinder haben kann: einen linken und einen rechten Knoten.

Struktur eines binären Baums:

• Wurzel: Der oberste Knoten des Baums, von dem alle anderen Knoten abzweigen.

• Knoten: Jeder Knoten im Baum hat einen Wert und kann höchstens zwei Kinder haben.

• Blätter: Die Endknoten des Baums, die keine Kinder haben.

Übergänge (Traversals) in einem binären Baum:

1. In-Order Traversal (Symmetrischer Durchlauf):

   • Links, Wurzel, Rechts (LWR)

   • Der In-Order Traversal besucht zuerst den linken Teilbaum, dann die Wurzel und schließlich den rechten Teilbaum. Das Ergebnis ist eine sortierte Liste, wenn der Baum ein Suchbaum ist.

2. Pre-Order Traversal (Vorwärtsdurchlauf):

   • Wurzel, Links, Rechts (WLR)

   • Der Pre-Order Traversal beginnt mit der Wurzel, dann geht es zum linken Teilbaum und schließlich zum rechten Teilbaum.

3. Post-Order Traversal (Rückwärtsdurchlauf):

   • Links, Rechts, Wurzel (LRW)

   • Der Post-Order Traversal besucht zuerst den linken Teilbaum, dann den rechten Teilbaum und zuletzt die Wurzel.

4. Level-Order Traversal (Breitendurchlauf):

   • Beginnt bei der Wurzel und arbeitet sich schichtweise von oben nach unten vor. Zuerst werden alle Knoten auf Ebene 1 besucht, dann auf Ebene 2 und so weiter.

Diese Traversals bieten verschiedene Wege, um die Knoten eines binären Baums zu durchlaufen und auf die darin enthaltenen Daten zuzugreifen. Je nach Anwendungsfall können unterschiedliche Traversals nützlich sein.

Beim einem linearen Suchalgorithmus werden die Elemente eines Arrays, beginnent mit Index 0, der Reihe nach mit einem gesuchten Element verglichen. Also vereinfacht ausgedrückt man vergleicht Index 0 mit dem gesuchten Wert ist es nicht der richtige geht man weiter zu index 1 usw. bis das gesuchte Element gefunden wird. Man bekommt dann den Index des gesuchten Elements wenn es im Array gefunden wurde. Dabei müssen im schlimmsten Fall alle Elemente durchsucht werden was dazu führt das die Laufzeitkomplexität O(N) ist, also die Zeit die zum finden eines Elements gebraucht wird proportional zur Menge der Daten ist.

Die Menge der zu durchsuchenden Elemente wird in jedem Schritt halbiert

Bei einem Binären Suchalgorithmus muss eine sortierte Liste (array) als ausgangspunkt vorliegen. Dabei wird so vorgegangen dass zuerst dass mittlere Element eines Arrays mit dem gesuchten Wert verglichen wird. Entspricht der gesuchte Wert dem mittleren Element ist die Suche vorbei. Wenn nicht dann wird überprüft ob der gesuchte Wert in der linken oder rechten Hälfte liegt (bei Zahlen z.B. durch einen größer oder kleiner Vergleich). Sollte das Element in der linken Hälfte zu finden sein wird wieder das mittlere Element der linken Hälfte gewählt und der Prozess beginnt von neuem. Das geht so lange weiter bis das Element gefunden wurde oder keine Elemente mehr zum Vergleich vorhanden sind. Die Laufzeitkomplexität ist O(log(N))

Ein binärer Suchbaum ist eine Baumstruktur, in der jeder Knoten höchstens zwei Kinder hat. Die Werte in den linken Teilbäumen sind kleiner oder gleich dem Wert des Elternknotens, und die Werte in den rechten Teilbäumen sind größer als der Wert des Elternknotens. Dies ermöglicht effiziente Suchoperationen in logarithmischer Zeit. Deine Beschreibung des Ablaufs, wie man in einem binären Suchbaum nach einem Element sucht, ist ebenfalls zutreffend. Man beginnt am Root-Knoten und navigiert je nach Vergleich der Werte zu den entsprechenden Kindknoten, bis man das gesuchte Element findet oder feststellt, dass es nicht im Baum vorhanden ist.

1. Internal Sorting (internes Sortieren): Dies bezieht sich auf das Sortieren von Daten, die komplett im Hauptspeicher (RAM) des Computers passen. Alle zu sortierenden Elemente werden im RAM gehalten, was die Sortierung effizienter macht, da der Zugriff auf den Hauptspeicher viel schneller ist als auf externe Speichermedien wie Festplatten.

2. External Sorting (externes Sortieren): Dies bezieht sich auf das Sortieren von Daten, die zu groß sind, um vollständig im Hauptspeicher gehalten zu werden. In solchen Fällen müssen Daten in kleinere Teile aufgeteilt und auf die Festplatte ausgelagert werden, um sie zu sortieren. Dies erfordert zusätzliche Schritte, da Daten zwischen RAM und Festplatte verschoben werden müssen.

3. In-Place Sorting (Sortieren auf der Stelle): Bei einem In-Place-Sortieralgorithmus wird kein zusätzlicher Speicher benötigt, um die Sortierung durchzuführen. Der Algorithmus arbeitet direkt auf den vorhandenen Daten, indem er Elemente im Speicher umordnet, um die gewünschte Reihenfolge zu erreichen.

4. Stable Sorting Method (Stabiler Sortieralgorithmus): Ein stabiler Sortieralgorithmus ist einer, der die relative Reihenfolge von Elementen beibehält, die den gleichen Schlüsselwert haben. Das bedeutet, wenn zwei Elemente den gleichen Schlüssel haben, werden sie nach der Sortierung in der gleichen Reihenfolge bleiben, wie sie vorher waren. Stabile Sortieralgorithmen sind wichtig, wenn es auf die Erhaltung von Reihenfolgen ankommt, z.B. wenn Daten bereits teilweise sortiert sind und die relative Position der Elemente beibehalten werden soll.

Im Kontext von Sortieralgorithmen ist der "Schlüssel" der Wert, der verwendet wird, um die Elemente zu vergleichen und zu sortieren.

Wenn wir zum Beispiel eine Liste von Studenten haben und wir sie nach ihren Noten sortieren möchten, dann ist die Note der Schlüssel. Jeder Student hat eine Note, die als Schlüssel für die Sortierung verwendet wird.

In einem stabilen Sortieralgorithmus wird sichergestellt, dass, wenn zwei oder mehr Elemente den gleichen Schlüsselwert haben, ihre ursprüngliche Reihenfolge beibehalten wird. Das bedeutet, wenn zwei Studenten die gleiche Note haben, werden sie nach der Sortierung in der gleichen Reihenfolge bleiben, wie sie zuvor waren. Das ist besonders wichtig, wenn es zusätzliche Informationen gibt, die die Sortierreihenfolge beeinflussen könnten.

Zum Beispiel, wenn zwei Studenten die gleiche Note haben, aber unterschiedliche Geburtsdaten, könnten wir wollen, dass der stabil sortierte Algorithmus die Reihenfolge basierend auf den Geburtsdaten beibehält.

der Bubble Sort vergleicht immer zwei benachbarte Elemente miteinader. Ist das linke Element größer als das rechte werden sie vertauscht andernfalls bleibt die Reihenfolge erhalten. Dieser Vorgang wird so lange wiederholt bis der Sortieralgorithmus einemal komplet über alle Elemente gefahren ist und keine Vertauschung stattgefunden hat. In einem Array werden zuerst Index 0 und 1 verglichen, dann Index 1 und 2 dann Index 2 und 3 usw.

Er ist ein einfach zu implementierender Suchalgorithmus allerdings nicht schnell/effizent

1. Gehe die Liste durch und finde das kleinste Element.

2. Tausche dieses kleinste Element mit dem ersten Element in der Liste.

3. Betrachte den Rest der Liste (ab dem zweiten Element) als den noch zu sortierenden Teil.

4. Wiederhole die Schritte 1-3 für den verbleibenden unsortierten Teil, indem du das kleinste Element im verbleibenden Teil findest und es mit dem ersten Element dieses Teils tauschst.

5. Fahre so fort, bis die gesamte Liste sortiert ist.

Hier ist eine beispielhafte Durchführung von Selection Sort für eine Liste von Zahlen:

Unsortierte Liste: [5, 2, 9, 3, 7]

1. Das kleinste Element ist 2. Tausche es mit dem ersten Element: [2, 5, 9, 3, 7]

2. Betrachte den Rest der Liste (5, 9, 3, 7) und finde das kleinste Element 3. Tausche es mit dem zweiten Element: [2, 3, 9, 5, 7]

3. Betrachte den Rest der Liste (9, 5, 7) und finde das kleinste Element 5. Tausche es mit dem dritten Element: [2, 3, 5, 9, 7]

4. Betrachte den Rest der Liste (9, 7) und finde das kleinste Element 7. Tausche es mit dem vierten Element: [2, 3, 5, 7, 9]

Die Liste ist nun vollständig sortie

es ist nicht stabil weil Beispiel [2a,2b,1] im ersten Schritt wird der 1. 2 mit 1 getauscht man erhält [1,2b,2a]

1. Der Algorithmus beginnt mit dem zweiten Element in der Liste (Index 1), da das erste Element angenommen wird, bereits sortiert zu sein.

2. Das aktuelle Element wird mit dem vorherigen Element verglichen.

3. Wenn das aktuelle Element kleiner ist als das vorherige Element, tauschen sie ihre Positionen, bis die richtige Position für das aktuelle Element gefunden ist.

4. Schritt 3 wird für alle vorherigen Elemente wiederholt, bis das aktuelle Element an der richtigen Stelle einsortiert ist.

5. Der Algorithmus geht dann zum nächsten Element und wiederholt die Schritte 2 bis 4.

Der Insertion Sort Algorithmus arbeitet, indem er das betrachtete Element in den bereits sortierten Teil der Liste "einfügt". Es ist, als würde man Karten in einer Hand sortieren, indem man eine Karte nach der anderen nimmt und sie an die richtige Stelle im bereits sortierten Teil einfügt.

Der Merge Sort funktioniert nach dem Prinzip Teile und Herrsche. Ein Array von Elementen wird so lange halbiert bis die Elemente paarweise in einem Array vorliegen. Dieses Element päärchen wird dann sortiert (durch größer kleiner Vergleich). Nachem die Paare sortiert sind werden die Einzelnen Paare wie bei einer Baumstruktur zusammengefügt. Zuerst werden die Paare so miteinander verglichen dass sich ein sortiertes 4er Paar bildet. Aus zwei sortierten 4 Paaren wird ein sortiertes 8 Paar dass geht solange weiter bis alle Elemente in einem einzigen sortierten Array sind.

Als erstes wird ein Pivot Element aus dem Array ausgewählt. Das kann jedes Element sein, meist wird das mittlere Element im Array genommen. Das Pivot Element wird in die mitte des arrays verschoben falls es nicht bereits in der mitte ist und teilt das array in zwei Hälften. Die Elemente der linken Hälfte und rechten Helfte werden so verschoben dass links von Pivot Element nur kleinere Werte als das Pivot Element liegen und rechts nur größere wobei hier die Reihenfolge noch nicht verändert wird. Anschließend werden aus der linken und rechten Hälfte wieder ein Pivot Elment gewählt. Die Elemente links und rechts werden dann wieder so sortiert dass kleinere Werte links vom Pivot stehen und größere rechts vom Pivot. Dieser Vorgang hält so lange an bis die Elemente nicht mehr weiter geteilt werden können bzw. die Elemente sortiert sind.