Kotlinでアルゴリズムとデータ構造 ソート編

参考

この記事では酒井潤さんが「アルゴリズムとデータ構造」をpythonで解説されてるudemyの講座を基にKotlinで再現しています。
酒井さんのツイート
https://twitter.com/sakaijun/status/1322222298422632449
講座url
https://udemy.com/course/python-algo/?couponCode=80515F7DEDBC4776BF87

ソートとは

データの集合を一定の規則に従って並べかえることを言います。ソートに使われるアルゴリズムは様々で、コストとの兼ね合いで使用するアルゴリズムを選択します。それぞれのソートのコストについては「ソート　時間計算量」などと計算するといい記事が見つかるかと思います。
[5, 8, 1, 4] 昇順にソート -> [1, 4, 5, 8]

バブルソート

＊ソートされる仕組み
①　隣あうリストの要素を比較して左の要素 > 右の要素だった場合二つの位置を入れ替える。これを全て要素に適用することでリスト内で最も大きい要素が一番右へ移動する。　　　　　　　　　　　　　　　　　　　　　　
② 1によって右端の要素が最も大きいことがわかっているので最右端の要素を抜きにして1を行う。
③ 2を繰り返すことによって大きい要素が右に移動し続け最終的に昇順のリストが完成

fun bubbleSort(numbers: MutableList<Int>): List<Int>{
        val lenNumbers = numbers.size
        for (i in 0 until lenNumbers){
            for(j in 0 until lenNumbers - 1 - i){  //②
                if (numbers[j] > numbers[j+1]){  //①
                    val temp = numbers[j]
                    numbers[j] = numbers[j+1]
                    numbers[j+1] = temp
                }
            }
        }
        return numbers
    }

    val numbers = mutableListOf<Int>(2, 5, 1, 8, 7, 3)
    print(bubble_sort(numbers))

   //出力結果　[1, 2, 3, 5, 7, 8]

＊細かい解説
for(j in 0 until len_numbers - 1 - i)
- 1の意味→隣り合う要素を比較する際numbers[ j ]とnumbers[ j+1]を比較しているのでインデックス番号はリストの最後の1個手前まで取得すればOK。
- iの意味→最右端の要素を抜きにして1を行うために- iをしている。

選択ソート

＊ソートされる仕組み
① 最左端の要素を暫定最小の要素として左端のインデックス番号を変数min_idxに保存
② numbers[ min_idx ]とその他の要素を１つ１つ比較し、numbers[ min_idx ]よりも小さい要素が見つかった場合その要素のインデックス番号でmin_idxを更新
③ numbers[ min_idx ]とnumbers[ i ]の値を入れ替える

    fun selectSort(numbers: MutableList<Int>): List<Int>{
        val lenNumbers = numbers.size
        for (i in 0 until lenNumbers){
            var minIdx = i  //①
            for (j in i + 1 until lenNumbers){
                if (numbers[minIdx] > numbers[j]) minIdx = j  //②
            }

            val temp = numbers[i]  //③
            numbers[i] = numbers[minIdx]
            numbers[minIdx] = temp
        }
        return numbers
    }

    val numbers = mutableListOf<Int>(2, 5, 1, 8, 7, 3)
    println(select_sort(numbers))
   //出力結果[1, 2, 3, 5, 7, 8]

＊細かい解説
for ( j in i + 1 until len_numbers)
i + 1の意味→min_idx(初期値がi)と比較するためi + 1とすることでiの一つ右隣のインデックス番号からスタートできる

min_idxの値が更新されなくてもnumbers[ i ]とnumbers[ min_idx ]を交換してもいいのか→min_idxの値が更新されない場合min_idxは初期値 i のままなのでnumbersに変化は起きない

挿入ソート

*特徴
適当な箇所を見つけて要素を挿入する

① tempにnumbers[ i ]を代入
② 変数jの初期値をi-1とする　　 *この時点で j は i の左隣
③ while文の条件がtrueの場合で numbers[ j +1]とnumbers[ j ]の位置を入れ替え、j をデクリメントする。
④ 3をwhile文がfalseになるまで繰り返すことでnumbers[ j ] の適切な位置を見つけることができる。
⑤ 余分にデクリメントされているので１を足し合わせnumbers[ j + 1]にtempを代入する

fun insertionSort(numbers: MutableList<Int>): List<Int>{
        val lenNumbers = numbers.size
        for (i in 1 until lenNumbers){
            val temp = numbers[i]  //①
            var j = i - 1  //②
            while (j  >= 0 && numbers[j] > temp){
                numbers[j+1] = numbers[j]  //③
                j -= 1
            }
            numbers[j+1] = temp  //⑤
        }
        return numbers
    }

    val numbers = mutableListOf<Int>(2, 5, 1, 8, 7, 3)
    println(insertionSort(numbers))
   //出力結果[1, 2, 3, 5, 7, 8]

＊細かい解説
for文を１から始める理由→tempの左どなりの要素のインデックス番号として j を定義するので１から始めている

終わり

アルゴリズムとデータ構造の解説はpythonやC言語でされてることが多いので、Kotlinしか知らんけど勉強したいという方の参考になれば！