作者godfat (godfat 真常)
看板Ruby
标题Re: [问题] 使用Ruby语法问题
时间Fri Nov 23 19:54:12 2007
※ 引述《forkome (丁丁是个人材)》之铭言：
: def sort(array)
: return [] if array.empty?
: left, right = array[1..-1].partition { |y|
: y <= array.first
: }
: sort(left) + [ array.first ] + sort(right)
: end
: 这是我在网路找到的快速排序法，不过我看不太懂
: (left, right = )这部分的用法
这是 parallel assignment, 等号右边的结果如果是一个 array 的话，
left 会是 array[0] 而 right 会是 array[1]
: left永远取到的值是 [] 空阵列
partition 是一个分割 method, 他会将输入分割成两个 array,
yield 为 true 的和 yield 为 false 的两块。
e.g.,
irb(main):001:0> (0..10).partition{|i| i<5}
=> [[0, 1, 2, 3, 4], [5, 6, 7, 8, 9, 10]]
i < 5 的在 return array 中的 [0], 反之则在 [1]
left, right = (0..10).partition{|i| i<5}
则 left 会是 [0, 1, 2, 3, 4],
right 会是 [5, 6, 7, 8, 9, 10]
你说 left 永远是 [], 表示你传进去的 predicate 的回传都是 false.
在上述的 quick-sort 中，表示你的 array.first 一直是最小的，
也就是 quick-sort 的 worst case...（吧？）
: left,right 这部分是什麽意思呢
上面说明了
: y<= array.first , <=的功用又是什麽呢？
这边是将 array.first 当做分割标准（那词一时想不起来是什麽），
比较理想的办法是取头、中、尾的平均值，这也有个名词...
你熟 quick-sort 吗？不熟的话建议先读读 quick-sort,
否则这边你会不容易看懂为什麽这样可以排序好。
--
In Lisp, you don't just write your program down toward the language,
you also build the language up toward your program.
《Programming Bottom-Up》－ Paul Graham 1993
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.135.28.18
1F：推 forkome:讲解的真详细，我了解QuickSort，只是不懂语法使用 11/23 21:32
2F：→ forkome:之前是用指标的做法，从左右两边开始找中间值 11/23 21:33
3F：→ forkome:而Ruby居然可以分割array，用法更方便，真好用 11/23 21:37
4F：推 godfat:其实有个关键是 gc, 而在 functional programming 中， 11/23 21:52
5F：→ godfat:这样做其实是蛮直觉的作法 11/23 21:52
6F：推 janyfor:真的很直觉 这跟看演算法差不多阿XD 11/23 22:09
7F：→ edwar:pivot? 11/23 22:56