def bubble_sort(c)
  c.size.times do |i|
    (c.size - 1).downto(i+1) do |j|
      if c[j][1] < c[j - 1][1]
        c[j], c[j - 1] = c[j - 1], c[j]
      end
    end
  end
  c
end

def select_sort(c)
  c.size.times do |i|
    m = i
    i.upto(c.size - 1) do |j|
      if c[j][1] < c[m][1]
        m = j
      end
    end
    c[i], c[m] = c[m], c[i]
  end
  c
end

input = %w[H4 C9 S4 D2 C3]
input.map! do |e|
  e =~ /(?<m>\w)(?<n>\d+)/
  [$1, $2.to_i]
end
s = [bubble_sort(input), select_sort(input)]
check = input.group_by {|e| e[1]}.select {|k,v| v.size > 1}
m = ['Stable', 'Stable']
2.times do |n|
  n = s[n]
  check.each do |k, v|
    if n.select {|e| e[1] == k} != v
      m[n] = 'Not stable'
    end
  end
end

puts s[0].map(&:join).join(' ')
puts m[0]
puts s[1].map(&:join).join(' ')
puts m[1]