Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
class card:
    """
    suit: S, H, C, D
    number: 1~10
    """
    def __init__(self, card_input):
        self.suit = card_input[:1]
        self.number = int(card_input[1:])
    
    def __str__(self):
        return self.suit + str(self.number)


def print_list(a):
    out = ''
    for ai in a:
        out += str(ai) + ' '
    else:
        out = out[:-1]
    print(out)

def bubble_sort(a, n):
    for i in range(0, n):
        for j in range(n - 1, i, -1):
            if a[j].number < a[j - 1].number:
                tmp = a[j]
                a[j] = a[j - 1]
                a[j - 1] = tmp
    return a
                
def selection_sort(a, n):
    for i in range(0, n):
        minj = i
        for j in range(i, n):
            if a[j].number < a[minj].number:
                minj = j
        tmp = a[i]
        a[i] = a[minj]
        a[minj] = tmp
    return a

n = int(input())
input_cards = input().split(' ')
cards = []
for in_card in input_cards:
    cards.append(card(in_card))

bubble = bubble_sort(cards[:], n)
print_list(bubble)
print("Stable")

selection = selection_sort(cards[:], n)
print_list(selection)
if bubble == selection:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-525602
42329671
# Output:
42329671
Stable
42329671
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(["Not stable","Stable"][c==d])


# Example run
# Input:
-58867430
k^S/8NM/
# Output:
k^S/8NM/
Stable
k^S/8NM/
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())
cardsR = input().split()
cardsS = cardsR[:]

print(' '.join(BubbleSort(cardsR, n)))
print("Stable")
print(*SelectionSort(cardsS, n))
print("Stable" if cardsR == cardsS else "Not stable")

