【プログラミング初心者】Swift練習問題~ソート~回答例

ソート

回答例

func sort(list: [Int]) -> [Int] {
    var sortedList = list

    for currentIndex in 0..<sortedList.count {
        for sortIndex in (currentIndex + 1)..<sortedList.count {
            if sortedList[currentIndex] < sortedList[sortIndex] {
                let tmp = sortedList[currentIndex]
                sortedList[currentIndex] = sortedList[sortIndex]
                sortedList[sortIndex] = tmp
            }
        }
    }

    return sortedList
}

解説

降順ソートなので配列の0番から順に大きい値が格納されるように実装します。

ソートの考え方

この実装はバブルソートと呼ばれ、ソートにおいて最も基本となる考え方です。

[10, 11, 5, 15, 9, 2, 5]という配列を例にとって考え方を図で解説します。

最初の配列のイメージは以下の通りです。

ソート1.png

まず0番の配列に注目していきます。

はじめに0番と1番の値を比較します。
比較した結果10 < 11となるので0番と1番の値を入れ替え、大きい値を0番に格納します。

ソート2.png

次は0番と2番の値を比較します。
11 > 5となるので入れ替えは発生しません。

ソート3.png

その後0番と3~6番までの値を比較していき大きい方ければ0番の値と入れ替えます。
その結果配列は以下の状態になります。

ソート4.png

入れ替えが終わった結果0~6番の中で最大の値が0番に格納されています。

次は1番の配列に注目します。

先の処理で0番が最大値ということは確定しているため1番と2番から比較していきます。
10 > 5なのでここは入れ替えません。

ソート5.png

1番と3番を比較します。
10 < 11なので1番と3番の値を入れ替えます。

ソート6.png

ここからもやはり同様に1番と残りの4~6番まで比較していきます。
その結果、1~6番の中で最大値が1番として格納されることになります。

ここからまた注目する配列番号を2、3…とずらし、同じ操作を行っていくことで最終的に大きい順に並べ替えることができます。

ソート7.png

このように大きいものが泡のように上に上がってくるという意味でこのソート方法は「バブルソート」と呼ばれています。

実装

後はソートの考え方で解説した方法に沿って実装するだけです。

外側のループで注目する要素番号をずらし、配列の数だけループを回します。
currentIndexが注目する要素番号になります。

内側のループでcurrentIndexに格納されている値と比較します。
sortIndexが比較対象の要素番号です。
先程説明した通り比較対象の要素番号はcurrentIndexの次から始まるので
(currentIndex + 1)..<sortedList.countとしています。
※ 効率が悪くなりますが0..<sortedList.countとしてループを回しても結果は変わりません。

ifで値を比較し大きければ値を入れ替えています。
入れ替え処理は以下のようにしています。

let tmp = sortedList[currentIndex]
sortedList[currentIndex] = sortedList[sortIndex]
sortedList[sortIndex] = tmp

tmpという変数にsortedList[currentIndex]を格納しています。

直観的に

sortedList[currentIndex] = sortedList[sortIndex]
sortedList[sortIndex] = sortedList[currentIndex]

としてしまいたいところかも知れませんが、このようにするとはじめのsortedList[currentIndex] = sortedList[sortIndex]sortedList[currentIndex]の値が書き換わっています。
そのためsortedList[sortIndex] = sortedList[currentIndex]では書き換わった後の値を代入していることになり、sortedList[currentIndex]sortedList[sortIndex]は同じ値になってしまいます。

これを防ぐために一時的に値を格納する用の変数としてtmpを作り、値を入れ替えています。

あとはループが最後まで回ればソートが完了します。

ソートが完了したらあとは戻り値としてsortedListをreturnしてあげれば処理完了となります。

コメント

タイトルとURLをコピーしました