Sortieralgorithmen in Kotlin: Eine ausführliche Anleitung

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

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

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

• Отсортированные данные гораздо быстрее искать (вспомните поиск в телефонной книге)
• Многие алгоритмы требуют предварительно отсортированных данных
• Это основа для работы баз данных, поисковых систем и любого анализа данных

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

В Kotlin, как и в любом современном языке, есть встроенные методы сортировки. Но чтобы стать настоящим программистом, нужно понимать, что происходит «под капотом». Именно этому мы и научимся.

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

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

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

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

Сложность: O(n²) — очень медленно для больших массивов.

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

Вы ищете самый маленький элемент и ставите его в начало. Потом ищете второй по величине и ставите на второе место. И так далее. Как если бы вы перебирали колоду карт, каждый раз вытаскивая самую маленькую.

Сложность: O(n²) — тоже медленно, но чуть быстрее пузырька.

3. Сортировка вставками (Insertion Sort)

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

Сложность: O(n²) в худшем случае, но O(n) в лучшем (когда массив уже отсортирован).

4. Быстрая сортировка (Quick Sort)

Самый популярный алгоритм. Вы выбираете «опорный» элемент (pivot), а затем делите массив на две части: все элементы меньше опорного — слева, все больше — справа. Потом повторяете то же самое для каждой части. Это как если бы вы сортировали книги по году издания: сначала отделили старые от новых, потом каждую группу ещё раз поделили.

Сложность: O(n log n) в среднем, O(n²) в худшем (но это редко).

5. Сортировка слиянием (Merge Sort)

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

Сложность: O(n log n) — всегда, даже в худшем случае.

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

Kotlin предоставляет несколько способов сортировки. Давайте разберём их все.

Встроенные методы

Метод	Что делает	Возвращаемое значение	Пример
sorted()	Сортирует коллекцию по возрастанию	Новый список (оригинал не меняется)	list.sorted()
sortedDescending()	Сортирует по убыванию	Новый список	list.sortedDescending()
sort()	Сортирует изменяемый список на месте	Unit (изменяет оригинал)	mutableList.sort()
sortDescending()	Сортирует по убыванию на месте	Unit	mutableList.sortDescending()
sortedBy()	Сортирует по указанному свойству	Новый список	list.sortedBy { it.length }
sortBy()	Сортирует на месте по свойству	Unit	mutableList.sortBy { it.age }

Совет: Используйте sorted(), когда нужно сохранить оригинальный список. Используйте sort(), когда оригинал можно изменять — это экономит память.

Сортировка с компаратором

Если нужно задать сложные правила сортировки, используйте sortedWith() или sortWith():

// Сортировка строк по длине, а потом по алфавиту
val words = listOf("кот", "собака", "ёж", "тигр")
val sorted = words.sortedWith(compareBy({ it.length }, { it }))
println(sorted) // [ёж, кот, тигр, собака]

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

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

fun bubbleSort(arr: IntArray) {
    // Получаем длину массива
    val n = arr.size
    
    // Внешний цикл: делаем n-1 проходов
    for (i in 0 until n - 1) {
        // Внутренний цикл: сравниваем соседние элементы
        for (j in 0 until n - i - 1) {
            // Если текущий элемент больше следующего
            if (arr[j] > arr[j + 1]) {
                // Меняем их местами
                val temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
}

// Проверяем работу
fun main() {
    val numbers = intArrayOf(64, 34, 25, 12, 22, 11, 90)
    println("До сортировки: ${numbers.joinToString()}")
    bubbleSort(numbers)
    println("После сортировки: ${numbers.joinToString()}")
}

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

fun selectionSort(arr: IntArray) {
    val n = arr.size
    
    // Проходим по всем элементам
    for (i in 0 until n - 1) {
        // Считаем, что текущий элемент — минимальный
        var minIndex = i
        
        // Ищем реальный минимальный элемент в оставшейся части
        for (j in i + 1 until n) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j
            }
        }
        
        // Если нашли меньший элемент, меняем местами
        if (minIndex != i) {
            val temp = arr[i]
            arr[i] = arr[minIndex]
            arr[minIndex] = temp
        }
    }
}

fun main() {
    val numbers = intArrayOf(29, 10, 14, 37, 13)
    println("До: ${numbers.joinToString()}")
    selectionSort(numbers)
    println("После: ${numbers.joinToString()}")
}

Пример 3: Сортировка вставками (Insertion Sort)

fun insertionSort(arr: IntArray) {
    // Начинаем со второго элемента (первый считаем отсортированным)
    for (i in 1 until arr.size) {
        // Запоминаем текущий элемент
        val key = arr[i]
        var j = i - 1
        
        // Сдвигаем элементы, которые больше key, вправо
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]
            j--
        }
        
        // Вставляем key на правильное место
        arr[j + 1] = key
    }
}

