Алгоритмы и структуры данных на Swift: полный курс для начинающих

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

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

В этой статье мы разберём базовые структуры данных (массивы, словари, множества) и ключевые алгоритмы (сортировка, поиск) на Swift. Все примеры кода готовы к запуску в Xcode Playground.

Основные структуры данных в Swift

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

Массивы (Array)

Массив — это упорядоченная коллекция элементов одного типа. В Swift массивы являются строго типизированными и имеют фиксированный порядок.

// Создание массива
var numbers: [Int] = [1, 2, 3, 4, 5]

// Добавление элемента
numbers.append(6)

// Доступ по индексу
let first = numbers[0] // 1

// Итерация
for number in numbers {
    print(number)
}

// Сортировка на месте
numbers.sort() // [1, 2, 3, 4, 5, 6]

Массивы идеальны, когда важен порядок элементов и нужен быстрый доступ по индексу (O(1)). Однако вставка или удаление в начале массива требует O(n) времени.

Словари (Dictionary)

Словарь хранит пары "ключ-значение". Ключи должны быть уникальными и хешируемыми (например, String, Int).

// Создание словаря
var scores: [String: Int] = ["Alice": 95, "Bob": 87]

// Добавление или обновление
scores["Charlie"] = 92

// Получение значения (опционально)
if let aliceScore = scores["Alice"] {
    print("Alice's score: \(aliceScore)")
}

// Удаление
scores.removeValue(forKey: "Bob")

Словари обеспечивают доступ к значению по ключу за O(1) в среднем. Используйте их, когда данные естественно группируются по уникальным ключам.

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

Множество — это неупорядоченная коллекция уникальных элементов. Полезно для проверки принадлежности и удаления дубликатов.

// Создание множества
var fruits: Set<String> = ["Apple", "Banana", "Orange"]

// Добавление
fruits.insert("Mango")

// Проверка наличия
if fruits.contains("Apple") {
    print("Apple is in the set")
}

// Удаление дубликатов из массива
let arrayWithDuplicates = [1, 1, 2, 3, 3, 4]
let uniqueSet = Set(arrayWithDuplicates) // {1, 2, 3, 4}

Базовые алгоритмы на Swift

Теперь применим структуры данных для решения типовых задач. Рассмотрим сортировку и поиск.

Алгоритмы сортировки

Swift имеет встроенную функцию sort(), но для понимания напишем классический алгоритм быстрой сортировки (Quick Sort).

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, 1, 8, 2, 9, 4]
let sorted = quickSort(unsorted)
print(sorted) // [1, 2, 3, 4, 6, 8, 9]

Quick Sort — один из самых эффективных алгоритмов со средней сложностью O(n log n). Для небольших массивов можно использовать встроенный sorted().

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

Линейный поиск прост, но медленный (O(n)). Для отсортированных данных используйте бинарный поиск (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]
if let index = binarySearch(sortedArray, target: 7) {
    print("Элемент найден на индексе \(index)") // 3
}

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

Практический пример: анализ текста

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

func wordFrequency(in text: String) -> [String: Int] {
    // Удаляем знаки препинания и приводим к нижнему регистру
    let cleanedText = text.lowercased()
        .components(separatedBy: CharacterSet.punctuationCharacters)
        .joined()
    
    let words = cleanedText.split(separator: " ").map(String.init)
    var frequency: [String: Int] = [:]
    
    for word in words {
        frequency[word, default: 0] += 1
    }
    
    return frequency
}

let sampleText = "Swift Swift is great. Swift is powerful."
let freq = wordFrequency(in: sampleText)
print(freq)
// ["swift": 3, "is": 2, "great": 1, "powerful": 1]

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

Заключение

Мы рассмотрели ключевые структуры данных (массивы, словари, множества) и базовые алгоритмы (сортировка, бинарный поиск) на Swift. Эти знания — основа для решения любых задач в iOS/macOS разработке.

Советы для дальнейшего изучения:

• Потренируйтесь реализовывать связные списки и стеки на Swift.
• Изучите