sortとsort_by

今回は、Rubyに関して書きます

sortメソッド

• Arrayクラスのメソッド
  • 配列内の要素を並び替えすためのメソッド
    • 数の大きさ
    • 行の長さ
    • アルファベット順
    • アルファベット逆順
    • などなど

たとえば、

array = ["a", "c", "b", "f", "d", "e"]

sorted = array.sort do |a, b|
  a <=> b
end

p sorted #=> ["a", "b", "c", "d", "e", "f"]

sortメソッドは、配列の要素を余分に呼び出します。

どういう事かというと、

array = ["a", "c", "b", "f", "d", "e"]
i = 0

sorted = array.sort do |a, b|
  i += 2
  a <=> b
end

p sorted #=> ["a", "b", "c", "d", "e", "f"]
p i #=> 20

つまり、サイズが6の配列に対して、要素の呼び出し回数が20回であり、
これが、サイズの大きい配列とかになると非常に時間がかかってしまいます。

sort_byメソッド

sortメソッドでは非常に処理に時間がかかってしまう場合に使用されるのが、sort_byメソッド

array = ["a", "c", "b", "f", "d", "e"]
i = 0

sorted = array.sort_by do |item|
  i += 1
  item
end

p sorted #=> ["a", "c", "b", "f", "d", "e"]
p i #=> 6

sort_byメソッドは、すべての要素に対して、同じ条件でソートを行ないたい時に使用します。

実際の使用例

mysql> select * from users;
+----------+--------+
| name     |    age |
+----------+--------+
| タナカ   |     22 |
| スズキ   |     22 |
| サトウ   |     21 |
| ヨシダ   |     22 |
+--------- +--------+
4 rows in set (0.01 sec)

sort_byメソッドは、並び替え条件に配列を指定することができる。

users = User.find(:all)

sorted = users.sort_by do |u|
  [u.age, u.name]
end

p sorted.map(&:name) #=> [サトウ, スズキ, タナカ, ヨシダ]

この場合、第一条件がageで第二条件がnameです。

安定なソートと不安定なソート(stable_sort と unstable_sort)

• 安定なソート
  • ソート条件が同じであった場合、もとの順序を保持したまま並び替えを行うソートのこと
  • 参照：安定ソート - Wikipedia
• 不安定なソート
  • ソート条件以外の条件の並び順が元の並び順とは依存しないソートのこと

で、sort_byは安定なソートではありません。
参考：プログラミング言語 Ruby リファレンスマニュアル

そこで、sort_byで安定ソートを実現する方法を紹介します。

users = User.find(:all)
i = 0

sorted = users.sort_by do |u|
  [u.age, i += 1]
end

p sorted.map(&:name) #=> [サトウ, タナカ, スズキ, ヨシダ]

参考：http://blog.goo.ne.jp/minimal_room/e/91ad1e860020316a219e751502ef085e

つまり、どういう事かというと、第一条件が同じ時は第二条件であるiで並び替えます。
ということは、第一条件が同じ要素は、i(元々の配列に格納されている順に大きくなる)で並び替えるので、並び順を崩すことなく、並び替えを行うことができます。

最後までお読みいただきありがとうございました。
何か不備等ございましたら、ツッコミ等などよろしくお願い致します。

たのしいRuby 第3版

----- 追記 -----
安定なソートと不安定なソートに関して追記しました(2011/05/02)