fun main() {
    val numbers = intArrayOf(12, 11, 13, 5, 6)
    println("До: ${numbers.joinToString()}")
    insertionSort(numbers)
    println("После: ${numbers.joinToString()}")
}

Пример 4: Быстрая сортировка (Quick Sort)

fun quickSort(arr: IntArray, low: Int, high: Int) {
    if (low < high) {
        // Находим индекс опорного элемента
        val pi = partition(arr, low, high)
        
        // Рекурсивно сортируем левую и правую части
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)
    }
}

// Функция разделения массива
fun partition(arr: IntArray, low: Int, high: Int): Int {
    // Выбираем последний элемент как опорный
    val pivot = arr[high]
    
    // Индекс меньшего элемента
    var i = low - 1
    
    // Проходим по всем элементам
    for (j in low until high) {
        // Если текущий элемент меньше или равен опорному
        if (arr[j] <= pivot) {
            i++
            // Меняем местами
            val temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
        }
    }
    
    // Ставим опорный элемент на правильное место
    val temp = arr[i + 1]
    arr[i + 1] = arr[high]
    arr[high] = temp
    
    return i + 1
}

fun main() {
    val numbers = intArrayOf(10, 7, 8, 9, 1, 5)
    println("До: ${numbers.joinToString()}")
    quickSort(numbers, 0, numbers.size - 1)
    println("После: ${numbers.joinToString()}")
}

Пример 5: Сортировка слиянием (Merge Sort)

fun mergeSort(arr: IntArray) {
    // Базовый случай: массив из 1 элемента уже отсортирован
    if (arr.size <= 1) return
    
    // Делим массив пополам
    val mid = arr.size / 2
    val left = arr.copyOfRange(0, mid)
    val right = arr.copyOfRange(mid, arr.size)
    
    // Рекурсивно сортируем обе половины
    mergeSort(left)
    mergeSort(right)
    
    // Сливаем отсортированные половины
    merge(arr, left, right)
}

fun merge(arr: IntArray, left: IntArray, right: IntArray) {
    var i = 0 // Индекс в левом массиве
    var j = 0 // Индекс в правом массиве
    var k = 0 // Индекс в результирующем массиве
    
    // Сравниваем элементы и добавляем меньший
    while (i < left.size && j < right.size) {
        if (left[i] <= right[j]) {
            arr[k] = left[i]
            i++
        } else {
            arr[k] = right[j]
            j++
        }
        k++
    }
    
    // Добавляем оставшиеся элементы из левого массива
    while (i < left.size) {
        arr[k] = left[i]
        i++
        k++
    }
    
    // Добавляем оставшиеся элементы из правого массива
    while (j < right.size) {
        arr[k] = right[j]
        j++
        k++
    }
}

fun main() {
    val numbers = intArrayOf(38, 27, 43, 3, 9, 82, 10)
    println("До: ${numbers.joinToString()}")
    mergeSort(numbers)
    println("После: ${numbers.joinToString()}")
}

Пример 6: Сортировка списка объектов

// Создаём класс для примера
data class Student(val name: String, val grade: Int, val age: Int)

fun main() {
    val students = listOf(
        Student("Анна", 5, 17),
        Student("Борис", 3, 16),
        Student("Вика", 4, 18),
        Student("Глеб", 5, 16)
    )
    
    // Сортировка по оценке (по возрастанию)
    val byGrade = students.sortedBy { it.grade }
    println("По оценкам: $byGrade")
    
    // Сортировка по возрасту (по убыванию)
    val byAgeDesc = students.sortedByDescending { it.age }
    println("По возрасту (убыв): $byAgeDesc")
    
    // Сложная сортировка: сначала по оценке, потом по имени
    val complex = students.sortedWith(
        compareBy({ it.grade }, { it.name })
    )
    println("Сложная сортировка: $complex")
}

