Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
N = int(input())
Numbers = list(input().split())
A = Numbers[::]
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] 
print(' '.join(A))
print('Stable')
B = Numbers[::]
for i in range(N):
    minj = i
    for j in range(i, N):
        if int(B[j][1]) < int(B[minj][1]):
            minj = j
    B[i], B[minj] = B[minj], B[i]
print(' '.join(B))
if A == B:
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
-7
'VhS
# Output:
'VhS
Stable
'VhS
Stable
N = int(input())
A = list(map(str, input().split()))
unsorted_A = A[:]
bub_A = A[:]
sel_A = A[:]

def BubbleSort(bub_A):
    for i in range(N):
        for j in range(1, N):
            if bub_A[j][1] < bub_A[j-1][1]:
                swp = bub_A[j]
                bub_A[j], bub_A[j-1] = bub_A[j-1], swp

    print(' '.join(bub_A))
    print('Stable')

def SelectionSort(sel_A):
    for i in range(N):
        min = i
        for j in range(i, N):
            if sel_A[j][1] < sel_A[min][1]:
                min = j
        if sel_A[i][1] > sel_A[min][1]:
            sel_A[i], sel_A[min] = sel_A[min], sel_A[i]

    print(' '.join(sel_A))
    if bub_A == sel_A:
        print('Stable')
    else:
        print('Not stable')

BubbleSort(bub_A)
SelectionSort(sel_A)


# Example run
# Input:
-525059
t],
# Output:
t],
Stable
t],
Stable
input()
C = [[x[0], x[1]] for x in list(input().split())]
D = C.copy()
N = len(C)

# バブルソート
for i in range(0, N-1, 1):
    for j in range(N-1, i, -1):
        if C[j][1] < C[j-1][1]:
            tmp = C[j]
            C[j] = C[j-1]
            C[j-1] = tmp

# 選択ソート
for i in range(0, N-1, 1):
    minj = i
    for j in range(i, N, 1):
        if D[j][1] < D[minj][1]:
            minj = j
    tmp = D[i]
    D[i] = D[minj]
    D[minj] = tmp

# バブルソートの結果出力
length = len(C)
for i in range(length):
    if i == length - 1:
        print("".join(C[i]), end="")
    else:
        print("".join(C[i]), end=" ")

print("")
print("Stable")

# 選択ソートの結果出力
for i in range(length):
    if i == length - 1:
        print("".join(D[i]), end="")
    else:
        print("".join(D[i]), end=" ")

print("")
if C == D:
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
avf*R
/<s%MVU
# Output:
/<
Stable
/<
Stable
def compare_cards(a, b):
    return a[1] < b[1]
 
def bubble(C):
    for i in range(len(C)):
        for j in range(len(C) - 1, i, -1):
            if compare_cards(C[j], C[j - 1]):
                C[j], C[j - 1] = C[j -1], C[j]
                
def selection(C):
    for i in range(len(C)):
        mini = i
        for j in range(i, len(C)):
            if compare_cards(C[j], C[mini]):
                mini = j
        C[i], C[mini] = C[mini], C[i]
        
def check_stable(originC, sortedC):
    for i in range(len(originC) - 1):
        if not compare_cards(sortedC[i], sortedC[i + 1]):
            if originC.index(sortedC[i]) > originC.index(sortedC[i + 1]):
                return 'Not stable'
    return 'Stable'
 
         
N = int(input())
C = input().split()
 
print(*C)

