0

I'm working with a sorting function that takes an array of Ints already sorted in descending order and places a new Int in its correct spot. (i.e if my sorted array was [10, 7, 2] and the new int was 5, the function would return [10, 7, 5, 2]). The function for doing this, once it has found the correct spot for the new Int, slices the original array into the items before the new Ints spot and those after, and then combines the slices with the new Int.

The problem I'm running into is that this won't give me an array but rather an array slice.

Code:

func addToSorted(sorted: [Int], new: Int) ->  [Int] {
    if sorted.count == 0 {
        return [new]
    } else {
        for index in 0..<sorted.count {
            let item = sorted[index]
            if new > item {
                return sorted[..<index] + [new] + sorted[index...]
            }
        }
    }
}

let result = addToSorted(sorted: [10, 7, 2], new: 5)
print(result) // expected [10, 7, 5, 2]
Improve this question

3 Answers 3

Reset to default
4

This is a more generic (and efficient) alternative which uses binary search

extension RandomAccessCollection where Element : Comparable {
    func descendingInsertionIndex(of value: Element) -> Index {
        var slice : SubSequence = self[...]
        
        while !slice.isEmpty {
            let middle = slice.index(slice.startIndex, offsetBy: slice.count / 2)
            if value > slice[middle] {
                slice = slice[..<middle]
            } else {
                slice = slice[index(after: middle)...]
            }
        }
        return slice.endIndex
    }
}

And use it

var array = [10, 7, 5, 2]
let index = array.descendingInsertionIndex(of: 4)
array.insert(4, at: index)
print(array) // [10, 7, 5, 4, 2]

For ascending order replace if value > slice[middle] with if value < slice[middle] and return slice.endIndex with return slice.startIndex

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

This is exactly what I had in mind, bravo! Using iteration instead of recursion is a cherry on top.
I am hesitant to use binary search for 2 reasons: 1) The arrays I'll be working with will have a small input size (think 10...20 elements at the most) and 2) I can expect the new Ints to be larger than the average element in the sorted array, so I will rarely ever have to iterate through the entire sorted array to place a new Int.
Apart form the fact that on average binary search is faster already with 5 elements my suggestion does not consume any additional memory because the slicing does not create any new objects.
@JohnSorensen You can add a "fast path" to descendingInsertionIndex(of:) that uses linear-search for small enough arrays below some threshold size (that's determined through profiling). You could also add a check that compares to the first element so that "always prepending" use-cases get faster. Though for big datasets, it would be better to flip things around so you're appending to the end more frequently. Prepending on arrays is slow for large data sets.
2

If you use the Swift Algorithms, this insertion is a one-liner:

var arr = [10, 7, 2]
arr.insert(5, at: arr.partitioningIndex {$0 < 5})
print (arr) // [10, 7, 5, 2]

This is very efficient — O(log n) — because your array is already partitioned (sorted) and therefore it uses a binary search.

Improve this answer

Comments

1

You would have to promote the slices to arrays:

return Array(sorted[..<index]) + [new] + Array(sorted[index...])

A few other points:

  1. You should make a habit out of using sorted.isEmpty over sorted.count == 0, it's much faster for some collections that don't store their count, such as lazy collections or even String (IIRC).

  2. A better approach would be to just use Array.insert(_:at:):

    var sorted = sorted // Make a local mutable copy
sorted.insert(new, at: index)

  3. BTW after your for loop, you need insert at the end of your array (this also removes the need for checking the empty case):

    return sorted + [new]

    Since this works even when sorted is empty, you can remove that special case.

  4. Since you know your data structure is already sorted, you can use binary search instead of linear search to find the insertion index faster.

Improve this answer

1 Comment

@Rob Haha indeed! I was trying to keep it formatting only, and add the callsite at the end, but that snuck in. Fixed!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.