Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
import copy

N = int(input())
C = input().split(' ')

def bubble_sort(bubble_C, N):
    for i in range(N):
        for j in range(i+1, N)[::-1]:
            if int(bubble_C[j][1]) < int(bubble_C[j-1][1]):
                tmp = bubble_C[j]
                bubble_C[j] = bubble_C[j-1]
                bubble_C[j-1] = tmp
    return bubble_C

def selection_sort(sel_C, N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if int(sel_C[j][1]) < int(sel_C[minj][1]):
                minj = j
        tmp = sel_C[i]
        sel_C[i] = sel_C[minj]
        sel_C[minj] = tmp
    return sel_C

def check_stable(C1, C2):
    C_order_table = {}
    sorted_C_order_table = {}
    for i in range(len(C1)):
        if C_order_table.get(C1[i][1]):
            C_order_table[C[i][1]] += C1[i][0]
        else:
            C_order_table[C1[i][1]] = C1[i][0]
        
        if sorted_C_order_table.get(C2[i][1]):
            sorted_C_order_table[C2[i][1]] += C2[i][0]
        else:
            sorted_C_order_table[C2[i][1]] = C2[i][0]
    
    is_stable = True
    for n in range(1, 10):
        if C_order_table.get(str(n)) != sorted_C_order_table.get(str(n)):
            is_stable = False
            break
    
    if is_stable:
        print('Stable')
    else:
        print('Not stable')

bubble_C = copy.copy(C)
sel_C = copy.copy(C)

sorted_C = bubble_sort(bubble_C, N)
print(" ".join(sorted_C))
check_stable(C, sorted_C)

sorted_C = selection_sort(sel_C, N)
print(" ".join(sorted_C))
check_stable(C, sorted_C)


# Example run
# Input:
-1
u}U
# Output:
u}U
Stable
u}U
Stable
length = int(input())
eles = [l for l in input().split()]
is_stable = 'Stable'

import copy
_copy = copy.deepcopy(eles)

for i in range(length):
    for j in range(length-1, 0, -1):
        if _copy[j][1] < _copy[j-1][1]:
            _copy[j], _copy[j-1] = _copy[j-1], _copy[j]

print(*_copy)
print(is_stable)

__copy = copy.deepcopy(eles)

for i in range(length-1):
    _min = i
    for l in range(i, length):
        if __copy[l][1] < __copy[_min][1]:
            _min = l
    if __copy[i][1] != __copy[_min][1]:
        __copy[i], __copy[_min] = __copy[_min], __copy[i]
        is_stable = 'Not stable'

print(*__copy)
print(is_stable)

# Example run
# Input:
-1998
8u=^Atb
# Output:
8u=^Atb
Stable
8u=^Atb
Stable
def bubbleSort(numlist):
    n = len(numlist)
    flag = True
    for i in range(n):
        if flag is False:
            break
        flag = False
        for j in range(n - 1, i, -1):
            if numlist[j][1] < numlist[j - 1][1]:
                numlist[j], numlist[j - 1] = numlist[j - 1], numlist[j]
                flag = True

def selectionSort(numlist):
    n = len(numlist)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if numlist[min_index][1] > numlist[j][1]:
                min_index = j
        
        if min_index != i:
            numlist[min_index], numlist[i] = numlist[i], numlist[min_index]

def print_numlist(numlist):
    if len(numlist) == 1:
        print(numlist[0])
    else:
        n = len(numlist)
        for i in range(n - 1):
            print(numlist[i], end=' ')
        print(numlist[-1])

if __name__ == '__main__':
    n = int(input())
    numlist = [num for num in input().replace('\n', '').split(' ')]
    numlist2 = numlist.copy()
    bubbleSort(numlist)
    print_numlist(numlist)
    print('Stable')
    selectionSort(numlist2)
    print_numlist(numlist2)
    flag = True
    for i in range(len(numlist)):
        if numlist[i] != numlist2[i]:
            flag = False
            break
    if flag:
        print('Stable')
    else:
        print('Not stable')


