Sorting Big Int value in Swift

Question

I have a problem to sort some numbers, which are string first. The numbers are too huge for UInt64, so i converted the string numbers to float and then sorted it. That works out great. But then i need to print these numbers with no decimals. So I tried to format the numbers. But the Bigger number are changing its value after formatting it.

Here is the Input array to sort -
["6","31415926535897932384626433832795","1","3","10","3","5"]

And I need to print output in exactly this format -

1

3

3

5

10

31415926535897932384626433832795

Here is my code in swift -

import Foundation
var a = Array<Float>()
var b = ["6","31415926535897932384626433832795","1","3","10","3","5"]
a = b.map{ Float($0)! }
for i in 0..<(a.count-1){
    var min = i
    for j in (i+1)..<a.count{
        if a[j] < a[min] {
            min = j
        }
    }

    var temp = a[i]
    a[i] = a[min]
    a[min] = temp
}
for val in a{
    print(String(format: "%.0f",val.rounded(.down)))
}

My Output is -

1

3

3

5

6

10

31415927314585224784361549725696

If you notice the last biggest number is changed from the original input. Any suggestions would be much appreciated! Thanks!

Answer 1

You can use numeric comparison:

let values = ["6","31415926535897932384626433832795","1","3","10","3","5"]

let sortedValues = values.sorted { (value1, value2) in
    let order = value1.compare(value2, options: .numeric)
    return order == .orderedAscending
}

print(sortedValues) // ["1", "3", "3", "5", "6", "10", "31415926535897932384626433832795"]

Answer 2

With using float, you may get unexpected result for orders between big ints:

var str = "Hello, playground"
let inArray = [
    "6",
    "31415926535897932384626433832797",
    "31415926535897932384626433832796",
    "31415926535897932384626433832795",
    "1",
    "3"
]
let outArray = inArray.sorted {Float($0)! < Float($1)!}
print(outArray)
//->["1", "3", "6", "31415926535897932384626433832797", "31415926535897932384626433832796", "31415926535897932384626433832795"]

As described in mag_zbc's answer, Float has about only 7 significant digits, so all less significant digits are lost.

Float("31415926535897932384626433832797") == Float("31415926535897932384626433832795")
//->true

---

If the digits of your numbers are 38 at most, you can use Decimal (as also suggested in mag_zbc's answer).

let outWithDecimal = inArray.sorted {Decimal(string: $0)! < Decimal(string: $1)!}
print(outWithDecimal)
//->["1", "3", "6", "31415926535897932384626433832795", "31415926535897932384626433832796", "31415926535897932384626433832797"]

---

Or else, if your data contains numbers with more than 38 digits, String comparison would work with a little pre-processing:

(Assuming all your numbers are non-negative integer.)

extension String {
    func fillZeroLeft(_ length: Int) -> String {
        if self.characters.count < length {
            return String.init(repeating: "0", count: length-self.characters.count) + self
        } else {
            return self
        }
    }
}

let maxLen = inArray.lazy.map{$0.characters.count}.max()!
let outWithString = inArray.sorted {$0.fillZeroLeft(maxLen) < $1.fillZeroLeft(maxLen)}
print(outWithString)
//->["1", "3", "6", "31415926535897932384626433832795", "31415926535897932384626433832796", "31415926535897932384626433832797"]

(But numeric comparison in Sulthan's answer seems to be better for me!)

Answer 3

It's impossible to accurately represent such big numbers using primitive types in Swift.

Your value is ~3e+32
UInt64 has a max value of ~1,8e+18
Float uses 24 bits for a significant, which allows to accurately represent a number up to ~1.6e+8 Double uses 53 bits for significant, which allows to accurately represent a number up to ~9e+15

Floating point types (Float and Double) are able to hold much greater values, but they will lose accuracy above the numbers their significants can hold.

Apart from using some external library, I'd suggest using NSDecimalNumber class, which is supposed to be able to hold up to 38 decimal digits - which is enough for numbers in your example. However, if you need even bigger numbers, then you'll need to look for some external library.