アルゴリズム | クイックソート

概要

クイックソート

内容

最良計算量および平均計算量はO( n\log n )。

ソート仕様

・適当な数（ピボットという）を選択する
・ピボットより小さい数を前方、大きい数を後方に移動
・二分割された各々のデータを、それぞれソートする（再帰）

コード

quick_sort.rb

# encoding: utf-8

class Array
  def quick_sort
    return self if self.size <= 1
    pivod = self.first
    lefts, rights = [], []
    (1..self.size - 1).each do |i|
      next if lefts.push_if(self[i]) {self[i] < pivod}
      rights.push_if(self[i]) {self[i] > pivod}
    end
    lefts, rights = lefts.quick_sort, rights.quick_sort
    lefts.push(pivod) + rights
  end

  def push_if(value, &block)
    self.push value if block.call
  end
end

テストコード

quick_sort_spec.rb

# encoding: utf-8
require_relative "../quick_sort"

describe Array do
  cases = [
    {
      input_ary: [5,4,3,2,1],
      expected: [1,2,3,4,5]
    },
    {
      input_ary: [1,2,3,4,5],
      expected: [1,2,3,4,5]
    },
    {
      input_ary: [1,4,3,2,5],
      expected: [1,2,3,4,5]
    },
    {
      input_ary: [2,4,3,5,1],
      expected: [1,2,3,4,5]
    },
    {
      input_ary: [3,4,5,2,1],
      expected: [1,2,3,4,5]
    }
  ]

  cases.each do |c|
    it "#quick_sort" do
      actual = c[:input_ary].quick_sort
      expect(actual).to eq(c[:expected])
    end
  end
end