Turn and face the strange: Using a C function to merge (or stable) sort in Swift (Swift 3, Xcode 8)

on


It was suggested that Swift include a stable (or merge) sort function and I hope this becomes the case.  At present, however, we must turn to pure Swift implementations presented by others or turn to the C functions accessible through Swift. (According to the man pages, mergesort: is a stable sort function.) 

It should be noted that the mergesort: function has some restrictions that make generic use difficult if not impossible. Not least connected to closures, but at the moment I just want to look at the basics of mergesort:
public func mergesort(_ __base: UnsafeMutableRawPointer!, _ __nel: Int, _ __width: Int, _ __compar: @escaping @convention(c) (UnsafeRawPointer?, UnsafeRawPointer?) -> Int32) -> Int32
This is quite an unwieldy looking function but let's break it down.
  • base: this is a pointer to a mutable array, which can be implemented using the in-out notation of & so &arrayName is what you'll see here
  • nel: is the array length, so arrayName.count goes here
  • width: is the byte width of the values contained in the array, so here we insert for example MemoryLayout<Int>.size where between the angle brackets goes the type
  • compar: is where we use a closure to determine how the sort will take place and the values come via UnsafeRawPointers. To get at the value pointed to by the pointers and make the comparison you can use something like this, $0.unsafelyUnwrapped.load(as: Int.self)  > $1.unsafelyUnwrapped.load(as: Int.self). As I understand it here we must return an Int32 and are instructing through this integer how far the index should be advanced. So if we have a comparison between two values, as we when the array is iterated over in the sort, and those two values are equal there should be no advancement in the (first) value being compared but if the value is less than the second value it moves backwards (or rather stays to the left of the second value) and if the value is greater than the second value then it moves forward by one (moving past the second value). And this comparison keeps happening until the array is sorted.
So here's a demonstration in code:
var array = ["mango", "apple", "pear", "orange", "banana"]
mergesort(&array, array.count, MemoryLayout<String>.size, {
    let a = $0.unsafelyUnwrapped.load(as:String.self)
    let b = $1.unsafelyUnwrapped.load(as:String.self)
    if a == b {
        return 0
    }
    else if a < b {
        return -1 }
    else {
        return 1
    }
})
print(array) // ["apple", "banana", "mango", "orange", "pear"]

Further fun

I thought it worth implementing secondary sorting to extend the exercise and these are my first steps here:
enum SortType {
    case Ascending
    case Descending
}
enum SortError:Error {
    case ArrayLengthsNotEqual
}


enum SortBy {
    
    case IntegerArray([Int], type:SortType), DoubleArray([Double], type:SortType),  StringArray([String], type:SortType)
    
