Yuki's Tech Blog

仕事で得た知見や勉強した技術を書きます。

トップ > アルゴリズム > 主要なソートについてまとめる

主要なソートについてまとめる

アルゴリズム

目次

概要

ソートについて学んだので、まとめます。

今回は以下の基本的な3つのソート

と応用的な3つのソート

をまとめます。 あと、基本的には、ソートするので、ソート済みではない数値を要素とした配列(a)をinputとします。

バブルソート

バブルソートとは

バブルソートとは、隣り合う2項の大小関係を比較してソートしていくよなソート方法です。

具体的な手順

  1. a[0]とa[1]の大小関係を比較する。
  2. a[0] > a[1]の場合、a[0]とa[1]の値を入れ替える。1ループごとに入れ替えていく。
  3. それをどんどん繰り返していって、一番でかい数を一番右端に配置する。
  4. 一番でかい右端の数を除いて、1 ~ 4の手順を繰り返す
  5. 最後までループが完了したら、ソートが完了している。

サンプルコード

# @param [Array<Integer>] numbers
# return [Array<Integer>]
def bubble_sort(numbers)
  (0..(numbers.length - 1)).each do |i|
    (1..(numbers.length - (i + 1))).each do |j|
      if numbers[j - 1] > numbers[j]
        numbers[j - 1], numbers[j] = numbers[j], numbers[j - 1]
      end
    end
  end
  
  numbers
end

numbers = [6, 1, 2, 9, 0]
puts "整列前: ", numbers.join(" ")

sorted_numbers = bubble_sort(numbers)
puts "整列後: ", sorted_numbers.join(" ")

# => 
# 整列前: 
# 6 1 2 9 0
# 整列後: 
# 0 1 2 6 9

選択ソート

選択ソートとは

選択ソートとは、ソート順序が確定していないデータから、最小値を見つけて、その最小値を左に置くことを繰り返すことで、ソートをしていくようなソート方法です。

具体的な手順

  1. 配列aの最小値を取得する
  2. その最小値を一番左に配置する。
  3. 1 ~ 3を繰り返す
  4. 最後までループが完了したら、ソートが完了している。

サンプルコード

# @param [Array<Integer>] numbers
# return [Array<Integer>]
def selection_sort(numbers)
  (0..numbers.length - 1).each do |i|
    minimum_numbers = numbers[i..].min
    min_index = numbers.find_index(minimum_numbers)
    numbers[i], numbers[min_index] = numbers[min_index], numbers[i]
  end
  
  numbers
end

numbers = [6, 1, 2, 9, 0]
puts "整列前: ", numbers.join(" ")

sorted_numbers = selection_sort(numbers)
puts "整列後: ", sorted_numbers.join(" ")

# => 
# 整列前: 
# 6 1 2 9 0
# 整列後: 
# 0 1 2 6 9

挿入ソート

挿入ソートとは

挿入ソートとは、データを整列済と未整列の2つに分類し、未整列データの先頭の要素を、整列済みデータの正しい場所に挿入していくことで、ソートしていく方法のことです。

具体的な手順

  1. 未整列データの一番先頭の要素を、整列済みデータとする
  2. 2番目以降の未整列データの一番先頭の要素を、1番目と比較して、適切な位置に挿入する。
  3. 1 ~ 3を繰り返す。
  4. 最後までループが完了したら、ソートが完了している。

サンプルコード

# @param [Array<Integer>] numbers
# return [Array<Integer>]
def insertion_sort(numbers)
  # 0番目を整列済みとする
  (1..numbers.length - 1).each do |i|
    position = i
    # 指定したインデックス以降で隣り合う2項の大小関係をチェックしている
    # ここで条件式を満たさないってことは、positionが0か、
    # numbers[position]がちゃんとnumbers[position - 1]よりでかい(インデックスに従ってちゃんと昇順になっている)
    while position.positive? && numbers[position - 1] > numbers[position]
      numbers[position - 1], numbers[position] = numbers[position], numbers[position - 1]
      # 一個ずらして、その前の数と大小関係を比較する
      position -= 1
    end
  end
  
  numbers
