就活の時期だし...アルゴリズム復習してみようかな←


もしデザ @ 慶應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 なにかと便利そう!

この調子で今後もアルゴリズム勉強していきたいと思いまっす。


アルゴリズムを学ぼう
川中真耶, 杵渕朋彦, 椎名俊輔
アスキー・メディアワークス
発行日: 2012-06-01
対応フォーマット: PDF