# Example run
# Input:
-69919
SaT:n(BF
# Output:
SaT:n(BF
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:
-106
=(B?CZ
# Output:
=(B?CZ
Stable
=(B?CZ
Stable
#ALDS1_2-C Sort 1 - Stable Sort
def selectionSort(A,N):
    c=0
    for i in range(N):
        minj = i
        j=i
        while j<N:
            if(int(A[j][1])<int(A[minj][1])):
                minj = j
            j+=1
        if(i!=minj):
            A[i],A[minj]=A[minj],A[i]
            c+=1
    return c

def bubbleSort(A,N):
    c=0
    flag=1
    while flag:
        flag=0
        j=N-1
        while j>0:
            if(int(A[j][1])<int(A[j-1][1])):
                c+=1
                A[j],A[j-1]=A[j-1],A[j]
                flag=1
            j-=1
    return c

N=int(input())
A=input().split()
checkA=[""]*9
for i in range(N):
    checkA[int(A[i][1])-1]+=A[i][0]

B=[]+A
C=[]+A

bubbleSort(B,N)
checkB=[""]*9
for i in range(N):
    checkB[int(B[i][1])-1]+=B[i][0]
S=""
for i in range(N-1):
    S+=B[i]+" "
S+=str(B[-1])
print(S)
if(checkB==checkA):
    print("Stable")
else:
    print("Not stable")
    
selectionSort(C,N)
checkC=[""]*9
for i in range(N):
    checkC[int(C[i][1])-1]+=C[i][0]
S=""
for i in range(N-1):
    S+=C[i]+" "
S+=str(C[-1])
print(S)
if(checkC==checkA):
    print("Stable")
else:
    print("Not stable")

# Example run
# Input:
-525059
t],
# Output:
t],
Stable
t],
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):
    m=0
    flag=True
    while(flag):
        flag=False
        for i in range(n-1,0,-1):
            if(a[i-1][1:] > a[i][1:]):
                tmp=a[i-1]
                a[i-1]=a[i]
                m+=1
                a[i]=tmp
                flag=True
                
    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:
-477934499
^E\I{8)(B
# Output:
^E\I{8)(B
Not stable
^E\I{8)(B
Not stable
# -*- coding: utf-8 -*-


def bubble_sort(c):
    c = list(c)
    for i in range(len(c)):
        for j in range(len(c)-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 selection_sort(c):
    c = list(c)
    for i in range(len(c)):
        minj = i
        for j in range(i+1, len(c)):
            if int(c[j][1]) < int(c[minj][1]):
                minj = j
        c[i], c[minj] = c[minj], c[i]
    return c

input_num = int(input())
input_list = input().split()
bubble_list = bubble_sort(input_list)
selection_list = selection_sort(input_list)
for c in bubble_list:
    print(c, end='')
    if c != bubble_list[len(bubble_list)-1]:
        print(' ', end='')
print("\nStable")
stable_flg = True
for i in range(len(input_list)):
    if bubble_list[i] != selection_list[i]:
        stable_flg = False
    print(selection_list[i], end='')
    if i < len(input_list)-1:
        print(" ", end='')
if stable_flg:
    print("\nStable")
else:
    print("\nNot stable")

# Example run
# Input:
390
]tY
# Output:
]tY
Stable
]tY
Stable
def bubblesort(c, n):
	for i in range(n):
		for j in range(n-1, 0, -1):
			if (c[j][1] < c[j-1][1]):
				c[j], c[j-1] = c[j-1], c[j]

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

def output(c):
	for i in range(len(c)):
		if i != 0: print(" ", end="")
		print("{}{}".format(c[i][0], c[i][1]), end="")
	print()

def isstable(inp, outp, 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 (inp[i][1] == inp[j][1] and
						inp[i][0] == outp[b][0] and
						inp[j][0] == outp[a][0]):
						print("Not stable")
						return
	print("Stable")


def main():
	n = int(input())
	data = input().split()
	cards = []

	for c in data:
		cards.append((c[0],int(c[1])))
	cards1 = cards[:]
	cards2 = cards[:]

	bubblesort(cards1, n)
	output(cards1)
	isstable(cards, cards1, n)

	selectionsort(cards2, n)
	output(cards2)
	isstable(cards, cards2, n)

if __name__ == "__main__":
	main()

# Example run
# Input:
-1131247330
-9
# Output:
-9
Stable
-9
Stable
N = int(input())
A = input().split()
B = A[:]

def BubbleSort(A, N):
    for i in range(N):      # iは未ソートの部分列の先頭のインデックス
        for j in range(N-1, i, -1):     # 隣接要素を比較するのは未ソート部分列の末尾から先頭まで
            if A[j-1][1] > A[j][1]:           # 隣接要素を比較
                A[j-1], A[j] = A[j], A[j-1]     # 大小関係が逆の場合、交換
    return A


def SelectionSort(B, N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if B[minj] [1]> B[j][1]:
                minj = j
        B[i], B[minj] = B[minj], B[i]       
    return B

ans_b = BubbleSort(A, N)
print(*ans_b)
print("Stable")
ans_s = SelectionSort(B, N)
print(*ans_s)
if ans_b == ans_s:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-33
R&e8
# Output:
R&e8
Stable
R&e8
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:
-145
lD/
# Output:
lD/
Stable
lD/
Stable
def BubbleSort(C, N):

    for i in range(N):
        for j in range(N-1, i, -1):
            if C[j][1] < 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 C[j][1] < C[minj][1]:
                minj = j
        C[i], C[minj] = C[minj], C[i]
    return C

def isStable(C1, C2, N):
    if C1 != C2:
        return "Not stable"
    return "Stable"

Num = int(input())
Cards = [x for x in input().split()]
card1 = BubbleSort(list(Cards), Num)
card2 = SelectionSort(list(Cards), Num)

print(" ".join(card1))
print(isStable(card1, card1, Num))
print(" ".join(card2))
print(isStable(card1, card2, Num))



# Example run
# Input:
-16
)jy
# Output:
)jy
Stable
)jy
Stable
n = int(input())
a = list(input().split())

A = []
A1 = []
A2 = []
for i in a:
    A.append(list(i))
    A1.append(list(i))
    A2.append(list(i))

# check stable or not
def is_stable(A3):
    for i in range( 1, n ):
        if int(A3[i-1][1]) == int(A3[i][1]):
            sm = i-1
            bg = i
            for j in range( n ):
                if ( A[j][0] == A3[sm][0]) & ( A[j][1] == A3[sm][1]):
                    t1 = j
                if ( A[j][0] == A3[bg][0]) & ( A[j][1] == A3[bg][1]):
                    t2 = j
            print(t1)
            print(t2)
            if t1 > t2:
                return "Not stable"
    return "Stable"

# bubble
for i in range( n ):
    for j in range( n-1, i, -1 ):
        if int(A1[j][1]) < int(A1[j-1][1]):
            t = A1[j-1]
            A1[j-1] = A1[j]
            A1[j] = t

s = is_stable(A1)
print(*A1)
print(s)


# selection
for i in range( n ):
    minj = i
    for j in range( i+1, n ):
        if int(A2[j][1]) < int(A2[minj][1]):
            minj = j
    if minj != i:
        t = A2[i]
        A2[i] = A2[minj]
        A2[minj] = t

s = is_stable(A2)
print(*A2)
print(s)

# Example run
# Input:
-100686
)M5lG+
# Output:
[')', 'M', '5', 'l', 'G', '+']
Stable
[')', 'M', '5', 'l', 'G', '+']
Stable
n=int(input())
r=input().split()

