diff options
| -rw-r--r-- | mrbgems/mruby-enum-ext/mrblib/enum.rb | 2 | ||||
| -rw-r--r-- | mrblib/array.rb | 39 | ||||
| -rw-r--r-- | mrblib/enum.rb | 46 |
3 files changed, 40 insertions, 47 deletions
diff --git a/mrbgems/mruby-enum-ext/mrblib/enum.rb b/mrbgems/mruby-enum-ext/mrblib/enum.rb index 7e101cf65..7741e515d 100644 --- a/mrbgems/mruby-enum-ext/mrblib/enum.rb +++ b/mrbgems/mruby-enum-ext/mrblib/enum.rb @@ -201,7 +201,7 @@ module Enumerable ary.push([block.call(e), i]) } if ary.size > 1 - __sort_sub__(ary, ::Array.new(ary.size), 0, 0, ary.size - 1) do |a,b| + __sort_sub__(ary, 0, ary.size - 1) do |a,b| a <=> b end end diff --git a/mrblib/array.rb b/mrblib/array.rb index d5a2d8405..be98f217e 100644 --- a/mrblib/array.rb +++ b/mrblib/array.rb @@ -1,3 +1,4 @@ +# coding: utf-8 ## # Array # @@ -193,9 +194,45 @@ class Array include Enumerable ## + # Quick sort + # a : the array to sort + # left : the beginning of sort region + # right : the end of sort region + def __sort_sub__(a, left, right, &block) + if left < right + i = left + j = right + pivot = a[i + (j - i) / 2] + while true + while ((block)? block.call(a[i], pivot): (a[i] <=> pivot)) < 0 + i += 1 + end + while ((block)? block.call(pivot, a[j]): (pivot <=> a[j])) < 0 + j -= 1 + end + break if (i >= j) + tmp = a[i]; a[i] = a[j]; a[j] = tmp; + i += 1 + j -= 1 + end + __sort_sub__(a, left, i-1, &block) + __sort_sub__(a, j+1, right, &block) + end + end + # private :__sort_sub__ + + ## # Sort all elements and replace +self+ with these # elements. def sort!(&block) - self.replace(self.sort(&block)) + size = self.size + if size > 1 + __sort_sub__(self, 0, size - 1, &block) + end + self + end + + def sort(&block) + self.dup.sort!(&block) end end diff --git a/mrblib/enum.rb b/mrblib/enum.rb index fb55efcf8..12bd1d37b 100644 --- a/mrblib/enum.rb +++ b/mrblib/enum.rb @@ -316,45 +316,6 @@ module Enumerable alias select find_all ## - # TODO - # Does this OK? Please test it. - def __sort_sub__(sorted, work, src_ary, head, tail, &block) - if head == tail - sorted[head] = work[head] if src_ary == 1 - return - end - - # on current step, which is a src ary? - if src_ary == 0 - src, dst = sorted, work - else - src, dst = work, sorted - end - - key = src[head] # key value for dividing values - i, j = head, tail # position to store on the dst ary - - (head + 1).upto(tail){|idx| - if ((block)? block.call(src[idx], key): (src[idx] <=> key)) > 0 - # larger than key - dst[j] = src[idx] - j -= 1 - else - dst[i] = src[idx] - i += 1 - end - } - - sorted[i] = key - - # sort each sub-array - src_ary = (src_ary + 1) % 2 # exchange a src ary - __sort_sub__(sorted, work, src_ary, head, i - 1, &block) if i > head - __sort_sub__(sorted, work, src_ary, i + 1, tail, &block) if i < tail - end -# private :__sort_sub__ - - ## # Return a sorted array of all elements # which are yield by +each+. If no block # is given <=> will be invoked on each @@ -364,12 +325,7 @@ module Enumerable # # ISO 15.3.2.2.19 def sort(&block) - ary = [] - self.each{|*val| ary.push(val.__svalue)} - if ary.size > 1 - __sort_sub__(ary, ::Array.new(ary.size), 0, 0, ary.size - 1, &block) - end - ary + self.map{|*val| val.__svalue}.sort end ## |