Algoritmos de ordenação em Swift: um guia completo

Что это такое и зачем? (аналогия из реальной жизни)

Представь, что ты — библиотекарь, и у тебя есть огромная стопка книг, которые нужно расставить по алфавиту. Если книг всего пять, ты можешь сделать это за пару минут, просто перебирая их вручную. Но что, если книг тысяча? Или десять тысяч? Тут уже нужен чёткий план действий — алгоритм сортировки.

В программировании сортировка — это процесс упорядочивания элементов в определённом порядке (по возрастанию, убыванию, по алфавиту и т.д.). Это одна из самых фундаментальных задач, с которой сталкивается каждый разработчик. Без сортировки невозможно представить работу баз данных, поисковых систем, интернет-магазинов и даже твоего плейлиста в музыкальном приложении.

Важно: Сортировка — это не просто «расставить по порядку». Это целая наука о том, как это сделать максимально быстро и эффективно, особенно когда данных много.

Аналогия из жизни: Представь, что ты сортируешь колоду карт. Ты можешь:

• Методом «пузырька»: проходишь по всей колоде, сравнивая соседние карты и меняя их местами, если они не в том порядке. Самые «лёгкие» карты (с малым значением) постепенно всплывают вверх, как пузырьки в газировке.
• Методом «вставки»: берёшь карту из середины колоды и вставляешь её в нужное место среди уже отсортированных карт. Так обычно сортируют карты в руке во время игры.
• Методом «слияния»: делишь колоду на маленькие стопки, сортируешь каждую, а потом сливаешь их вместе, как ручьи в реку.

Каждый метод имеет свои плюсы и минусы. Какой-то быстрее на маленьких объёмах, какой-то — на огромных. Наша задача — разобраться, как они работают «под капотом» и как их реализовать на Swift.

Теория: как это работает изнутри

Прежде чем писать код, давай разберёмся, какие вообще бывают алгоритмы сортировки и в чём их ключевое отличие. Главный показатель — временная сложность (Big O notation). Не пугайся этого термина — это просто способ сказать, насколько быстро алгоритм справляется с задачей, когда данных становится всё больше и больше.

Основные виды сортировок

Запомни: O(n²) — это «квадратичная сложность». Если элементов 10, то операций ~100. Если 1000 — то ~1 000 000. Чувствуешь разницу? O(n log n) — это «линейно-логарифмическая сложность». Для 1000 элементов — это ~10 000 операций. В 100 раз быстрее!

Как работает «Быстрая сортировка» (Quick Sort) — разбор на пальцах

Это самый популярный алгоритм. Давай разберём его шаг за шагом, чтобы ты понял магию:

1. Выбираем опорный элемент (pivot). Можно взять первый, последний или средний элемент массива.
2. Разделяем (partition). Все элементы, которые меньше опорного, отправляем влево от него, а те, что больше — вправо. Сам опорный элемент оказывается на своём «законном» месте.
3. Рекурсия. Теперь у нас есть два подмассива: левый (все элементы меньше pivot) и правый (все элементы больше pivot). Применяем к ним те же шаги 1 и 2.
4. Базовый случай. Если в подмассиве остался 0 или 1 элемент — сортировать нечего, возвращаем его как есть.

Этот алгоритм называется «разделяй и властвуй». Он разбивает большую задачу на маленькие, которые решить гораздо проще.

Синтаксис в Swift: все формы и варианты

Swift — один из самых удобных языков для работы с сортировкой. У него есть встроенные методы, которые работают «из коробки», но мы также можем написать свои алгоритмы для полного понимания процесса.

1. Встроенная сортировка массивов

Самый простой способ — использовать метод sort() (сортирует на месте) или sorted() (возвращает новый отсортированный массив).

// Исходный массив
var numbers = [5, 2, 8, 1, 9]

// Сортировка на месте (изменяет исходный массив)
numbers.sort()
print(numbers) // [1, 2, 5, 8, 9]

