Алгоритмы и структуры данных на Swift: полный гайд для iOS-разработчика

Онлайн-тренажер Python для начинающих

Изучайте Python легко и без перегрузки теорией. Решайте практические задачи с автоматической проверкой, получайте подсказки на русском языке и пишите код прямо в браузере — без необходимости что-либо устанавливать.

Начать курс

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

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

1. Базовые структуры данных в Swift: массивы, множества и словари

Swift предоставляет мощные встроенные коллекции, но понимание их внутреннего устройства помогает писать более эффективный код.

Массивы (Array)

Массив — упорядоченная коллекция элементов с доступом по индексу. В Swift Array реализован как динамический массив с амортизированной сложностью O(1) для добавления в конец.

// Создание и базовые операции
var numbers = [1, 2, 3, 4, 5]
numbers.append(6) // O(1) в среднем
numbers.insert(0, at: 0) // O(n) — сдвиг элементов
let first = numbers[0] // O(1)
numbers.removeLast() // O(1)
numbers.remove(at: 2) // O(n) — сдвиг

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

Set — неупорядоченная коллекция уникальных элементов. Реализована на основе хеш-таблицы, что даёт O(1) для вставки, удаления и поиска.

var uniqueNumbers: Set<Int> = [1, 2, 3, 3, 4]
print(uniqueNumbers) // [1, 2, 3, 4] — дубликаты удалены
uniqueNumbers.insert(5) // O(1)
let contains = uniqueNumbers.contains(3) // true, O(1)

Словари (Dictionary)

Ассоциативный массив для хранения пар "ключ-значение". Также основан на хеш-таблицах.

var scores: [String: Int] = ["Alice": 95, "Bob": 87]
scores["Charlie"] = 92 // O(1)
if let aliceScore = scores["Alice"] {
    print("Alice: \(aliceScore)")
}
scores.removeValue(forKey: "Bob") // O(1)

2. Пользовательские структуры данных: стеки, очереди и связанные списки

Хотя в Swift нет встроенных реализаций стека и очереди, их легко реализовать самостоятельно.

Стек (Stack) — LIFO

Стек работает по принципу "последний вошёл — первый вышел". Используется для отмены действий, обхода деревьев в глубину.

struct Stack<Element> {
    private var storage: [Element] = []
    
    mutating func push(_ element: Element) { storage.append(element) }
    mutating func pop() -> Element? { storage.popLast() }
    func peek() -> Element? { storage.last }
    var isEmpty: Bool { storage.isEmpty }
}

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

Очередь (Queue) — FIFO

Очередь работает по принципу "первый вошёл — первый вышел". Используется для обработки задач в порядке поступления.

struct Queue<Element> {
    private var input: [Element] = []
    private var output: [Element] = []
    
    mutating func enqueue(_ element: Element) { input.append(element) }
    
    mutating func dequeue() -> Element? {
        if output.isEmpty {
            output = input.reversed()
            input.removeAll()
        }
        return output.popLast()
    }
    
    var isEmpty: Bool { input.isEmpty && output.isEmpty }
}

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

Связанный список (Linked List)

Связанный список состоит из узлов, каждый из которых ссылается на следующий. Позволяет эффективно вставлять/удалять элементы в середине списка.

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

class LinkedList<T> {
    var head: ListNode<T>?
    
    func append(_ value: T) {
        let newNode = ListNode(value)
        guard var current = head else { head = newNode; return }
        while let next = current.next { current = next }
        current.next = newNode
    }
    
    func remove(at index: Int) {
        guard index > 0, let _ = head else { return }
        var current = head
        var prev: ListNode<T>?
        for _ in 0..<index {
            prev = current
            current = current?.next
        }
        prev?.next = current?.next
    }
}

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

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

Один из самых эффективных алгоритмов сортировки со средней сложностью O(n log n).

func quickSort<T: Comparable>(_ array: [T]) -> [T] {
    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, 1, 8, 2, 5]
let sorted = quickSort(unsorted) // [1, 2, 3, 5, 6, 8]

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

Работает только на отсортированных массивах. Сложность O(log n).

func binarySearch<T: Comparable>(_ array: [T], target: T) -> Int? {
    var low = 0
    var high = array.count - 1
    
    while low <= high {
        let mid = (low + high) / 2
        if array[mid] == target { return mid }
        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
}