def BubbleSort(c):
    for i in range(len(c)-1):
        for j in range(len(c)-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):
    for i in range(len(c)-1):
        m=i
        for j in range(i, len(c)-1):
            if int(c[j][-1]) < int(c[m][-1]):
                m=j
        c[j], c[m]=c[m],c[j]
    return c
l=r
a=BubbleSort(l)
#for i in range(10):
print(*a)
print('Stable')
b=SelectionSort(l)
#for i in range(0):
print(*b)
if a==b:
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
7381
.SD+<
# Output:
.SD+<
Stable
.SD+<
Stable
def BubbleSort(C, N):
    for i in range(0,N):
        for j in range(N-1,i,-1):
            if C[j][1:] < C[j-1][1:]:
                #  C[j] と C[j-1] を交換
                tmp = C[j]
                C[j] = C[j-1]
                C[j-1] = tmp
    ret = " ".join(C)
    print(ret)
    print("stable")
    return ret

def SelectionSort(C, N):
    for i in range(0,N):
        minj = i
        for j in range(i,N):
            if C[j][1:] < C[minj][1:]:
                minj = j
        # C[i] と C[minj] を交換
        tmp = C[i]
        C[i] = C[minj]
        C[minj] = tmp
    ret = " ".join(C)
    print(ret)
    return ret

