[あやふや解消シリーズ]ソートアルゴリズムについて[vol.2]

本記事の概要

• ソートアルゴリズムについて手法および計算量を比較した
• 上記のソートアルゴリズムをRubyを用いて実装した

動機

ソートについての知識をもう一度整理したいため。
また、普段Railsばかり使っていて、Rubyに関する知識があまり身についていない事に不安を覚えたため。

ソートについて

定義

the arrangement of data in a prescribed sequence.
データを所定の順序で並べること。

出典　https://www.lexico.com/en/definition/sort

手法

ここでは、有名なソートアルゴリズムのみを取り扱う。

挿入ソート

$O(n^2)$

insertion_sort.rb

def insertion_sort(array)
  len = array.length

  (1..(len-1)).each do |i| 
    tmp = array[i]
    j = i - 1 

    while j >= 0
      if tmp < array[j]
        array[j], array[j+1] = array[j+1], array[j]
      end 
      j -= 1
      p array
    end 
  end 
  return array
end

require 'pp'

array = Array.new(10){ rand(100) }
pp array
pp (sorted_array = insertion_sort(array))
puts "is_sorted: #{array.sort == sorted_array}"

バブルソート

$O(n^2)$

bubble_sort.rb

def bubble_sort(array)
  ary = array.dup
  pos_max = ary.size- 1

  (0...(pos_max)).each{|n|
    (0...(pos_max - n)).each{|ix|
      iy = ix + 1
      ary[ix], ary[iy] = ary[iy], ary[ix] if ary[ix] > ary[iy]
    }
  }

  ary
end

require 'pp'

array = Array.new(10){ rand(100) } 
pp array
pp (sorted_array = bubble_sort(array))
puts "is_sorted: #{array.sort == sorted_array}"

ヒープソート

$O(nlogn)$

heap_sort.rb

def make_heap(array, parent, end_element)
  temp = array[parent]
  child = 0

  while parent < (end_element + 1) / 2
    left_child = (parent * 2) + 1
    right_child = left_child + 1

    if right_child <= end_element && array[right_child] > array[left_child]
      child = right_child
    else
      child = left_child
    end

    if temp >= array[child]
      break
    end

    array[parent] = array[child]
    parent = child
  end

  array[parent] = temp
end

def heap_sort(array)
  number_of_elements = array.count
  center = (number_of_elements - 1) / 2
  while center >= 0
    make_heap(array, center, number_of_elements - 1)
    center += -1
  end

  end_element = number_of_elements - 1
  while end_element > 0
    array[0], array[end_element] = array[end_element], arr[0]
    make_heap(array, 0, end_element - 1)
    end_element += -1
  end
end

require 'pp'

array = Array.new(10){ rand(100) } 
pp array
pp (sorted_array = heap_sort(array))
puts "is_sorted: #{array.sort == sorted_array}"

マージソート

$O(nlogn)$

merge_sort.rb

def merge_sort array
  return array if array.length == 1
  return [array.min, array.max] if array.length == 2

  half = array.length / 2

  left = merge_sort array[0..(half-1)]
  right = merge_sort array[half..-1]

  lv = left.shift
  rv = right.shift
  Array.new(array.size){
    if lv < rv
      lv.tap{ lv = left.shift || right[-1] || rv }
    else
      rv.tap{ rv = right.shift || left[-1] || lv }
    end
  }
end

require 'pp'

array = Array.new(10){ rand(100) }
pp array
pp (sorted_array = merge_sort(array))
puts "is_sorted: #{array.sort == sorted_array}"

クイックソート

$O(nlogn)$

quick_sort.rb

# ピボットは平均値を選択

def average(array)
  avg = array.sum / array.length
end

def average_sample(array, count)
  average(array.sample(count))
end

def select_pivot array, size
  if size < 4096
    average(array)
  else
    average_sample(array, 16)
  end
end

def qsort(array)
  if array.size == 1
    return array
  elsif array.size == 2
    return array if array[0] < array[1]
    return [array[1],array[0]]
  end

  pivot = select_pivot array, array.length
  left, right = array.partition{|num| num < pivot }
  qsort(left) + qsort(right)
end

require 'pp'

array = Array.new(10){ rand(100) }
pp array
pp (sorted_array = qsort(array))
puts "is_sorted: #{array.sort == sorted_array}"

参考

Qiita / @asm / Rubyで各種ソートアルゴリズム
Hatena Blog / Verification of the hypothesis / 【アルゴリズムの勉強】Rubyでヒープソートを書いてみる
YYUUIIKK BLOG 日々のメモ / Rubyで挿入ソート