# Example run
# Input:
-240192
d-3D,
# Output:
d-3D,
Stable
d-3D,
Stable
import copy


def SelectionSort(arr, n):
    for i in range(n):
        mini = i
        for j in range(i, n):
            if arr[j]['val'] < arr[mini]['val']:
                mini = j
        if mini != i:
            arr[i], arr[mini] = arr[mini], arr[i]
    return


def BubleSort(arr, n):
    for i in range(n):
        for j in range(n - 1, i, -1):
            if arr[j]['val'] < arr[j-1]['val']:
                arr[j], arr[j-1] = arr[j-1], arr[j]
    return


def isStable(inarr, comparr, n):
    i = 0
    while i < n:
        tmpVal = comparr[i]['val']
        for j in range(n):
            if inarr[j]['val'] == tmpVal:
                if inarr[j]['crd'] == comparr[i]['crd']:
                    if i != n - 1 and comparr[i+1]['val'] == tmpVal:
                        i += 1
                    else:
                        break
                else:
                    return 'Not stable'
        i += 1
    return 'Stable'



n = int(input())
arr = input().split()
tar = []

for s in arr:
    tar.append({'crd': s[0], 'val': s[1], 'str': s})

bub = copy.copy(tar)
BubleSort(bub, n)

w = ""
for s in bub:
    w += s['str'] + ' '
print(w)
print(isStable(tar, bub, n))

bub = copy.copy(tar)
SelectionSort(bub, n)

w = ""
for s in bub:
    w += s['str'] + ' '
print(w)
print(isStable(tar, bub, n))



# Example run
# Input:
-1
mY%@Uzn-T
# Output:
mY%@Uzn-T 
Stable
mY%@Uzn-T 
Stable
n = int(input())
a = list(map(str,input().split()))

# バブルソート
def bubble(a, n):
    for i in range(n):
        for j in range(n-1,i,-1):
            if int(a[j][1]) < int(a[j-1][1]):
                tmp = a[j]
                a[j] = a[j-1]
                a[j-1] = tmp
    return a

# 選択ソート
def selection(a, n):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if int(a[j][1]) < int(a[minj][1]):
                minj = j
        tmp = a[i]
        a[i] = a[minj]
        a[minj] = tmp
    return a

# 安定性判定
def stable(in_a, out_a, n):
    for i in range(n):
        for j in range(i+1, n):
            for a in range(n):
                for b in range(a+1,n):
                    if in_a[i] == in_a[j] and in_a[i] == out_a[b] and in_a[j] == out_a[a]:
                        return False
    return True

print(' '.join(bubble(a,n)))
print(stable(a, bubble(a,n), n))
print(' '.join(selection(a,n)))
print(stable(a, selection(a,n), n))