Пример 7: Сортировка с кастомным компаратором

fun main() {
    // Сортируем строки по их длине
    val words = listOf("яблоко", "груша", "слива", "ананас", "киви")
    
    // Сортировка по длине (сначала короткие)
    val byLength = words.sortedBy { it.length }
    println("По длине: $byLength")
    
    // Сортировка по последней букве
    val byLastChar = words.sortedBy { it.last() }
    println("По последней букве: $byLastChar")
    
    // Сортировка с кастомным правилом
    val custom = words.sortedWith(Comparator { a, b ->
        // Сначала сравниваем по длине
        val lengthCompare = a.length.compareTo(b.length)
        // Если длина одинаковая, сравниваем по алфавиту
        if (lengthCompare != 0) lengthCompare else a.compareTo(b)
    })
    println("Кастомная: $custom")
}

Сравнение с Python: чем похоже и чем отличается

Характеристика	Kotlin	Python
Встроенная сортировка	sorted(), sort()	sorted(), list.sort()
Сортировка по ключу	sortedBy { it.property }	sorted(key=lambda x: x.property)
Сортировка на месте	mutableList.sort()	list.sort()
Типизация	Строгая, нужно указывать типы	Динамическая, типы не указываются
Производительность	Выше (компилируется в JVM)	Ниже (интерпретируемый)
Синтаксис лямбд	{ it.property }	lambda x: x.property

Главное отличие: В Kotlin вы обязаны указать тип данных, с которыми работаете. Это делает код более надёжным, но требует большего внимания к деталям. Python прощает больше ошибок, но может «выстрелить в ногу» в самый неожиданный момент.

Типичные ошибки и подводные камни

1. Забыли про мутабельность

// ОШИБКА: sorted() возвращает новый список, не изменяя оригинал
val list = listOf(3, 1, 2)
list.sorted() // Это не изменит list!
println(list) // [3, 1, 2] — не отсортировано!

// ПРАВИЛЬНО:
val sortedList = list.sorted()
println(sortedList) // [1, 2, 3]

2. Сортировка null-значений

// ОШИБКА: если в списке есть null, sortedBy упадёт
val list = listOf("a", null, "b")
// list.sortedBy { it.length } // NullPointerException!

// ПРАВИЛЬНО: используем sortedByNullable
val sorted = list.sortedBy { it?.length ?: 0 }
println(sorted) // [null, "a", "b"]

3. Изменение коллекции во время сортировки

// ОШИБКА: ConcurrentModificationException
val list = mutableListOf(1, 2, 3)
for (item in list) {
    if (item == 2) {
        list.remove(item) // Ошибка!
    }
}

// ПРАВИЛЬНО: используем итератор
val iterator = list.iterator()
while (iterator.hasNext()) {
    if (iterator.next() == 2) {
        iterator.remove()
    }
}

4. Сортировка по умолчанию для пользовательских типов

// ОШИБКА: если не реализовать Comparable
class Person(val name: String)
val people = listOf(Person("Анна"), Person("Борис"))
// people.sorted() // Ошибка компиляции!

// ПРАВИЛЬНО: реализуем Comparable или используем sortedBy
data class Person(val name: String) : Comparable {
    override fun compareTo(other: Person) = name.compareTo(other.name)
}

Лучшие практики и советы профессионалов

1. Всегда используйте встроенные методы, когда это возможно

Kotlin предоставляет оптимизированные алгоритмы сортировки. Не пишите свою пузырьковую сортировку для продакшена — используйте sorted() или sort().

2. Выбирайте правильный алгоритм для задачи

Ситуация	Рекомендуемый алгоритм
Маленький массив (до 50 элементов)	Сортировка вставками
Большой массив, нужна скорость	Быстрая сортировка
Нужна стабильная сортировка	Сортировка слиянием
Массив почти отсортирован	Сортировка вставками
Ограничена память	Пирамидальная сортировка (Heap Sort)

