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

n = int(input())
cards = [(s[0],int(s[1])) for s in input().split()]

cards_1 = copy(cards)
cards_2 = copy(cards)

need_to_sort = True
while need_to_sort:
    need_to_sort = False
    for index in range(len(cards_1) - 1, 0, -1):
        if cards_1[index][1] < cards_1[index-1][1]:
            cards_1[index], cards_1[index-1] = cards_1[index-1], cards_1[index]
            need_to_sort = True

print(" ".join([s[0]+ str(s[1]) for s in cards_1]))
print("Stable")

for idx1 in range(len(cards_2)):
    mins = idx1
    for idx2 in range(idx1, len(cards_2)):
        if cards_2[idx2][1] < cards_2[mins][1]:
            mins = idx2
    
    if mins != idx1:
        cards_2[idx1], cards_2[mins] = cards_2[mins], cards_2[idx1]

print(" ".join([s[0]+ str(s[1]) for s in cards_2]))

is_stable = True
for index in range(n):
    if cards_1[index] != cards_2[index]:
        is_stable = False
        break

print("Stable" if is_stable else "Not stable")


# Example run
# Input:
-11989124
-407
# Output:
-4
Stable
-4
Stable
import copy

class suit():
    def __init__(self, card):
        self.s = card
    def value(self):
        return int(self.s[1])

def bubblesort(seq):
    for i in range(len(seq)):
        for j in reversed(range(i + 1, len(seq))):
            if seq[j].value() < seq[j - 1].value() :
                seq[j], seq[j - 1] = seq[j - 1], seq[j]

    return seq

def selectionsort(seq):
    for i in range(len(seq)):
        mini = i
        for j in range(i, len(seq)):
            if seq[j].value() < seq[mini].value():
                mini = j

        seq[i], seq[mini] = seq[mini], seq[i]

    return seq

def is_stable(inp, out):
    for i in range(len(inp)):
        if inp[i] != out[i]:
            return "Not stable"
    return "Stable"

def main():
    cards = list()
    n = int(input())

    for card in input().split():
        cards.append(suit(card))

    seq1 = copy.copy(cards)
    seq2 = copy.copy(cards)

    seq1 = bubblesort(seq1)
    seq2 = selectionsort(seq2)

    print(seq1[0].s, end="")
    for i in range(1, len(seq1)):
        print(" " + seq1[i].s, end = "")
    print("\nStable")

    print(seq2[0].s, end="")
    for i in range(1, len(seq2)):
        print(" " + seq2[i].s, end = "")
    print("\n" + is_stable(seq1, seq2), end="")
    print()

main()


# Example run
# Input:
-1068
977
# Output:
977
Stable
977
Stable
def val(a):
    return int(a[1:])


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

def selection(lst,n):
    for i in range(n):
        minj=i
        for j in range(i,n):
            if val(lst[j])<val(lst[minj]):
                minj=j
        if i!=minj:
            lst[minj],lst[i]=lst[i],lst[minj]
    return lst

n=int(input())
lst=input().split()
lstc=lst[:]
blst=bubble(lstc,n)
lstc=lst[:]
slst=selection(lstc,n)


print(" ".join(blst))
print("Stable") #バブルソートは安定ソート
print(" ".join(slst))
if slst==blst : print("Stable")
else : print("Not stable")


