Counting sort in Swift

Question

I have this sorting algorithm which takes an array of dictionary values:

guard var imageUrlString = anyImage.value as? [String:AnyObject] else { return }

I then loop through it, adding the values with the smallest Int key to a new array to be used afterward. Thus the values in this array of AnyObjects would go from 1 to n.

I was wondering if I could make it more concise.

var values = [AnyObject]()
var keys = [String]()
var Done = false
var j = 1

 while !Done {
    for i in imageUrlString {
        let key = Int(String(i.key.last!))

        if j == key {
            values.append(i.value)
            keys.append(i.key)
            print(i, " This is the i for in if ")
            if imageUrlString.count == j {
                print("Done yet: yes", values[0], " ", values[3])
                Done = true
                break;
            }
            j+=1
        } else {
            print("No,,.")
        }
    }
}

Answer 1

Making it to the promised land of O(n)

To reproduce your code in a playground, a Media struct could be defined this way:

struct Media {
    let mediaUrl: String
    let postTimeStamp: String?
    let timeStamp: String  //A double would be more appropriate

    init(mediaUrl: String, timeStamp: String, postTimeStamp: String? = nil) {
        self.mediaUrl = mediaUrl
        self.timeStamp = timeStamp
        self.postTimeStamp = postTimeStamp
    }
}

Let's suppose the value of imageUrlString is this:

let imageUrlString: [String: Media] =
    ["media1": Media(mediaUrl: "URL", timeStamp: "573889179.6991431", postTimeStamp: "573889189.73954"),
     "media4": Media(mediaUrl: "URL", timeStamp: "573889185.750419"),
     "media2": Media(mediaUrl: "URL", timeStamp: "573889181.49576"),
     "media3": Media(mediaUrl: "URL", timeStamp: "573889183.89598")]

var values = [Media]()

Your code works by relying on the chance of having the last character read from the imageUrlString dictionary, equal the order of the element you want to append to the values array.

Bear in mind that a dictionary is an unordered collection. And unless mutated, the order of elements stays the same. The worst case would be when, reading elements from the dictionary, yields elements in a reversed "order". In this case, you'll have to read from the dictionary n*(n+1)/2 times, in order to build your values array. In other terms, this algorithm is has O(n²) time complexity (worst case), O(n) best case, and is not the proper Counting Sort Algorithm which is O(n).

Here is an attempt to make this O(n):

let tempo = Media(mediaUrl: "", timeStamp: "")
var values = Array(repeating: tempo, count: imageUrlString.count)
var keys = Array(repeating: "", count: imageUrlString.count)

for entry in imageUrlString {
    let index = Int(String(entry.key.last!))! - 1  //Force-unwrapping for brevity
    (keys[index], values[index]) = entry
}

---

Robustness

The code in question relies on external facts that are not checked in code. For example:

• If imageUrlString is empty, Done will never be mutated and thus the outer loop will be infinite;
• The order of the elements in the result array relies on the last character in a string;
• The last character in all the keys has to exist and be numerical for j to be incremented. Otherwise, you're in for another infinite loop;
• Breaking the outer loop relies on the digits at the end of the keys go from 1 to at least imageUrlString.count.

---

Breaking an outer loop

Instead of mutating the variable Done (which shouldn't be uppercased since it's an instance, not a class/type/struct/enum/etc), you can break from a nested loop this way:

OuterLoop: while true {
    for i in imageUrlString {
        ...
        if imageUrlString.count == j {
            break OuterLoop
        }
        ...
    }
}

---

Straight forward sorting

In Swift 5, Timsort is the algorithm that is going to be used by the standard library while sorting. It has better time complexity than Introsort and is more versatile and less memory greedy than O(n) sorting algorithms.

So, why not just use it to sort the entries in imageUrlString by timeStamp or a some other more reliable criteria?

let values = imageUrlString.values
    .sorted(by: { $0.timeStamp < $1.timeStamp }) 

(If you're sure that timeStamps represent real numbers, you could cast them to Double before comparing them)

Answer 2

Consider:

let dictionary = ["3": "c", "1": "a", "2": "b”]

If you want to get separate arrays of keys and values, sorted by the order of the Int values of the keys, you can do:

let (keys, values) = dictionary.map { (Int($0.key) ?? 0, $0.value) }  // get `Int` keys
    .sorted { $0.0 < $1.0 }                                           // now sort by those `Int` values
    .reduce(into: ([Int](), [String]())) { arrays, entry in           // divide that up into two arrays
        arrays.0.append(entry.0)
        arrays.1.append(entry.1)
}

That results in a keys of [1, 2, 3] and values of ["a", "b", "c"].

But a key observation is that you actually have to explicitly sort your results. Dictionaries, unlike arrays, are unordered. E.g. regardless of what order the keys appeared in a dictionary literal or JSON, when you iterate through the key-value pairs in a dictionary, the order may be different. You have to convert to an array and sort it yourself if order is important.

---

The above arbitrarily uses 0 for any keys (if any) that couldn’t be converted to an Int. If you just wanted to drop those entries, you could alternatively do:

let (keys, values) = dictionary.compactMap { entry in Int(entry.key).map { ($0, entry.value) } }
    .sorted { $0.0 < $1.0 }                                       // now sort by those `Int` values
    .reduce(into: ([Int](), [String]())) { arrays, entry in       // divide that up into two arrays
        arrays.0.append(entry.0)
        arrays.1.append(entry.1)
}