1. 7kaji

    No comment

    7kaji
Changes in body
Source | HTML | Preview
@@ -1,33 +1,59 @@
```ruby
require 'benchmark'
class Array
+ def quicksort
+ return self if self.size <= 1
+ pivot = self[0]
+ right = Array.new
+ left = Array.new
+ (1..self.size-1).each do |i|
+ if self[i] <= pivot
+ left.push(self[i])
+ else
+ right.push(self[i])
+ end
+ end
+ left = left.quicksort
+ right = right.quicksort
+ return left + [pivot] + right
+ end
+
+ # もっとRubyっぽい書き方
def quick_sort
return self if self.length <= 1
pivot = pop
left, right = partition { |e| e < pivot }
push pivot
left.quick_sort + [pivot] + right.quick_sort
end
end
sample = (0..10000).sort_by { rand }
-#ベンチマークとってみた
puts Benchmark::CAPTION
+puts Benchmark.measure { sample.quicksort }
puts Benchmark.measure { sample.quick_sort }
puts Benchmark.measure { sample.sort }
```
```
user system total real
- 0.040000 0.000000 0.040000 ( 0.035148)
- 0.000000 0.000000 0.000000 ( 0.001645)
+ 0.060000 0.000000 0.060000 ( 0.058320)
+ 0.040000 0.000000 0.040000 ( 0.045914)
+ 0.000000 0.000000 0.000000 ( 0.001648)
```
+Arrayに組み込んでみました。
+quicksortが今回作成したものですが、
+Enumerable#partitionを使うとよりRubyっぽくかけます。
+(quick_sort)
+> [Rubyでソート・アルゴリズムを表現しよう!](http://melborne.github.io/2010/10/12/Ruby/)
+
Array#sortの実装はこちら(C言語)
https://github.com/ruby/ruby/blob/trunk/array.c
(rb_ary_sort_bangメソッドで実装されているっぽい)
-C言語難しくてよくわからない(´・ω・`)
+C言語難しくてよくわからないです(´・ω・`)
+
+