3. Используйте sortedBy для читаемости

// ПЛОХО: трудно читать
list.sortedWith(Comparator { a, b -> a.length.compareTo(b.length) })

// ХОРОШО: понятно с первого взгляда
list.sortedBy { it.length }

4. Не забывайте про sortedDescending

// Вместо этого:
list.sortedBy { -it.length }

// Делайте так:
list.sortedByDescending { it.length }

5. Тестируйте на граничных случаях

// Всегда проверяйте:
val emptyList = emptyList()
val singleElement = listOf(1)
val allSame = listOf(5, 5, 5)
val alreadySorted = listOf(1, 2, 3)
val reversed = listOf(3, 2, 1)

Вопросы для самопроверки

1. Вопрос: Какая сложность у пузырьковой сортировки в худшем случае?
   Ответ: O(n²). Потому что мы делаем n проходов, и на каждом проходе сравниваем n элементов.
2. Вопрос: Чем отличается sorted() от sort() в Kotlin?
   Ответ: sorted() возвращает новый отсортированный список, не изменяя оригинал. sort() сортирует изменяемый список на месте и ничего не возвращает.
3. Вопрос: Какой алгоритм сортировки самый быстрый в среднем случае?
   Ответ: Быстрая сортировка (Quick Sort) со сложностью O(n log n).
4. Вопрос: Что произойдёт, если вызвать sorted() на списке с null-значениями?
   Ответ: Будет выброшено исключение NullPointerException. Нужно использовать sortedBy с обработкой null.
5. Вопрос: Как отсортировать список объектов по двум полям?
   Ответ: Использовать sortedWith(compareBy({ поле1 }, { поле2 })).
6. Вопрос: В чём преимущество сортировки слиянием перед быстрой сортировкой?
   Ответ: Сортировка слиянием всегда работает за O(n log n), даже в худшем случае. Быстрая сортировка может деградировать до O(n²).
7. Вопрос: Какой алгоритм лучше использовать для почти отсортированного массива?
   Ответ: Сортировку вставками — она работает за O(n) на почти отсортированных данных.
8. Вопрос: Что такое «стабильная сортировка»?
   Ответ: Это сортировка, которая сохраняет относительный порядок равных элементов. Например, если два студента имеют одинаковую оценку, они останутся в том же порядке, что и были.
9. Вопрос: Как отсортировать список строк по убыванию длины?
   Ответ: list.sortedByDescending { it.length }.
10. Вопрос: Почему не стоит писать свою сортировку для продакшена?
    Ответ: Встроенные методы Kotlin оптимизированы, протестированы и используют лучшие алгоритмы. Ваша реализация, скорее всего, будет медленнее и содержать ошибки.

Итог и что изучить дальше

Мы прошли долгий путь от простой пузырьковой сортировки до сложных алгоритмов вроде быстрой сортировки и сортировки слиянием. Теперь вы знаете:

• Как работают основные алгоритмы сортировки
• Как использовать встроенные методы Kotlin
• Как писать свои реализации для учебных целей
• Какие ошибки чаще всего допускают новички
• Как выбирать правильный алгоритм для задачи

Что изучать дальше:

1. Пирамидальная сортировка (Heap Sort) — ещё один алгоритм со сложностью O(n log n), который использует структуру данных «куча».
2. Сортировка подсчётом (Counting Sort) — работает за O(n + k), но только для целых чисел в ограниченном диапазоне.
3. Поразрядная сортировка (Radix Sort) — сортирует числа по разрядам, очень быстрая для чисел.
4. Алгоритмы поиска — бинарный поиск, поиск подстроки, поиск в графах.
5. Структуры данных — деревья, хеш-таблицы, кучи — они помогут понять, как работают продвинутые алгоритмы.

Запомните: Сортировка — это не просто алгоритм. Это способ мышления. Когда вы научитесь сортировать данные, вы научитесь думать как программист. А это — самый ценный навык в нашей профессии.

Практикуйтесь, пишите код, экспериментируйте с разными алгоритмами. И помните: лучший способ понять алгоритм — реализовать его своими руками. Удачи в программировании!