Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
class Card:
    def __init__(self, mark, value):
        self.mark = mark
        self.value = value

    def __eq__(self, other):
        if not isinstance(other, Card):
            return NotImplemented
        return self.value == other.value and self.mark == other.mark

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

    def __str__(self):
        return self.mark + str(self.value)


def BubbleSort(arr):
    res = [Card(c.mark, c.value) for c in arr]
    swap_flg = True
    i = 0
    while swap_flg:
        swap_flg = False
        for j in range(len(res) - 1, i, -1):
            if (res[j] < res[j - 1]):
                res[j], res[j - 1] = res[j - 1], res[j]
                swap_flg = True
        i += 1
    return res


def SelectionSort(arr):
    res = [Card(c.mark, c.value) for c in arr]
    for i in range(0, len(res)):
        minj = i
        for j in range(i, N):
            if res[j] < res[minj]:
                minj = j
        if (i != minj):
            res[i], res[minj] = res[minj], res[i]
    return res


def isStable(in_arr, out_arr):
    stable_arr = BubbleSort(in_arr)
    return all(out_arr[i] == stable_arr[i] for i in range(0, len(out_arr)))


N = int(input())
arr = [Card(s[0], int(s[1])) for s in input().split()]
b_arr = BubbleSort(arr)
print(' '.join(map(str, b_arr)))
print('Stable' if isStable(arr, b_arr) else 'Not stable')
s_arr = SelectionSort(arr)
print(' '.join(map(str, s_arr)))
print('Stable' if isStable(arr, s_arr) else 'Not stable')



# Example run
# Input:
-84559984
-58783
# Output:
-5
Stable
-5
Stable
def bubble_sort(c, n):
  l = c[:]
  for i in range(n-1):
    for j in reversed(range(i+1, N)):
      if l[j][1] < l[j-1][1]:
        l[j], l[j-1] = l[j-1], l[j]
  return l

def selection_sort(c, n):
  l = c[:]
  for i in range(n):
    min_x = i
    for j in range(i, n):
      if l[j][1] < l[min_x][1]:
        min_x = j
    l[i], l[min_x] = l[min_x], l[i]
  return l

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


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

bubble_sorted_list = bubble_sort(C, N)
selection_sorted_list = selection_sort(C, N)

print(" ".join(map("".join, bubble_sorted_list)))
print("Stable" if is_stable(C, bubble_sorted_list, N) else "Not stable")
print(" ".join(map("".join, selection_sorted_list)))
print("Stable" if is_stable(C, selection_sorted_list, N) else "Not stable")



# Example run
# Input:
-15915
:u{kD)1)
# Output:
:u{kD)1)
Stable
:u{kD)1)
Stable
class card:

    def __init__(self,cv):
        c = cv[0:1]
        v = int(cv[1:2])
        self.c = c
        self.v = v
    

    def self_str(self):
        q = str(str(self.c) + str(self.v))
        return q


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


b = a[:]
c = a[:]

for i in range(n):
    for j in range(n-1, i, -1):
        if b[j].v < b[j-1].v:
            b[j], b[j-1] = b[j-1],b[j]

print(" ".join(x.self_str() for x in b))

coua = ["" for i in range(10)]
coub = ["" for i in range(10)]
conb = ""
for i in range(n):
    for j in range(n):
        if i != j:
            if a[i].v == a[j].v:
                coua[a[i].v] += a[i].c
            if b[i].v == b[j].v:
                coub[b[i].v] += b[i].c
if coua == coub:
     conb = "Stable"
else:
    conb = "Not stable"
print(conb)





for i in range(n):
    mini = i
    for j in range(i, n):
        if c[j].v < c[mini].v:
            mini = j
    c[mini], c[i] = c[i], c[mini]

print(" ".join(x.self_str() for x in c))

couc = ["" for i in range(10)]
conc = ""
for i in range(n):
    for j in range(n):
        if i != j:
            if c[i].v == c[j].v:
                couc[c[i].v] += c[i].c
if coua == couc:
     conc = "Stable"
else:
    conc = "Not stable"

print(conc)

# Example run
# Input:
-9
89
# Output:
89
Stable
89
Stable
# Stable Sort

length = int(input())
cards = input().rstrip().split()
cards1 = [card for card in cards]
cards2 = [card for card in cards]

def value(n):
    number = n[1:]
    return int(number)

def char(cards):
    charSets = [[] for i in range(10)]
    for i in range(length):
        char = cards[i][:1]
        val = value(cards[i])
        # print('絵柄: ' + char + ', 数字: ' + str(val))
        charSets[val].append(char)
    return charSets

