Suchen und Sortieren auf der linearen Datenstruktur Array🔖

Im Rahmen dieser Einheiten beschäftigen wir uns mit dem Suchen und Sortieren von Objekten. Der Einfachheit halber werden wir uns am Anfang auf das Sortieren von Zahlen beschränken, wobei jedes Objekt sortiert bzw. gesucht werden kann, wenn ein Suchkriterium vorliegt. In unserem Fall arbeiten wir auf der Datenstruktur Array Arrays

UML Diagramm zum Projekt🔖

Das unten stehende UML Diagramm dient als Vorlage. Das dargestellte Diagramm ist ein Implementaionsdiagram, da programmiersprachenspezifische Elemente (hier Java) enthalten sind.

Ein Entwurfsdiagramm ist programmiersprachenunabhängig und kann als Vorlage für unterschiedlichte Programmiersprachen genutzt werden. Da Konstruktoren, get- und set-Methoden pragrammiersprachenspezifisch sind werden diese nicht mit dargestellt.

Entwurfsdiagramm🔖

Implementationsdiagramm🔖

Aufgabe(n) zur Lösung mit edugit🔖

0. Bearbeite die Aufgaben unter "Arbeiten mit BlueJ und edugit".
1. Erstelle eine Arbeitskopie des Projekts. Eine Arbeitskopie kannst du unter https://edugit.org/abitur-2024/01-suchen-und-sortieren-abi-2024.git mit BlueJ auschecken.
2. Kopiere die Vorlagenklasse unter deinem Namen z.B.: Sortieren_Ulf in dasselbe Projekt.
3. Implementiere zuerst die Methoden, die kein Sortier- oder Suchalgorithmus sind. Was die einzelnen Methoden leisten sollen, steht in den Methodenkommentaren!
4. Teste deine Implementationen, indem du die erzeugten Objekte inspiziert. Ist das Array immer den Anforderungen entsprechend gefüllt?
5. Commitet, pusht und aktualisiere deine Implementation.
6. Fertigt mit dem Struktogrameditor der Uni Dresden Struktogramme zu den einfachen Sortieralgorithmen: Bubble-, Insertion- und Selectionsort an und speichere sowohl eine Bilddatei als auch eine .json Datei deines Struktograms.
7. Nutze den Quellcodeexport und teste deine Exporte in deiner Klasse. Sollte etwas nicht funktionieren, verbessere es und passe auch deine Struktogramme dementsprechend an.
8. Commitet, pusht und aktualisiere deine Implementation.
9. Fahre nach demselben Vorgehen (6-8) mit den beiden Suchmethoden (lineare Suche und binäre Suche) fort. Hilfestellungen findest du wieder in den Methodendokumentationen.
10. Fahre nach demselben Vorgehen (6-8) mit den beiden rekursiven Sortiermethoden (Quicksort und Mergesort) fort. Hilfestellungen findest du wieder in den Methodendokumentationen.
11. Beginne zum Beginn einer Stunde mit einer frischen Arbeitskopie deiner Implementation.

Aufgabe(n) zur Lösung mit der online-IDE🔖

1. Implementiere zuerst die Methoden, die kein Sortier- oder Suchalgorithmus sind. Was die einzelnen Methoden leisten sollen, steht in den Methodenkommentaren! Nutze hierfür die Vorlage in der Online-IDE. Hilfestellungen findest du im weiteren Kapitel. Informationen zur Klasse Mathe und den Umgagn mit dieser findest du hier https://www.learnj.de/doku.php?id=api:documentation:math:start und hier https://www.learnj.de/doku.php?id=einstieg:weiteredatentypen:start#die_klasse_math
2. Teste deine Implementationen, indem du die erzeugten Objekte inspiziert. Ist das Array immer den Anforderungen entsprechend gefüllt?
3. Commitet, pusht und aktualisiere deine Implementation.
4. Fertigt mit dem Struktogrameditor der Uni Dresden Struktogramme zu den einfachen Sortieralgorithmen: Bubble-, Insertion- und Selectionsort an und speichere sowohl eine Bilddatei als auch eine .json Datei deines Struktograms.
5. Nutze den Quellcodeexport und teste deine Exporte in deiner Klasse. Sollte etwas nicht funktionieren, verbessere es und passe auch deine Struktogramme dementsprechend an.
6. Commitet, pusht und aktualisiere deine Implementation.
7. Fahre nach demselben Vorgehen (6-8) mit den beiden Suchmethoden (lineare Suche und binäre Suche) fort. Hilfestellungen findest du wieder in den Methodendokumentationen.
8. Fahre nach demselben Vorgehen (6-8) mit den beiden rekursiven Sortiermethoden (Quicksort und Mergesort) fort. Hilfestellungen findest du wieder in den Methodendokumentationen.
9. Beginne zum Beginn einer Stunde mit einer frischen Arbeitskopie deiner Implementation.

