Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
n = int(input())
cardlist=list(map(str,input().split()))
def BubbleSort(C):
    for i in range(len(C)):
        for j in range(len(C)-1):
            if (C[j][-1:] >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)):
        minj = i
        for j in range(i,len(C)):
            if (C[j][-1:] < C[minj][-1:]):
                minj = j
        C[i],C[minj] = C[minj],C[i]
    return C
cardlist1 = cardlist.copy()
bubble = BubbleSort(cardlist)
print(*bubble)
print('Stable')
selection = SelectionSort(cardlist1)
print(*selection)
if(bubble == selection):
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
43251559
U]r$Yl
# Output:
U]r$Yl
Stable
U]r$Yl
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)
_is_stable = ''
for i in range(length-1):
    _min = i
    _is_stable = 'Stable'
    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:
-203888
`A_\6MN
# Output:
`A_\6MN
Stable
`A_\6MN
def bubble(b,p):
    for i in range(0,p):
        for j in reversed(range(i+1,n)):
            if int(b[j][1]) < int(b[j-1][1]):
                b[j],b[j-1] = b[j-1],b[j]
    return b

def selection(A,N):
    for i in range(0,N):
        minj = i
        for j in range(i,N):
            if int(A[j][1]) < int(A[minj][1]):
                minj = j
        if i != minj:
            A[i],A[minj] = A[minj],A[i]

    return A

n = int(input())
a = [s for s in input().split()]
c = a.copy()
print(" ".join(map(str,bubble(a,n))))
print("Stable")
d = selection(c,n)
print(" ".join(map(str,d)))
if a == d:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-13840614
Ju.
# Output:
Ju.
Stable
Ju.
Stable
def bubbleSort(x):
    A = x[:]
    flag_stable = True
    
    for i in range(1, len(A)):
        for j in range(1, len(A) - i + 1):
            if  A[j - 1][1] > A[j][1]:
                A[j], A[j - 1] = A[j - 1], A[j]

                if not flag_stable:
                    continue

                if A[j - 1][1:] == A[j][1:]:
                    flag_stable = False

    return A, flag_stable

def selectionSort(x):
    A = x[:]
    flag_stable = True

    for i in range(len(A)):
        minj = i

        for j in range(i + 1, len(A)):

            if A[j][1] < A[minj][1]:
                minj = j

        if minj != i:
            A[i], A[minj] = A[minj], A[i]

            if not flag_stable:
                continue

            for k in range(i, minj):
                if A[k][1] == A[minj][1]:
                    flag_stable = False

    return A, flag_stable




N = int(input())
card = list(input().split())

card_bubbleSort, flag_stable_bubbleSort = bubbleSort(card)
card_selectionSort, flag_stable_selectionSort = selectionSort(card)


print(*card_bubbleSort)

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

print(*card_selectionSort)

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



# Example run
# Input:
-108
s?jyi97
# Output:
s?jyi97
Stable
s?jyi97
Stable
import copy

n = int(input())

l = list(input().split())
C1 = []

for v in l:
    s = v[0]
    m = int(v[1])
    C1.append((s, m))

C2 = copy.deepcopy(C1)

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]

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

result1 = [t[0]+str(t[1]) for  t in C1]
result2 = [t[0]+str(t[1]) for  t in C2]

print(" ".join(result1))
print("Stable")
print(" ".join(result2))
if result1 == result2:
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
-1406309
-967
# Output:
-9
Stable
-9
Stable
def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def rls(): return list(map(str, input().split()))
def pl(a): print(" ".join(list(map(str, a))))


N = ri()
a = rls()
bubble = a[:]

flag = True
while(flag):
    flag = False
    for i in range(1, N):
        if(bubble[-i][1] < bubble[-i-1][1]):
            hold = bubble[-i]
            bubble[-i] = bubble[-i-1]
            bubble[-i-1] = hold
            flag = True
pl(bubble)
print("Stable")  # ?????????Stable

selection = a[:]
for i in range(N):
    minj = i
    for j in range(i, N):
        if(selection[j][1] < selection[minj][1]):
            minj = j
    hold = selection[i]
    selection[i] = selection[minj]
    selection[minj] = hold

pl(selection)
print("Stable" if bubble == selection else "Not stable")

# Example run
# Input:
-8799
abTcLg*7.
# Output:
abTcLg*7.
Stable
abTcLg*7.
Stable
def BubbleSort(C, N):
    '''C: list of str((S|H|C|D)+str(int)) -> list of str, str
    '''
    cli = C.copy()
    for i in range(N):
        for j in range(N - 1, i, -1):
            if int(cli[j][1:]) < int(cli[j - 1][1:]):
                cli[j], cli[j-1] = cli[j-1], cli[j]
    return cli, "Stable"

def SelectionSort(C,N):
    '''C: list of str((S|H|C|D)+str(int)) -> list of str, str
    '''
    cli = C.copy()
    for i in range(N):
        minj = i
        for j in range(i, N):
            if int(cli[j][1:]) < int(cli[minj][1:]):
                minj = j
        cli[i], cli[minj] = cli[minj], cli[i]
    return cli, isStable(cli, C)
def isStable(L1, L2):
    '''list of str(sorted), list of str -> str('Stable' or 'Not stable')
    '''
    s1, s2 = None, None
    #i1, i2 = None, None
    for i in range(len(L1)-1):
        for j in range(i+1, len(L1)):
            if int(L1[i][1:]) == int(L1[j][1:]):
                s1, s2 = L1[i], L1[j]  #i < j
                if L2.index(s1) >= L2.index(s2):
                    return 'Not stable'
    return 'Stable'
def printlist(L):
    for itm in L[:-1]:
        print(itm, end = ' ')
    print(L[-1])

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

L, s = BubbleSort(C, N)
printlist(L)
print(s)
L, s = SelectionSort(C, N)
printlist(L)
print(s)



# Example run
# Input:
-23909
Jq\y`
# Output:
Jq\y`
Stable
Jq\y`
Stable
n = int(input())