# Example run
# Input:
-7737
ulQ!ZrP7l
# Output:
ulQ!ZrP7l
Stable
ulQ!ZrP7l
Stable
#愚直な判定
def JudgeStable(inC, outC, 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 inC[i][1] == inC[j][1] and inC[i] == outC[b] and inC[j] == outC[a]:
                        return False
    return True

def PrintJudge(judge):
    if judge:
        print('Stable')
    else:
        print('Not stable')
        
def BubbleSort(C, N):
    for i in range(N):
        for j in reversed(range(i+1, N)):
            if C[j-1][1] > C[j][1]:
                C[j-1], C[j] = C[j], C[j-1]
                
def SelectionSort(C, N):
    for i in range(N):
        minj = i
        for j in range(i+1, N):
            if C[minj][1] > C[j][1]:
                minj = j
        C[minj], C[i] = C[i], C[minj]
                
def PrintC(C):
    print(' '.join([''.join([c[0], str(c[1])]) for c in C]))

N = int(input())
C = [[c[0], int(c[1])] for c in input().split()]
C1 = C.copy()
C2 = C.copy()

BubbleSort(C1, N)
SelectionSort(C2, N)

PrintC(C1)
PrintJudge(JudgeStable(C, C1, N))

PrintC(C2)
PrintJudge(JudgeStable(C, C2, N))


# Example run
# Input:
-1057486868
10366
# Output:
10
Stable
10
Stable
def bubbleSort(c):
    for i in range(0, len(c) - 1):
        for j in range(len(c)-1, i, -1):
            if c[j][1] < c[j-1][1]:
                c[j], c[j-1] = c[j-1], c[j]


def selectionSort(c):
    for i in range(0, 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]


def isStable(c1, c2):
    for i in range(0, len(c1)):
        if c1[i][0] == c2[i][0]:
            return False
    return True


import copy
n = int(input())
c1 = input().split()
c2 = copy.copy(c1)

bubbleSort(c1)
selectionSort(c2)
print(*c1)
print("Stable")
print(*c2)
print("Stable") if isStable(c1, c2) else print("Not stable")



# Example run
# Input:
-950319
6'm
# Output:
6'm
Stable
6'm
Not stable
N = int(input())
l = input().split()
l2 = l[:]
for j in range(N):
    for i in range(N-1):
        if l[i][1] > l[i+1][1]:
            l[i], l[i+1] = l[i+1], l[i]
for i in range(0,len(l)-1):
    print(l[i],end=' ')
print(l[N-1])
print("Stable")

for j in range(0,len(l2)-1):
    min = l2[j][1]
    a = j
    for i in range(j,len(l2)):
        if min > l2[i][1]:
            min = l2[i][1]
            a = i
    l2[j],l2[a] = l2[a],l2[j]
for i in range(0,len(l2)-1):
    print(l2[i],end=' ')
print(l2[N-1])
if l==l2:
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
1
.-[!jV'ZI
# Output:
.-[!jV'ZI
Stable
.-[!jV'ZI
Stable
def bubble_sort(cards):
    list_length = len(cards)

    for i in range(list_length):
        for j in range(list_length-1,i,-1):
            if int(cards[j][1:]) < int(cards[j-1][1:]):
                cards[j],cards[j-1] = cards[j-1],cards[j]
    return cards

def selection_sort(cards):
    list_length = len(cards)

    for i in range(list_length):
        min_element = i
        for j in range(i+1,list_length):
            if int(cards[j][1:]) < int(cards[min_element][1:]):
                min_element = j
        cards[i],cards[min_element] = cards[min_element],cards[i]
    return cards

n = int(input())
cards = input().split()
bubble_cards = [i for i in bubble_sort(cards)]
selection_cards = [i for i in selection_sort(cards)]

print(' '.join(bubble_cards))
print('Stable')
print(' '.join(selection_cards))
if bubble_cards == selection_cards:
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
-30792
9\60Qh=t8
# Output:
9\60Qh=t8
Stable
9\60Qh=t8
Stable
n = int(input())
l = []
for i in input().split():
  t = []
  for j in i: t += [j]
  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 l.index(t[j-1]) > l.index(t[j]) else 0
print(*["{0}{1}".format(i[0], i[1]) for i in t])
print("Not stable" if f > 0 else "Stable")

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


# Example run
# Input:
-256018
?7&49\6
# Output:
?7
Stable
?7
Stable
def bubble(N,C):
  for i in range(N):
    for j in range(i+1,N)[::-1]:
      if C[j][1] < C[j-1][1]:
        _=C[j]
        C[j]=C[j-1]
        C[j-1]=_
  print(*C)

def selection(N,C):
  for i in range(N):
    minj=i
    for j in range(i,N):
      if C[minj][1] > C[j][1]:
        minj=j
    _=C[minj]
    C[minj]=C[i]
    C[i]=_
  print(*C)

def stable(A,C):
  result='Stable'
  for i in range(1,10):
    a=[j for j in A if j[1]==str(i)]
    c=[k for k in C if k[1]==str(i)]
    if a!=c:
      result='Not stable'
  print(result)

N=int(input())
C=list(input().split())
A=C[:]
bubble(N,C)
stable(A,C)
C=A[:]
selection(N,C)
stable(A,C)


# Example run
# Input:
-30
YQocc[TJS
# Output:
YQocc[TJS
Stable
YQocc[TJS
Stable
import copy
n = int(input())
A = list(map(str,input().split()))
B = copy.copy(A)

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

def SelectionSort(A,n):
    for i in range(n):
        minj = i
        for j in range(i,n):
            if int(A[j][1:2])<int(A[minj][1:2]):
                minj = j
        v = A[i]
        A[i] = A[minj]
        A[minj] = v
    return A

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


# Example run
# Input:
-726599
AhnEV<
# Output:
AhnEV<
Stable
AhnEV<
Stable
def bubbleSort(A, N):
    flag = 1
    while flag:
        flag = 0
        for j in range(N-1, 0, -1):
            if A[j][1] < A[j-1][1]:
                A[j], A[j-1] = A[j-1], A[j]
                flag = 1
    print(*A)
    return A


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

    print(*A)
    return A


def isStable(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] == output[b] and input[j] == output[a]:
                        print("Not stable")
                        return False
    print("Stable")
    return True

arr_length = int(input())
arr_num = [i for i in input().split(" ")]

isStable(arr_num, bubbleSort(list(arr_num), arr_length), arr_length)

isStable(arr_num, selectionSort(list(arr_num), arr_length), arr_length)


# Example run
# Input:
-8799
abTcLg*7.
# Output:
abTcLg*7.
Stable
abTcLg*7.
Stable
n = int(input())
l = input().split(" ")
L = l[:]
for k in range(n - 1):
    for j in range(n - 1, 0, -1):
        if L[j][1:] < L[j - 1][1:]:
            L[j], L[j - 1] = L[j - 1], L[j]
    m = l[k:].index(min(l[k:], key=lambda x: x[1]))
    if m != 0:
        l[k], l[m + k] = l[m + k], l[k]
print(*L)
print("Stable")
print(*l)
print(['Not s', 'S'][l == L] + 'table')


# Example run
# Input:
-41939
:]U4
# Output:
:]U4
Stable
:]U4
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

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

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

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

print(" ".join(B))
print("Stable")
print(" ".join(S))
if st(B, S) == True:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-256478906
8P!9,=^6j
# Output:
8P!9,=^6j
Stable
8P!9,=^6j
Stable
# coding: utf-8
# Here your code !

def BubbleSort(A,N):
    count = 0
    flag = 1
    while flag:
        flag = 0
        for i in range(1,N):
            if int(A[N-i][1]) < int(A[N-i-1][1]):
                A[N-i] , A[N-i-1] = A[N-i-1] , A[N-i]
                flag = 1
                print(A)
    return A

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[j],C[minj] = C[minj],C[j]
    return C

if __name__ == '__main__':
    n = int(input())
    data = input().split()
    selection = data
    selection = SelectionSort(selection,n)
    print(" ".join(BubbleSort(data,n)))
    print("Stable")
    print(" ".join(selection))
    if data == selection:
	    print("Stable")
    else:
	    print("Not Stable")

# Example run
# Input:
-929
tx=.[pSe
# Output:
tx=.[pSe
Stable
tx=.[pSe
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:
-740
85[tBatc
# Output:
85[tBatc
Stable
85[tBatc
Stable
def bubbeSort(arr):
    for i in range(len(arr)):
        for j in range(len(arr) - 1, i, -1):
            if arr[j][1] < arr[j - 1][1]:
                arr[j], arr[j - 1] = arr[j - 1], arr[j]

def selectSort(arr):
    for i in range(len(arr)):
        Min = i
        for j in range(i, len(arr)):
            if arr[j][1] < arr[Min][1]:
                Min = j
        if i != Min:
            arr[i], arr[Min] = arr[Min], arr[i]

n = int(input())
arr = list(map(str, input().split()))
arr1 = arr[:]
bubbeSort(arr)
selectSort(arr1)
print(*arr)
print("Stable")
print(*arr1)
print(["Not stable", "Stable"][arr == arr1])


# Example run
# Input:
1165
(&"h#Xyo
# Output:
(&"h#Xyo
Stable
(&"h#Xyo
Stable
n=int(input())
c=input().split()
d=c[:]

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")

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)
if c==d:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-11
7.**G\f
# Output:
7.**G\f
Stable
7.**G\f
Stable
import copy


def group(arr):
    r = {}
    for a in arr:
        if r.get(a[1]):
            r[a[1]] += a[0]
        else:
            r[a[1]] = a[0]

    return r


n = int(input())
A = list(input().split(' '))
_A = copy.deepcopy(A)

for _ in range(n - 1):
    for i in range(1, n)[::-1]:
        if A[i - 1][1] > A[i][1]:
            A[i - 1], A[i] = A[i], A[i - 1]
print(*A)
print('Stable')

A = copy.deepcopy(_A)

for i in range(n - 1):
    minv_idx = i
    for k in range(i + 1, n):
        if A[minv_idx][1] > A[k][1]:
            minv_idx = k
    if i != minv_idx:
        A[i], A[minv_idx] = A[minv_idx], A[i]

print(*A)
if group(A) == group(_A):
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
1
+[3a?Sh
# Output:
+[3a?Sh
Stable
+[3a?Sh
Stable
def bSort(A):
    flag = 1
    i = 0
    count = 0
    while flag:
        flag = 0
        for j in range(len(A)-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
                count += 1
        i += 1
    return A, count

def sSort(A):
    count = 0
    for i in range(len(A)):
        minj = i
        for j in range(i, len(A)):
            if int(A[j][1]) < int(A[minj][1]):
                minj = j
        if minj != i:
            count += 1
        tmp = A[i]
        A[i] = A[minj]
        A[minj] = tmp
    return A, count

def isStable(input_a, output_a):
    for v1, v2 in zip(input_a, output_a):
        if v1 != v2:
            return 'Not stable'
    return 'Stable'

if __name__ == '__main__':
    length = input()
    data = input().split()
    sort_s, _= sSort(list(data))
    sort_b, _= bSort(list(data))
    print (' '.join([str(x) for x in sort_b]))
    print (isStable(sort_b, sort_b))
    print (' '.join([str(x) for x in sort_s]))
    print (isStable(sort_b, sort_s))


# Example run
# Input:
+53a5
-17760757
# Output:
-17760757
Stable
-17760757
Stable
def bs(a,n):
    ans=0
    flag=True
    while flag:
        flag=False
        for i in range(n-1,0,-1):
            if int(a[i][1])<int(a[i-1][1]):
                a[i],a[i-1]=a[i-1],a[i]
                flag=True
                ans+=1
    return a

def ss(a,n):
    ans=0
    for i in range(n):
        m=i
        for j in range(i,n):
            if int(a[j][1])<int(a[m][1]):
                m=j
        if m!=i:
            a[i],a[m]=a[m],a[i]
            ans+=1
    return a
N=int(input())
A=list(input().split())
B=A[:]
ans1,ans2=bs(A,N),ss(B,N)
print(*ans1)
print("Stable")
print(*ans2)
print("Stable" if ans1==ans2 else "Not stable")


# Example run
# Input:
-15356396
VtQHWP
# Output:
VtQHWP
Stable
VtQHWP
Stable
# -*- coding: utf-8 -*-
# ALDS1_2_C

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

N = int(input())
C = input().split()
C1 = C.copy()
C2 = C.copy()

BSC = BubbleSort(C1)
print(" ".join(BSC))
print("Stable")
SSC = SelectionSort(C2)
print(" ".join(SSC))
if BSC == SSC:
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
-2503
10842
# Output:
10842
Stable
10842
Stable
#バブルソート
def BubbleSort(C,N):
    for i in range (0,N,1):
        for j in range(N-1,i,-1):
            if int(C[j][1:2]) < int(C[j-1][1:2]):
                tmp = C[j]
                C[j] = C[j-1]
                C[j-1] = tmp
    print(' '.join(C))

    
                
#選択ソート
def SelectionSort(C,N):
    for i in range(0,N,1):
        minj = i
        for j in range(i,N,1):
            if int(C[j][1:2]) < int(C[minj][1:2]):
                minj = j
        tmp = C[i]
        C[i] = C[minj]
        C[minj] = tmp
    print(' '.join(C))



N = int(input())
A = list(input().split())
Bubble_A = A.copy()
Selection_A = A.copy()

BubbleSort(Bubble_A,N)
print("Stable")
SelectionSort(Selection_A,N)
flag = True
for Bubble,Selection in zip(Bubble_A,Selection_A):
    if Bubble != Selection:
        flag = False
if flag :
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
-4190
6[d@26_
# Output:
6[d@26_
Stable
6[d@26_
Stable
import copy

def bubble_sort(a):
    ba = copy.copy(a)
    flag = True
    for i in range(0, n):
        if not flag:
            break
        flag = False
        for j in range(n-1, 0, -1):
            if int(ba[j][1]) < int(ba[j-1][1]):
                ba[j], ba[j-1] = ba[j-1], ba[j]
                flag = True

    return ba

def selection_sort(a):
    sa = copy.copy(a)
    for i in range(n):
        flag = False
        minj = i
        for j in range(i, n):
            if int(sa[j][1]) < int(sa[minj][1]):
                minj = j
                flag = True
        if flag:
            sa[i], sa[minj] = sa[minj], sa[i]

    return sa

def is_stable(ba, sa):
    for b, s in zip(ba, sa):
        if b != s:
            return 'Not Stable'
    return 'Stable'


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

ba = bubble_sort(a)
print(' '.join(map(str, ba)))
print('Stable')

sa = selection_sort(a)
print(' '.join(map(str, sa)))
print(is_stable(ba, sa))



# Example run
# Input:
-1131247330
d=C>#:p
# Output:
d=C>#:p
Stable
d=C>#:p
Stable
import copy
n=int(input())
num=input().split()
numa=copy.copy(num)
numb=copy.copy(num)

#buble
for i in range(0,n):
	a=0
	for j in range(n-1,i,-1):
		if numa[j][1:]<numa[j-1][1:]:
			a=numa[j]
			numa[j]=numa[j-1]
			numa[j-1]=a
print(' '.join(list(map(str,numa))))
print('Stable')

#select
for i in range(0,n):
	minj=i
	b=0
	for j in range(i,n):
		if numb[j][1:]<numb[minj][1:]:
			minj=j
	b=numb[minj]
	numb[minj]=numb[i]
	numb[i]=b
print(' '.join(list(map(str,numb))))
if numb==numa:
	print('Stable')
else:
	print('Not stable')
		



# Example run
# Input:
0
A9?b;/#NX
# Output:
A9?b;/#NX
Stable
A9?b;/#NX
Stable
#!/usr/bin/env python
# encoding: utf-8


class Solution:
    def stable_sort(self):
        # write your code here
        array_length = int(input())
        array = [str(x) for x in input().split()]

        bubble_result = self.bubble_sort(array=array, array_length=array_length)
        selection_result = self.selection_sort(array=array, array_length=array_length)

        # check whether selection sort is stable
        if bubble_result == selection_result:
            print("Stable")
        else:
            print("Not Stable")

    @staticmethod
    def selection_sort(array, array_length):
        # selection sort
        selection_count = 0
        for i in range(array_length):
            min_j = i
            for j in range(i, array_length):
                if array[j][1] < array[min_j][1]:
                    min_j = j
            array[i], array[min_j] = array[min_j], array[i]
            if i != min_j:
                selection_count += 1

        result = " ".join(map(str, array))
        print(result)
        return result

    @staticmethod
    def bubble_sort(array, array_length):
        flag, bubble_count, cursor = 1, 0, 0
        while flag:
            flag = 0
            for j in range(array_length - 1, cursor, -1):
                if array[j][1] < array[j - 1][1]:
                    array[j], array[j - 1] = array[j - 1], array[j]
                    flag = 1
                    bubble_count += 1
        cursor += 1
        result = " ".join(map(str, array))
        print(result)
        print("Stable")
        return result


if __name__ == '__main__':
    solution = Solution()
    solution.stable_sort()

# Example run
# Input:
-29082932
P~H
# Output:
P~H
Stable
P~H
Stable
def check_stable(before_sort_list, after_sort_list):
    N = len(before_sort_list)
    for i in range(0, N, 1):
        for j in range(i+1, N, 1):
            for a in range(0, N, 1):
                for b in range(a+1, N, 1):
                    if before_sort_list[i][1] == before_sort_list[j][1] and before_sort_list[i] == after_sort_list[b] and before_sort_list[j] == after_sort_list[a]:
                        return False
    return True

def bubble_sort(cards_list, N):
    for i in range(0, N, 1):
        for j in range(N-1, i, -1):
            if cards_list[j][1] < cards_list[j-1][1]:
                cards_list[j], cards_list[j-1] = (cards_list[j-1], cards_list[j])
    return cards_list


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


num_cards = int(input())
cards = input().split(' ')

sorted_cards1 = bubble_sort(cards.copy(), num_cards)
sorted_cards2 = selection_sort(cards.copy(), num_cards)

print(' '.join(sorted_cards1))
print('Stable' if check_stable(cards, sorted_cards1) else 'Not stable')
print(' '.join(sorted_cards2))
print('Stable' if check_stable(cards, sorted_cards2) else 'Not stable')


# Example run
# Input:
0
]P}lXg<'
# Output:
]P}lXg<'
Stable
]P}lXg<'
Stable
def compare_cards(a, b):
    return a[1] < b[1]

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

def selection_sort(A):
    for i in range(len(A)):
        mini = i
        for j in range(i, len(A)):
            if compare_cards(A[j], A[mini]):
                mini = j
        A[i], A[mini] = A[mini], A[i]

def check_stable(originA, sortedA):
    for i in range(len(originA)-1):
        if not compare_cards(sortedA[i], sortedA[i+1]):
            if originA.index(sortedA[i]) > originA.index(sortedA[i+1]):
                return "Not stable"
    return "Stable"

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

bubbleA = list(A)
selectionA = list(A)

bubble_sort(bubbleA)
selection_sort(selectionA)

print(*bubbleA)
print(check_stable(A, bubbleA))

print(*selectionA)
print(check_stable(A, selectionA))

# Example run
# Input:
5101803
#("Ua
# Output:
#("Ua
Stable
#("Ua
Stable