Einfache Sortieralgorithmen🔖

Bubblesort und optimierter Bubblesort🔖

Video🔖

Erklärung🔖

Beispiel Anwendung:🔖

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	ges. Zahl
16	78	11	9	0	777	45	109	8	90	11

Struktogramm und Java Quellcode🔖

Insertionsort🔖

Video🔖

Erklärung🔖

Der Insertion Sort ist ein stabiler Sortieralgorhitmus. Übersetzen lässt sich Insertion Sort mit den englischen Wörtern Insertion = Einfügen und Sort = Sortieren, so mit herrscht Sortieren durch Einfügen. Es gibt einen sortierten- und unsortierten Bereich in Insertion Sort. Die erste Zahl (im Array Fach 0) gehört von Anfang an zum sortierten Bereich, daraufhin wird die nächste Zahl im unsortierten Bereich mit den Zahlen im sortierten Bereich verglichen und an die richtige Position gebracht. Dies bedeutet das der Algorhithmus in-place (weiterer Speicherplatz wird außerhalb des Arrays nicht benötigt) arbeitet.

Beispiel Anwendung:🔖

[0]	[1]	[2]	[3]	[4]	[5]
16	78	11	9	0	777
16	78	11	9	0	777
16	78	11	9	0	777
16	11	78	9	0	777
11	16	78	9	0	777
11	16	9	78	0	777
11	9	16	78	0	777
9	11	16	78	0	777
9	11	16	0	78	777
9	11	0	16	78	777
9	0	11	16	78	777
0	9	11	16	78	777
0	9	11	16	78	777

Struktorgramm und Java Quellcode🔖

Selectionsort🔖

Video🔖

Erklärung🔖

Beispiel Anwendung:🔖

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	ges. Zahl
16	78	11	9	0	777	45	109	8	90	11

Struktorgramm und Java Quellcode🔖

Rekursive Sortieralgorithmen🔖

Mergesort🔖

Video🔖

Erklärung🔖

Beispiel Anwendung:🔖

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	ges. Zahl
16	78	11	9	0	777	45	109	8	90	11

Struktorgramm und Java Quellcode🔖

Quicksort🔖

Video🔖

Erklärung🔖

Das Array wird um ein frei zu wählendes Pivotelement sortiert. Anschließend wird dasselbe Prinzip auf die kleineren "Teilarrays" angewand, bis das Problem trivial ist, also nuur noch ein Elemnt sortiert werden muss.

Beispiel Anwendung🔖

Aufruf Gesamtarray🔖

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
16	78	11	0	9	777	45	109	8	90
L				P					R
16	78	11	0	9	777	45	109	8	90
L				P				R
8	78	11	0	9	777	45	109	16	90
	L			P				R
8	78	11	0	9	777	45	109	16	90
	L			P			R
8	78	11	0	9	777	45	109	16	90
	L			P		R
8	78	11	0	9	777	45	109	16	90
	L			P	R
8	78	11	0	9	777	45	109	16	90
	L			P R
8	9	11	0	78	777	45	109	16	90
	L P			R
8	9	11	0	78	777	45	109	16	90
	L P		R
