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

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

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

Стек (Stack) на Swift: LIFO в действии

Стек — это коллекция, работающая по принципу "последним пришёл — первым вышел" (LIFO). Представьте стопку тарелок: вы берёте только верхнюю. В iOS стек используется, например, для навигации (UINavigationController) или для отмены действий (Undo).

Реализуем стек на Swift с использованием дженериков:

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

// Пример использования
var stack = Stack<String>()
stack.push("Первый")
stack.push("Второй")
stack.push("Третий")

print(stack.pop()!) // Третий
print(stack.peek()!) // Второй

Где применяется? В приложениях для отображения истории просмотров, в парсерах (проверка скобок), в алгоритмах обхода графов (DFS).

Очередь (Queue): FIFO для обработки задач

Очередь работает по принципу "первым пришёл — первым вышел" (FIFO). Как очередь в магазине: кто первый встал, того первого и обслужили. В Swift очередь часто используется для управления задачами (DispatchQueue), обработки сетевых запросов или анимаций.

Базовая реализация очереди:

struct Queue<Element> {
    private var elements: [Element] = []
    
    mutating func enqueue(_ element: Element) {
        elements.append(element)
    }
    
    @discardableResult
    mutating func dequeue() -> Element? {
        return isEmpty ? nil : elements.removeFirst()
    }
    
    func front() -> Element? {
        return elements.first
    }
    
    var isEmpty: Bool {
        return elements.isEmpty
    }
    
    var count: Int {
        return elements.count
    }
}

// Пример использования
var queue = Queue<Int>()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)

print(queue.dequeue()!) // 1
print(queue.front()!)   // 2

Проблема производительности: removeFirst() на массиве имеет сложность O(n), так как все элементы сдвигаются. Для высокой производительности используйте ContiguousArray или двухстороннюю очередь (deque). В реальных проектах Apple рекомендует DispatchQueue для многопоточности.

Алгоритмы сортировки: от пузырька до быстрой сортировки

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

Пузырьковая сортировка (Bubble Sort) — O(n²)

Простой, но медленный алгоритм. Полезен для обучения, но не для продакшена.

func bubbleSort(_ array: inout [Int]) {
    guard array.count > 1 else { return }
    
    for i in 0..<array.count {
        var swapped = false
        for j in 0..<(array.count - 1 - i) {
            if array[j] > array[j + 1] {
                array.swapAt(j, j + 1)
                swapped = true
            }
        }
        if !swapped { break } // оптимизация: массив уже отсортирован
    }
}

var numbers = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(&numbers)
print(numbers) // [11, 12, 22, 25, 34, 64, 90]

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

Совет: Для массивов с повторяющимися элементами быстрая сортировка стабильна, но требует дополнительной памяти. В Swift стандартная sort() использует гибридный алгоритм (introsort), который сочетает быструю сортировку, пирамидальную и сортировку вставками.

Бинарный поиск: нахождение элемента за 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
        let guess = array[mid]
        
        if guess == target {
            return mid
        } else if guess > target {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    
    return nil // элемент не найден
}

let sortedArray = [1, 3, 5, 7, 9, 11, 13, 15]
if let index = binarySearch(sortedArray, target: 7) {
    print("Элемент найден на индексе: \(index)") // 3
} else {
    print("Элемент не найден")
}

Где применяется? В поиске по отсортированным спискам (например, контакты в адресной книге), в алгоритмах машинного обучения, в базах данных