N = int(input())
C = input().split(" ")
ret_B = BubbleSort(C,N)
ret_S = SelectionSort(C,N)
if ret_B == ret_S:
    print("stable")
else:
    print("Not stable")



# Example run
# Input:
-755
Ze8P!
# Output:
Ze8P!
stable
Ze8P!
stable
def bubble_sort(arr, n):
    for i in range(n):
        for j in reversed(range(i + 1, n)):
            if arr[j - 1].value > arr[j].value:
                arr[j - 1], arr[j] = arr[j], arr[j - 1]
    return arr


def selection_sort(arr, n):
    for i in range(n):
        min_idx = i
        for j in range(i, n):
            if arr[j].value < arr[min_idx].value:
                min_idx = j
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr


class Card:
    def __init__(self, card_str):
        self.value = int(card_str[1])
        self.mark = card_str[0]
        self.str = card_str


def is_stable(stable_arr, target_arr):
    for s, t in zip(stable_arr, target_arr):
        if s.str != t.str:
            return False
    return True


def main():
    n = int(input())
    # cards = ["H4", "C9", "S4", "D2", "C3"]
    cards = input().split()
    arr = [Card(card_str) for card_str in cards]
    # n = 5
    b_arr = bubble_sort(arr, n)
    print(" ".join([b.str for b in b_arr]))
    print("Stable")
    arr = [Card(card_str) for card_str in cards]
    s_arr = selection_sort(arr, n)
    print(" ".join([s.str for s in s_arr]))
    if is_stable(b_arr, s_arr):
        print("Stable")
    else:
        print("Not stable")


if __name__ == "__main__":
    main()



# Example run
# Input:
-23909
-68
# Output:
-68
Stable
-68
Stable
import copy
def convert(list):
    res=" ".join(map(str, list))
    return res

n=int(input())
a=list(map(str,input().split()))

b=a[:]
s=copy.deepcopy(a)

for i in range(n-1):
    for j in reversed(range(i+1,n)):
        if b[j][1]<b[j-1][1]:
            bj=b[j]
            b[j]=b[j-1]
            b[j-1]=bj
bub=convert(b)
print(bub)
print("Stable")

for k in range(n):
    minl=k
    for l in range(k,n):
        if s[minl][1]>s[l][1]:
            minl=l

    if minl!=k:
        sk=s[k]
        s[k]=s[minl]
        s[minl]=sk

se=convert(s)
print(se)
if s==b:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-15827722
;RQ5GI*>r
# Output:
;RQ5GI*>r
Stable
;RQ5GI*>r
Stable
class card(object):
    def __init__(self, str):
        self.symbol = str[0]
        self.num = int(str[1:])
    
    def __lt__(self,obj):
        if(self.num < obj.num):
            return True
        else:
            return False
    def __gt__(self,obj):
        if(self.num > obj.num):
            return True
        else:
            return False

    def display_card(self):
        print("{0}{1}".format(self.symbol,self.num),end="")

n = int(input())
s = input()
org = list(map(card,s.split()))  

bub = list(org)
sel = list(org)

#####################################
"""
Bubble sort(bub[])
""" '''
for i in range(0,len(bub)):
    for j in range(len(bub)-1,i-1,-1):
        if(bub[j] < bub[j-1]):
            tmp = bub[j]
            bub[j] = bub[j-1]
            bub[j-1] = tmp
'''
flag = True
while(flag==True):
    flag = False
    for i in range(1,len(bub)):
        if(bub[i]<bub[i-1]):
            bub[i],bub[i-1] = bub[i-1],bub[i]
            flag = True