cards_b = input().split()
cards_s = list(cards_b)

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

#SelectionSort
for i in range(n):
    min_i = i
    for j in range(i, n):
        if int(cards_s[j][1]) < int(cards_s[min_i][1]):
            min_i = j
    cards_s[i], cards_s[min_i] = cards_s[min_i], cards_s[i]

print(" ".join(cards_b))
print("Stable")
print(" ".join(cards_s))

if cards_b == cards_s:
    print("Stable")
else:
    print("Not Stable")

# Example run
# Input:
-29588
s8H2
# Output:
s8H2
Stable
s8H2
Stable
import copy

def bubble(N, A):
    for i in range(N - 1):
        for j in reversed(range(1, N)):
            if A[j - 1][1] > A[j][1]:
                tmp = A[j]
                A[j] = A[j - 1]
                A[j - 1] = tmp

def select(N, A):
    for i in range(N):
        min = i
        for j in range(i, N):
            if A[min][1] > A[j][1]:
                min = j
        tmp = A[i]
        A[i] = A[min]
        A[min] = tmp

N = int(input())

#カード入力
S = [i for i in input().split()]
B = copy.deepcopy(S)

bubble(N, B)
select(N, S)

print(B)
print(S)


# Example run
# Input:
1
TK>
# Output:
['TK>']
['TK>']
n = int(input())
*A, = input().split()
B = A[:]
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(*A)
print("Stable")
 
for i in range(n):
    mj = i
    for j in range(i, n):
        if B[j][1] < B[mj][1]:
            mj = j
    B[i], B[mj] = B[mj], B[i]
print(*B)
if A == B:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
0
Sy&8x|,=9
# Output:
Sy&8x|,=9
Stable
Sy&8x|,=9
Stable
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


class Card(object):

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

    def __str__(self):
        return str(self.card)


def print_array(a):
    print(" ".join(map(str, a)))


def bubblesort(cards, n):
    c = cards[:]
    for i in range(0, n):
        for j in range(n - 1, i - 1, -1):
            if c[j].value < c[j - 1].value:
                (c[j], c[j - 1]) = (c[j - 1], c[j])
    return c


def selectionsort(cards, n):
    c = cards[:]
    for i in range(0, n):
        minj = i
        for j in range(i, n):
            if c[j].value < c[minj].value:
                minj = j
        (c[i], c[minj]) = (c[minj], c[i])
    return c


def main():
    n = int(input())
    cards = list(map(Card, input().split()))
    b = bubblesort(cards, n)
    print_array(b)
    print("Stable")
    s = selectionsort(cards, n)
    print_array(s)
    if b == s:
        print("Stable")
    else:
        print("Not stable")


if __name__ == "__main__":
    main()

# Example run
# Input:
-1
52
# Output:
52
Stable
52
Stable
import copy

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

# BubbleSort
bub_c = copy.deepcopy(c)
for i in range(n):
    for j in range(n-1, i, -1):
        if bub_c[j][1] < bub_c[j-1][1]:
            bub_c[j], bub_c[j-1] = bub_c[j-1], bub_c[j]

