Thursday, June 30, 2016

Swift 3 - Selection Sort Challenge

Erica Sadun has an interesting post on the Make it Swifter Challenge for a functional implementation of a selection sort.  The original challenge was posted by Adriano Ferreira on the Swift Users email list.

While the selection sort doesn't scale well with O(n^2), it does do well at performing in tight memory constraints.  It's also very easy to implement.  However,  most of the solutions submitted ended up doing a lot of memory/array copying.

Here is my attempt at solving the problem in functional way with minimal memory allocation / array copying.  Note this does request Swift-3:

func selectionSort(_ array: inout [Int]) {
    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!])
        }
    }
}


Here is a non-mutating version of the above:


func selectionSorted(_ 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
}

As an extension to Array:

extension Array {
    
    func selectionSorted(isOrderedBefore: (Element, Element) -> Bool) -> [Element] {
        var arrayCopy = self
        for index in 0..<arrayCopy.count {
            let minIndex = arrayCopy
                .indices
                .clamped(to: index..<arrayCopy.count)
                .min(isOrderedBefore: { 
                     isOrderedBefore(arrayCopy[$0], arrayCopy[$1]) } )
            if index != minIndex {
                swap(&arrayCopy[index], &arrayCopy[minIndex!])
            }
        }
        return arrayCopy
    }

}

Example:


let x = [1, 3, 5, 2, 4, 9, 8, -5, 6, 4]
let minSort = x.selectionSorted(isOrderedBefore: { $0 < $1 })


That was my stab at making a functional version of SelectionSorted.  Please feel to leave your comments below.