swift sort昇順

Question

var arr = [1,5,3,7,9,8]
var sortArr = arr.sorted(by:{(a:Int,b:Int) -> Bool in return a < b})
print(sortArr)

この配列を昇順に並べ替えるクロージャの流れがわかりません。
aとbの引数にどういう順番で配列の要素が入り、a < bこの判定がおこなわれるのでしょうか？

Answer 1

ソートにはいろんな種類がありますが、例えば バブルソート を Swift で書くとこんな感じになります。

func bubbleSort(_ arr: inout [Int]) {
   for i in 0..<(arr.count - 1) {
       for j in 0..<(arr.count - i - 1) {
           if arr[j + 1] < arr[j] {
               arr.swapAt(j, j + 1)
           }
       }
   }
}

Swift の配列のソートにはもっと賢いアルゴリズムが使われてるはずですが、大事なのはこの部分。

           if arr[j + 1] < arr[j] {
               arr.swapAt(j, j + 1)
           }

配列から 2 つの要素を取り出して比較して、その結果によって要素を並び替える、というのはどのソートアルゴリズムにも共通しています。そして、比較に < を使うと数値や文字列などの限られた型にしか適用できませんが、これをクロージャを使って書くことでさまざまな型の配列をいろんな順番でソートできるようになります。

なお、ソートの際にクロージャが実際に使われる様子は、次のようにすれば観察できます。

var arr = [1, 5, 3, 7, 9, 8]
var sortArr = arr.sorted(by: { (a:Int, b:Int) -> Bool in
  print("comparing (a) and (b) : (a < b)")
  return a < b
})
print(sortArr)

実行結果

comparing 5 and 1 : false
comparing 3 and 5 : true
comparing 3 and 1 : false
comparing 7 and 5 : false
comparing 9 and 7 : false
comparing 8 and 9 : true
comparing 8 and 7 : false
[1, 3, 5, 7, 8, 9]

Comments

[退会済みユーザー]

この実行結果を見るようにランダムで配列の要素が2つ入っているということでしょうか？5と1が最初に配列から抽出され入り、次に3と5が来るように何かの規則性があるのでしょうか？

[hoshi-takanori]

実際にどの順番で呼ばれるかはアルゴリズムによります。
https://qiita.com/r-ngtm/items/f4fa55c77459f63a5228

[TsukubaDepot]

横からすみません。
Swift5だと、TimSort と呼ばれるアルゴリズムが採用されているようです。

https://github.com/apple/swift/blob/main/stdlib/public/core/Sort.swift

446 行目あたりから説明がありますが、日本語で詳しい説明が必要であれば、TimSort をキーワードに調べればいくつかの解説が出てくるようです。