# Example run
# Input:
-415721250
zsjHO[h
# Output:
zsjHO[h
True
zsjHO[h
True
# -*- coding: utf-8 -*-


def bubble_sort(cards, num):
    flag = True
    while flag:
        flag = False
        for left in range(num-1, 0, -1):
            right = left - 1
            if cards[left][1] < cards[right][1]:
                cards[right], cards[left] = cards[left], cards[right]
                flag = True

    print(list_to_str(cards))


def selection_sort(cards, num):
    for head in range(num):
        min_i = head

        for target in range(head+1, num):
            if cards[target][1] < cards[min_i][1]:
                min_i = target
        cards[head], cards[min_i] = cards[min_i], cards[head]

    print(list_to_str(cards))


def is_stable(before, after, num):
    for i in range(num):
        for j in range(i+1, num):
            for a in range(num):
                for b in range(a+1, num):
                    if before[i][1] == before[j][1]\
                    and before[i] == after[b]\
                    and before[j] == after[a]:
                        return 'Not stable'
    return 'Stable'


def list_to_str(l, delimiter=' '):
    # The default delimiter is one space.
    return delimiter.join([str(v) for v in l])


if __name__ == '__main__':
    num = int(input())
    cards = input().split()
    cards_for_bubble = cards.copy()
    cards_for_selection = cards.copy()

    bubble_sort(cards_for_bubble, num)
    print(is_stable(cards, cards_for_bubble, num))

    selection_sort(cards_for_selection, num)
    print(is_stable(cards, cards_for_selection, num))

# Example run
# Input:
-58867430
k^S/8NM/
# Output:
k^S/8NM/
Stable
k^S/8NM/
Stable
import re
import copy
pattern = r'([0-9])'
repatter = re.compile(pattern)

n = int(input())
text = input()

*lists, = text.split(" ")
lists2 = copy.copy(lists)
lists3 = copy.copy(lists)


# バブルソート
def bubble_sort(a):
    flag = 1
    i = 0
    while flag:
        flag = 0
        for j in range(n-1, i, -1):
            x = repatter.findall(a[j])
            y = repatter.findall(a[j-1])
            if x < y:
                a[j], a[j-1] = a[j-1], a[j]
                flag = 1
        i += 1
    print(*a)
    print("Stable")


# 選択ソート
def select_sort(a):
    for i in range(n):
        min_j = i
        for j in range(i+1, n):
            x = repatter.findall(a[j])
            y = repatter.findall(a[min_j])
            if x < y:
                min_j = j
        a[i], a[min_j] = a[min_j], a[i]
    print(*a)


def isStable(before, after):
    flag = True
    for i in range(n):
        for j in range(i+1, n):
            for a in range(n):
                for b in range(a+1, n):
                    x = repatter.findall(before[i])
                    y = repatter.findall(before[j])
                    if x == y and before[i] == after[b] and before[j] == after[a]:
                        flag = False
    if flag is True:
        print("Stable")
    else:
        print("Not stable")


bubble_sort(lists)
select_sort(lists2)
isStable(lists3, lists2)


# Example run
# Input:
-1403621
c*]NA
# Output:
c*]NA
Stable
c*]NA
Stable
import copy

n = int(input())
check = True
a = input().split()

a = [(x[0], int(x[1])) for x in a]
b = copy.deepcopy(a)

#Bubble Sort
flag = True
i = 0
while flag:
    flag = False

    for j in range(n-1, i, -1):
        if a[j][1] < a[j-1][1]:
            tmp = a[j]
            a[j] = a[j-1]
            a[j-1] = tmp
            flag = True

    i += 1

#Selection sort
for i in range(0, n):
    minj = i
    for j in range(i, n):
        if b[j][1] < b[minj][1]:
            minj = j
   
    if i != minj:
        tmp = b[i]
        b[i] = b[minj]
        b[minj] = tmp


for i in range(len(a)):
    if i!=len(a)-1:
        print(a[i][0], end="")
        print(a[i][1], end=" ")
    else:
        print(a[i][0], end="")
        print(a[i][1], end="")
print()
print("Stable")

for i in range(len(b)):
    if i!=len(b)-1:
        print(b[i][0], end="")
        print(b[i][1], end=" ")
    else:
        print(b[i][0], end="")
        print(b[i][1], end="")

print()

for i in range(len(b)):
    if a[i][0] != b[i][0]:
        print("Not stable")
        check = False
        break
if check:
    print("Stable")


# Example run
# Input:
-1
-3439167
# Output:
-3
Stable
-3
Stable
def bubble_sort(a, n):
  for i in range(0,n):
    for j in range(n-1,i,-1):
      if a[j][1] < a[j-1][1]:
        a[j], a[j-1] = a[j-1], a[j]
  return a

def selection_sort(b, n):
  for i in range(0,n):
    minj = i
    for j in range(i, n):
      if b[j][1] < b[minj][1]:
        minj = j
    b[i], b[minj] = b[minj], b[i]
  return b

if __name__ == '__main__':
  n = int(input())
  a = list(map(str, input().split()))
  b = a[:]
  buble = bubble_sort(a,n)
  select = selection_sort(b,n)
  print(" ".join(map(str, buble)))
  print("Stable")
  print(" ".join(map(str, select)))
  if select == buble:
    print("Stable")
  else:
    print("Not stable")


