This is heapsort in a Swift playground. I needed a stable sort, so naturally I wrote an… unstable sort.
Of course, you can just use sort() or sorted(), but if you are inclined to roll your own, the Swifty way to do it is to create an extension. Note that an Array extension with a Generic Where Clause is needed to make element comparisons > < == work.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
//: Playground - noun: a place where people can play import Cocoa // var elements = [0, 6, 0, 6, 4, 0, 6, 0, 6, 0, 4, 3, 0, 1, 5, 1, 2, 4, 2, 4] var elements = [10, 6, 0, 1, 2, 5, 4, 3, 7, 8, 9] extension Array where Element: Comparable { func heapSorted() -> Array { var r = self func parent(_ i: Int) -> Int { return ((i+1) / 2) - 1 } func leftChild(_ i: Int) -> Int { return ((i + 1) * 2) - 1 } func rightChild(_ i: Int) -> Int { return leftChild(i) + 1 } func descend(i: Int, limit: Int) { let lindex = leftChild(i) let rindex = rightChild(i) if rindex > limit || r[lindex] > r[rindex] { if lindex <= limit && r[lindex] > r[i] { (r[lindex],r[i]) = (r[i],r[lindex]) descend(i: lindex, limit: limit) } } else if rindex <= limit { if r[rindex] > r[i] { (r[rindex],r[i]) = (r[i],r[rindex]) descend(i: rindex, limit: limit) } } } func maxHeapify() { let lastParent = parent(r.count - 1) for i in (0...lastParent).reversed() { descend(i: i, limit: r.count - 1) } } func sortFromHeap() { for i in (1..<r.count).reversed() { (r[0],r[i]) = (r[i],r[0]) descend(i: 0, limit: i-1) } } maxHeapify() sortFromHeap() return r } } elements.heapSorted().forEach{print($0, terminator: " ")} print() |
On to writing mergesort (stable).
Sigh.
