Ttykuu

I have the below sorting algorithm which takes an array of dictionary values as declared below:

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,,.")
 
 

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)

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)