Last active
September 20, 2016 15:12
-
-
Save erica/124b64b4e71372fe04b44e1e02d448ca to your computer and use it in GitHub Desktop.
This file contains 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
/// An indexed tuple specifically for use with enumerated results | |
public typealias Indexed<Index, Value> = (index: Index, value: Value) | |
public extension Array { | |
/// Establishes a lazy sequence of enumerated items using index and value labels | |
public func indexed() -> LazyMapSequence<EnumeratedSequence<[Element]>, Indexed<Index, Element>> { | |
return enumerated() | |
.lazy | |
.map({ return $0 as Indexed<Index, Element> }) | |
} | |
} | |
/// Perform a simple selection sort | |
/// | |
/// "Selection sort is noted for its simplicity, and it has performance | |
/// advantages over more complicated algorithms in certain situations, | |
/// particularly where auxiliary memory is limited." | |
/// | |
/// - Complexity: O(count^2) | |
/// - Reference: [https://en.wikipedia.org/wiki/Selection_sort](https://en.wikipedia.org/wiki/Selection_sort) | |
/// | |
func selectionSort(_ array: [Int]) -> [Int] { | |
guard let minElement = array | |
.indexed() | |
.min(isOrderedBefore: { $0.value < $1.value }) | |
else { return [] } | |
var array = array // mutable shadow | |
array.remove(at: minElement.index) | |
return [minElement.value] + selectionSort(array) | |
} | |
let x = [1, 3, 5, 2, 4, 9, 8, -5, 6, 4] | |
print(selectionSort(x)) // [-5, 1, 2, 3, 4, 4, 5, 6, 8, 9] | |
print(selectionSort([2])) // [2] | |
print(selectionSort([])) // [] | |
// Without my forced index naming, the code would look more | |
// like this using indexed arguments. | |
// | |
// ```swift | |
// func selectionSortBasic(_ array: [Int]) -> [Int] { | |
// guard let minElement = array.enumerated() | |
// .min(isOrderedBefore: { $0.1 < $1.1 }) else { return [] } | |
// var array = array // mutable shadow | |
// array.remove(at: minElement.0) | |
// return [minElement.1] + selectionSort(array) | |
// } | |
// ``` |
How to learn something about Sequence
Type? Could you give some advice Thank you!
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The indexed extension on an array is really awesome.
I know that this was an overall improvement on Adriano Ferreira's challenge, but is this implementation really a selection sort? The goal was to use functional programming techniques in swift. However, the big advantage of the selection sort is that it is a "in-place comparison sort". It can have memory advantages over other sorts. However, the original implementation creates lots of extra memory allocations and it doesn't swap the found minimal value with the value at the bottom of the "sorted" list. What about something like the following.
I think this best captures the spirit of a selection sort in a functional way.