// Сортировка с созданием нового массива
let sortedNumbers = numbers.sorted()
print(sortedNumbers) // [1, 2, 5, 8, 9]
print(numbers) // [1, 2, 5, 8, 9] — исходный массив не изменился

2. Сортировка по убыванию

По умолчанию сортировка идёт по возрастанию. Чтобы изменить порядок, используем замыкание (closure).

let numbers = [5, 2, 8, 1, 9]

// Сортировка по убыванию
let descending = numbers.sorted { $0 > $1 }
print(descending) // [9, 8, 5, 2, 1]

// Можно и так (более короткая запись)
let descending2 = numbers.sorted(by: >)
print(descending2) // [9, 8, 5, 2, 1]

3. Сортировка словарей

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

let scores = ["Анна": 95, "Борис": 80, "Виктор": 100]

// Сортировка по ключам (по алфавиту)
let sortedByKey = scores.sorted { $0.key < $1.key }
print(sortedByKey) // [(key: "Анна", value: 95), (key: "Борис", value: 80), (key: "Виктор", value: 100)]

// Сортировка по значениям (по убыванию баллов)
let sortedByValue = scores.sorted { $0.value > $1.value }
print(sortedByValue) // [(key: "Виктор", value: 100), (key: "Анна", value: 95), (key: "Борис", value: 80)]

4. Сортировка пользовательских структур

Если у тебя есть свои типы данных (struct или class), нужно указать, по какому полю сортировать.

struct Student {
    let name: String
    let grade: Int
}

let students = [
    Student(name: "Иван", grade: 4),
    Student(name: "Мария", grade: 5),
    Student(name: "Петр", grade: 3)
]

// Сортировка по имени
let sortedByName = students.sorted { $0.name < $1.name }
for student in sortedByName {
    print("(student.name): (student.grade)")
}
// Вывод:
// Иван: 4
// Мария: 5
// Петр: 3

// Сортировка по оценке (по убыванию)
let sortedByGrade = students.sorted { $0.grade > $1.grade }
for student in sortedByGrade {
    print("(student.name): (student.grade)")
}
// Вывод:
// Мария: 5
// Иван: 4
// Петр: 3

5. Протокол Comparable

Если ты хочешь, чтобы твои структуры можно было сортировать без указания полей каждый раз, реализуй протокол Comparable.

struct Product: Comparable {
    let name: String
    let price: Double
    
    // Реализуем оператор сравнения
    static func < (lhs: Product, rhs: Product) -> Bool {
        return lhs.price < rhs.price
    }
    
    // Для полной реализации Comparable нужно также реализовать ==
    static func == (lhs: Product, rhs: Product) -> Bool {
        return lhs.price == rhs.price
    }
}

let products = [
    Product(name: "Ноутбук", price: 1200),
    Product(name: "Мышь", price: 25),
    Product(name: "Монитор", price: 450)
]

// Теперь можно сортировать просто так!
let sortedProducts = products.sorted()
for product in sortedProducts {
    print("(product.name): (product.price)$")
}
// Вывод:
// Мышь: 25.0$
// Монитор: 450.0$
// Ноутбук: 1200.0$

Примеры кода — от простого к сложному

Теперь перейдём к самому интересному — написанию алгоритмов сортировки вручную. Каждый пример будет полностью рабочим и подробно прокомментирован.

Пример 1: Пузырьковая сортировка (Bubble Sort)

Самый простой для понимания, но самый медленный алгоритм.

// Функция пузырьковой сортировки
func bubbleSort(_ array: inout [Int]) {
    // Получаем количество элементов в массиве
    let n = array.count
    
    // Внешний цикл: проходим по массиву n-1 раз
    for i in 0.. array[j+1] {
                // Меняем местами с помощью временной переменной
                let temp = array[j]
                array[j] = array[j+1]
                array[j+1] = temp
            }
        }
    }
}

