【Kotlin練習問題】コレクション：ソート（並び替え）

コレクションにおける要素の順番
問題
- 答え
完全無料で通えるプログラミングスクール
おすすめ書籍

コレクションにおける要素の順番

コレクションの要素の順番は特定のコレクション型においては重要な側面と言えます。

例えば、要素が全く同じ2つのリストでも、要素の順番が違うと等しいものとはみなされません。

Kotlinではオブジェクトの順番はいくつかの方法で定義することができます。はじめに順番の種類を確認しておきましょう。

ナチュラルオーダー（通常順）

一つ目はナチュラルオーダー（natural order）と呼ばれるものです。
これはComparableインターフェースを継承しているクラスに対して定義されます。他の順番が指定されていないときに適用されます。

ほとんどの組み込み型はComparableインターフェースを継承しているので、最初から比較できるようになっています。

数値型は「1は0より大きい」や「-3.4fは-5fより大きい」というように、伝統的な順番を用いています。
CharとStringは辞書と同じ形式の順番を用いています。”b”は”a”より後や、”world”は”hello”よりあとといった感じです。

自分で定義した型にナチュラルオーダーを定義するには、その型にComparableを継承させます。そのためにはcompareTo()関数を実装しなければなりません。またcompareTo()は同じ型の別のオブジェクトを引数にとり、対象となっているオブジェクトとどちらが大きいかを示すInt値を返すようにします。

正の数はcompareToが使われているオブジェクト（レシーバーオブジェクト）のほうが引数のオブジェクトよりも大きいことを意味します。
負の数は引数よりも小さいことを意味します。
0はレシーバーオブジェクトと引数が等しいことを意味します。

以下が実装例です。

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 両オブジェクトのmajorは等しいがminorは右辺のほうが大きいため
    println(Version(2, 0) > Version(1, 5)) //true　左辺のmajorが右辺よりも大きいため
}

基本的な関数であるsorted()とsortedDescending()はナチュラルオーダーで昇順、または降順に並び替えられたコレクションの要素を返します。この関数はComparableを継承している要素のコレクションに適用できます。

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]

カスタムオーダー

カスタムオーダー（custom order）はどの型のインスタンスでも好きなように並び替えることができます。

Comparableを継承していないため比較出来ないオブジェクトに対してや、比較できるオブジェクトにナチュラルオーダー以外の順番を定義したりすることができます。

カスタムオーダーをある型に定義するには、Comparatorをその型に作成してあげます。
Comparatorはcompare()という関数を含んでおり、そのクラスのインスタンスを2つ、引数にとり、それらの比較結果を示すIntを返します。比較結果のIntは上のcompareTo()で示したものと同じ方式で解釈されます。

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

上はString型を辞書形式ではなく、lengthComparatorを使うことで文字の長さで比べるカスタムオーダーの例です。

Comparatorを実装するより簡単な方法はスタンダードライブラリのcompareBy()関数という使います。

compareBy()はインスタンスからComparable値を生成するラムダ関数を引数にとり、生成された値のナチュラルオーダーで並び替えるカスタムオーダーを定義します。紛らわしい言い回しになってしまいますが、もともとのインスタンスのナチュラルオーダーではありません。

compareBy()を用いると、上のコードは以下のように書き換えられます。

println(listOf("aaa", "bb", "c").sortedWith(compareBy { it.length }))

比較出来ないオブジェクトをカスタムオーダーで並び替えるには、sortedBy()またはsortedByDescending()を用います。
これらはコレクションの要素をComparable値にするためのセレクター関数をとり、その値のナチュラルオーダーで並び替えます。以下が使用例です。

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を使用することもできます。

それにはComparatorにsortedWith()関数を渡します。この関数を用いて、文字列を長さで並び替えるコードを書くと以下のようになります。

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()関数を用いることで、逆順に並び替えたコレクションを取得することができます。

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

reversed()で返されたコレクションはもとのコレクションの要素をコピーした新しいコレクションなので、もとのコレクションを後で変更しても、すでにreversed()で取得されたコレクションには影響しません。

ランダムオーダー

最後がランダムオーダーです。Kotlinにはコレクションの要素をランダムに並び替えて格納された新しいリストを返す関数、shuffled()があります。引数なし、またはRandomオブジェクトを用いて呼び出すことができます。

val numbers = listOf("one", "two", "three", "four")
println(numbers.shuffled())

以上、Kotlinのコレクションのパッケージにはナチュラル、カスタム、さらにランダムオーダーでソートする関数が用意されています。このページでは読み込み専用のコレクションに適用できるソート関数を説明しました。

最後に確認問題を解いてみましょう。

問題

顧客（Customer）の注文数（Order）で降順に並び替えて返す関数を実装してください。

実装にはsortedByDescendingを使ってください。

なお、Shopクラスと全ての関連するクラスはShop.ktに含まれています。

問題コード：

// 顧客の注文数を降順で並び替えた顧客のリストを返す
fun Shop.getCustomersSortedByOrders(): List<Customer> =
        TODO()

Shop.kt

data class Shop(val name: String, val customers: List<Customer>)

data class Customer(val name: String, val city: City, val orders: List<Order>) {
    override fun toString() = "$name from ${city.name}"
}

data class Order(val products: List<Product>, val isDelivered: Boolean)

data class Product(val name: String, val price: Double) {
    override fun toString() = "'$name' for $price"
}

data class City(val name: String) {
    override fun toString() = name
}

答え

fun Shop.getCustomersSortedByOrders(): List<Customer> =
        customers.sortedByDescending { it.orders.size }

［解説］

セレクター関数として、it.orders.sizeを取ることで顧客の注文数の数を比較しています。

考える順番としては、まずShopクラスに対して使う関数なので、Shopクラスのcustomers（List型）に対してsortedByDescendingを使い、そのcustomersの中のそれぞれのcustomerがもつorders（List型）のサイズ（ordersに含まれるorderの数＝注文数）を調べています。

答え

その他の問題はこちらからどうぞ。