# Example run
# Input:
-1800135697
@c!;Qz
# Output:
@c!;Qz
Stable
@c!;Qz
Stable
def bubble_sort(A):
    for i in range(len(A)):
        for j in range(len(A) - 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 selection_sort(A):
    n = len(A)
    for i in range(n):
        mini = i
        for j in range(i, n):
            if int(A[j][1]) < int(A[mini][1]):
                mini = j
        if mini != i:
            A[i], A[mini] = A[mini], A[i]
    return A

n = int(input())
A = input().split()
B = bubble_sort(A)
C = selection_sort(A)
print(' '.join(B))
print('Stable')
print(' '.join(C))
if B == C:
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
0
-31
# Output:
-31
Stable
-31
Stable
import copy

def bublesort(array, n):
    flag = 1
    while(flag):
        i=0
        flag=0
        for j in range(len(array)-1, i, -1):
            if array[j][1] < array[j-1][1]:
                array[j],array[j-1] = array[j-1],array[j]
                flag = 1
        i += 1

def selectionsort(array,n):
    for i in range(len(array)):
        minj = i
        for j in range(i,len(array)):
            if array[j][1] < array[minj][1]:
                minj = j
        array[minj],array[i] = array[i],array[minj]

factor = int(input())
numbers = input().split()
numbers_select = copy.deepcopy(numbers)


bublesort(numbers,factor)
selectionsort(numbers_select,factor)

print(" ".join(list(map(str, numbers))))
print("Stable")

print(" ".join(list(map(str, numbers_select))))
print("Stable") if numbers == numbers_select else print("Not stable")



# Example run
# Input:
-97071
Zz}.
# Output:
Zz}.
Stable
Zz}.
Stable
N = int(input())
A = list(input().split())
number = [int(a[1]) for a in A]
mark = [a[0] for a in A]

def bubbleSort(C_number, C_mark, N):
    for i in range(N):
        for j in reversed(range(i+1, N)):
            if C_number[j] < C_number[j-1]:
                # 番号の順番交換
                temp = C_number[j]
                C_number[j] = C_number[j-1]
                C_number[j-1] = temp
                # マークも順番交換
                temp = C_mark[j]
                C_mark[j] = C_mark[j-1]
                C_mark[j-1] = temp
    return C_number, C_mark

def selectionSort(num, mark, N):
    for i in range(N):
        min_val = min(num[i:])
        min_index = num[i:].index(min_val) + i
        if num[i] != min_val:
            # 番号の順番交換
            temp = num[i]
            num[i] = min_val
            num[min_index] = temp
            # マークも順番交換
            temp = mark[i]
            mark[i] = mark[min_index]
            mark[min_index] = temp

    return num, mark

b_num, b_mark = bubbleSort(number.copy(), mark.copy(), N)
s_num, s_mark = selectionSort(number, mark, N)

b = [b_mark[i]+str(b_num[i]) for i in range(N)]
s = [s_mark[i]+str(s_num[i]) for i in range(N)]

print(*b)
print("Stable")
print(*s)
is_same = [b[i]==s[i] for i in range(N)]
if all(is_same):
    print("Stable")
else:
    print("Not stable") 

            







# Example run
# Input:
-227062494
655252
# Output:

Stable

Stable
def Bubble_Sort(l,n):
    count = 0
    dec = 0
    
    is_reverse = True
    while is_reverse:
        is_reverse = False
        
        for i in range(n-1-dec):
            if l[i][1] > l[i+1][1]:
                l[i] , l[i+1] = l[i+1], l[i]
                is_reverse = True
                count += 1
        
        dec += 1

def selectionSort(A,n):
    count = 0
    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]
        count = count + int( i != minj)
    return count

n = int(input())
A = input().split()
B = A.copy()
Bubble_Sort(B,n)
print(' '.join(B))
print('Stable')

selectionSort(A,n)
print(' '.join(A))
if A == B:
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
-8439645
Y)lx&:Sr
# Output:
Y)lx&:Sr
Stable
Y)lx&:Sr
Stable
#安定なソート
#4つの絵柄と9つの数字から成る36枚のカード
def bubble(nums,N):
    for i in range(N-1): #先頭が確定するまで調べる（確定したら先頭の次の値が先頭になる）
        j = N-1
        while j > i:
            if nums[j-1][1] > nums[j][1]:
                nums[j-1], nums[j] = nums[j], nums[j-1]
            j = j - 1 #交換したら次の値に移動する
    return nums

def selection(nums,N):
    for i in range(N-1):
        minj = i
        for j in range(i+1,N): #配列を探索し、最小値を見つける
            if nums[minj][1] > nums[j][1]:
                minj = j
        if minj != i:
            nums[minj], nums[i] = nums[i], nums[minj]
    return nums

N = int(input())
nums = input().split()
nums2 = nums.copy()
#numsをそのまま二つのソートで使うと、後のソートでは先のソートの影響を受けるので、コピーしておく
#あるいは、numsではなくnums[:]を引数とする