def bubble(cards):
    for i in range(length):
        j = length - 1
        while j > i:
            if value(cards[j]) < value(cards[j - 1]):
                cards[j], cards[j - 1] = cards[j - 1], cards[j]
            j -= 1
    return cards

def selection(cards):
    # count = 0
    for i in range(length):
        minj = i
        for j in range(i, length):
            if value(cards[j]) < value(cards[minj]):
                minj = j
        #if minj != i:
            # count += 1
        cards[i], cards[minj] = cards[minj], cards[i]
    return cards

def stable(cards1, cards2):
    if char(cards1) == char(cards2):
        return 'Stable'
    else:
        return 'Not stable'

c = cards
b = bubble(cards1)
s = selection(cards2)

print(b)
print(stable(c, b))
print(s)
print(stable(c, s))



# Example run
# Input:
-58867430
k^S/8NM/
# Output:
['k^S/8NM/']
Stable
['k^S/8NM/']
Stable
def bubble_sort(sequence):
    for i in range(len(sequence)):
        for j in range(len(sequence)-1, i, -1):
            if int(sequence[j-1][1]) > int(sequence[j][1]):
                sequence[j], sequence[j-1] \
                    = sequence[j-1], sequence[j]
    return sequence


def selection_sort(sequence):
    for i in range(len(sequence)):
        mini = i
        for j in range(i, len(sequence)):
            if int(sequence[j][1]) < int(sequence[mini][1]):
                mini = j
        sequence[i], sequence[mini] = sequence[mini], sequence[i]
    return sequence   


def main():
    input()
    cards = input().split()
    bubble = bubble_sort(cards[:])
    selection = selection_sort(cards[:])
    stable = sorted(cards, key=lambda card: int(card[1]))
    print(' '.join(bubble))
    print('Stable' if bubble == stable else 'Not stable')
    print(' '.join(selection))
    print('Stable' if selection == stable else 'Not stable')


if __name__ == "__main__":
    main()



# Example run
# Input:
kU){S
-2
# Output:
-2
Stable
-2
Stable
def bubbleSort(C1,N):
    for i in range(N):
        for j in range(N-1,i,-1):
            if C1[j][1] < C1[j-1][1]:
                C1[j],C1[j-1] = C1[j-1],C1[j]
    print(*C1)
    print("Stable")
    return C1[:]
    
def selectSort(C2,N):
    for i in range(0,N):
        minj = i
        for j in range(i,N-1):
            if C2[j][1] > C2[j+1][1]:
                minj = j+1
        C2[i],C2[minj] = C2[minj],C2[i]
    return C2[:]

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

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

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


# Example run
# Input:
-1921542
d-3D,
# Output:
d-3D,
Stable
d-3D,
Stable
def buble(n,x,count):
    for i in range(1,n + 1):
        for j in range(1,i):
            if int(x[i - j][1]) < int(x[i - j - 1][1]):
                x[i - j],x[i - j - 1] = x[i - j - 1],x[i - j]
                count += 1  
    print (" ".join(x))
    print ("Stable")
    
def delection(n,x,flag):
    
    for i in range(n - 1):
        minx = i
        for j in range(i + 1,n):
            if x[j][1] == x[i][1]:
                flag = 1
            if x[j][1] < x[minx][1]:
                minx = j
        
        if not i == minx:
            x[i],x[minx]=x[minx],x[i]
            
    print (" ".join(x))
    if flag == 1:
        print ("Stable")
    else:
        print ("Not stable")
    
n = int(input())
x = list(map(str,input().split()))
y = x
count = 0
flag = 0
buble(n,x,count)
delection(n,y,flag)

# Example run
# Input:
-38652
Vmlrog5Sa
# Output:
Vmlrog5Sa
Stable
Vmlrog5Sa
Not stable
import copy

def is_stable(ax,bx):
    num=[]
    for ix in ax:
        if ix[1] not in num:
            num.append(ix[1])
    for ix in num:
        cx=[]
        for jx in ax:
            if jx[1]==ix:
                cx.append(jx)
        dx=[]
        for jx in bx:
            if jx[1]==ix:
                dx.append(jx)
        if cx!=dx:
            return "Not stable"
    else:
        return "Stable"

def array_print(ar):
    s=""
    for i in range(len(ar)):
        s+=(ar[i][0]+str(ar[i][1]))
        if i!=n-1:
            s+=" "
    return s

n=int(input())
a=[[i[0],int(i[1])]for i in input().split()]
b1=copy.deepcopy(a)
b2=copy.deepcopy(a)

#バブルソート
f=1
while f:
    f=0
    for i in range(n-1):
        if b1[n-i-1][1]<b1[n-i-2][1]:
            b1[n-i-1],b1[n-i-2]=b1[n-i-2],b1[n-i-1]
            f=1
print(array_print(b1))
print(is_stable(a,b1))

#選択ソート
for i in range(n):
    min=i
    for j in range(i+1,n):
        if b2[min][1]>b2[j][1]:
            min=j
    b2[min],b2[i]=b2[i],b2[min]
print(array_print(b2))
print(is_stable(a,b2))



# Example run
# Input:
-554740
65444
# Output:
65 
Stable
65 
Stable
n = int(input())
a = input().strip().split()

# bubble sort
b = a[:]
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]

