AOJ ALDS1_6_C Quick Sort - 電波ビーチ

ソートアルゴリズムの実装自体やったことないぜ！！！！！！！！！メリークリスマスイヴ！！！！！！！！！

n 枚のカードの列を整列します。１枚のカードは絵柄(S, H, C, またはD)と数字のペアで構成されています。これらを以下の疑似コードに基づくクイックソートで数字に関して昇順に整列するプログラムを作成してください。partition は ALDS1_6_B の疑似コードに基づくものとします。

また、与えられた入力に対して安定な出力を行っているかを報告してください。ここでは、同じ数字を持つカードが複数ある場合、それらが入力で与えられた順序であらわれる出力を「安定な出力」とします。

安定な出力かどうかとは

クイックソートは与えられた配列の要素同士を交換するので安定でない配列ということらしい。安定な出力をするソートにはマージソートがある。

クイックソートとマージソートを実装してそれぞれに配列を投げて得られた結果が同じならば安定、異なれば非安定ということにする。

マージソート

分割統治してソートする感じ。半分ずつに分割する部分とそれを統合（merge）する部分がある

半分ずつに分ける
分けたうちの左側と右側を比較
- 先頭から比較していって小さい方を選択
比較してできた結果からさらに大きい単位で比較

ソート済のLとRをみたときにそれぞれ上の処理をやるとできた結果Aは全体でソートされている。これを小さい単位（2数の比較）から大きくしていく感じ

def merge(a, l, m, r)
  l_arr = a[l, m-l] << 10000000000000000000
  l_i = 0
  r_arr = a[m, r-m] << 10000000000000000000
  r_i = 0

  (l...r).each do |idx|
    # 小さい方から入れていく
    if l_arr[l_i] <= r_arr[r_i]
      a[idx] = l_arr[l_i]
      l_i+=1
    else
      a[idx] = r_arr[r_i]
      r_i+=1
    end
  end
end

def merge_sort(a, left, right)
  if 1 < right-left
    mid = (right+left)/2
    merge_sort(a, left, mid)
    merge_sort(a, mid, right)
    merge(a, left, mid, right)
  end
end

これのmergeメソッドのとこが統合に当たる。あるいは配列ごと作ってぶちこむ手もある。LLならこっちのが簡単そう*1。どっちもやってるこたぁおんなじ

def merge(left, right)
  ret = []
  loop do
    break if left.size.zero? && right.size.zero?
    # 先頭の小さい方から入れていく
    if left.empty? || (!right.empty? && right.first <= left.first)
      ret << right.shift
    elsif right.empty? || (!left.empty? && left.first < right.first)
      ret << left.shift
    else
      p "fuck"
      exit
    end
  end 
  ret
end

def merge_sort(a)
  return a if a.size == 1
  mid = a.size/2
  left = a[0, mid]
  right = a[mid, mid+1]
  left = merge_sort(left)
  right = merge_sort(right)
  return merge(left, right)
end

これも分割統治。配列から適当なpivotを決めて、pivotより左側に「pivotより小さい要素」、右側に「pivotより大きい要素」がくるようにする。この操作をpartitionと呼ばうらしい。partitionによって配列の更新と、更新後のpivotのインデックスを返すようにすれば、pivotより小さい部分の配列と大きい部分の配列に分割できるのでそれらに対して同じように処理していくのだ。partitionの部分はなんか説明しにくいので見てくれ

def partition(a, l, r)
  pivot = a[r-1]
  j = l-1
  (l...r).each do |i|
    if a[i] <= pivot
      j+=1
      a[j], a[i] = a[i], a[j]
    end
  end
  return j
end

def quick_sort(a, l, r)
  if 1 < r-l
    q = partition(a, l, r)
    quick_sort(a, l, q)
    quick_sort(a, q+1, r)
  end
end

だいたいの言語のsort関数なんかはサイズが小さいときはマージソートで大きいときはクイックソート使うらしいみたいなのを聞いたことがある。知らんけど

実装

入力される要素に合わせて上で書いたやつを書き換えたりなんかしたり

def partition(a, l, r)
  pivot = a[r-1][1]
  j = l-1
  (l...r).each do |i|
    if a[i][1] <= pivot
      j+=1
      a[j], a[i] = a[i], a[j]
    end
  end
  return j
end

def quick_sort(a, l, r)
  if 1 < r-l
    q = partition(a, l, r)
    quick_sort(a, l, q)
    quick_sort(a, q+1, r)
  end
end


def merge(a, l, m, r)
  l_arr = a[l, m-l] << ['死', 10000000000000000000]
  l_i = 0
  r_arr = a[m, r-m] << ['死', 10000000000000000000]
  r_i = 0
  
  (l...r).each do |idx|
    # 小さい方から入れていく
    if l_arr[l_i][1] <= r_arr[r_i][1]
      a[idx] = l_arr[l_i]
      l_i+=1
    else
      a[idx] = r_arr[r_i]
      r_i+=1
    end
  end
end

def merge_sort(a, left, right)
  if 1 < right-left
    mid = (right+left)/2
    merge_sort(a, left, mid)
    merge_sort(a, mid, right)
    merge(a, left, mid, right)
  end
end

n = gets.to_i
a = []
n.times do
  a << gets.chomp.split.map{|x| x.match?(/\d/) ? x.to_i : x}
end
b = a.clone
quick_sort(a, 0, n)
merge_sort(b, 0, n)

puts a == b ? "Stable" : "Not stable"
a.each do |av|
  puts "#{av[0]} #{av[1]}"
end

はいよくできましたえらいね。クリスマスプレゼントは職がいいです

*1:LLなら軽率に配列を作ったりぶっ壊すのが楽という雑魚認識

安定な出力かどうか とは

マージソート

クイックソート

実装

安定な出力かどうかとは