result1 = bubble(nums,N)
print(' '.join(map(str,result1)))
print("Stable")
result2 = selection(nums2,N)
print(' '.join(map(str,result2)))
print("Stable" if result1 == result2 else "Not stable")



# Example run
# Input:
-74461
p>)zg
# Output:
p>)zg
Stable
p>)zg
Stable
import copy
n = int(input())
a = input().split()
a_bubble = a
a_selection = copy.deepcopy(a)
flag = 1
k = 0
while flag == 1:
    flag = 0
    for i in range(n-1,k,-1):
        if int(a_bubble[i-1][1]) > int(a_bubble[i][1]):
            a_bubble[i],a_bubble[i-1] = a_bubble[i-1],a_bubble[i]
            flag = 1
    k += 1
print(" ".join(a_bubble))
print("Stable")
for i in range(n):
    minj = i
    for j in range(i,n):
        if int(a_selection[j][1]) < int(a_selection[minj][1]):
            minj = j
    a_selection[i],a_selection[minj] = a_selection[minj],a_selection[i]
print(" ".join(a_selection))
if a_selection == a_bubble:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-887384
~_p|DP\
# Output:
~_p|DP\
Stable
~_p|DP\
Stable
#! /usr/local/bin/python3
# coding: utf-8

def swap(c, i, j):
    t = c[i]
    c[i] = c[j]
    c[j] = t

def bubble_sort(cs, f):
    c = cs[:]
    for i in range(len(c) - 1):
        for j in range(len(c) - 1, i, -1):
            if f(c[j - 1]) > f(c[j]):
                swap(c, j - 1, j)
            # print(i, j, c)
    return c

def selection_sort(cs, f):
    c = cs[:]
    for i in range(len(c)):
        minj = i
        for j in range(i, len(c)):
            if f(c[j]) < f(c[minj]):
                minj = j
        swap(c, i, minj)
        # print(c)
    return c

def to_group(c):
    b = {}
    for i in c:
        if not(i[1] in b):
            b[i[1]] = [i]
        else:
            b[i[1]] = b[i[1]] + [i]
    return b

def is_stable(c, s): 
    bc = to_group(c)
    bs = to_group(s(c, lambda x: x[1]))
    # print(bc)
    # print(bs)
    for k in bc:
        if bc[k] != bs[k]:
            return "Not stable"
    return "Stable"

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

print(" ".join(bubble_sort(c, lambda x: x[1])))
print(is_stable(c, bubble_sort))

print(" ".join(selection_sort(c, lambda x: x[1])))
print(is_stable(c, selection_sort))




# Example run
# Input:
21390345
'PbIsr[
# Output:
'PbIsr[
Stable
'PbIsr[
Stable
class Trump(str):
    def __init__(self, card):
        super().__init__()
        self.num = int(card[1])

def trump_bubble_sort(A, N):
    flg = True
    while flg:
        flg = False
        for i in range(1, N):
            if A[i - 1].num > A[i].num:
                A[i], A[i - 1] = A[i - 1], A[i]
                flg = True
    return A


def trump_selection_sort(A, N):
    for i in range(0, N-1):
        min_idx = i
        for j in range(i+1, N):
            if A[min_idx].num > A[j].num:
                min_idx = j
        A[i], A[min_idx] = A[min_idx], A[i]
        
    return A

N = int(input().rstrip())
A = [Trump(a) for a in input().rstrip().split()]
A_2 = A.copy()

bubble_result = trump_bubble_sort(A, N)
selection_result = trump_selection_sort(A_2, N)

stable = True
for i in range(0, N):
    if bubble_result[i] != selection_result[i]:
        stable = False
        break
print(" ".join(bubble_result))
print("Stable")
print(" ".join(selection_result))
print("Stable" if stable else "Not stable")
    



# Example run
# Input:
0
13
# Output:
13
Stable
13
Stable
def bubblesort(n, a):
    r = a[:]
    for i in range(n):
        for j in range(n-1, i, -1):
            if int(r[j][1]) < int(r[j-1][1]):
                r[j], r[j-1] = r[j-1], r[j]

    print(*r)
    print("Stable")