// Тестируем
var numbers = [64, 34, 25, 12, 22, 11, 90]
print("До сортировки: (numbers)")
bubbleSort(&numbers)
print("После сортировки: (numbers)")
// Вывод:
// До сортировки: [64, 34, 25, 12, 22, 11, 90]
// После сортировки: [11, 12, 22, 25, 34, 64, 90]

Пример 2: Сортировка выбором (Selection Sort)

На каждом шаге находим минимальный элемент и ставим его в начало.

// Функция сортировки выбором
func selectionSort(_ array: inout [Int]) {
    let n = array.count
    
    // Проходим по всем элементам массива
    for i in 0..

// Функция сортировки вставками
func insertionSort(_ array: inout [Int]) {
    let n = array.count
    
    // Начинаем со второго элемента (индекс 1), так как первый элемент считаем отсортированным
    for i in 1.. key {
            array[j + 1] = array[j] // Сдвигаем элемент вправо
            j -= 1
        }
        
        // Вставляем key на освободившееся место
        array[j + 1] = key
    }
}

// Тестируем
var numbers = [12, 11, 13, 5, 6]
print("До сортировки: (numbers)")
insertionSort(&numbers)
print("После сортировки: (numbers)")
// Вывод:
// До сортировки: [12, 11, 13, 5, 6]
// После сортировки: [5, 6, 11, 12, 13]

// Функция быстрой сортировки
func quickSort(_ array: [Int]) -> [Int] {
    // Базовый случай: если в массиве 0 или 1 элемент — он уже отсортирован
    guard array.count > 1 else { return array }
    
    // Выбираем опорный элемент (pivot) — возьмём средний элемент
    let pivot = array[array.count / 2]
    
    // Разделяем массив на три части:
    // 1. Элементы меньше pivot
    let less = array.filter { $0 < pivot }
    // 2. Элементы равные pivot
    let equal = array.filter { $0 == pivot }
    // 3. Элементы больше pivot
    let greater = array.filter { $0 > pivot }
    
    // Рекурсивно сортируем левую и правую части, затем объединяем
    return quickSort(less) + equal + quickSort(greater)
}

// Тестируем
let numbers = [3, 6, 8, 10, 1, 2, 1]
print("До сортировки: (numbers)")
let sorted = quickSort(numbers)
print("После сортировки: (sorted)")
// Вывод:
// До сортировки: [3, 6, 8, 10, 1, 2, 1]
// После сортировки: [1, 1, 2, 3, 6, 8, 10]

