すずろぐ

人生大逆転を目指す、鈴木俊吾の成長日記

Kotlin 整数リストの選択ソートプログラムを作成してみた

f:id:Suzushin:20170429140030j:plain

こんにちは、すずしんです。

今日は、Kotlinの学習をしてみました。
Kotlinのおおまかな仕様を確認した後で、どんなプログラムを書こうかなと考えていたのですが…。
ここはやはり比較的入門しやすいソートのプログラムを書いてみようとなりました。
そこで、今回は整数リスト選択ソートをするプログラムを作成してみました。

選択ソートとは?

選択ソートというのは、配列の最小値(最大値)を持つ要素を探して、それを配列の先頭要素と交換することで整列を行っていくソートアルゴリズムです。
最悪計算量はO(n2)と遅いのですが、実装が単純なためしばしば用いられることがあります。

ここでは、昇順で値を並びかえることを考えます。
選択ソートでは、まずデータ列の中で最も小さい値を探し、1番目の要素と交換します。
続いて2番目以降のデータ列から最も小さい値を探し、2番目の要素と交換します。
このような手順を、データ列の最後(の1回前)まで繰り返すとソートが完了します。

数字を使った選択ソートの例は以下のような感じです。
各回で最も小さい値を探して、値を入れ替えるという手順を踏みます。

5 9 1 4 7 (初期状態)
1 9 5 4 7 (1回目)
1 4 5 9 7 (2回目)
1 4 5 9 7 (3回目)
1 4 5 7 9 (4回目)
1 4 5 7 9 (終了)

Kotlinでの選択ソート

今回私が作成した、Kotlin版選択ソートのソースコードは以下のような感じです。

main関数では、まずScannerを用意して標準入力を受け付ける準備をします。
そして、整数のリストとなる文字列を入力してもらい、それを整数のMutableListに変換します。
そのリストの内容を表示して初期状態を確認してから、ソートを行い、再びリストの内容を表示しています。
sort関数では、forループでインデックスを更新しながら、各回の最小値を探して交換する作業を繰り返しています。

import java.util.*

fun main(args: Array<String>) {
    val scanner: Scanner = Scanner(System.`in`)
    val n: MutableList<Int> = scanner.nextLine().split(",").map({ it.toInt() }).toMutableList()
    scanner.close()

    println(n)
    sort(n)
    println(n)
}

fun sort(n: MutableList<Int>) {
    var tmp: Int
    var minIndex: Int
    for(i in n.indices.filter({ it < n.size - 1 })) {
        minIndex = i
        n.indices.filter({ it >= i + 1 }).forEach({ j -> if(n[j] < n[minIndex]) minIndex = j })
        if(minIndex != i) {
            tmp = n[i]
            n[i] = n[minIndex]
            n[minIndex] = tmp
        }
    }
}

今回のプログラムを作成するにあたって困ったのが、forループの回数指定です。
forループ中に使うためのインデックス(i, j)の範囲を指定する方法が最初分からず悩みましたが…。
filter()を使えば上手くいくかもと思って、試しにやってみたところ良い感じになりました。

私はJavaでも選択ソートのプログラムを書いたことがありますが…。
Javaとは若干プログラムの雰囲気が違います。
Kotlinに慣れてしまうと、こちらの方が書きやすくなるのでしょうかね?

実行結果

上記のプログラムを実行してみた結果の例は以下のような感じです。
整数のリストの入力は「,」で区切って入力します。
実行結果を見てみると、確かに昇順に並び替えられているのが分かりますね。

5,1,8,4,9,2,3,7,6
[5, 1, 8, 4, 9, 2, 3, 7, 6]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

ひとこと

今回はKotlinで選択ソートをするプログラムを作成してみましたが…。
アルゴリズムの基本的な考え方は他の言語とも同じですね。
後はどうやって実装するかの話になってきます。

私はまだまだですが…。
map()やfilter()などをうまく使いこなせるようになれば、もっと簡潔にプログラムを書けそうな感じがしますね。
スムーズにプログラムを作成できるようにもっと勉強しなければっ!

やはり、Hello Worldのプログラムと比べれば…。
だいぶプログラムを作成したという達成感がありますね。
今後はさらに高度な事ができるように、Kotlinの学習を続けていきたいと思います。

関連商品

amzn.to