print(' '.join(b))
print('Stable')

# selection sort
for i in range(n):
    mini = i
    for j in range(i, n):
        if a[j][1] < a[mini][1]:
            mini = j
    a[i], a[mini] = a[mini], a[i]
print(' '.join(a))
print('Stable' if a == b else 'Not stable')

# Example run
# Input:
-7
._I{;=Sl;
# Output:
._I{;=Sl;
Stable
._I{;=Sl;
Stable
def bubble_sort(A):
    N=len(A)
    flag=True
    while flag:
        flag=False
        j=0
        for i in range(N-1, j, -1):
            if A[i-1][1:]>A[i][1:]:
                A[i-1],A[i]=A[i],A[i-1]
                flag=True
        j+=1
    return A

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

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

bub=bubble_sort(A[:])
sel=selection_sort(A)
msg="Stable"

for i in range(N):
    if bub[i]!=sel[i]:
        msg="Not stable"

print(*bub)
print("Stable")
print(*sel)
print(msg)


# Example run
# Input:
-161684
<}:H+53a
# Output:
<}:H+53a
Stable
<}:H+53a
Stable
N=int(input())
A=input().split()

B=A[:]
S=A[:]

def BubbleSort(A, N):
    count = 0
    flag = True
    while flag:
        flag = False
        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]
                count += 1
                flag = True
                
    return A

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 += 1
    return A

b = BubbleSort(B, N)
s = SelectionSort(S, N)
print(*b)
print("Stable")
print(*s)

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

# Example run
# Input:
-227062494
/DJd,
# Output:
/DJd,
Stable
/DJd,
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:
-36866075
#9DXV
# Output:
#9DXV
Stable
#9DXV
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
    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
        if i != minj:
            C[i],C[minj] = C[minj],C[i]
    return C


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

# Example run
# Input:
-30547349
[oP
# Output:
[oP
Stable
[oP
Stable
def is_stable(oline, line):
    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 (oline[i][1] == oline[j][1]) & (oline[i] == line[b]) & (oline[j] == line[a]):
                        return False
    return True

N = int(input())
line = input().split()
oline = line.copy()
#BubbleSort
for i in range(N):
    for j in range(N-1, i, -1):
        if int(line[j][1]) < int(line[j-1][1]):
            tmp = line[j]
            line[j] = line[j-1]
            line[j-1] = tmp
print(' '.join(line))
print(('Not stabe', 'Stable')[is_stable(oline, line)])

#SelectionSort
line = oline.copy()
for i in range(N):
    minj = i
    for j in range(i+1, N):
        if int(line[minj][1]) > int(line[j][1]):
            minj = j
    tmp = line[i]
    line[i] = line[minj]
    line[minj] = tmp
print(' '.join(line))

print(('Not stabe', 'Stable')[is_stable(oline, line)])

# Example run
# Input:
-4
a:4}N
# Output:
a:4}N
Stable
a:4}N
Stable
import copy
def bubbleSort(A, N):
    cnt = 0
    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
                cnt = cnt + 1
    return cnt
 
 
def selectionSort(A, N):
    cnt = 0
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if A[j][1] < A[minj][1]:
                minj = j
        cnt = cnt + int(i != minj)
        A[i], A[minj] = A[minj], A[i]
    return cnt
 
def prArr(A, N):
    for i in range(N):
        if i != 0:
            print(" ", end = "")
        print(A[i], end = "")
    print()
 
     
N = int(input())
A = [i for i in input().split()]
B = copy.deepcopy(A)
 
bubbleSort(A, N)
selectionSort(B, N)
 
prArr(A, N)
print("Stable")
 
prArr(B, N)
print("Stable" if A == B else "Not stable")


# Example run
# Input:
-2147483648
"At:Js>
# Output:

Stable

Stable
import copy