end

numbers = [6, 1, 2, 9, 0]
puts "整列前: ", numbers.join(" ")

sorted_numbers = insertion_sort(numbers)
puts "整列後: ", sorted_numbers.join(" ")

# => 
# 整列前: 
# 6 1 2 9 0
# 整列後: 
# 0 1 2 6 9

クイックソート

クイックソートとは

クイックソートは、真ん中の要素(インデックスが a.length / 2のような要素)を基準値として、その基準値より大きい要素を集めた配列と、その基準値より小さい配列を集めた配列を作って、作成した配列に対してもクイックソートを繰り返すことで、ソートしていくようなソート方法です。

クイックソートでは1つの大きな問題を複数の部分問題に分けて、それらを再起的に解くことによって、結果的に大きな問題を解いています。つまり、クイックソートでは、分割統治法の考え方を用いていることが分かります。

ja.wikipedia.org

今までの基本的なソートの計算量はO(N2)ですが、クイックソートの計算量はO(NlogN)であり、早いです。

具体的な手順

  1. 整列されていない要素の真ん中の値(index = a.length / 2)を求める。この値を基準値とする
  2. 基準値より小さい配列を作成する。同様に基準値より大きい配列を作成する
  3. それらの配列に対して、クイックソートを実施する。クイックソートの関数に渡された配列の要素数が1の場合、そのまま配列を返す
  4. ソートされた左側の配列 + 基準値 + ソートされた右側の配列を実行して、それを戻り値とする。
  5. ソートされている

サンプルコード

# @param [Array<Integer>] numbers
# return [Array<Integer>]
def quick_sort(numbers)
  # 空の配列に対してquick_sortが呼ばれる可能性がある
  return numbers if numbers.length == 1 || numbers.empty?
  
  standard_index = numbers.length / 2
  standard_number = numbers[standard_index]
  left_numbers = numbers.filter.with_index { |number, i| i != standard_index && number < standard_number }
  right_numbers = numbers.filter.with_index { |number, i| i != standard_index && number >= standard_number }
  
  sorted_left_numbers = quick_sort(left_numbers)
  sorted_right_numbers = quick_sort(right_numbers)
  
  sorted_left_numbers.push(standard_number).concat(right_numbers)
end

numbers = [6, 1, 2, 9, 0]
puts "整列前: ", numbers.join(" ")

sorted_numbers = quick_sort(numbers)
puts "整列後: ", sorted_numbers.join(" ")

# => 
# 整列前: 
# 6 1 2 9 0
# 整列後: 
# 0 1 2 6 9

マージソート

マージソートとは

マージソートとは、真ん中のインデックスをさかえめにして2つのグループを作って、そのグループに対して要素が1になるまでマージソートを繰り返して、最終的にソートをしてくようなソート方法です。

具体的な手順

  1. 真ん中のインデックスをさかえめにして、そのさかえめのインデックス以上のインデックスを持つ配列と、そのさかえめのインデックス未満のインデックスを持つ配列に分ける
  2. そしてグループに対して、マージソートを再起的に繰り返して、そのグループの要素数が1になるまで繰り返す。
  3. ソートされたグループを、右側のグループをリバースさせて合体させる(小 ~ 大 ~ 小のレイヤーに配列がなっている)。その後、その合体させた配列の最も左の要素と最も右の要素を比較していって、小さい方を先に別の配列に入れる。その後、合体させた配列から小さい方を削除する。それを繰り返すと、ソートされた配列が完成する。

iをa.length / 2とすると、 クイックソートは、a[0.. i - 1] + a[i] + a[i + 1 ..]でソートしていくが、マージソートは、a[0..i - 1] + a[i..]でソートしていくので、そこを間違えないようにしましょう。

サンプルコード

