Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
/// 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)
// }
// ```

adrfer commented Jun 28, 2016

Hi there!

The commented out example needs a quick fix. Here it is:

return [minElement.1] + selectionSortBasic(array)

why not guard var?

tcunning commented Jun 29, 2016

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.

func selectionSort(_ originalArray: [Int]) -> [Int] {
    var array = originalArray
    for index in 0..<array.count {
        let minIndex = array.indices.clamped(to: index..<array.count).min(isOrderedBefore: { array[$0] < array[$1] })
        if index != minIndex {
            swap(&array[index], &array[minIndex!])
        }
    }
    return array
}

I think this best captures the spirit of a selection sort in a functional way.

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