n = int(input())

blist = list(map(str, input().split()))
slist = copy.deepcopy(blist)

cnt = 0

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


for i in range(n):
    minj = i
    for j in range(i, n):
        if slist[j][1] < slist[minj][1]:
            minj = j
    if i != minj:
        cnt += 1
        slist[i], slist[minj] = slist[minj], slist[i]

for i in range(n):
    if i == n-1:
        print(blist[i])
    else:
        print(blist[i] + " ", end="")

print("Stable")

for i in range(n):
    if i == n-1:
        print(slist[i])
    else:
        print(slist[i] + " ", end="")

for b, s, in zip(blist, slist):
    if b != s:
        print("Not stable")
        exit()

print("Stable")



# Example run
# Input:
-236387597
W1}iQ@j
# Output:
Stable
Stable
N = int(input())
C1 = list(input().split()) 
C2 = C1[:]

def get_card_suit(card):
    return card[:1]

def get_card_value(card):
    return card[1:]

def bubble_sort(card):
    r_exists = True

    while r_exists == True:

        r_exists = False

        i = N - 1

        while i >= 1:

            if get_card_value(card[i]) < get_card_value(card[i - 1]):
                
                card[i], card[i - 1] = card[i - 1], card[i]

                r_exists = True
            
            i -= 1

def select_sort(card):
    i = 0

    while i < N:

        min_j = i
        j = i

        while j < N:

            if get_card_value(card[j]) < get_card_value(card[min_j]):

                min_j = j

            j += 1

        card[i], card[min_j] = card[min_j], card[i]

        i += 1

def output(card):
    s = ''

    for x in card:

        s = s + str(x) + ' '

    print(s.rstrip())

def is_stable():
    i = 0

    while i < N:
        if get_card_suit(C1[i]) != get_card_suit(C2[i]):
            return False
        i += 1
    
    return True

bubble_sort(C1)
select_sort(C2)

output(C1)
print('Stable')

output(C2)
if is_stable() == True:
    print('Stable')
else:
    print('Not Stable')



# Example run
# Input:
0
&k7$an8
# Output:
&k7$an8
Stable
&k7$an8
Stable
def bubbleSort(c):
    for i in range(len(c)):
        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]
    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


n = int(input())
b = input().split()
s = b[:]

b = bubbleSort(b)
s = selectionSort(s)

print(*b)
print('Stable')
print(*s)
print('Stable' if b == s else 'Not stable')



# Example run
# Input:
107
m;+CP)0C
# Output:
m;+CP)0C
Stable
m;+CP)0C
Stable
n = int(input())
bLst = input().split()
iLst = bLst

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

print(*bLst)
print("Stable")

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

print(*iLst)
if bLst == iLst:
    print("Stable");
else:
    print("Not stable")


# Example run
# Input:
1
!dTK>W{jT
# Output:
!dTK>W{jT
Stable
!dTK>W{jT
Stable
def buble_sort(seq):
    l = len(seq)
    res = seq[:]
    for i in range(l):
        for j in range(i+1, l)[::-1]:
            if res[j][-1] < res[j-1][-1]:
                res[j], res[j-1] = res[j-1], res[j]
    return res


def selection_sort(seq):
    l = len(seq)
    res = seq[:]
    for i in range(l):
        mi = i
        for j in range(i, l):
            if res[j][-1] < res[mi][-1]:
                mi = j
        if i is not mi:
            res[i], res[mi] = res[mi], res[i]
    return res


def is_stable(seq, sorted_seq):
    card_dic = {s[-1]: [] for s in set(seq)}
    for s in seq:
        key = s[-1]
        card_dic[key].append(s[0])

    for ss in sorted_seq:
        key = ss[-1]
        val = card_dic[key].pop(0)
        if not val == ss[0]:
            return False
    return True


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

b_sorted = buble_sort(C)
print(' '.join(b_sorted))
print('Stable' if is_stable(C, b_sorted) else 'Not stable')

s_sorted = selection_sort(C)
print(' '.join(s_sorted))
print('Stable' if is_stable(C, s_sorted) else 'Not stable')

# Example run
# Input:
13499019
\@LU%V
# Output:
\@LU%V
Stable
\@LU%V
Stable
n=int(input())
A=input().split()
B=A[::]

flag=1
while flag:
  flag=0
  for i in range(n-1,0,-1):
    if int(A[i-1][1])>int(A[i][1]):
      A[i-1],A[i]=A[i],A[i-1]
      flag=1
print(*A)
print("Stable")

for i in range(n-1):
  minj=i
  for j in range(i,n):
    if int(B[minj][1])>int(B[j][1]):
      minj=j
  if minj!=i:
    B[i],B[minj]=B[minj],B[i]
print(*B)
if A==B:
  print("Stable")
else:
  print("Not stable")


# Example run
# Input:
-9225256
kQ@YZ@p
# Output:
kQ@YZ@p
Stable
kQ@YZ@p
Stable
def Bubble_Sort(C1, N):
    for i in range(N):
        for j in reversed(range(i+1,N)):
            if C1[j][1] < C1[j-1][1]:
                a = C1[j]
                C1[j] = C1[j-1]
                C1[j-1] = a
    
    return(C1)

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

        a = C2[minj]
        C2[minj] = C2[i]
        C2[i] = a
        #print(C)
    return(C2)

N = int(input())
A1 = list(map(str,input().split()))
A2 = A1.copy()
B1 = Bubble_Sort(A1,N)
B2 = SelectionSort(A2,N)

print(' '.join(map(str, A1)))
print("Stable")
print(' '.join(map(str, A2)))
if A1 == A2:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-16
)jy
# Output:
)jy
Stable
)jy
Stable
n = int(input())
c = input().split()
c = [(int(s[1]), s[0]) for s in c]
d = c.copy()

