Swift Stable Sort?

Question

At this time (March 28, 2015): If I want to use a stable sort in swift, I have to use NSArray and sortWithOptions or write my own stable sort in Swift such as an insertion sort? I see in the Apple Swift docs that sorted is not stable.

Example of stable sort in NSMutableArray:

[array sortWithOptions:NSSortStable usingComparator:^NSComparisonResult(id obj1, id obj2) {
    return [obj1 compare:obj2];
}];

Am I missing another option that's available to me in Swift other than using Objective-C or writing my own sort?

yeah.. you can also write a swift-wrapper that calls the objective-c function - if there really isn't one yet.. — Michael, Mar 28 '15 at 20:44
of course! I had a brain fart. Make that an answer and I will green check mark that, @Michael . :) — finneycanhelp, Mar 28 '15 at 20:45
Does this answer your question? [How to stable sort an array in swift?](https://stackoverflow.com/questions/40673374/how-to-stable-sort-an-array-in-swift) — Abdurrahman Mubeen Ali, Dec 13 '19 at 17:22

sketchyTech · Answer 1 · 2016-10-26T15:11:18.543

In addition to your Swift wrapper approach you can use the C mergesort: function

var array2 = ["mango", "apple", "pear", "apple", "orange", "banana"]
mergesort(&array2, array2.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(array2) // ["apple", "apple", "banana", "mango", "orange", "pear"]

or write a Pure Swift approach which makes things more generic:

var array = ["mango", "apple", "pear", "banana", "orange", "apple", "banana"]

enum SortType {
    case Ascending
    case Descending
}

struct SortObject<T> {
    let value:T
    let startPosition:Int
    var sortedPosition:Int?
}

func swiftStableSort<T:Comparable>(array:inout [T], sortType:SortType = .Ascending) {

    var sortObjectArray = array.enumerated().map{SortObject<T>(value:$0.element, startPosition:$0.offset, sortedPosition:nil)}

    for s in sortObjectArray {
        var offset = 0
        for x in array[0..<s.startPosition]  {
            if s.value < x {
                offset += sortType == .Ascending ? -1 : 0
            }
            else if s.value > x {
                offset += sortType == .Ascending ? 0 : -1
            }
        }

        for x in array[s.startPosition+1..<array.endIndex]  {
            if s.value > x  {
                offset += sortType == .Ascending ? 1 : 0
            }
            else if s.value < x  {
                offset += sortType == .Ascending ? 0 : 1
            }
        }
        sortObjectArray[s.startPosition].sortedPosition = offset + s.startPosition
    }

    for s in sortObjectArray {
        if let sInd = s.sortedPosition {
            array[sInd] = s.value
        }
    }

}

swiftStableSort(array: &array, sortType:.Ascending) // ["apple", "apple", "banana", "banana", "mango", "orange", "pear"]
swiftStableSort(array: &array, sortType:.Descending) // ["pear", "orange", "mango", "banana", "banana", "apple", "apple"]

(This is my humble and straightforward approach, no doubt others can optimise.)

Swift Stable Sort?

1 Answers1

Linked