    init?<S: Sequence>(arr: S, type:SortType = .Ascending) {
        if arr is [Int] {
            self = SortBy.IntegerArray(arr as! [Int], type: type)
        }
        else if arr is [Double] {
            self = SortBy.DoubleArray(arr as! [Double], type: type)
        }
        else if arr is [String] {
            self = SortBy.StringArray(arr as! [String], type: type)
        }
        else {
            return nil
        }
        
    }
    
    
    func sort<A>(arr:Array<A>) throws -> Array<A> {
        switch self {
        case .IntegerArray(let i):
            guard i.0.count == arr.count else {throw SortError.ArrayLengthsNotEqual}
            var arr = zip(i.0,arr).flatMap{$0}
            if i.type == .Ascending {
                mergesort(&arr, arr.count, MemoryLayout<(Int,A)>.size, {
                    let a = $0.unsafelyUnwrapped.load(as:(Int.self, Any.self).0)
                    let b = $1.unsafelyUnwrapped.load(as:(Int.self, Any.self).0)
                    if a == b {return 0}
                    else if a < b {return -1}
                    else {
                        return 1
                    }
                    }
                )
            }
            else {
                mergesort(&arr, arr.count, MemoryLayout<(Int,A)>.size, {
                    let a = $0.unsafelyUnwrapped.load(as:(Int.self, Any.self).0)
                    let b = $1.unsafelyUnwrapped.load(as:(Int.self, Any.self).0)
                    if a == b {
                        return 0
                    }
                    else if a > b {
                        return -1
                    }
                    else {
                        return 1
                    }
                    }
                )
            }
            return arr.map{$0.1}
            
        case .DoubleArray(let d):
            guard d.0.count == arr.count else {throw SortError.ArrayLengthsNotEqual}
            var arr = zip(d.0,arr).flatMap{$0}
            
            if d.type == .Ascending {
                mergesort(&arr, arr.count, MemoryLayout<(Double,A)>.size, {
                    let a = $0.unsafelyUnwrapped.load(as:(Double.self, Any.self).0)
                    let b = $1.unsafelyUnwrapped.load(as:(Double.self, Any.self).0)
                    if a == b {return 0} else if a < b {return -1}
                    else {return 1}})
            }
            else {
                mergesort(&arr, arr.count, MemoryLayout<(Double,A)>.size, {
                    let a = $0.unsafelyUnwrapped.load(as:(Double.self, Any.self).0)
                    let b = $1.unsafelyUnwrapped.load(as:(Double.self, Any.self).0)
                    if a == b {return 0} else if a > b {return -1}
                    else {return 1}})
            }
            
            return arr.map{$0.1}
            
        case .StringArray(let str):
            guard str.0.count == arr.count else {throw SortError.ArrayLengthsNotEqual}
            var arr = zip(str.0,arr).flatMap{$0}
            
            if str.type == .Ascending {
                mergesort(&arr, arr.count, MemoryLayout<(String,A)>.size, {
                    let a = $0.unsafelyUnwrapped.load(as:(String.self, Any.self).0)
                    let b = $1.unsafelyUnwrapped.load(as:(String.self, Any.self).0)
                    if a == b {return 0} else if a < b {return -1}
                    else {return 1}})
            }
            else {
                mergesort(&arr, arr.count, MemoryLayout<(String,A)>.size, {
                    let a = $0.unsafelyUnwrapped.load(as:(String.self, Any.self).0)
                    let b = $1.unsafelyUnwrapped.load(as:(String.self, Any.self).0)
                    if a == b {return 0} else if a > b {return -1}
                    else {return 1}})
            }
            return arr.map{$0.1}
            
        }}
    
}
And implementation looks like this: 
// data
var arr1 = ["3892", "3926", "3977", "4028", "4030", "4043", "4059", "4062", "2547", "2622", "2691", "3913"].map{Double($0)!}

var arr2 = ["A", "K", "L", "B", "M", "N", "O", "P", "Q", "T", "S", "V"]
    
var arr3 = [1, 2, 4, 1, 9, 10, 8, 9, 11, 12, 14, 13]
arr3

// implementatation
// first create your sorter,  the ordering array (used to create the SortBy instance) must contain Int, Double,  or String
if let sorter = SortBy(arr: arr3) {
    do {
        arr1 = try sorter.sort(arr: arr1)
        arr2 = try sorter.sort(arr: arr2)
        arr3 = try sorter.sort(arr: arr3)
    }
    catch SortError.ArrayLengthsNotEqual {
        print("Array lengths are not equal, no sorting has taken place!!!")
    }
    catch {
        print("other error, no sorting has taken place!!!")
    }
}

arr3 //[1, 1, 2, 4, 8, 9, 9, 10, 11, 12, 13, 14]
arr2 // ["A", "B", "K", "L", "O", "M", "P", "N", "Q", "T", "V", "S"]
arr1 // [4028, 3892, 3926, 3977, 4059, 4062, 4030, 4043, 2547, 2622, 3913, 2691]
I need to test this code and make sure it works consistently but it seems to be. (As I noted at the beginning the lack of generics when using C functions restrict things a little.)


Comments

Post a Comment