Pi Horse Pi Horse - 9 months ago 25
Ruby Question

Sorting an array in Ruby (Special Case)

I have an array in Ruby which has values as follows

xs = %w(

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

ys = %w(

I have tried using the
function, but it places
. I am not sure why that happens


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:

  1. 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 "" is converted to [1, 2, 10, 3]. Let's call this transformation f.

  2. 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".