8	0	11	9	78	777	45	109	16	90
	L		P R
8	0	11	9	78	777	45	109	16	90
		L	P R
8	0	9	11	78	777	45	109	16	90
		L P	R
8	0	9	11	78	777	45	109	16	90
		L P

Teilung und rekursiver Aufruf🔖

[0]	[1]		[2]		[3]	[4]	[5]	[6]	[7]	[8]	[9]
8	0		9		11	78	777	45	109	16	90
L	P R

Tauschen🔖

[0]	[1]		[2]		[3]	[4]	[5]	[6]	[7]	[8]	[9]
0	8		9		11	78	777	45	109	16	90
L P	R
0	8		9		11	78	777	45	109	16	90
L P R

Teilung🔖

[0]		[1]		[2]		[3]	[4]	[5]	[6]	[7]	[8]	[9]
0		8		9		11	78	777	45	109	16	90
L P R

Rekursiver Aufruf🔖

[0]		[1]		[2]		[3]	[4]	[5]	[6]	[7]	[8]	[9]
0		8		9		11	78	777	45	109	16	90
						L			P			R
0		8		9		11	78	777	45	109	16	90
							L		P			R
0		8		9		11	78	777	45	109	16	90
							L		P		R
0		8		9		11	16	777	45	109	78	90
							L		P		R
0		8		9		11	16	777	45	109	78	90
								L	P		R
0		8		9		11	16	777	45	109	78	90
								L	P	R
0		8		9		11	16	777	45	109	78	90
								L	P R
0		8		9		11	16	45	777	109	78	90
								L P	R

Teilung und rekursiver Aufruf🔖

[0]		[1]		[2]		[3]	[4]		[5]	[6]	[7]	[8]	[9]
0		8		9		11	16		45	777	109	78	90
						L	P R
0		8		9		11	16		45	777	109	78	90
						L P R

Teilung🔖

[0]		[1]		[2]		[3]		[4]		[5]	[6]	[7]	[8]	[9]
0		8		9		11		16		45	777	109	78	90
						L P R

Rekursiver Aufruf🔖

[0]		[1]		[2]		[3]		[4]		[5]	[6]	[7]	[8]	[9]
0		8		9		11		16		45	777	109	78	90
										L		P		R

[0]		[1]		[2]		[3]		[4]		[5]	[6]	[7]	[8]	[9]
0		8		9		11		16		45	777	109	78	90
											L	P		R
0		8		9		11		16		45	777	109	78	90
											L	P	R
0		8		9		11		16		45	777	109	78	90
											L	P R
0		8		9		11		16		45	109	777	78	90
											L P	R
0		8		9		11		16		45	109	777	78	90
											L P R

Teilung und rekursiver Aufruf🔖

[0]		[1]		[2]		[3]		[4]		[5]		[6]		[7]	[8]	[9]
0		8		9		11		16		45		109		777	78	90
												L P R
0		8		9		11		16		45		109		777	78	90
														L	P	R
0		8		9		11		16		45		109		777	78	90
														L	P R
0		8		9		11		16		45		109		78	777	90
														L P	R
0		8		9		11		16		45		109		78	777	90
														L P R

Teilung und rekursiver Aufruf🔖

[0]		[1]		[2]		[3]		[4]		[5]		[6]		[7]		[8]	[9]
0		8		9		11		16		45		109		78		777	90
																L	P R
0		8		9		11		16		45		109		78		90	777
																L P	R
0		8		9		11		16		45		109		78		90	777
																L P R

Fertig🔖

[0]		[1]		[2]		[3]		[4]		[5]		[6]		[7]		[8]		[9]
0		8		9		11		16		45		109		78		90		777
																		L P R

Legende:

Links: L

Pivot: P

Rechts: R

Struktorgramm und Java Quellcode🔖

Aufwandsabschätzung🔖

https://cryptpad.fr/sheet/#/2/sheet/view/xH9bfbaoI0-4Vb9TtHEUxhpMWZ-P63gabh4H6ZmrGy0/