Skip to content

Instantly share code, notes, and snippets.

@vjosullivan
Last active August 26, 2016 09:38
Show Gist options
  • Save vjosullivan/d63971c80a96cf7973c6e0036b766855 to your computer and use it in GitHub Desktop.
Save vjosullivan/d63971c80a96cf7973c6e0036b766855 to your computer and use it in GitHub Desktop.
A Swift 3.0 template for comparing sorting algorithms.
import Foundation
/// A template for comparing different sorting algorithms.
///
/// To use:
/// - Sublass `SortTemplate`.
/// - Override the function `algorithm to sort the internal var `array`.
/// - Initialise the new class with data to be sorted.
/// - Call the `sort()` function.
class SortTemplate<C: Comparable> {
/// A copy of array to be sorted. This copy is preserved through each sort and used to initialise the actual array to be sorted.
let initialArray: [C]
/// The actual array to be sorted.
private(set) var array: [C]
/// The number of data comparisons made during the sort.
private(set) var compareCount = 0
/// The number of data exchanges made during the sort.
private(set) var exchangeCount = 0
/// The duration of the sort.
private(set) var sortDuration: TimeInterval = 0
/// Initia;ises the instance with the test data.
/// - parameter array: The test data. (Immutable and reused each time the sort is run.)
init(array: [C]) {
self.initialArray = array
self.array = array
}
/// Calls (and times) the actual sort algorithm.
final func sort() {
array = initialArray
let startTime = Date()
algorithm()
sortDuration = Date().timeIntervalSince(startTime)
}
/// The sort algorithm. (Must be overridden.)
/// - note: Always use the `isLess` function to compare data value. This ensure that the number of data comparisons is recorded.
open func algorithm() {
// Must be overridden.
}
/// Compares two data values and updates a comparison counter.
final func isLess(_ this: C, than: C) -> Bool {
compareCount += 1
return this < than
}
/// Exchanges the two data items at the given indexes and updates the exchange counter.
final func exchange(_ i: Int, _ j: Int) {
let temp = array[i]
array[i] = array[j]
array[j] = temp
exchangeCount += 1
}
/// - returns: `true` if the array is sorted, otherwise `false`.
final func isSorted() -> Bool {
for i in 0..<(array.count - 1) {
if array[i] > array[i + 1] {
return false
}
}
return true
}
}
extension SortTemplate: CustomStringConvertible {
var description: String {
var desc = "Sorted \(array.count) items in \(sortDuration) seconds."
desc += "\nComparisons: \(compareCount). Exchanges: \(exchangeCount)."
return desc
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment