就活の時期だし...アルゴリズム復習してみようかな←
もしデザ @ 慶應SFC • 2011/7/8 • #moshideza • Part 1
1年前にこの動画を見てヤル気だしたの思い出してもっかい見てみた。
(ちなみにpart6まである)
本場の人の話を聞くのはとてもおもしろい。
かつモチベーションがあがる!
もっかい見てみて今の自分の状況にピッタリの内容があった。人材の話。(part5〜)
シリコンバレーでの面接では簡単なアルゴリズムのコードを問うらしい。
これはショートカットさせない為。(詳しくは動画見てみてくだはい。)
ってことで自分も就活生だしアルゴリズムを復習してみた...
この講演では動的計画法の問題を例にしていた。(所謂ナップサック問題でおk?)
が、アルゴリズムをあまり意識していないダメダメな自分は基本的なソートの問題をやってみた。
ソートといえば、クイックソートっしょ!
ということで今回はクイックソートをrubyで実装。
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 end p [1,3,99,2,54,22,0,6].quicksort
実行結果はこんなかんじ。たぶんおk。
$ ruby quick_sort.rb [0, 1, 2, 3, 6, 22, 54, 99]
せっかくだからArrayクラスに組み込んでみた。
ぐぐってみたら、もっとrubyっぽいスマートな書き方があったのでそちらも参考に載せておく。(変数名は統一させてもらいました。。)
class Array def quick_sort return self if length <= 1 pivot = pop left, right = partition { |e| e < pivot } push pivot left.quick_sort + [pivot] + right.quick_sort end end
※補足
partition() は要素を2つの配列に分けるメソッド
↑クイックソートの為にあるようなメソッドだなぁと思いましたw なにかと便利そう!
この調子で今後もアルゴリズム勉強していきたいと思いまっす。