# Example run
# Input:
-87
>x#!w6b>
# Output:
>x#!w6b>
Stable
>x#!w6b>
Stable
def get_value(s):
    return int(s[1])

def get_suit(s):
    return s[0]

def bubble_sort(A):
    a = list(A)
    for i in range(0, len(a)):
        
        
        for j in range(len(a)-1, i, -1):
            if get_value(a[j-1]) > get_value(a[j]):
                a[j-1], a[j] = a[j], a[j-1]
    return a

def selection_sort(A):
    a = list(A)
    for i in range(len(A)-1):
        i_min = i
        for j in range(i+1, len(A)):
            if get_value(a[j]) < get_value(a[i_min]):
                i_min = j
        a[i], a[i_min] = a[i_min], a[i]
    return a

def is_stable(A_orig, A_sort):
    dict_orig = {}
    dict_sort = {}
    
    # dict初期化
    for i in range(10):
        dict_orig[i] = list()
        dict_sort[i] = list()
    
    # dictに値設定
    for i in range(0, len(A_orig)):
        
        vo = get_value(A_orig[i])
        vs = get_value(A_sort[i])
        so = get_suit(A_orig[i])
        ss = get_suit(A_sort[i])
        
        dict_orig[vo].append(so)
        dict_sort[vs].append(ss)
    
    # stableかどうか検証
    for i in range(10):
        for j in range(len(dict_orig[i])):
            if dict_orig[i][j] is not dict_sort[i][j]:
                return False
    return True

input()
input_arr = input().split()

arr_bubble = bubble_sort(input_arr)
arr_selection = selection_sort(input_arr)

print(' '.join(arr_bubble))
print('Stable' if is_stable(input_arr, arr_bubble) else 'Not stable')
print(' '.join(arr_selection))
print('Stable' if is_stable(input_arr, arr_selection) else 'Not stable')


# Example run
# Input:
a+3s
230
# Output:
230
Stable
230
Stable
import copy

def print_list(A):
    print(*A, sep=" ")

def swap(a, b):
    return b, a

def val(str):
    return int(str[1])

def is_stable(_in, _out, n):
    for i in range(0, n):
        for j in range(i+1, n):
            for a in range(0, n):
                for b in range(a+1, n):
                    if val(_in[i]) == val(_in[j]) and _in[i] == _out[b] and _in[j] == _out[a]:
                        return False
    return True

def print_stable(_in, _out, n):
    if is_stable(_in, _out, n):
        print("Stable")
    else:
        print("Not Stable")    

def find_minj(A, i, n):
    minj = i
    for j in range(i, n):
        if val(A[j]) < val(A[minj]):
            minj = j
    return minj        

def bubble_sort(A, n):
    A0 = copy.copy(A)
    flg = 1 #逆の隣接要素が存在する
    i = 0
    while flg:
        flg = 0
        for j in range(n-1, i, -1):
            if val(A[j-1]) > val(A[j]):
                A[j-1], A[j] = swap(A[j-1], A[j])
                flg = 1
        i += 1
    print_list(A)
    print_stable(A0, A, n)

def selection_sort(A, n):
    A0 = copy.copy(A)
    for i in range(0, n):
        minj = find_minj(A, i, n)
        if val(A[i]) > val(A[minj]):
            A[i], A[minj] = swap(A[i], A[minj])
    print_list(A)
    print_stable(A0, A, n)

n = int(input())
A = list(map(int,input().split()))
B = copy.copy(A)

bubble_sort(A, n)
selection_sort(B, n)


# Example run
# Input:
-101281970
-210
# Output:
-210
Stable
-210
Stable
def bubble_sort(A, n):
	for i in range(n):
		for j in range(n-1, i, -1):
			if A[j][1] < A[j-1][1]:
				A[j], A[j-1] = A[j-1], A[j]

	print(' '.join(A))

