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

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

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

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

1. Стек (Stack) и очередь (Queue): фундаментальные структуры

Стек и очередь — это две базовые структуры данных, которые часто используются в iOS-разработке. Например, стек используется для навигации в UINavigationController, а очередь — для управления задачами в OperationQueue или DispatchQueue.

Реализация стека (LIFO — Last In, First Out)

Стек работает по принципу "последний пришел — первый ушел". Добавление элемента (push) и удаление (pop) происходят с одного конца — вершины стека.

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

// Пример использования
var navigationStack = Stack<String>()
navigationStack.push("Главный экран")
navigationStack.push("Детали товара")
navigationStack.push("Корзина")
print(navigationStack.pop() ?? "") // Выведет: "Корзина"
print(navigationStack.peek() ?? "") // Выведет: "Детали товара"

Где применяется: Отмена операций (Undo/Redo), проверка корректности скобок в парсерах, обход дерева в глубину (DFS).

Реализация очереди (FIFO — First In, First Out)

Очередь работает по принципу "первый пришел — первый ушел". Элементы добавляются в конец (enqueue) и удаляются из начала (dequeue).

struct Queue<Element> {
    private var storage: [Element] = []
    
    mutating func enqueue(_ element: Element) {
        storage.append(element)
    }
    
    @discardableResult
    mutating func dequeue() -> Element? {
        guard !storage.isEmpty else { return nil }
        return storage.removeFirst()
    }
    
    func peek() -> Element? {
        return storage.first
    }
    
    var isEmpty: Bool {
        return storage.isEmpty
    }
}

// Пример использования
var taskQueue = Queue<String>()
taskQueue.enqueue("Загрузка изображений")
taskQueue.enqueue("Синхронизация данных")
taskQueue.enqueue("Отправка аналитики")
print(taskQueue.dequeue() ?? "") // Выведет: "Загрузка изображений"

Где применяется: Обработка сетевых запросов, обход дерева в ширину (BFS), очереди задач в фоновых потоках.

2. Бинарный поиск: скорость против простоты

Бинарный поиск — это классический алгоритм, который находит элемент в отсортированном массиве за логарифмическое время O(log n). В iOS он часто применяется при работе с большими отсортированными наборами данных, например, при поиске контактов или записей в базе данных.

func binarySearch<T: Comparable>(in array: [T], target: T) -> Int? {
    var lowerBound = 0
    var upperBound = array.count - 1
    
    while lowerBound <= upperBound {
        let midIndex = (lowerBound + upperBound) / 2
        let midValue = array[midIndex]
        
        if midValue == target {
            return midIndex
        } else if midValue < target {
            lowerBound = midIndex + 1
        } else {
            upperBound = midIndex - 1
        }
    }
    return nil // Элемент не найден
}

// Пример использования
let sortedNumbers = [1, 3, 5, 7, 9, 11, 13, 15]
if let index = binarySearch(in: sortedNumbers, target: 11) {
    print("Элемент найден на индексе \(index)") // Выведет: 4
} else {
    print("Элемент не найден")
}

Важно: Бинарный поиск работает только на отсортированных массивах. Если массив не отсортирован, предварительно используйте алгоритмы сортировки.

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

Хотя в Swift есть встроенная функция sort(), понимание механизмов сортировки помогает писать оптимизированный код и выбирать правильный алгоритм под конкретную задачу. Рассмотрим две популярные реализации.

Быстрая сортировка (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 = [8, 3, 1, 7, 0, 10, 2]
let sorted = quickSort(unsorted)
print(sorted) // Выведет: [0, 1, 2, 3, 7, 8, 10]

Сортировка слиянием (Merge Sort)

Стабильный алгоритм с гарантированной сложностью O(n log n). Отлично подходит для работы с большими объемами данных.

func mergeSort<T: Comparable>(_ array: [T]) -> [T] {
    guard array.count > 1 else { return array }
    
    let midIndex = array.count / 2
    let leftArray = mergeSort(Array(array[0..<midIndex]))
    let rightArray = mergeSort(Array(array[midIndex..<array.count]))
    
    return merge(left: leftArray, right: rightArray)
}

func merge<T: Comparable>(left: [T], right: [T]) -> [T] {
    var leftIndex = 0
    var rightIndex = 0
    var result: [T] = []