// Функция разделения массива (partition)
func partition(_ array: inout [Int], low: Int, high: Int) -> Int {
    // Выбираем опорный элемент (последний элемент)
    let pivot = array[high]
    var i = low - 1 // Индекс для элементов меньше pivot
    
    // Проходим по всем элементам от low до high-1
    for j in low..

// Функция слияния двух отсортированных массивов
func merge(_ left: [Int], _ right: [Int]) -> [Int] {
    var result: [Int] = []
    var leftIndex = 0
    var rightIndex = 0
    
    // Сливаем массивы, пока в обоих есть элементы
    while leftIndex < left.count && rightIndex < right.count {
        if left[leftIndex] < right[rightIndex] {
            result.append(left[leftIndex])
            leftIndex += 1
        } else {
            result.append(right[rightIndex])
            rightIndex += 1
        }
    }
    
    // Добавляем оставшиеся элементы из левого массива (если есть)
    while leftIndex < left.count {
        result.append(left[leftIndex])
        leftIndex += 1
    }
    
    // Добавляем оставшиеся элементы из правого массива (если есть)
    while rightIndex < right.count {
        result.append(right[rightIndex])
        rightIndex += 1
    }
    
    return result
}

// Функция сортировки слиянием
func mergeSort(_ array: [Int]) -> [Int] {
    // Базовый случай: массив из 0 или 1 элемента уже отсортирован
    guard array.count > 1 else { return array }
    
    // Находим середину массива
    let mid = array.count / 2
    
    // Рекурсивно сортируем левую и правую половины
    let left = mergeSort(Array(array[0..

// Массив строк разной длины
let words = ["кот", "собака", "я", "программирование", "Swift", "алгоритм"]

// Сортируем строки по длине (от самой короткой к самой длинной)
let sortedByLength = words.sorted { $0.count < $1.count }
print("По длине (возрастание): (sortedByLength)")
// Вывод: ["я", "кот", "Swift", "собака", "алгоритм", "программирование"]

// Сортируем строки по длине (от самой длинной к самой короткой)
let sortedByLengthDesc = words.sorted { $0.count > $1.count }
print("По длине (убывание): (sortedByLengthDesc)")
// Вывод: ["программирование", "алгоритм", "собака", "Swift", "кот", "я"]

// Сортируем сначала по длине, а если длина одинаковая — по алфавиту
let sortedByLengthThenAlphabet = words.sorted {
    if $0.count != $1.count {
        return $0.count < $1.count
    } else {
        return $0 < $1
    }
}
print("По длине, затем по алфавиту: (sortedByLengthThenAlphabet)")
// Вывод: ["я", "кот", "Swift", "собака", "алгоритм", "программирование"]

// Создаём массив кортежей (имя, возраст)
let people = [
    ("Анна", 25),
    ("Борис", 30),
    ("Виктор", 22),
    ("Галина", 25)
]

// Сортируем по возрасту
let sortedByAge = people.sorted { $0.1 < $1.1 }
print("По возрасту: (sortedByAge)")
// Вывод: [(Виктор, 22), (Анна, 25), (Галина, 25), (Борис, 30)]

// Сортируем по имени (по алфавиту)
let sortedByName = people.sorted { $0.0 < $1.0 }
print("По имени: (sortedByName)")
// Вывод: [(Анна, 25), (Борис, 30), (Виктор, 22), (Галина, 25)]

// Сортируем по возрасту, а если возраст одинаковый — по имени
let sortedByAgeThenName = people.sorted {
    if $0.1 != $1.1 {
        return $0.1 < $1.1
    } else {
        return $0.0 < $1.0
    }
}
print("По возрасту, затем по имени: (sortedByAgeThenName)")
// Вывод: [(Виктор, 22), (Анна, 25), (Галина, 25), (Борис, 30)]

var numbers = [3, 1, 2]

// ❌ Ошибка: Cannot pass immutable value as inout argument
bubbleSort(numbers)

// ✅ Правильно
bubbleSort(&numbers)

let numbers: [Int?] = [3, nil, 1, 2]

// ❌ Ошибка: Value of optional type 'Int?' must be unwrapped
// let sorted = numbers.sorted { $0 < $1 }

// ✅ Правильно: используем nil-коалесценцию
let sorted = numbers.sorted {
    ($0 ?? Int.max) < ($1 ?? Int.max)
}
print(sorted) // [Optional(1), Optional(2), Optional(3), nil]

let numbers = [3, 1, 2]

// ❌ Ошибка: сортировка по возрастанию, а не по убыванию
let wrong = numbers.sorted { $0 < $1 }
print(wrong) // [1, 2, 3] — это возрастание!

// ✅ Правильно для убывания
let correct = numbers.sorted { $0 > $1 }
print(correct) // [3, 2, 1]

var numbers = [3, 1, 2]

// ❌ Ошибка: изменение массива во время итерации
for i in 0.. 1 {
        numbers.remove(at: i) // Это приведёт к пропуску элементов или крашу
    }
}

// ✅ Правильно: используй filter
numbers = numbers.filter { $0 <= 1 }
print(numbers) // [1]

let words = ["ёлка", "елка", "Йод", "йод"]

// ❌ Ошибка: сортировка без учёта локали
let wrong = words.sorted()
print(wrong) // ["Йод", "елка", "йод", "ёлка"] — не по алфавиту!

// ✅ Правильно: используем localizedCompare
let correct = words.sorted { $0.localizedCompare($1) == .orderedAscending }
print(correct) // ["елка", "ёлка", "йод", "Йод"] — теперь по алфавиту