"""
selection sort(sel[])
"""

for i in range(0,len(sel)-1):
    minj = i
    for j in range(i,len(sel)):
        if(sel[j] < sel[minj]):
            minj = j
    sel[i],sel[minj] = sel[minj],sel[i]
       
"""
comp org(org[])
"""


# buble

for i in range(0,len(bub)):
    bub[i].display_card()
    if (i==len(bub)-1):
        print("\n",end="")
    else :
        print(" ",end="")
print("Stable")
# selec
                
for i in range(0,len(sel)):
    sel[i].display_card()
    if (i==len(sel)-1):
        print("\n",end="")
    else :
        print(" ",end="")
if(bub == sel): 
    print("Stable")
else:
    print("Not stable")

# Example run
# Input:
4
-7467726
# Output:
-7467726
Stable
-7467726
Stable
n = int(input())
c = input().split()
d = c[:]

# bubblesort
for i in range(n):
    for j in range(n - 1, i, -1):
        if d[j][1] < d[j - 1][1]:
            d[j], d[j - 1] = d[j - 1], d[j]
print(*d)
print("Stable")

# selectionsort
for i in range(n):
    minj = i
    for j in range(i, n):
        if c[j][1] < c[minj][1]:
            minj = j
    c[i], c[minj] = c[minj], c[i]

print(*c)
print("Stable" if c == d else "Not stable")

