0

I am trying to implement a radix sort in Swift (strictly out of boredom). I have been basing my work thus far on the C/C++ method found here.

For the most part everything is working as I would expect, except for one for loop which is giving me trouble. 

for (int exp = 1; max / exp > 0; exp *= 10)

Swift no longer allows C style for loops so this won't fly. I have been trying to recreate the loop using several approaches including this: 

var exp: Int = 1
for _ in (1..<(max / exp)).reversed()
{
    //My code
    exp = exp * 10
}

The problem here is Int can't contain the size of exp after several iterations of the loop. Since the original loop definition works just fine in Objective-C I believe my complete approach is flawed but I can't see where.

Any thoughts?

Léo Natan
  • 56,823
  • 9
  • 150
  • 195
William Smith
  • 1,949
  • 4
  • 25
  • 45
  • 2
    Your condition is evaluated only once in your Swift version, with value 1. Use a while cycle instead. – Sulthan Oct 29 '16 at 22:28
  • 1
    @MartinR agreed, especially with your non-`Int.max`-overflow addition to the end of you answer. – dfrib Oct 29 '16 at 22:36
  • 1
    Note that your C code does not work correctly for numbers close to `INT_MAX`: `exp *= 10` can overflow even if `max/exp > 0` (which is equivalent to `exp <= max` for positive numbers). – Martin R Oct 29 '16 at 22:45
  • Based on the solution in the dupe target, e.g. `exp = sequence(first: exp, next: { $0 <= max/10 && 0 < max/$0 ? $0 * 10 : nil}).reduce(0) { $1 }` should solve your C-style -> Swift loop conversion safely. – dfrib Oct 29 '16 at 22:53
  • @MartinR btw, do you know a neater way to get the last element of a (possibly infinite) sequence? (Say we're only interested in the last, as in this example). We'll need to traverse the elements one by one, by I wonder if there's a better choice than the `reduce` solution above (the only alternative I could come up with was `.map { $0 }.last ?? 0`). – dfrib Oct 29 '16 at 22:58
  • @dfri: No, I don't. OP did not explicitly state that only the last value is needed. If that is the case then I would probably go with a while-loop, similar to the answer below: `var exp = 1; while 10 * exp <= max { exp *= 10 }`. – Martin R Oct 29 '16 at 23:03
  • @MartinR Ok, thanks! Minor prompt w.r.t. ninja-edit: in this exponential growth example, that `while` loop should probably use condition `exp <= max/10` though (or overflow for suff. large `max` values, as `10 * exp` is tested once even for the failed test, `> max`). – dfrib Oct 29 '16 at 23:14
  • @dfri Yes that is what I meant. – Martin R Oct 29 '16 at 23:17
  • I realize this thread is closed or soon to be, but for the record I used the very simple `while` loop as suggested and it worked great. I guess after staring at sorting algorithms for a few hours I lost sight of the forest for the trees. Thanks, guys! – William Smith Oct 30 '16 at 00:30

0 Answers0