Skip to content

Instantly share code, notes, and snippets.

@nuclearace
Created January 10, 2015 07:36
Show Gist options
  • Save nuclearace/77664dd11c35eaa219a6 to your computer and use it in GitHub Desktop.
Save nuclearace/77664dd11c35eaa219a6 to your computer and use it in GitHub Desktop.
Some sort algorithms in Swift
func selectionSort(inout arr:[Int]) {
var min:Int
for n in 0..<arr.count {
min = n
for x in n&+1..<arr.count {
if (arr[x] < arr[min]) {
min = x
}
}
if min != n {
let temp = arr[min]
arr[min] = arr[n]
arr[n] = temp
}
}
}
func quicksort(inout list:[Int], var left:Int = -1, var right:Int = -1) {
if left == -1 && right == -1 {
left = 0
right = list.count - 1
}
func partition(left:Int, right:Int) -> Int {
var i = left
for j in left+1...right {
if list[j] < list[left] {
i++
(list[i], list[j]) = (list[j], list[i])
}
}
(list[i], list[left]) = (list[left], list[i])
return i
}
if right > left {
let pivotIndex = partition(left, right)
quicksort(&list, left: left, right: pivotIndex - 1)
quicksort(&list, left: pivotIndex + 1, right: right)
}
}
func heapsort(inout list:[Int], var count:Int = -1) {
if count == -1 {
count = list.count
}
func shiftDown(inout list:[Int], start:Int, end:Int) {
var root = start
while root * 2 + 1 <= end {
var child = root * 2 + 1
var swap = root
if list[swap] < list[child] {
swap = child
}
if child + 1 <= end && list[swap] < list[child + 1] {
swap = child + 1
}
if swap == root {
return
} else {
(list[root], list[swap]) = (list[swap], list[root])
root = swap
}
}
}
func heapify(inout list:[Int], count:Int) {
var start = (count - 2) / 2
while start >= 0 {
shiftDown(&list, start, count - 1)
start--
}
}
heapify(&list, count)
var end = count - 1
while end > 0 {
(list[end], list[0]) = (list[0], list[end])
end--
shiftDown(&list, 0, end)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment