Last active
August 11, 2018 17:33
-
-
Save mathewa6/dda7b384a95f9406a5d7 to your computer and use it in GitHub Desktop.
A review of basic algorithms in Swift, started after reading http://bost.ocks.org/mike/algorithms/
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //A review thanks to http://bost.ocks.org/mike/algorithms/ | |
| import Foundation | |
| func exchange<T>(inout elementsIn array: [T], i: Int, j: Int) | |
| { | |
| let temp: T = array[i] | |
| array[i] = array[j] | |
| array[j] = temp | |
| } | |
| ///Fisher-Yates Shuffle | |
| ///:param: array Array to shuffle | |
| func shuffle<T>(inout array: [T]) | |
| { | |
| var n = array.count | |
| while(n > 0) { | |
| //arc4random() doesn't work | |
| let index = Int(rand()) % n-- | |
| exchange(elementsIn: &array, i: index, j: n) | |
| } | |
| } | |
| ///Insertion Sort | |
| ///:param: array Array to sort | |
| func insertionSort<T: Comparable>(inout array: [T]) | |
| { | |
| for var i = 1; i < array.count; ++i { | |
| for var j = i; j > 0; --j { | |
| if array[j-1] > array[j] { | |
| exchange(elementsIn: &array, i: j-1, j: j) | |
| } | |
| } | |
| } | |
| } | |
| ///Quick Sort | |
| ///:param: array Array to sort | |
| func quickSort<T: Comparable>(inout array: [T], left: Int, right: Int) | |
| { | |
| if left < right - 1 { | |
| var pivot: Int = (left + right) >> 1 | |
| pivot = part(&array, left: left, right: right, pivot: pivot) | |
| quickSort(&array, left: left, right: pivot) | |
| quickSort(&array, left: pivot + 1, right: right) | |
| } | |
| } | |
| func part<T: Comparable>(inout array: [T], left: Int, right: Int, pivot: Int) -> Int | |
| { | |
| let pivotValue: T = array[pivot] | |
| var l = left, r = right | |
| exchange(elementsIn: &array, i: pivot, j: --r) | |
| for var i: Int = l; i < r; ++i { | |
| if array[i] < pivotValue { | |
| exchange(elementsIn: &array, i: i, j: l++) | |
| } | |
| } | |
| exchange(elementsIn: &array, i: l, j: r) | |
| return l | |
| } | |
| ///Merge Sort(Bottom Up) | |
| ///:param: array Array to sort | |
| func mergeSort<T: Comparable>(inout array: [T]) | |
| { | |
| let n = array.count | |
| var a0 = array | |
| var a1 = Array<T>() | |
| for idx in 0...n-1 { | |
| a1.append(a0[idx]) | |
| } | |
| for var m = 1; m <= n; m <<= 1{ | |
| for var i = 0; i < n; i += m << 1 { | |
| let left = i, right = min(i + m, n), end = min(i + (m << 1), n) | |
| merge(&a0, a1: &a1, left: left, right: right, end: end) | |
| } | |
| array = a0 | |
| a0 = a1 | |
| a1 = array | |
| } | |
| } | |
| func merge<T: Comparable>(inout a0: [T], inout a1: [T], left: Int, right: Int, end: Int) | |
| { | |
| var i0 = left | |
| var i1 = right | |
| for var j = left; j < end; ++j { | |
| if i0 < right && (i1 >= end || a0[i0] <= a0[i1]) { | |
| a1[j] = a0[i0++] | |
| } else { | |
| a1[j] = a0[i1++] | |
| } | |
| } | |
| } | |
| var a = [1,2,3,4,5,8,9,6] | |
| shuffle(&a) | |
| a | |
| mergeSort(&a) | |
| a |
Author
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Updated for Swift 2.2