Instantly share code, notes, and snippets.

Embed
What would you like to do?
Heap Sort Swift
//Safe bounds check for Array
//http://stackoverflow.com/questions/25329186/safe-bounds-checked-array-lookup-in-swift-through-optional-bindings
extension Collection {
/// Returns the element at the specified index iff it is within bounds, otherwise nil.
subscript (safe index: Index) -> Iterator.Element? {
return index >= startIndex && index < endIndex ? self[index] : nil
}
}
//Helper function to exchange position in one array
//From: http://stackoverflow.com/questions/24077880/swift-make-method-parameter-mutable
func exchange<T>(_ data: inout [T], i:Int, j:Int) {
let temp:T = data[i]
data[i] = data[j]
data[j] = temp
}
//Heap Sort methods
func leftLeafIndex(_ rootIndex:Int)->Int{
let heapIndex = rootIndex+1
return heapIndex*2-1
}
func rightLeafIndex(_ rootIndex:Int)->Int{
let heapIndex = rootIndex+1
return heapIndex*2
}
func heapLastIndex<T:Comparable>(_ A:Array<T>)->Int{
return A.count-1
}
func parentOfNode<T:Comparable>(_ A:Array<T>, indexNode:Int)->Int{
return indexNode/2
}
func maxHeapify<T:Comparable>(_ A:inout Array<T>,indexRoot:Int){
if leftLeafIndex(indexRoot)>heapLastIndex(A) {return}
let rootValue = A[indexRoot] as T
var largestIndex = indexRoot
var largestValue = rootValue
if let leftLeafValue:T = A[safe:leftLeafIndex(indexRoot)] {
if leftLeafValue > largestValue {
largestValue = leftLeafValue
largestIndex = leftLeafIndex(indexRoot)
}
}
if let rightLeafValue:T = A[safe:rightLeafIndex(indexRoot)] {
if rightLeafValue > largestValue {
largestValue = rightLeafValue
largestIndex = rightLeafIndex(indexRoot)
}
}
if largestIndex != indexRoot {
exchange(&A, i: indexRoot, j: largestIndex)
maxHeapify(&A,indexRoot: largestIndex)
}}
func buildMaxHeap<T:Comparable>(_ A:inout Array<T>){
if A.count<2 {return}
var lastParentIndex:Int = A.count/2
while lastParentIndex >= 0 {
maxHeapify(&A, indexRoot: lastParentIndex)
lastParentIndex -= 1;
}
}
func heapSort<T:Comparable>(_ A:Array<T>)->Array<T>{
var A = A
if A.count<2 {return A}
buildMaxHeap(&A)
var sortedA:Array<T> = []
while A.count>1 {
sortedA.insert(A[0], at: 0)
exchange(&A, i: 0, j: A.count-1)
A.removeLast()
maxHeapify(&A, indexRoot: 0)
}
sortedA.insert(A[0], at: 0)
return sortedA
}
// Heap Sort MAX-Priority Queue
func maxNode<T:Comparable>(_ A:Array<T>)->T{
return A[0]
}
func extractMaxNode<T:Comparable>(_ A:inout Array<T>)->T{
let max = A[0]
A[0] = A[A.count-1]
A.removeLast()
maxHeapify(&A, indexRoot: 0)
return max
}
func increaseNode<T:Comparable>(_ A:inout Array<T>, index:Int, value:T){
var index = index
if A[index] > value {return}
A[index] = value
while (index >= 0 && A[parentOfNode(A,indexNode: index)]<value){
exchange(&A, i: index, j: parentOfNode(A, indexNode: index))
index = parentOfNode(A, indexNode: index)
}
}
func insertNode<T:Comparable>(_ A:inout Array<T>, value:T){
A.append(value)
increaseNode(&A, index: A.count-1, value: value)
}
//Main
var unsortedArray2:Array<Int> = [4,1,3,2,16,9,10,14,8]
print("Unsorted array :" + unsortedArray2.description)
let sortedArray2 = heapSort(unsortedArray2)
print("Sorted array with heap sort :" + sortedArray2.description)
@marioeguiluz

This comment has been minimized.

Copy link
Owner Author

marioeguiluz commented Sep 21, 2016

Updated for Swift 3.0 with Generics

@iyumeg

This comment has been minimized.

Copy link

iyumeg commented May 16, 2017

Why don't you use "swap" function?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment