ちょっとアルゴニズム - Quicksort(Swift)

クイックソート｜大きい順 - Qiita

raywenderlich/swift-algorithm-club

最初のリンクがPythonでの処理で、下がSwiftでのソート例です。

Swiftのコードです。すっきりしています。

func quicksort<T: Comparable>(_ a: [T]) -> [T] {
 
    guard a.count > 1 else { return a }
 
    let pivot = a[a.count/2]
 
    let less = a.filter { $0 < pivot }
 
    let equal = a.filter { $0 == pivot }
 
    let greater = a.filter { $0 > pivot }

    return quicksort(less) + equal + quicksort(greater)
}

guard a.count > 1 else { return a }

で1個以上の配列を対象にしています。

let pivot = a[a.count/2]

pivot と呼ばれる、基準にする値を決めます。この場合配列の真ん中の値を基準の値としています。

let less = a.filter { $0 < pivot }
let equal = a.filter { $0 == pivot }
let greater = a.filter { $0 > pivot }

そして、基準の値と比べて、大きい、

3つのグループにフィルターで分けます。

return quicksort(less) + equal + quicksort(greater)

そして返り値を取得して、quicksort()で再帰処理します。

分割統治法とも呼ばれ、pivotを基準に分割して並び替えするという操作を再帰で実行しています。pivotですが配列の最初にする例示が多いようですが、その数値を基準とするだけなので理解しやすい、わかりやすいところで良いです。