Pi Horse - 8 months ago 22

Ruby Question

I have an array in Ruby which has values as follows

`xs = %w(2.0.0.1`

2.0.0.6

2.0.1.10

2.0.1.5

2.0.0.8)

and so on. I want to sort the array such that the final result should be something like this :

`ys = %w(2.0.0.1`

2.0.0.6

2.0.0.8

2.0.1.5

2.0.1.10)

I have tried using the

`array.sort`

`"2.0.1.10"`

`"2.0.1.5"`

Answer

Using a Schwartzian transform (Enumerable#sort_by), and taking advantage of the lexicographical order defined by an array of integers (Array#<=>):

```
ips.sort_by { |ip| ip.split(".").map(&:to_i) }
```

How this works:

First you must realize that you can't directly compare strings containing numbers and expect them to be ordered:

`"2" > "1"`

indeed, but`"11" < "2"`

because strings are compared lexicographically, char by char (like words in a dictionary). Therefore you must convert the string into something than can be compared (integers):`ip.split(".").map(&:to_i)`

. For example`"1.2.10.3"`

is converted to`[1, 2, 10, 3]`

. Let's call this transformation`f`

.You could now naively use

`Enumerable#sort`

:`ips.sort { |a, b| f(a) <=> f(b) }`

. But this is both verbose and inefficient (at least O(n log n) calls to`f`

); that's where the Schwartzian transform comes in handy, it performs only O(n) calls to`f`

. Equally importantly, it's now possible to write it in a more concise and declarative manner:`ips.sort_by { |x| f(x) }`

. You can read it as "sort the`ips`

by the order defined by the`f`

transformation".