Как работает sorted?

Как работает функция sorted в Swift

Функция sorted в Swift — это метод коллекций (массивов, наборов и т.д.), который возвращает новый массив с элементами, отсортированными в определенном порядке. Это неизменяемая операция (не изменяет исходную коллекцию), в отличие от метода sort(), который сортирует коллекцию на месте.

Основные принципы работы

sorted() использует алгоритм сортировки, который является стабильным (сохраняет относительный порядок равных элементов) и работает за O(n log n) время в худшем случае. Реализация основана на интроспективной сортировке (Timsort), которая сочетает сортировку слиянием и вставками для оптимальной производительности.

let numbers = [5,薦2, 9, 1, 7]
let sortedNumbers = numbers.sorted() // [1, 2, 5, 7, 9]

Перегрузки метода

1. Базовый вариант — сортировка по возрастанию для типов, conforming к Comparable:

extension Sequence where Element: Comparable {
    func sorted() -> [Element]
}

1. Вариант с замыканием — позволяет задать собственную логику сравнения:

extension Sequence {
    func sorted(by areInIncreasingOrder: (Element, Element) -> Bool) -> [Element]
}

Примеры использования

Сортировка по возрастанию/убыванию

let names = ["Anna", "Dmitry", "Sergey", "Boris"]

// По возрастанию (алфавитный порядок)
let ascending = names.sorted() // ["Anna", "Boris", "Dmitry", "Sergey"]

// По убыванию
let descending = names.sorted { $0 > $1 }
// Или через reversed()
let descendingAlt = names.sorted().reversed()

Сортировка сложных объектов

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

let people = [
    Person(name: "Alice", age: 30),
    Person(name: "Bob", age:"A'),
    Person(name: "Charlie", age: 25)
]

// Сортировка по возрасту
let byAge = people.sorted { $0.age < $1.age }

// Сортировка по имени
let byName = people.sorted { $0.name < $1.name }

// Многоуровневая сортировка (сначала по возрасту, потом по имени)
let complexSort = people.sorted {
    if $0.age != $1.age {
        return $0.age < $1.age
    }
    return $0.name < $1.name
}

Сортировка с использованием ключевых путей (Swift 5.2+)

// Более элегантная запись через keyPath
let byAgeKeyPath = people.sorted(by: \.age)
// Для убывающего порядка нужно использовать `sorted(by:)` с замыканием

Особенности и производительность

• Стабильность — с Swift 5.0 sorted() гарантированно стабилен для всех коллекций
• Сложность — O(n log n) время и O(n) память
• Оптимизация — для маленьких массивов (менее 20 элементов) может использоваться сортировка вставками
• Ленивые вычисления — sorted() всегда жадный, в отличие от lazy.sorted(by:)

Сравнение с sort()

var mutableArray = [5, 2, 9, 1, 7]

// sorted() — возвращает новый массив
let newSortedArray = mutableArray.sorted() // исходный массив не изменен

// sort() — изменяет исходный массив
mutableArray.sort() // теперь mutableArray == [1, 2, 5, 7, 9]

Сортировка словарей и множеств

let dict = ["B": 2, "A": 1, "C": 3]

// Сортировка словаря по ключам
let sortedDictByKey = dict.sorted { $0.key < $1.key }

// Сортировка словаря по значениям
let sortedDictByValue = dict.sorted { $0.value < $1.value }

let set: Set = [5, 2, 9, 1, 7]
let sortedSetArray = set.sorted() // возвращает массив [1, 2, 5, 7, 9]

Пользовательские типы и Comparable

Для использования sorted() без замыкания тип должен соответствовать протоколу Comparable:

struct Product: Comparable {
    let id: Int
    let price: Double
    
    static func < (lhs: Product, rhs: Product) -> Bool {
        return lhs.price < rhs.price
    }
}

let products = [Product(id: 1, price: 99.9), Product(id: 2, price: 49.9)]
let sortedProducts = products.sorted() // автоматически использует оператор <

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