def selectionsort(n, a):
    r = a[:]
    ret = "Stable"
    for i in range(n):
        tmp = i
        for j in range(i, n):
            if int(r[j][1]) < int(r[tmp][1]):
                tmp = j
        r[i], r[tmp] = r[tmp], r[i]
        if r[i][0] != r[tmp][0] and int(r[i][1]) == int(r[tmp][1]):
            ret = "Not Stable"

    print(*r)
    print(ret)


def main():
    n = int(input())
    a = list(input().split())

    bubblesort(n, a)
    selectionsort(n, a)


if __name__ == '__main__':
    main()



# Example run
# Input:
-213
\a&K8&(#
# Output:
\a&K8&(#
Stable
\a&K8&(#
Stable
def str_selection_sort(a,n):
    m=0
    for i in range(0,n):
        minj=i
        for j in range(i,n):
            if(int(a[minj][1:]) > int(a[j][1:])):
                minj=j
        if(minj!=i):
            m+=1
            a[minj],a[i] = a[i],a[minj]
        
    print(" ".join(a))
    return a

def str_bubble_sort(a,n):
    for j in range(0,n):
        for i in range(n-1,j,-1):
            if(int(a[i-1][1:]) > int(a[i][1:])):
                a[i],a[i-1]=a[i-1],a[i]

    print(" ".join(a))
    return a

def is_stable(a,b,n):
    for i in range(1,n):
        if(b[i-1][1:]!=b[i][1:]):
            continue
        flag=False
        for j in a:
            if(j[:1]==b[i-1][:1] and (not flag)):
                flag=True
                continue
            if(j[:1]==b[i][:1]):
                if(not flag):
                    return False
                else:
                    return True
        
        if(flag):
            return False

a=[]
n=int(input())
s=input()
a=s.split()
b=str_bubble_sort(list(a),n)
if(is_stable(a,b,n)):
    print("Stable")
else:
    print("Not stable")
b=str_selection_sort(list(a),n)
if(is_stable(a,b,n)):
    print("Stable")
else:
    print("Not stable")

# Example run
# Input:
-1510426
a;M<
# Output:
a;M<
Not stable
a;M<
Not stable
N = int(input())
array = list(input().split())
array2 = array[:]
array3 = array[:]

def bubble_sort(array, N):
	flag = 1
	i = 0
	while flag:
		flag = 0 
		j = N-1
		while j > i:
			if array[j][1] < array[j-1][1]:
				array[j], array[j-1] = array[j-1], array[j]
			j -= 1
			flag = 1
		i += 1


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

def is_stable(Input, output, 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 Input[i][1] == Input[j][1] and Input[i][1] == output[b][1] and Input[j][1] == output[a][1]:
						return False
	return True 

bubble_sort(array, N)
print(' '.join(array))
print('Stable')
selection_sort(array2,N)
print(' '.join(array2))
if is_stable(array3, array2, N):
	print('Stable')
else:
	print('Not stable')







# Example run
# Input:
0
!rJx
# Output:
!rJx
Stable
!rJx
Stable
import copy
def isStable(n,n_old):
  for i in range(len(n)-1):
    for j in range(i+1,len(n),+1):
      for a in range(len(n)-1):
        for b in range(a+1,len(n),+1):
          if n[i][1]==n[j][1]:
            if n[i]==n_old[b] and n[j]==n_old[a]:
              return 'Not stable'
  return 'Stable'
  
m=int(input())
n=list(map(str,input().split()))
n_old=copy.deepcopy(n)

for i in range(m-1):
  for j in range(m-1,i,-1):
    if int(n[j][1])<int(n[j-1][1]):
      n[j],n[j-1]=n[j-1],n[j]

print(' '.join(map(str, n)))
print(isStable(n,n_old))

n=copy.deepcopy(n_old)

for i in range(len(n)-1):
  minj=i
  cnt=0
  for j in range(i+1,len(n)):
    if n[j][1]<n[minj][1]:
      minj=j
      cnt=1
  if cnt==1:
    n[i],n[minj]=n[minj],n[i]

print(' '.join(map(str, n)))
print(isStable(n,n_old))


# Example run
# Input:
-192707
z,sS*<;]?
# Output:
z,sS*<;]?
Stable
z,sS*<;]?
Stable
def bubble_sort(C, N):
    flag = 1
    while flag:
        flag = 0
        for j in range(1, N):
            if list(C[j])[1] < list(C[j-1])[1]:
                C[j], C[j-1] = C[j-1], C[j]
                flag = 1
        N -= 1
    return C

def selction_sort(C, N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if list(C[j])[1] < list(C[minj])[1]:
                minj = j
        C[i], C[minj] = C[minj], C[i]
    return C

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

st = [''] * 9
bubble_st = [''] * 9
selection_st = [''] * 9
bubble_c = bubble_sort(C[:], N)
selection_c = selction_sort(C[:], N)
for i in range(N):
    st[int(list(C[i])[1])-1] += list(C[i])[0]
    bubble_st[int(list(bubble_c[i])[1])-1] += list(bubble_c[i])[0]
    selection_st[int(list(selection_c[i])[1])-1] += list(selection_c[i])[0]
print(' '.join(bubble_c))
if st == bubble_st:
    print('Stable')
else:
    print('Not stable')
print(' '.join(selection_c))
if st == selection_st:
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
-89546968
/<U
# Output:
/<U
Stable
/<U
Stable
def bubble_sort(A, N):
    A = list(A)
    for i in range(1, N):
        for j in range(0, N-i):
            if A[j][1] > A[j+1][1]:
                A[j], A[j+1] = A[j+1], A[j]
    tmp = []
    for x, y in A:
        tmp.append(x+str(y))
    return tmp


def selection_sort(A, N):
    A = list(A)
    for i in range(0, N-1):
        pivot = i
        for j in range(i+1, N):
            if A[pivot][1] > A[j][1]:
                pivot = j
        if pivot != i:
            A[pivot], A[i] = A[i], A[pivot]
    tmp = []
    for x, y in A:
        tmp.append(x+str(y))
    return tmp


N = int(input())
X = list(map(str, input().split()))
A = []
for x in X:
    A.append((x[0], int(x[1])))
A = tuple(A)
a = bubble_sort(A, N)
print(*a)
print('Stable')
b = selection_sort(A, N)
print(*b)
if a == b:
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
-64990941
-12142
# Output:
-1
Stable
-1
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]

print(*__copy)

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

print(is_stable)

# Example run
# Input:
0
fZv`:{qO
# Output:
fZv`:{qO
Stable
fZv`:{qO
Stable
n=int(input())
b=input().split()
s=b[:]
for i in range(n):
    for j in range(n-1,i,-1):
        if b[j][1]<b[j-1][1]:b[j],b[j-1]=b[j-1],b[j]
    m=i
    for j in range(i,n):
        if s[m][1]>s[j][1]:m=j
    s[m],s[i]=s[i],s[m]
print(*b)
print('Stable')
print(*s)
print(['Not stable','Stable'][b==s])

# Example run
# Input:
-2040
RN-`2,MZ0
# Output:
RN-`2,MZ0
Stable
RN-`2,MZ0
Stable
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]:
                # リストの要素の文字列は2次元配列として記憶される
                A[j],A[j-1] = A[j-1],A[j]
    return A

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
        A[i],A[mini] = A[mini],A[i]
    return A


N = int(input())
# example for input to array : H4 C9 S4 D2 C3 (from cards)
array = [i for i in input().split()]
array_cp = list(array)

result_bs = BubbleSort(array)
print(*result_bs)
print('Stable') # Bubble sort is stable

result_ss = SelectionSort(array_cp)
print(*result_ss)
if result_ss == result_bs:
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
1419428
W9E
# Output:
W9E
Stable
W9E
Stable
def selectionSort(A, N):
	for i in range(N):
		minj = i
		for j in range(i, N):
			if A[j][1:] < A[minj][1:]:
				minj = j
		if i != minj:
			tmp = A[i]
			A[i] = A[minj]
			A[minj] = tmp

	return A

def bubbleSort(A, N):
	for i in range(N):
		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

	return A

if __name__ == '__main__':
	n = int(input())
	R = list(map(str, input().split()))
	C = R[:]
	SR = selectionSort(R, n)
	BR = bubbleSort(C, n)

	fStable = SR == BR

	print(" ".join(map(str, BR)))
	print("Stable")
	print(" ".join(map(str, SR)))
	if (fStable == True):
		print("Stable")
	else:
		print("Not stable")


# Example run
# Input:
-48655
%fAakyV$
# Output:
%fAakyV$
Stable
%fAakyV$
Stable
def print_list(l):
    for i, n in enumerate(l):
        if i == N - 1:
            print(l[i])
        else:
            print(l[i], end=' ')

N = int(input())
A = input().split()
B = list(A)
for i in range(N):
    for j in range(N-1, i, -1):
        if int(A[j][1]) < int(A[j-1][1]):
            w = A[j]; A[j] = A[j-1]; A[j-1] = w
print_list(A)
print('Stable')

for i in range(N):
    min_j = i
    for j in range(i, N):
        if int(B[j][1]) < int(B[min_j][1]):
            min_j = j
    w = B[i]; B[i] = B[min_j]; B[min_j] = w
print_list(B)
if A == B:
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
0
g>!d1,AY
# Output:
g>!d1,AY Stable
g>!d1,AY Stable
def BubbleSort(C, N):
    for i in range(N):
        for j in range(N - 1, i, -1):
            if int(C[j][1]) < int(C[j - 1][1]):
                C[j], C[j - 1] = C[j - 1], C[j]
    return C

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

def isStable(B, S, N):
    for i in range(N):
        if B[i] != S[i]:
            return False
    return True

N = int(input())
B = input().split()
S = B[:]
B = BubbleSort(B, N)
S = SelectionSort(S, N)
mes = "Stable" if isStable(B, S, N) else "Not stable"
print(" ".join(B))
print("Stable")
print(" ".join(S))
print(mes)

# Example run
# Input:
-1325982
8YU=Cz
# Output:
8YU=Cz
Stable
8YU=Cz
Stable
STABLE = 'Stable'
UNSTABLE = 'Not stable'


def main():
  card_num = int(input())
  cards = input().split()

  bubble_sorted = bubble_sort(cards, card_num)
  select_sorted = select_sort(cards, card_num)

  stability = True
  for i, c in enumerate(select_sorted):
    if c != bubble_sorted[i]:
      stability = False
      break
  stability = STABLE if stability else UNSTABLE

  print(' '.join(bubble_sorted))
  print(STABLE)

  print(' '.join(select_sorted))
  print(stability)

  return 0


def order(card_sym):
  order = int(card_sym[1])
  return order


def select_sort(elements, element_num):
  elements = list(elements)

  for i in range(0, element_num - 1):
    min_val = order(elements[i + 1])
    min_index = i + 1
    for j in range(i + 1, element_num):
      if order(elements[j]) < min_val:
        min_val = order(elements[j])
        min_index = j
    if order(elements[i]) > order(elements[min_index]):
      elements[i], elements[min_index] = elements[min_index], elements[i]

  return elements


def bubble_sort(elements, element_num):
  elements = list(elements)

  for i in range(1, element_num):
    for j in reversed(range(i, element_num)):
      if order(elements[j - 1]) > order(elements[j]):
        elements[j - 1], elements[j] = elements[j], elements[j - 1]

  return elements


if __name__ == '__main__':
  main()

# Example run
# Input:
-1
;s?8>
# Output:
;s?8>
Stable
;s?8>
Stable
n = int(input())
trump = input().split()

def bubbleSort(trump, n):
    c = trump[::]
    for i in range(n):
        for j in range(n-1, i, -1):
            if int(c[j][1]) < int(c[j-1][1]):
                c[j], c[j-1] = c[j-1], c[j]
    print(' '.join(c))
    print('Stable')
    return c

def selectionSort(trump, n):
    c = trump[::]
    for i in range(n):
        minj = i
        for j in range(i+1, n):
            if int(c[j][1]) < int(c[minj][1]):
                minj = j
        c[i], c[minj] = c[minj], c[i]
    print(' '.join(c))
    return c

if bubbleSort(trump, n) == selectionSort(trump, n):
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
-52564348
(1bulQ!Z
# Output:
(1bulQ!Z
Stable
(1bulQ!Z
Stable