# SelectionSort
sel_c = copy.deepcopy(c)
for i in range(n):
    minj = i
    for j in range(i, n):
        if sel_c[j][1] < sel_c[minj][1]:
            minj = j
    sel_c[i], sel_c[minj] = sel_c[minj], sel_c[i]

shaped_bub = " ".join([c[0] + str(c[1]) for c in bub_c])
shaped_sel = " ".join([c[0] + str(c[1]) for c in sel_c])
print(shaped_bub, "Stable", sep="\n")
if [b[0] for b in bub_c] == [b[0] for b in sel_c]:
    print(shaped_sel, "Stable", sep="\n")
else:
    print(shaped_sel, "Not stable", sep="\n")


# Example run
# Input:
-755
-256478906
# Output:
-2
Stable
-2
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]
        

def selection_sort(a, n):
    for i in range(n):
        min = i
        for j in range(i, n):
            if a[j][1] < a[min][1]:
                min = j
        if min != i:
            a[min], a[i] = a[i], a[min]
            

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

B_A = O_A[:]
S_A = O_A[:]

bubble_sort(B_A, N)
selection_sort(S_A, N)
print(*B_A)
print('Stable')
print(*S_A)
for i in range(N):
    if B_A[i] != S_A[i]:
        print('Not stable')
        break
else:
    print('Stable')

    


# Example run
# Input:
-299483
~vkXMy>
# Output:
~vkXMy>
Stable
~vkXMy>
Stable
import copy

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

def SelectionSort(arr):
	n=len(arr)
	for i in range(n):
		minp=i
		for j in range(i,n):
			if int(arr[j][1])<int(arr[minp][1]):
				minp=j
		arr[minp],arr[i]=arr[i],arr[minp]
	return arr
  
def IsStable(basearr,resultarr):
  checkarr1=[[] for _ in range(14)]
  checkarr2=[[] for _ in range(14)]
  for i in range(len(basearr)):
    checkarr1[int(basearr[i][1])].append(basearr[i][0])
    checkarr2[int(resultarr[i][1])].append(resultarr[i][0])
  if checkarr1==checkarr2:
    print('Stable')
  else:
    print('Not stable')
  

n=int(input())
arr=list(map(str,input().split()))
bubble=BubbleSort(copy.deepcopy(arr))
selection=SelectionSort(copy.deepcopy(arr))
print(' '.join(map(str,bubble)))
IsStable(arr,bubble)
print(' '.join(map(str,selection)))
IsStable(arr,selection)


# Example run
# Input:
-5056872
2072477
# Output:
2072477
Stable
2072477
Stable
import copy
n = int(input())
A = input().split()
B = copy.deepcopy(A)
C = A[:]
for i in range(n):
    for j in range(n-1, i, -1):
        if int(B[j-1][1]) > int(B[j][1]):
            B[j-1], B[j] = B[j], B[j-1]
print(" ".join(B))
print("Stable")

_min = 0
for i in range(n):
    _min = i
    for j in range(i, n):
        if int(C[j][1]) < int(C[_min][1]):
            _min = j
    C[_min], C[i] = C[i], C[_min]
print(" ".join(C))
if B == C:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-507621088
!ZrP7l
# Output:
!ZrP7l
Stable
!ZrP7l
Stable
def bubbleSort(A,N):
    flag = 1 #????????????????????£??????????????????????????????????????¨??????
    i = 0

    while flag:
        flag = 0
        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
                flag = 1
        i += 1
    return A


def selectionSort(A,N):
    for i in range(0,N-1):
        minj = i
        j=i+1
        for j in range(j,N):
            if int(A[j][1]) < int(A[minj][1]):
                minj = j
        tmp = A[minj]
        A[minj] = A[i]
        A[i] = tmp
    return A

def isStable(ori,sorted):
    for i in range(len(ori)-1):
        for j in range(i+1, len(ori)-1):
            for a in range(len(ori)):
                for b in range(a+1, len(ori)):
                    if ori[i][1] == ori[j][1] and ori[i] == sorted[b] and ori[j] == sorted[a]:
                        return 'Not stable'
    return 'Stable'



if __name__ == '__main__':

    N = int(input())

    numbers = input().split(' ')
    n1 = numbers.copy()
    n2 = numbers.copy()

    A = bubbleSort(n1,N)

    print(A)
    print(isStable(numbers,A))

    B = selectionSort(n2,N)

    print(B)
    print(isStable(numbers, B))

# Example run
# Input:
-4664
=.[pS
# Output:
['=.[pS']
Stable
['=.[pS']
Stable
# input
n = int(input())
c_ori = input().split()

# bubble sort
c1 = c_ori[:]
for i in range(n):
    for j in range(n-1, i, -1):
        if c1[j][1] < c1[j-1][1]:
            c1[j-1], c1[j] = c1[j], c1[j-1]
print(*c1)
print('Stable')

# selection sort
c2 = c_ori[:]
for i in range(n):
    minj = i
    for j in range(i, n):
        if c2[j][1] < c2[minj][1]:
            minj = j
    c2[minj], c2[i] = c2[i], c2[minj]
print(*c2)

if c1 == c2:
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
-58
}x#m#d=C
# Output:
}x#m#d=C
Stable
}x#m#d=C
Stable
import copy

N = int(input())
C = list(list(input().split()))
Cb, Cs = copy.copy(C), copy.copy(C)


def BubbleSort(C, N):
    for i in range(N):
        for j in range(N-1, i, -1):
            if C[j-1][1] > C[j][1]:
                C[j-1], C[j] = C[j], C[j-1]
    for i in range(N):
        C[i] = "".join(C[i])
    print(" ".join(map(str, C)))


def SelectionSort(C, N):
    for i in range(N):
        minj = i
        for j in range(i,N):
            if C[minj][1] > C[j][1]:
                minj = j
        C[i], C[minj] = C[minj], C[i]
    for i in range(N):
        C[i] = "".join(C[i])
    print(" ".join(map(str, C)))

def StableCheck(Cin, Cout, N):
    for i in range(1,10):
        check1, check2 = [], []
        for j1 in Cin:
            if str(i) in j1:
                check1.append(j1)
        for j2 in Cout:
            if str(i) in j2:
                check2.append(j2)
        if check1 != check2:
            print("Not stable")
            exit()
    print("Stable")

BubbleSort(Cb, N)
StableCheck(C, Cb, N)
SelectionSort(Cs, N)
StableCheck(C, Cs, N)


# Example run
# Input:
-1893070
10823
# Output:
10823
Stable
10823
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(c, f):
    for i in range(len(c) - 1):
        for j in range(i + 1, len(c)):
            # print(i, j)
            if f(c[i]) > f(c[j]):
                swap(c, i, j)
    return c

def selection_sort(c, f):
    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)
    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:
125998
|!V2bBsP
# Output:
|!V2bBsP
Stable
|!V2bBsP
Stable
#安定なソート
#ようわからん
#バブルソートはどうやっても安定的なことが言いたい？

#バブルソート
def bubble_sort(list, length):
    flag = 1
    while(flag):
        flag = 0
        for j in reversed(range(1, length)):
            if list[j][1] < list[j-1][1]:
                list[j], list[j-1] = list[j-1], list[j]
                flag = 1

    return list

#選択ソート
def selection_sort(list, length):
    for i in range(length):
        minpos = i
        for j in range(i, length):
            if list[minpos][1] > list[j][1]:
                minpos = j

        list[i], list[minpos] = list[minpos], list[i]

    return list

#安定かどうかを判定するために常に安定なソートであるバブルソートと比較する

length = int(input())
cards_ = input().split()
cards = []
cards2 = []

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

b_list = bubble_sort(cards, length)
s_list = selection_sort(cards2, length)

result = ''
for b in b_list:
    result += b[0]+str(b[1]) + ' '
print(result[:-1])
print('Stable')

result = ''
for s in s_list:
    result += s[0]+str(s[1]) + ' '
print(result[:-1])

flag = 0
for i in range(len(b_list)):
    if b_list[i] != s_list[i]:
        print('Not stable')
        flag = 1
        break
if flag == 0:
    print('Stable')


# Example run
# Input:
-1131247330
-9
# Output:
-9
Stable
-9
Stable
N = int(input())
C = list(input().split())
_C = C.copy()

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]
print(*C)
print("Stable")

for i in range(N):
    m = i
    for j in range(i, N):
        if (_C[j][1] < _C[m][1]):
            m = j
    _C[i], _C[m] = _C[m], _C[i]
print(*_C)
if(C ==_C):
    print("Stable")
else:
    print("Not stable")

# Example run
# Input:
-2
^U11`Hf
# Output:
^U11`Hf
Stable
^U11`Hf
Stable
n = int(input())
l = []
s = {}
for i in input().split():
  t = []
  for j, k in enumerate(i):
    if j == 0 and k not in s:
      s[k] = len(s.keys())
    t += [k]
  l += [t]

t = l[:]
f = 0
for i in range(n):
  for j in range(n-1, 0, -1):
    if t[j][1] < t[j-1][1]:
      t[j], t[j-1] = t[j-1], t[j]
    elif t[j][1] == t[j-1][1]:
      f += 1 if s[t[j-1][0]] > s[t[j][0]] else 0
print(*["{0}{1}".format(i[0], i[1]) for i in t])
print("Not stable" if f > 0 else "Stable")

f = 0
for i in range(n):
  m = i
  for j in range(i, n):
    if l[j][1] < l[m][1]:
      m = j
    elif l[j][1] == l[m][1]:
      f += 1 if s[l[m][0]] > s[l[j][0]] else 0
  l[i], l[m] = l[m], l[i]
print(*["{0}{1}".format(i[0], i[1]) for i in l])
print("Not stable" if f > 0 else "Stable")


# Example run
# Input:
-2147483648
yg|U~
# Output:
yg
Stable
yg
Stable
import copy

def bubbleSort(cards):
    C = copy.copy(cards)
    for i in range(0, len(C)):
        for j in range(len(C) - 1, i, -1):
            if C[j][1] < C[j-1][1]:
                C[j-1], C[j] = C[j], C[j-1]
    return C

def selectionSort(cards):
    C = copy.copy(cards)
    for i in range(0, len(C)):
        min = i
        for j in range(i, len(C)):
            if C[j][1] < C[min][1]:
                min = j
        C[i], C[min] = C[min], C[i]
    return C


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

CB = bubbleSort(cards)
CS = selectionSort(cards)
print(' '.join(CB))
print('Stable')
print(' '.join(CS))
if CB == CS:
    print('Stable')
else:
    print('Not stable')

# Example run
# Input:
9850811
EwF
# Output:
EwF
Stable
EwF
Stable
def bubbleSort(cards, N):
    flag = True
    while flag:
        flag = False
        for j in range(N-1, 0, -1):
            if cards.numbers[j] < cards.numbers[j - 1]:
                cards.swap(j, j-1)
                flag = True
    return cards

def selectionSort(cards,N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if cards.numbers[j] < cards.numbers[minj]:
                minj = j
        if minj != i:
            cards.swap(i, minj)
    return cards

class Cards(object):
    
    def __init__(self, cards):
        self.cards = cards
        self.numbers = [int(card[1]) for card in cards]

    def filter_by_number(self, number):
        return [card for card in self.cards if card.endswith(str(number))]

    def swap(self, i, j):
        self.cards[i], self.cards[j] = self.cards[j], self.cards[i]
        self.numbers = [int(card[1]) for card in self.cards]

    def show(self):
        print(' '.join(self.cards))

    def is_stable(self, cards):
        for n in range(1,10):
            suits_x = self.filter_by_number(str(n))
            suits_y = cards.filter_by_number(str(n))
            if suits_x != suits_y:
                return False
        return True

    def copy(self):
        return Cards([card for card in self.cards])

def run():
    n = int(input())
    cards = Cards(input().split())
    cards_sorted = bubbleSort(cards.copy(),n)
    cards_sorted.show()
    if cards.is_stable(cards_sorted):
        print('Stable')
    else:
        print('Not Stable')

    cards_sorted = selectionSort(cards.copy(),n)
    cards_sorted.show()
    if cards.is_stable(cards_sorted):
        print('Stable')
    else:
        print('Not Stable')

if __name__ == '__main__':
    run()


# Example run
# Input:
-2147483648
-1406309
# Output:
-1406309
Stable
-1406309
Stable
import sys

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

def print_cards(arr_print, arr_compare):
	n = len(arr_print)
	same = True
	for i in range(n):
		if arr_compare != None and arr_print[i].card != arr_compare[i].card: same = False
		sys.stdout.write(str(arr_print[i]))
		if i != n - 1:
			sys.stdout.write(' ')
	print()
	return same

def swap(arr, i, j):
	temp = arr[i]
	arr[i] = arr[j]
	arr[j] = temp

def bubble_sort(arr):
	n = len(arr)
	for i in range(0, n):
		for j in range(n - 1, i, -1):
			if arr[j].value < arr[j - 1].value:
				swap(arr, j, j - 1)

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

n = int(input())
arr = list(map(str, input().split()))
cards1 = [None] * n
cards2 = [None] * n
for i in range(n):
	cards1[i] = Card(arr[i])
	cards2[i] = Card(arr[i])

bubble_sort(cards1)
selection_sort(cards2)

print_cards(cards1, None)
print('Stable')

stable = print_cards(cards2, cards1)
if stable == True:
	print('Stable')
else:
	print('Not stable')



# Example run
# Input:
-1
eXf?
# Output:

Stable

Stable