Algorithmen und Datenstrukturen in Swift: Das vollständige Handbuch

Algorithmen und Datenstrukturen in Swift: Vom Anfänger zum Profi

Swift ist eine leistungsstarke und intuitive Programmiersprache von Apple, die für die Entwicklung von Apps für iOS, macOS, watchOS und tvOS verwendet wird. Das Verständnis von Algorithmen und Datenstrukturen ist die Grundlage, die einen erfahrenen Entwickler von einem Anfänger unterscheidet. In diesem Artikel werden wir die wichtigsten Konzepte mit praktischen Beispielen in Swift durchgehen.

1. Grundlegende Datenstrukturen in Swift

Die Standardbibliothek von Swift bietet mehrere eingebaute Strukturen, die die Grundlage jeder Anwendung bilden.

Arrays (Array)

Eine geordnete Sammlung von Elementen desselben Typs. Unterstützt den wahlfreien Zugriff über einen Index.

var numbers: [Int] = [10, 20, 30, 40, 50]numbers.append(60)numbers.insert(5, at: 0)print(numbers[2]) // Ausgabe: 30

Wörterbücher (Dictionary)

Eine Sammlung von Schlüssel-Wert-Paaren für die schnelle Suche nach Daten über einen eindeutigen Schlüssel.

var userScores: [String: Int] = ["Alice": 95, "Bob": 87]userScores["Charlie"] = 92if let score = userScores["Alice"] {    print("Alice's score: \\(score)")}

Mengen (Set)

Eine ungeordnete Sammlung eindeutiger Elemente. Ideal zum Prüfen auf Vorhandensein oder zum Entfernen von Duplikaten.

let fruits: Set = ["Apple", "Banana", "Orange", "Apple"]print(fruits.count) // Ausgabe: 3 (Duplikat entfernt)

2. Implementierung von Stack und Queue in Swift

Stack und Queue sind klassische Datenstrukturen, die oft auf Basis von Arrays implementiert werden.

Stack (Stapel) — LIFO (Last In, First Out)

Elemente werden an einem Ende hinzugefügt und entfernt.

struct Stack<T> {    private var elements: [T] = []        mutating func push(_ value: T) {        elements.append(value)    }        mutating func pop() -> T? {        return elements.popLast()    }        func peek() -> T? {        return elements.last    }}

var stack = Stack<Int>()stack.push(1)stack.push(2)stack.push(3)print(stack.pop()!) // Ausgabe: 3

Queue (Warteschlange) — FIFO (First In, First Out)

Elemente werden am Ende hinzugefügt und am Anfang entfernt.

struct Queue<T> {    private var elements: [T] = []        mutating func enqueue(_ value: T) {        elements.append(value)    }        mutating func dequeue() -> T? {        return elements.isEmpty ? nil : elements.removeFirst()    }}

var queue = Queue<String>()queue.enqueue("First")queue.enqueue("Second")print(queue.dequeue()!) // Ausgabe: First

3. Sortier- und Suchalgorithmen

Betrachten wir zwei grundlegende Algorithmen, die in realen Projekten nützlich sind.

Quick Sort (Schnelle Sortierung)

Ein effizienter "Teile und Herrsche"-Algorithmus mit einer durchschnittlichen Komplexität von O(n log n).

func quickSort(_ array: [Int]) -> [Int] {    guard array.count > 1 else { return array }        let pivot = array[array.count / 2]    let less = array.filter { $0 < pivot }    let equal = array.filter { $0 == pivot }    let greater = array.filter { $0 > pivot }        return quickSort(less) + equal + quickSort(greater)}

let unsorted = [3, 6, 8, 10, 1, 2, 1]print(quickSort(unsorted)) // Ausgabe: [1, 1, 2, 3, 6, 8, 10]

Binary Search (Binäre Suche)

Funktioniert nur auf einem sortierten Array. Komplexität O(log n).

func binarySearch(_ array: [Int], target: Int) -> Int? {    var low = 0    var high = array.count - 1        while low <= high {        let mid = (low + high) / 2        if array[mid] == target {            return mid        } else if array[mid] < target {            low = mid + 1        } else {            high = mid - 1        }    }    return nil}

let sortedArray = [1, 3, 5, 7, 9, 11]if let index = binarySearch(sortedArray, target: 7) {    p