# Example run
# Input:
-3733491
`Hf
# Output:
`Hf
Stable
`Hf
Stable
# -*- coding: utf-8 -*-

from copy import deepcopy

"""
stable sort
"""
N = int(input())
cN = list(map(str, input().split()))
cN2 = deepcopy(cN)

# bubble sort
for i in range(N):
    for j in range(N-1, i, -1):
        if int(cN[j][1]) < int(cN[j-1][1]):
            tmp = cN[j]
            cN[j] = cN[j-1]
            cN[j-1] = tmp
print(' '.join(cN))
print('Stable')

# selection sort
for i in range(N):
    minj = i
    for j in range(i, N):
        if int(cN2[j][1]) < int(cN2[minj][1]):
            minj = j
    tmp = cN2[i]
    cN2[i] = cN2[minj]
    cN2[minj] = tmp
print(' '.join(cN2))

for i in range(N):
    if cN[i] != cN2[i]:
        print('Not stable')
        exit()
print('Stable')



# Example run
# Input:
-243756212
tx=.[pSe
# Output:
tx=.[pSe
Stable
tx=.[pSe
Stable
def bubble_sort(a, n):
  for i in range(0,n):
    for j in range(n-1,i-1,-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

def isStable(buble, select, n):
  for i in range(0,n):
    if buble[i] != select[i]:
      return False
  return True

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 isStable(buble,select,n):
    print("Stable")
  else:
    print("Not stable")


# Example run
# Input:
-235202
nzXv9U
# Output:
nzXv9U
Stable
nzXv9U
Stable
#coding:utf-8
#1_2_C

def BubbleSort(cards, n):
    for i in range(n):
        for j in range(n-1, i, -1):
            if cards[j][1] < cards[j-1][1]:
                cards[j], cards[j-1] = cards[j-1], cards[j]
    return cards

def SelectionSort(cards, n):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if cards[minj][1] > cards[j][1]:
                minj = j
        cards[i], cards[minj] = cards[minj], cards[i]
    return cards

n = int(input())
cards = input().split()
print(' '.join(BubbleSort(cards, n)))
print('Stable')
print(' '.join(SelectionSort(cards, n)))
if BubbleSort(cards, n) == SelectionSort(cards, n):
    print('Stable')
else:
    print('Not stable')

# Example run
# Input:
-24
$h8zRH#
# Output:
$h8zRH#
Stable
$h8zRH#
Stable
length = int(input())
targ = [n for n in input().split(' ')]
selecttarg = targ[:]
#bubbleflag = 0
for l in range(length):
    for init in range(l):
        if targ[l - init][1] < targ[l - init - 1][1]:
            disp = targ[l-init]
            targ[l-init] = targ[l-init-1]
            targ[l-init-1] = disp
print(' '.join([str(n) for n in targ]))

print("Stable")

selectflag = 0
for l in range(length):
    value = l
    samevalue = l
    for init in range(l+1,length):
        if selecttarg[value][1] > selecttarg[init][1]:
            value = init
        elif selectflag != 1 and selecttarg[l][1] == selecttarg[init][1]:
            samevalue = init
    if samevalue != l and value != l and value > samevalue:
        selectflag = 1
    disp = selecttarg[l]
    selecttarg[l] = selecttarg[value]
    selecttarg[value] = disp
print(' '.join([str(n) for n in selecttarg]))
if selectflag == 0:
    print("Stable")
else:
    print("Not stable")

# Example run
# Input:
-2058894
1,AYZUHn6
# Output:
1,AYZUHn6
Stable
1,AYZUHn6
Stable
import copy

def BubbleSort(C, N):
    stable = True

    for i in range(N):
        for j in range(i + 1, N)[::-1]:
            if C[j][2] < C[j - 1][2]:
                C[j], C[j - 1] = C[j - 1], C[j]

    
    AnswerPrint(C, IsStable(C))


def SelectionSort(C, N):
    stable = True

    for i in range(N):
        minj = i
        for j in range(i, N):
            if C[j][2] < C[minj][2]:
                minj = j

        C[i], C[minj] = C[minj], C[i]

    AnswerPrint(C, IsStable(C))


def IsStable(C):
    for index, c in enumerate(C):
        for i in range(index, len(C)):
            if (c[2] == C[i][2]) and (c[0] > C[i][0]):
                return False

    return True
                

def AnswerPrint(C, stable):
    out = ["{}{}".format(c[1], c[2]) for c in C]
    print(" ".join(out))

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



N = int(input())
inp = input().split()
C = [[index, c[0], int(c[1])] for index, c in enumerate(inp)]

BubbleSort(copy.copy(C), N)
SelectionSort(copy.copy(C), N)


# Example run
# Input:
-3515890
415326
# Output:
41
Stable
41
Stable
def selectionSort(arr):
	icnt = 0
	for i in range(0, len(arr)):
		imin = i
		for j in range(i + 1, len(arr)):
			if arr[j][1] < arr[imin][1]:
				#			if arr[j] < arr[imin]:
				imin = j
		if imin != i:
			arr[i], arr[imin] = arr[imin], arr[i]
			icnt = icnt + 1


def bubbleSort(arr):
	flg = True
	cnt = 0
	while flg:
		flg = False
		for i in range(len(arr) - 1, 0, -1):
			if arr[i][1] < arr[i - 1][1]:
				#			if arr[i] < arr[i - 1]:
				arr[i - 1], arr[i] = arr[i], arr[i - 1]
				cnt = cnt + 1
				flg = True

def combine(arr):
	result = ''
	for i in arr:
		result = result + i[0] + str(i[1]) + ' '
	return result.rstrip(' ')

n = int(input())
a = list(input().split())  # [H4, C9, S4, D2, C3]
# a = list(map(int, input().split()))
b = []  # [[H,4], [C,9], [S,4], [D,2], [C,3]]
for i in range(0, len(a)):
	b.append([a[i][0], int(a[i][1])])
c = b.copy()
# c = b

bubbleSort(b)
result_b = combine(b)

selectionSort(c)
result_s = combine(c)

print(result_b)
print('Stable')

print(result_s)
if result_s == result_b:
	print('Stable')
else:
	print('Not stable')




# Example run
# Input:
33
431968623
# Output:
43
Stable
43
Stable