Re: [問題] 使用Ruby語法問題

[godfat (godfat 真常)]

※ 引述《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
推 forkome:講解的真詳細，我了解QuickSort，只是不懂語法使用
→ forkome:之前是用指標的做法，從左右兩邊開始找中間值
→ forkome:而Ruby居然可以分割array，用法更方便，真好用
推 godfat:其實有個關鍵是 gc, 而在 functional programming 中，
→ godfat:這樣做其實是蠻直覺的作法
推 janyfor:真的很直覺 這跟看演算法差不多阿XD
→ edwar:pivot?