Skip to content

Instantly share code, notes, and snippets.

@Nirma
Last active Jun 21, 2018
Embed
What would you like to do?
// Insertion Sort
func insertionSort(_ elements: [Int]) -> [Int] {
guard elements.count >= 2, let last = elements.last else { return elements }
var copy = elements
var pivot = last
var idx: Int
for index in 0..<(elements.count - 1) {
idx = index
pivot = copy[idx + 1]
while (idx >= 0) && copy[idx] > pivot {
copy[idx + 1] = copy[idx]
idx -= 1
}
copy[idx + 1] = pivot
}
return copy
}
// Selection Sort
func selectionSort(_ items: [Int]) -> [Int] {
var copy = items
for index in (0..<items.count) {
var minEleIndex = index
for idx in ((index+1)..<items.count) {
if copy[idx] < copy[minEleIndex] {
minEleIndex = idx
}
}
copy.swapAt(minEleIndex, index)
}
return copy
}
// Counting Sort
func countingSrt(_ elements: [Int]) -> [Int] {
guard let max = elements.max() else { return elements}
var counts = [Int].init(repeating: 0, count: max + 1)
for item in elements {
counts[item] += 1
}
// construct output array
var cpy = elements
var itr = 0
for (index, item) in counts.enumerated() {
print("Index: \(index) item: \(item)")
for _ in 0..<item {
cpy[itr] = index
itr += 1
}
}
return cpy
}
// BROKEN
func partition(_ elements: inout [Int], low: Int, high: Int) -> Int {
guard low < high else { return low }
let pivot = elements[high]
print("Pivot: \(pivot)")
var store = low - 1
for index in (low...high) {
if elements[index] <= pivot {
store += 1
elements.swapAt(store, index)
}
}
elements.swapAt(store + 1, high)
return store
}
func quickSort(_ elements: inout [Int], low: Int, high: Int) {
guard low < high else { return }
let pi = partition(&elements, low: low, high: high)
quickSort(&elements, low: low, high: pi-1)
quickSort(&elements, low: pi+1, high: high)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment