Алгоритмы и структуры данных на Swift: полное руководство

Алгоритмы и структуры данных на Swift: от новичка до профессионала

Swift — мощный и интуитивный язык программирования от Apple, используемый для разработки приложений под iOS, macOS, watchOS и tvOS. Понимание алгоритмов и структур данных — фундамент, который отличает опытного разработчика от новичка. В этой статье мы разберём ключевые концепции с практическими примерами на Swift.

1. Базовые структуры данных в Swift

Стандартная библиотека Swift предоставляет несколько встроенных структур, которые лежат в основе любого приложения.

Массивы (Array)

Упорядоченная коллекция элементов одного типа. Поддерживает произвольный доступ по индексу.

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

Словари (Dictionary)

Коллекция пар «ключ-значение» для быстрого поиска данных по уникальному ключу.

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

Множества (Set)

Неупорядоченная коллекция уникальных элементов. Идеально для проверки наличия или удаления дубликатов.

let fruits: Set = ["Apple", "Banana", "Orange", "Apple"]
print(fruits.count) // Вывод: 3 (дубликат удалён)

2. Реализация стека и очереди на Swift

Стек и очередь — классические структуры данных, которые часто реализуются поверх массивов.

Стек (Stack) — LIFO (Last In, First Out)

Элементы добавляются и удаляются с одного конца.

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()!) // Вывод: 3

Очередь (Queue) — FIFO (First In, First Out)

Элементы добавляются в конец, а удаляются из начала.

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()!) // Вывод: First

3. Алгоритмы сортировки и поиска

Рассмотрим два фундаментальных алгоритма, которые полезны в реальных проектах.

Быстрая сортировка (Quick Sort)

Эффективный алгоритм «разделяй и властвуй» со средней сложностью 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)) // Вывод: [1, 1, 2, 3, 6, 8, 10]

Бинарный поиск (Binary Search)

Работает только на отсортированном массиве. Сложность 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) {
    print("Found at index: \(index)") // Вывод: Found at index: 3
}

4. Связный список (Linked List) — кастомная реализация

Связный список не входит в стандартную библиотеку Swift, но его легко реализовать самостоятельно.

class Node<T> {
    var value: T
    var next: Node?
    
    init(value: T) {
        self.value = value
    }
}

class LinkedList<T> {
    var head: Node<T>?
    
    func append(_ value: T) {
        let newNode = Node(value: value)
        if head == nil {
            head = newNode
            return
        }
        var current = head
        while current?.next != nil {
            current = current?.next
        }
        current?.next = newNode
    }
    
    func printList() {
        var current = head
        while current != nil {
            print(current!.value, terminator: " -> ")
            current = current?.next
        }
        print("nil")
    }
}

let list = LinkedList<Int>()
list.append(10)
list.append(20)
list.append(30)
list.printList() // Вывод: 10 -> 20 -> 30 -> nil

Заключение

Освоение алгоритмов и структур данных на Swift — ключевой шаг к написанию эффективного и масштабируемого кода для iOS и macOS. В этой статье мы рассмотрели:

• Встроенные структуры: Array, Dictionary, Set.
• Реализацию стека и очереди.
• Алгоритмы сортировки (Quick Sort) и поиска (Binary Search).
• Создание связного списка с нуля.

Практикуйтесь, экспериментируйте с кодом и внедряйте эти паттерны в свои проекты. Чем глубже вы понимаете структуры данных, тем увереннее чувствуете себя при решении сложных задач. Удачи в разработке!