Programming lesson
Sortier- und Datenstruktur-Algorithmen in Java: Ein Leitfaden für CSCI 251 Projekte
Lernen Sie Schritt für Schritt, wie Sie Insert Sort, Select Sort, Quick Sort, Merge Sort, Stack, Queue, HashTable, Binary Search Tree und Graph-Algorithmen in Java implementieren – genau wie in den CSCI 251 Projekten gefordert.
Einführung in die Sortier- und Datenstruktur-Algorithmen für CSCI 251
In den Projekten von CSCI 251 geht es darum, fundamentale Algorithmen und Datenstrukturen in Java zu implementieren. Von Sortierverfahren über Stacks und Queues bis hin zu Hashtabellen, Binärbäumen und Graphen – dieses Tutorial führt Sie durch die Kernkonzepte. Die Algorithmen sind nicht nur für Ihre Projekte wichtig, sondern auch für technische Vorstellungsgespräche bei Unternehmen wie Google oder Amazon, die oft nach Sortieralgorithmen Java und Datenstrukturen Implementierung fragen.
Projekt 1: Sortieralgorithmen – Insert, Select, Quick und Merge Sort
Im ersten Projekt implementieren Sie vier klassische Sortierverfahren. Diese Algorithmen sind die Grundlage für effiziente Datenverarbeitung – ähnlich wie ein Ranking-Algorithmus in einer Gaming-App wie League of Legends Spieler nach Rang sortiert.
Insert Sort (Einfügungssortierung)
Insert Sort funktioniert wie das Sortieren von Spielkarten: Sie nehmen ein Element nach dem anderen und fügen es an der richtigen Position in den bereits sortierten Teil ein. Die Methode insertSort erwartet ein int-Array und sortiert es in-place.
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}Dieser Code ist ideal, um Insert Sort Java zu verstehen. Die Laufzeit ist O(n²) im schlechtesten Fall, aber für kleine oder fast sortierte Arrays sehr effizient.
Select Sort (Auswahlsortierung)
Select Sort sucht bei jedem Durchlauf das kleinste Element und tauscht es an die aktuelle Position. Es ist einfach, aber nicht stabil.
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
int temp = arr[minIdx];
arr[minIdx] = arr[i];
arr[i] = temp;
}
}Beide Verfahren sind einfache Sortieralgorithmen, die Sie für Ihre CSCI 251 Projekt 1 Lösung benötigen.
Quick Sort (Schnellsortierung)
Quick Sort ist ein rekursiver Algorithmus, der nach dem Teile-und-Herrsche-Prinzip arbeitet. Ein Pivot-Element wird gewählt, und das Array wird in zwei Teile geteilt: links kleinere, rechts größere Elemente. Dann werden die Teile rekursiv sortiert.
private static int pivot(int[] arr, int begin, int end) {
int pivot = arr[begin];
int i = begin + 1;
int j = end;
while (i <= j) {
while (i <= j && arr[i] < pivot) i++;
while (i <= j && arr[j] > pivot) j--;
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
arr[begin] = arr[j];
arr[j] = pivot;
return j;
}
private static void quickSortRecursive(int[] arr, int begin, int end) {
if (begin < end) {
int pivotIndex = pivot(arr, begin, end);
quickSortRecursive(arr, begin, pivotIndex - 1);
quickSortRecursive(arr, pivotIndex + 1, end);
}
}
public static void quickSort(int[] arr) {
quickSortRecursive(arr, 0, arr.length - 1);
}Quick Sort ist im Durchschnitt O(n log n) und wird oft in der Praxis verwendet, z.B. in Java Collections Sort. Die rekursive Implementierung Quick Sort ist typisch für CSCI 251.
Merge Sort (Mergesort)
Merge Sort teilt das Array rekursiv in zwei Hälften, sortiert diese und führt sie zusammen. Die Merge-Methode ist entscheidend.
private static void merge(int[] arr, int start, int middle, int end) {
int[] temp = new int[end - start + 1];
int i = start, j = middle + 1, k = 0;
while (i <= middle && j <= end) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= middle) temp[k++] = arr[i++];
while (j <= end) temp[k++] = arr[j++];
System.arraycopy(temp, 0, arr, start, temp.length);
}
private static void mergeSortRecursive(int[] arr, int begin, int end) {
if (begin < end) {
int middle = (begin + end) / 2;
mergeSortRecursive(arr, begin, middle);
mergeSortRecursive(arr, middle + 1, end);
merge(arr, begin, middle, end);
}
}
public static void mergeSort(int[] arr) {
mergeSortRecursive(arr, 0, arr.length - 1);
}Merge Sort ist stabil und immer O(n log n), benötigt aber zusätzlichen Speicher. Es wird oft für große Datenmengen verwendet, z.B. in der Datenanalyse.
Projekt 2: Stack und Queue – Palindrome prüfen
Im zweiten Projekt implementieren Sie einen Stack (LIFO) und eine Queue (FIFO) mit ArrayList. Diese Datenstrukturen werden genutzt, um zu prüfen, ob ein String ein Palindrom ist. Ein Palindrom ist ein Wort, das vorwärts und rückwärts gleich gelesen wird, wie „Rentner“ oder „Lagerregal“. In der KI-Textverarbeitung werden Stacks oft für Syntaxanalyse verwendet.
Die Implementierung umfasst Methoden wie push, pop, enqueue, dequeue. Die Palindrom-Prüfung funktioniert, indem man den String in einen Stack und eine Queue einfügt und dann jeweils ein Element entfernt – sie müssen gleich sein.
public boolean isPalindrome(String s) {
Stack stack = new Stack();
Queue queue = new Queue();
for (char c : s.toCharArray()) {
stack.push(c);
queue.enqueue(c);
}
while (!stack.isEmpty()) {
if (stack.pop() != queue.dequeue()) {
return false;
}
}
return true;
}Dieses Projekt vertieft das Verständnis von Stack Queue Implementierung Java und ist eine typische CSCI 251 Projekt 2 Lösung.
Projekt 3: Hashtabelle – Eigene generische HashTable
Hier implementieren Sie eine generische Hashtabelle mit den Klassen MyHashEntry und MyHashTable. Die Hashtabelle speichert Schlüssel-Wert-Paare und verwendet eine Hashfunktion, um den Index zu berechnen. Kollisionen werden durch Verkettung (separate chaining) gelöst. Dies ist die Grundlage für Datenstrukturen Hashtabelle und wird in Datenbank-Indizes verwendet.
Die Methode put fügt ein Paar hinzu, get ruft den Wert ab. Die Hashtabelle muss generisch sein, d.h. MyHashTable<K, V>.
public class MyHashTable<K, V> {
private MyHashEntry<K, V>[] table;
private int capacity;
public MyHashTable(int capacity) {
this.capacity = capacity;
table = new MyHashEntry[capacity];
}
public void put(K key, V value) {
int index = Math.abs(key.hashCode()) % capacity;
MyHashEntry<K, V> entry = table[index];
while (entry != null) {
if (entry.getKey().equals(key)) {
entry.setValue(value);
return;
}
entry = entry.getNext();
}
MyHashEntry<K, V> newEntry = new MyHashEntry<>(key, value);
newEntry.setNext(table[index]);
table[index] = newEntry;
}
}Die generische Hashtable Java ist ein häufiges Thema in CSCI 251 Projekt 3.
Projekt 4: Binärer Suchbaum (Binary Search Tree)
Ein binärer Suchbaum speichert Elemente in sortierter Reihenfolge. Sie implementieren die Klassen TreeNode und BinarySearchTree. Methoden wie insert, search, delete und toString (rekursiv) sind gefordert. Die toString-Methode gibt den Baum in Klammernotation aus, wie im Projekt beschrieben.
public String toString() {
return "(" + nodeTraversal(root) + ")";
}
private String nodeTraversal(TreeNode node) {
if (node == null) return "--";
return node.getData().toString() + "(" + nodeTraversal(node.getLeft()) + ", " + nodeTraversal(node.getRight()) + ")";
}Binäre Suchbäume sind essenziell für Datenstrukturen Baum und werden in Suchalgorithmen verwendet. In der Praxis kommen sie in Datenbank-Indizes und Dateisystemen vor.
Projekt 5: Graph – Breitensuche (BFS) und Tiefensuche (DFS)
Im fünften Projekt implementieren Sie BFS und DFS für einen gerichteten gewichteten Graphen, der als Adjazenzmatrix dargestellt wird. Die Matrix wird von der Tastatur eingelesen. BFS verwendet eine Queue, DFS einen Stack oder Rekursion. Dies ist die Grundlage für Graphalgorithmen BFS DFS und wird in Sozialen Netzwerken (z.B. Freundesvorschläge) oder GPS-Navigation verwendet.
public void bfs(int start) {
boolean[] visited = new boolean[n + 1];
Queue<Integer> queue = new LinkedList<>();
visited[start] = true;
queue.add(start);
while (!queue.isEmpty()) {
int v = queue.poll();
System.out.print(v + " ");
for (int i = 1; i <= n; i++) {
if (matrix[v][i] != Integer.MAX_VALUE && !visited[i]) {
visited[i] = true;
queue.add(i);
}
}
}
}Die Graph Implementierung Java mit Adjazenzmatrix ist ein Kernbestandteil der CSCI 251 Projekt 5 Lösung.
Fazit
Diese fünf Projekte decken die wichtigsten Algorithmen und Datenstrukturen ab, die Sie für Ihre Java Programmierung Studium benötigen. Von Sortieralgorithmen über Stack und Queue bis hin zu Hashtabelle, Binärbaum und Graph – jedes Projekt stärkt Ihr Verständnis für effiziente Programmierung. Denken Sie daran, die gegebenen Dateien nicht zu ändern und die öffentlichen Methoden exakt zu implementieren. Nutzen Sie die bereitgestellten JAR-Dateien, um Ihre Lösungen zu testen. Viel Erfolg bei Ihren Projekten!