Сортировка коллекций

Для некоторых типов коллекций является важным аспектом то, как упорядочены их элементы. Например, два списка с одинаковыми элементами не равны, если их элементы упорядочены по-разному.

В Kotlin порядок объектов можно задать несколькими способами.

Во-первых, существует естественный порядок (ориг. natural order). Он характерен для наследников интерфейса Comparable. Если не был указан другой порядок сортировки, то они будут отсортированы в естественном порядке.

Большинство встроенных типов являются Comparable:

  • Числовые типы используют традиционный числовой порядок: 1 больше, чем 0; -3.4f больше, чем -5f и т.д.
  • Char и String используют лексикографический порядок: b больше, чем a; world больше, чем hello.

Таким образом, чтобы ваш собственный класс при сортировке использовал естественный порядок, сделайте его наследником Comparable. Дополнительно потребуется реализовать функцию compareTo(). В качестве аргумента она должна принимать другой объект такого же типа, а возвращать целое число, указывающее, какой из объектов больше:

  • Положительное значение показывает, что объект-приёмник больше аргумента.
  • Отрицательное значение показывает, что объект-приёмник меньше аргумента.
  • Ноль показывает, что объекты равны.

В примере ниже показан класс для сортировки версий, состоящий из переменных major и minor.

class Version(val major: Int, val minor: Int): Comparable<Version> {
    override fun compareTo(other: Version): Int {
        if (this.major != other.major) {
            return this.major - other.major
        } else if (this.minor != other.minor) {
            return this.minor - other.minor
        } else return 0
    }
}

fun main() {    
    println(Version(1, 2) > Version(1, 3)) // false
    println(Version(2, 0) > Version(1, 5)) // true
}

Пользовательский порядок (ориг. custom order) позволяет вам сортировать экземпляры любого типа так, как вам нравится. В частности, вы можете определить порядок для сортировки объектов, не являющихся наследниками Comparable, а также задать Comparable типам порядок, отличный от естественного. Осуществляется это при помощи Comparator. У Comparator есть функция compare(), которая принимает два объекта, а в качестве результата сравнения возвращает целое число. Результат интерпретируется так же, как описано выше для функции compareTo().

fun main() {
    val lengthComparator = Comparator { str1: String, str2: String -> str1.length - str2.length }
    println(listOf("aaa", "bb", "c").sortedWith(lengthComparator)) // [c, bb, aaa]
}

С помощью lengthComparator вы можете изменить порядок сортировки строк: вместо сортировки в лексикографическом порядке они будут отсортированы по длине.

Существует более упрощённый вариант использования Comparator - функция compareBy() из стандартной библиотеки. Она принимает лямбда-функцию, которая из объекта создаёт Comparable значение и задаёт пользовательский порядок, который по факту представляет из себя естественный порядок созданных Comparable значений.

Используя compareBy() можно модифицировать lengthComparator из примера выше следующим образом:

fun main() {  
    println(listOf("aaa", "bb", "c").sortedWith(compareBy { it.length })) // [c, bb, aaa]
}

Kotlin предоставляет функции, которые позволяют сортировать коллекции в естественном, пользовательском и даже в случайном порядке. В текущем разделе рассмотрены функции сортировки, которые работают только с неизменяемыми коллекциями. Такие функции возвращают результат сортировки в виде новой коллекции, содержащей элементы исходной коллекции, но упорядоченные в соответствии с заданным условием. Информация о функциях для сортировки изменяемых коллекций находится в разделе List: специфичные операции.

Естественный порядок

Основные функции sorted() и sortedDescending() возвращают элементы коллекции, отсортированные по возрастанию или убыванию в соответствии с их естественным порядком. Эти функции могут быть применены к коллекциям, содержащим элементы Comparable типа.

fun main() {
    val numbers = listOf("one", "two", "three", "four")

    println("Sorted ascending: ${numbers.sorted()}") // Sorted ascending: [four, one, three, two]
    println("Sorted descending: ${numbers.sortedDescending()}") // Sorted descending: [two, three, one, four]
}

Пользовательский порядок

Для сортировки объектов в пользовательском порядке или для сортировки объектов, не являющихся наследниками Comparable, существуют функции sortedBy() и sortedByDescending(). Они используют функцию-селектор для преобразования элементов коллекции в Comparable значения и сортируют коллекцию в естественном порядке этих значений.

fun main() {
    val numbers = listOf("one", "two", "three", "four")

    val sortedNumbers = numbers.sortedBy { it.length }
    println("Sorted by length ascending: $sortedNumbers") // Sorted by length ascending: [one, two, four, three]
    val sortedByLast = numbers.sortedByDescending { it.last() }
    println("Sorted by the last letter descending: $sortedByLast") // Sorted by the last letter descending: [four, two, one, three]
}

Чтобы задать пользовательский порядок для сортировки коллекции, вы можете предоставить свой собственный Comparator. Для этого вызовите функцию sortedWith() и передайте ей свой Comparator. С помощью этой функции сортировка строк по их длине будет выглядеть следующим образом:

fun main() {
    val numbers = listOf("one", "two", "three", "four")
    println("Sorted by length ascending: ${numbers.sortedWith(compareBy { it.length })}") // Sorted by length ascending: [one, two, four, three]
}

Обратный порядок

С помощью функции reversed() вы можете получить коллекцию, отсортированную в обратном порядке.

fun main() {
    val numbers = listOf("one", "two", "three", "four")
    println(numbers.reversed()) // [four, three, two, one]
}

reversed() возвращает новую коллекцию с копиями элементов из исходной коллекции. Поэтому, если вы измените исходную коллекцию, это не повлияет на ранее полученный от reversed() результат.

Другая функция - asReversed() - возвращает перевёрнутое представление исходной коллекции. Эта функция может быть более легковесной и предпочтительной, чем reversed(), при условии, что исходная коллекция не будет изменяться.

fun main() {
    val numbers = listOf("one", "two", "three", "four")
    val reversedNumbers = numbers.asReversed()
    println(reversedNumbers) // [four, three, two, one]
}

Если же в исходную коллекцию будут внесены изменения, все эти изменения отразятся в её перевёрнутых представлениях и наоборот.

fun main() {
    val numbers = mutableListOf("one", "two", "three", "four")
    val reversedNumbers = numbers.asReversed()
    println(reversedNumbers) // [four, three, two, one]
    numbers.add("five")
    println(reversedNumbers) // [five, four, three, two, one]
}

Однако, если источник не является списком, либо неизвестно является ли список изменяемым, тогда функция reversed() более предпочтительна для использования, поскольку она возвращает копию, которая в будущем не изменится.

Случайный порядок

Наконец, существует функция shuffled(), которая возвращает новый List, содержащий элементы исходной коллекции в случайном порядке. Её можно вызывать либо без аргументов, либо с объектом Random.

fun main() {
     val numbers = listOf("one", "two", "three", "four")
     println(numbers.shuffled()) // [three, four, one, two]
}