# Your code here!
# @param [Array<Integer>] numbers
# return [Array<Integer>]
def merge_sort(numbers)
  # 空の配列に対してquick_sortが呼ばれる可能性がある
  return numbers if numbers.length == 1 || numbers.empty?

  middle_index = numbers.length / 2
  left_numbers = numbers[0...middle_index]
  right_numbers = numbers[middle_index..]
  
  sorted_left_numbers = merge_sort(left_numbers)
  sorted_right_numbers = merge_sort(right_numbers)
  merge_numbers = sorted_left_numbers.concat(sorted_right_numbers.reverse)
  
  sorted_merge_numbers = []
  until merge_numbers.empty?
    # 要素が1個しかに場合、 = になるだけ
    if merge_numbers.first <= merge_numbers.last
      sorted_merge_numbers.push(merge_numbers.shift)
    else
      sorted_merge_numbers.push(merge_numbers.pop)
    end
  end

  sorted_merge_numbers
end

numbers = [6, 1, 2, 9, 0]
puts "整列前: ", numbers.join(" ")

sorted_numbers = merge_sort(numbers)
puts "整列後: ", sorted_numbers.join(" ")

# => 
# 整列前: 
# 6 1 2 9 0
# 整列後: 
# 0 1 2 6 9

ヒープソート

ヒープソートとは

まず、どの頂点に対しても、必ず親の値 >= 子の値が成立する木構造のことを、ヒープだったり、ヒープ木と呼びます。ヒープを作ることで、根の値が一番大きく、一番深い葉の値が一番小さくなります。

ヒープソートでは、ヒープを作った後に、根と葉の値を交換します。その後、元々の根を除いた木に対して、ヒープを作ります。そして同じことを繰り返すことで、最終的にソートされます。

具体的な手順

  1. 与えられた配列を木構造として捉える(頂点iの値がa[i]、頂点iの子がa[2i + 1]とa[2i + 2])
  2. 与えられた配列から、ヒープを作る
  3. ヒープの根と一番深い葉の値(つまり、配列の一番最初と一番最後の値)を交換します。
  4. その後、元々の根を除いた頂点で、1 ~ 3を繰り返す。
  5. ソートされている。

www.momoyama-usagi.com

サンプルコード

# @param [Array<Integer>] numbers
# return [Array<Integer>]
def create_heap(numbers)
  # 調べる対象
  # ヒープは親の値 >= 子の値になっていれば良いので、子供は調べなくて良い
  parent_count = numbers.length / 2 - 1
  
  while parent_count >= 0
    k = parent_count
    
    loop do
      # 深い親から先に見ていく
      parent = numbers[k]
      left_child = numbers[2 * k + 1]
      right_child = numbers[2 * k + 2]
    
      # left_childがいないってことは、子供が存在しないノード(つまり、子供)
      break unless left_child
    
      maximum_number = if right_child
                         [parent, left_child, right_child].max
                       else
                         [parent, left_child].max
                       end
    
      case maximum_number
      when parent
        break
      when left_child
        numbers[k], numbers[2 * k + 1] = left_child, parent
        # 交換先で 親が親の値 >= 子の値をチェックする
        k = 2 * k + 1
      when right_child
        numbers[k], numbers[2 * k + 2] = right_child, parent
        # 交換先で 親が親の値 >= 子の値をチェックする
        k = 2 * k + 2
      end
    end
    
    # 上の親でチェックする
    parent_count -= 1
  end
  
  numbers
end

# @param [Array<Integer>] numbers
# return [Array<Integer>]
def heap_sort(numbers)
  heap = create_heap(numbers)
  (1..numbers.length - 1).reverse_each do |i|
    heap[0], heap[i] = heap[i], heap.first
    heap[0..(i - 1)] = create_heap(heap[0..(i - 1)])
  end
  
  heap
end

終わり

計算量とかの証明がまだ深掘りできていないので、いずれ深掘りしようと思います。

参考記事

www.momoyama-usagi.com