# BubbleSort
for i in range(0, n):
    for j in [n-k for k in range(1, n-i)]:
        if c[j][0] < c[j-1][0]:
            c[j], c[j-1] = c[j-1], c[j]

ans1 = " ".join([c[i][1] + str(c[i][0]) for i in range(n)])
print(ans1)
print("Stable")

#SelectionSort
for i in range(0, n):
    minj = i
    for j in range(i, n):
        if d[j][0] < d[minj][0]:
            minj = j
    d[i], d[minj] = d[minj], d[i]

ans2 = " ".join([d[i][1] + str(d[i][0]) for i in range(n)])
print(ans2)
if ans2 == ans1:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-686
15761764
# Output:

Stable

Stable
def BubbleSort(C_B, N):
    for i in range(N):
        for j in range(N-1,i,-1):
            if int(C_B[j][1]) < int(C_B[j-1][1]) :
                C_B[j], C_B[j-1] = C_B[j-1], C_B[j]
    return C_B

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

def J(C, C_):
    for i in range(1,len(C_)):
        if int(C_[i-1][1]) == int(C_[i][1]):
            p = C.index(C_[i-1])
            q = C.index(C_[i])
            if q<p:
                return 'Not stable'
    return 'Stable'

N = int(input())
C = list(input().split())
C_B = C.copy()
C_S = C.copy()
CB = BubbleSort(C_B, N)
CS = SelectionSort(C_S, N)

for i in range(len(CB)):
    if i==len(CB)-1:
        print(CB[i])
    else:
        print(CB[i],end=' ')
print(J(C, CB))
for i in range(len(CS)):
    if i==len(CS)-1:
        print(CS[i])
    else:
        print(CS[i],end=' ')
print(J(C, CS))


# Example run
# Input:
-7581
,@oF:Y
# Output:
,@oF:Y
Stable
,@oF:Y
Stable
from typing import List


class Trump:
	def __init__(self, value, suit):
		self.value = value
		self.suit = suit

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


def bubble(C: List[Trump], N: int) -> None:
	for i in range(N):
		for j in range(N-1, i, -1):
			if C[j].value < C[j-1].value:
				C[j], C[j-1] = C[j-1], C[j]
	print(*C)


def selection(C: List[Trump], N: int) -> None:
	for i in range(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]
	print(*C)


if __name__ == "__main__":
	N = int(input())
	C1 = []
	for c in input().split():
		C1.append(Trump(int(c[1]), c[0]))
	C2 = C1.copy()

	bubble(C1, N)
	print("Stable")
	selection(C2, N)
	if C1 == C2:
		print("Stable")
	else:
		print("Not stable")


# Example run
# Input:
-15303
-412794
# Output:
-4
Stable
-4
Stable
import copy

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]:
                x = c[j]
                c[j] = c[j-1]
                c[j-1] = x
    return c

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
        x = c[i]
        c[i] = c[minj]
        c[minj] = x
    return c

n = int(input())
c = list(map(str, input().split()))
c1 = copy.deepcopy(c)
c2 = copy.deepcopy(c)

c1 = BubbleSort(c1, n)
print(*c1)
print('Stable')

c2 = SelectionSort(c2, n)
print(*c2)
if c1 == c2:
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
-37
vY;
# Output:
vY;
Stable
vY;
Stable