def selection_sort(A, n):
	for i in range(n):
		minj = i
		for j in range(i, n):
			if A[j][1] < A[minj][1]:
				minj = j

		A[i], A[minj] = A[minj], A[i]

	print(' '.join(A))

if __name__ == '__main__':
	n = int(input())
	A = list(input().split())
	B = A[:]

	bubble_sort(A, n)
	print('Stable')

	selection_sort(B, n)
	print('Stable' if A == B else 'Not stable')

# Example run
# Input:
0
]MO|p9.
# Output:
]MO|p9.
Stable
]MO|p9.
Stable
def BubbleSort(a, n):
    for i in range(n):
        for j in range(n-1, i, -1):
            if int(a[j][1]) < int(a[j - 1][1]):
                a[j], a[j-1] = a[j-1], a[j]
    return a


def SelectionSort(a, n):
    for i in range(n):
        mini = i
        for j in range(i, n):
            if int(a[j][1]) < int(a[mini][1]):
                mini = j
        a[i], a[mini] = a[mini], a[i]
    return a


n = int(input())
a = input().split()


b = a
a = BubbleSort(a, n)
b = SelectionSort(b, n)


print(*a)
print("Stable")
print(*b)

if a == b:
    print("Stable")
else:
    print("Not Stable")

# Example run
# Input:
-274078593
.+[3a?
# Output:
.+[3a?
Stable
.+[3a?
Stable
n = int(input())
a = list(map(str,input().split()))

data1 = a[:]
data2 = a[:]

def bubble_sort(data):
	for i in range(len(data)):
		for j in range(len(data)-1,i,-1):
			if(data[j][1] < data[j-1][1]):
				data[j],data[j-1] = data[j-1],data[j]

	return(data)

def selection_sort(data):
	for i in range(len(data)):
		minj = i
		for j in range(i,len(data)):
			if(data[j][1] < data[minj][1]):
				minj = j

		data[i],data[minj] = data[minj],data[i]

	return(data)
data1 = bubble_sort(data1)
data2 = selection_sort(data2)
print(*data1)
print("Stable")
print(*data2)
print("Stable" if data1 == data2 else "Not stable")



# Example run
# Input:
4902
$'!{+CY
# Output:
$'!{+CY
Stable
$'!{+CY
Stable
def bubbleSort(C1,N):
    for i in range(N):
        for j in range(N-1,i,-1):
            if C1[j][1] < C1[j-1][1]:
                C1[j],C1[j-1] = C1[j-1],C1[j]
    return C1[:]
    
def selectSort(C2,N):
    for i in range(0,N):
        minj = i
        for j in range(i,N-1):
            if C2[j][1] > C2[j+1][1]:
                minj = j+1
        C2[i],C2[minj] = C2[minj],C2[i]
    return C2[:]

N = int(input())
C1 = input().split()
C2 = C1[:]

C1 = bubbleSort(C1,N)
C2 = selectSort(C2,N)

print(*C1)
print("Stable")
print(*C2)
if C1 == C2:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-2476
z7=wN3*
# Output:
z7=wN3*
Stable
z7=wN3*
Stable
import copy
def SelectionSort(a):
    for i in range(len(a)):
        mini = i
        for j in range(i,len(a)):
            if a[j][1]<a[mini][1]:
                mini = j
        if i != mini:
            tmp = a[i]
            a[i] = a[mini]
            a[mini] = tmp
def BubbleSort(a):
    for i in range(len(a)):
        for j in range(len(a)-1,i,-1):
            if a[j][1]< a[j-1][1]:
                tmp = a[j]
                a[j] = a[j-1]
                a[j-1] = tmp

n = int(input())
a = list(input().split())
item = []
for i in a:
    item.append([i[0],int(i[1])])
a1 = copy.copy(item)
BubbleSort(a1)
ans1 = []
for i in a1:
    s = i[0] + str(i[1])
    ans1.append(s)
print(*ans1)
print("Stable")
a2 = copy.copy(item)
SelectionSort(a2)
ans2 = []
for i in a2:
    s = i[0] + str(i[1])
    ans2.append(s)
print(*ans2)
if ans1 == ans2:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-1
-4
# Output:
-4
Stable
-4
Stable
#coding: UTF-8

import copy
class Algo:
  @staticmethod
  def bubbleSort(r, c, n):
    flag = 1
    while flag:
      flag = 0
      for j in range(n-1, 0, -1):
        if c[j] < c[j-1]:
          c[j], c[j-1] = c[j-1], c[j]
          r[j], r[j-1] = r[j-1], r[j]
          flag = 1
    return r

  def selectionSort(r, c, n):
    for i in range(0,n):
      minj = i
      for j in range(i,n):
        if c[j] < c[minj]:
          minj = j
      if c[i] != c[minj]:
        c[i], c[minj] = c[minj], c[i]
        r[i], r[minj] = r[minj], r[i]
    return r

  def createIntList(r, n):
    c = []
    for i in range(0,n):
      c.append(r[i][1])
    return c

  def printList(r, n):
    for i in range(0,n):
      if i == n-1:
        print(r[i])
      else:
        print(r[i], " ", sep="", end="")

n = int(input())
r = list(map(str,input().split()))
c = Algo.createIntList(r, n)
br = Algo.bubbleSort(copy.deepcopy(r), copy.deepcopy(c), n)
ir = Algo.selectionSort(copy.deepcopy(r), copy.deepcopy(c), n)
Algo.printList(br, n)
print("Stable")
Algo.printList(ir, n)
if br == ir:
  print("Stable")
else:
  print("Not stable")

# Example run
# Input:
-227062494
/DJd,
# Output:
Stable
Stable
class Card:
    def __init__(self, s):
        self.suit = s[0]
        self.value = int(s[1])

    def __lt__(self, another_card):
        return self.value < another_card.value

    def __repr__(self):
        return self.suit + str(self.value)


def bubble_sort(A):
    n = len(A)
    A = A[:]
    for i in range(n):
        for j in reversed(range(i + 1, n)):
            if A[j] < A[j - 1]:
                A[j - 1], A[j] = A[j], A[j - 1]
    return A


def selection_sort(A):
    n = len(A)
    A = A[:]
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if A[j] < A[min_idx]:
                min_idx = j
        A[min_idx], A[i] = A[i], A[min_idx]
    return A


N = int(input())
A = [Card(s) for s in input().split()]
A_sorted_by_bsort = bubble_sort(A)
A_sorted_by_ssort = selection_sort(A)
print(*A_sorted_by_bsort)
print("Stable")
print(*A_sorted_by_ssort)
print("Stable" if A_sorted_by_ssort == A_sorted_by_bsort else "Not stable")



# Example run
# Input:
-2058894
298151
# Output:
29
Stable
29
Stable
n=int(input())
c=input().split();d=c[:]
for i in range(n-1):
 for j in range(0,n-i-1):
  if c[j][1]>c[j+1][1]:c[j],c[j+1]=c[j+1],c[j]
 b=[s[1]for s in d];m=b.index(min(b[i:]),i)
 if b[i]>b[m]:d[i],d[m]=d[m],d[i]
print(*c);print("Stable")
print(*d)
print(["Stable","Not stable"][len({i[1]for i in c})<len(c)])


# Example run
# Input:
-1686
k`dM4
# Output:
k`dM4
Stable
k`dM4
Stable
n=int(input())
a=list(map(str,input().split()))

ab=a[:]
flg=True
i=0
while flg:
    flg=False
    for j in range(n-1,i,-1):
        if ab[j][1]<ab[j-1][1]:
            ab[j],ab[j-1]=ab[j-1],ab[j]
            flg=True
    i+=1
print(' '.join(map(str,ab)))
print('Stable')

ac=a[:]
for i in range(n):
    minj=i
    for j in range(i,n):
        if ac[j][1]<ac[minj][1]:
            j,minj=minj,j
    if i!=minj:
        ac[i],ac[minj]=ac[minj],ac[i]
print(' '.join(map(str,ac)))

if ab==ac:
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
-358903
XMy>
# Output:
XMy>
Stable
XMy>
Stable
def bblsrt(cards):
    cards1 = cards.copy()
    for i in range(len(cards1)):
        for j in range(len(cards1) - 1, i, -1):
            if cards1[j][1] < cards1[j - 1][1]:
                cards1[j], cards1[j - 1] = cards1[j - 1], cards1[j]
    return cards1


def slcsrt(cards):
    cards2 = cards.copy()
    for i in range(len(cards2)):
        minj = i
        for j in range(i, len(cards2)):
            if cards2[j][1] < cards2[minj][1]:
                minj = j
        cards2[i], cards2[minj] = cards2[minj], cards2[i]
    return cards2


n = int(input())
C = list(input().split())
print(' '.join(bblsrt(C)))
print('Stable')
print(' '.join(slcsrt(C)))
print('Stable' if slcsrt(C) == bblsrt(C) else 'Not stable')



# Example run
# Input:
3
B(`!o+n
# Output:
B(`!o+n
Stable
B(`!o+n
Stable
#ALDS1_2_C
n = int(input())
a_master = input()

#BubbleSort
a = [[i[0],i[1]] for i in a_master.split()]
for ni in range(n):
   for ii in range(n-1, ni, -1):
      if int(a[ii][1]) < int(a[ii-1][1]):
        a[ii], a[ii-1] = a[ii-1], a[ii]
b_ans = " ".join(["".join(i) for i in a])
print(b_ans)
print("Stable")
#SelectionSort
a = [[i[0],i[1]] for i in a_master.split()]
for ni in range(n):
  mini = ni
  for ii in range(ni,n):
    if int(a[ii][1]) < int(a[mini][1]):
      mini = ii
  a[ni], a[mini] = a[mini], a[ni]
s_ans = " ".join(["".join(i) for i in a])
print(s_ans)
if b_ans == s_ans:
  print("Stable")
else:
  print("Not stable")


# Example run
# Input:
-3636
h&KOE@z
# Output:
h&
Stable
h&
Stable
def is_stable(output_str, same_num_str):
    if len(same_num_str)>0:
        for i in range(len(same_num_str)):
            if output_str.find(same_num_str[i]) == -1:
                return "Not stable"
    return "Stable"
    
data_num = int(input())
cards = input().split(" ")
cards2 = cards[:]
cnt = 0
num_1 = 0
num_2 = 0
same_num_str = []
output_str = ""
judge_stbl = ""
for i in range(data_num):
    
    for j in range(data_num-1, i,-1):
        if int(cards[j][1:]) < int(cards[j-1][1:]):
            cards[j], cards[j-1] = cards[j-1], cards[j]
        elif int(cards[j][1:]) == int(cards[j-1][1:]):
            same_num_str.append(cards[j-1]+" "+cards[j])    
            
output_str = " ".join(cards) 
judge_stbl = is_stable(output_str, same_num_str)

print(output_str + "\n" + judge_stbl)

same_num_str = []
output_str = ""
judge_stbl = ""

for i in range(data_num):
    min_idx = i
    for j in range(i, data_num):
        if int(cards2[j][1:]) < int(cards2[min_idx][1:]):
            min_idx = j
        elif int(cards2[j][1:]) == int(cards2[min_idx][1:]) and j != min_idx:
            same_num_str.append(cards2[min_idx]+" "+cards2[j])    

    if i != min_idx:
        cards2[i], cards2[min_idx] = cards2[min_idx], cards2[i]

output_str = " ".join(cards2) 
judge_stbl = is_stable(output_str, same_num_str)

print(output_str + "\n" + judge_stbl)

# Example run
# Input:
-5075395
)C[dhxed
# Output:
)C[dhxed
Stable
)C[dhxed
Stable