selection.swift

/// 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)
// }
// ```

Hi there!

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

return [minElement.1] + selectionSortBasic(array)

why not guard var?

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!