Сортировка массивов в Swift: шокирующие тесты производительности

1. Встроенный метод sort() — золотой стандарт

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

import Foundation

var numbers = [5, 3, 8, 1, 9, 2]
numbers.sort() // сортировка на месте
print(numbers) // [1, 2, 3, 5, 8, 9]

let sortedNumbers = numbers.sorted() // возвращает новый массив
print(sortedNumbers) // [1, 2, 3, 5, 8, 9]

Внутри sort() использует TimSort — гибридный алгоритм, который работает за O(n log n) в среднем и O(n) на почти отсортированных данных. Это тот же алгоритм, что используется в Python и Java. Он великолепно оптимизирован под современные процессоры.

2. Сортировка с замыканием: кастомизация

Если вам нужно отсортировать массив по убыванию или по сложному критерию, используйте замыкание:

let words = ["яблоко", "апельсин", "банан", "киви"]
let sortedByLength = words.sorted { $0.count < $1.count }
print(sortedByLength) // ["киви", "яблоко", "банан", "апельсин"]

let descendingNumbers = numbers.sorted(by: >)
print(descendingNumbers) // [9, 8, 5, 3, 2, 1]

Важно: замыкание должно быть чистой функцией (pure function) — без побочных эффектов. Иначе вы рискуете получить непредсказуемое поведение и падение производительности.

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

Когда вы работаете с собственными типами данных, лучше всего реализовать протокол Comparable. Это позволит использовать sort() без замыкания.

struct Person: Comparable {
    let name: String
    let age: Int

    static func < (lhs: Person, rhs: Person) -> Bool {
        return lhs.age < rhs.age // сортируем по возрасту
    }
}

let people = [
    Person(name: "Анна", age: 30),
    Person(name: "Борис", age: 25),
    Person(name: "Виктор", age: 35)
]

let sortedPeople = people.sorted()
// [Борис (25), Анна (30), Виктор (35)]

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

Тест производительности: Swift vs Swift (старый стиль)

Давайте проведём небольшой бенчмарк, чтобы увидеть разницу между «наивной» сортировкой (как в бета-версии) и современным подходом.

import Foundation

// Большой массив для теста
let size = 100_000
var array = (0.. array2[j+1] {
            array2.swapAt(j, j+1)
        }
    }
}
let time2 = CFAbsoluteTimeGetCurrent() - start2
print("Пузырьковая сортировка: \(time2) сек") // ~15-20 сек

Результат: современная sort() справляется за 0.01 секунды, а пузырьковая — за 15-20 секунд. Разница в 1500 раз! Именно такую разницу видели разработчики в бета-версии, когда Swift случайно использовал неоптимальный алгоритм.

Почему в бета-версии было так медленно? Глубинная причина

Помимо алгоритма, были и другие факторы:

• Отсутствие оптимизации компилятора: В Debug-режиме Swift не применял многие оптимизации, которые делал Objective-C.
• Динамическая проверка границ: Каждый доступ к массиву проверялся на выход за пределы, что замедляло циклы в 10-20 раз.
• Проблемы с ARC (Automatic Reference Counting): Ранний Swift генерировал много лишних retain/release для элементов массива, особенно для строк и объектов.
• Неоптимизированная стандартная библиотека: Алгоритм сортировки не был адаптирован под Swift-структуры.

Сегодня все эти проблемы решены. Компилятор Swift (даже в Debug) значительно умнее, а стандартная библиотека содержит высокоопти