Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
def isStable(before_sort, after_sort):
    num = len(before_sort)
    
    for i in range(0, num-1):
        for j in range(i+1, num):
            for a in range(0, num-1):
                for b in range(a+1, num):
                    if before_sort[i][1] == after_sort[j][1] and \
                       before_sort[i] == after_sort[b] and \
                       before_sort[j] == after_sort[a]:
                        print("i=%d / j=%d / a=%d / b=%d /before=%s / after=%s" % \
                            (i, j, a, b, before_sort[i][1],  after_sort[j][1]))
                        return False
    return True

def isStable2(sorted_data, bubble_sort_data):
    for i in range(0, len(sorted_data)):
        if sorted_data[i] != bubble_sort_data[i]:
            return False
    return True
    
def BubbleSort(c, n):
    for i in range(0, n):
        for j in range(n-1, i, -1):
            if int(c[j][1]) < int(c[j-1][1]):
                c[j], c[j-1] = c[j-1], c[j]

def SelectionSort(c, n):
    for i in range(0, n):
        minj = i
        for j in range(i, n):
            if int(c[j][1]) < int(c[minj][1]):
                minj = j
        c[i], c[minj] = c[minj], c[i]
    
num = int(input())
data = input().split(' ')

copy_data = data.copy()
BubbleSort(copy_data, num)
print(copy_data)
if isStable(copy_data, copy_data):
    print("Stable")
else:
    print("Not stable")

bubble_sort_data = data.copy()
SelectionSort(bubble_sort_data, num)
print(bubble_sort_data)
if isStable(bubble_sort_data, copy_data):
    print("Stable")
else:
    print("Not stable")

# Example run
# Input:
-1309
jtN_
# Output:
['jtN_']
Stable
['jtN_']
Stable
import copy

def bubble_sort(data_bubble):
    for i in range(len(data_bubble)):
        for j in range(len(data_bubble)-1, i, -1):
            if data_bubble[j][1] < data_bubble[j-1][1]:
                data_bubble[j], data_bubble[j-1] = data_bubble[j-1], data_bubble[j]
    return data_bubble


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


def set_list(data):
    base_list = [[], [], [], [], [], [], [], [], []]
    for elem in data:
        base_list[int(elem[1]) - 1].append(elem)
    return base_list


def is_stable(base, compare):
    base_list = set_list(base)
    compare_list = set_list(compare)
    for i, num in enumerate(base_list):
        for j, key in enumerate(num):
            if key != compare_list[i][j]:
                return 'Not stable'
    return 'Stable'


_ = int(input())
data = list(input().split())
bubble_list = copy.copy(data)
bubble_list = bubble_sort(bubble_list)
print(*bubble_list)
print(is_stable(data, bubble_list))
selection_list = copy.copy(data)
selection_list = selection_sort(selection_list)
print(*selection_list)
print(is_stable(data, selection_list))



# Example run
# Input:
-5
-14993
# Output:
-14993
Stable
-14993
Stable
class Card():

    def bubble_sort(self):
        bubble_card = [i for i in self]
        for i in range(len(bubble_card)):
            for j in range(len(self)-1, i, -1):
                if bubble_card[j].strip('SHCD') < bubble_card[j-1].strip('SHCD'):
                    bubble_card[j], bubble_card[j-1] = bubble_card[j-1], bubble_card[j]
        return bubble_card


    def selection_sort(self):
        select_card = [i for i in self]
        for i in range(len(select_card)):
            minj = i
            change = False
            for j in range(i + 1, len(select_card)):
                if select_card[minj].strip('SHCD') > select_card[j].strip('SHCD'):
                    minj = j
                    change = True
            if change:
                select_card[i], select_card[minj] = select_card[minj], select_card[i]
        return select_card


    def stable_sort(self):
        sort_card = [i for i in self]
        sort = []
        for i in range(len(sort_card)-1):
            min = i
            for j in range(i+1, len(sort_card)):
                if int(sort_card[min].strip('SHCD')) > int(sort_card[j].strip('SHCD')):
                    min = j
            min_card = sort_card[min]
            sort_card.pop(min)
            sort_card.insert(i,min_card)
        sort = sort_card
        return sort





def main():
    n = int(input())
    cards = [i for i in input().split()]
    bubble = Card.bubble_sort(cards)
    select = Card.selection_sort(cards)
    stable = Card.stable_sort(cards)

    for i in range(len(bubble)):
        print(bubble[i]) if i == len(bubble)-1 else print(str(bubble[i])+' ',end='')
    print('Stable') if bubble == stable else print('Not stable')

    for i in range(len(select)):
        print(select[i]) if i == len(select)-1 else print(str(select[i])+' ',end='')
    print('Stable') if select == stable else print('Not stable')


if __name__ == '__main__':
    main()

# Example run
# Input:
-210
ma;M
# Output:
ma;M
Stable
ma;M
Stable
def bubble_sort(r, n):
    flag = True  # ??£??\????´?????????¨????????°
    while flag:
        flag = False
        for i in range(n - 1, 0, -1):
            if r[i - 1][1] > r[i][1]:
                r[i - 1], r[i] = r[i], r[i - 1]
                flag = True
    return r


def select_sort(r, n):
    for i in range(0, n):
        minj = i
        for j in range(i, n):
            if r[j][1] < r[minj][1]:
                minj = j
        if i != minj:
            r[i], r[minj] = r[minj], r[i]
    return r


def stable_sort(r, sort_r):
    for i in range(len(r)):
        for j in range(i + 1, len(r)):
            for a in range(len(sort_r)):
                for b in range(a + 1, len(sort_r)):
                    if r[i][1] == r[j][1] and r[i] == sort_r[b] and r[j] == sort_r[a]:
                         return "Not Stable"

    return "Stable"


N = int(input())
R = list(input().split())
C = R[:]
BS_R = bubble_sort(R, N)
SS_R = select_sort(C, N)
print(*BS_R)
print(stable_sort(R, BS_R))
print(*SS_R)
print(stable_sort(R, SS_R))

# Example run
# Input:
-3
BUOC
# Output:
BUOC
Stable
BUOC
Stable
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:
-368743555
~iIDHWq%Z
# Output:
~iIDHWq%Z
Stable
~iIDHWq%Z
Stable
a = int(input())
b = list(map(str, input().split()))
# print(b)

# print(b[1][1])
# print(type(int(b[1][1])))

# for k in range(len(b)):
#     c.append(b[k][1])
# print(c)

c = b[:] #リストで参照渡しをせずに、値のみを渡す方法。
d = b[:]

# print(id(b))
# print(id(c))
# print(id(d))

def BubleSort(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 isStable(In, Out):
    for m in range(0,len(Out)):
        for n in range(m+1,len(Out)):
            for x in range(0,len(Out)):
                for y in range(x+1,len(Out)):
                    if int(In[m][1])==int(In[n][1]) and In[m] == Out[y] and In[n] == Out[x]:
                        return print('Not stable')
    return print('Stable')

def SelectSort(d):
    for i in range(len(d)-1):
        mini = i
        for j in range(i+1,len(d)):
            if int(d[mini][1])>int(d[j][1]):
                mini=j
        if int(d[mini][1])!=int(d[i][1]):
            d[i],d[mini]=d[mini],d[i]
    return d


print(*BubleSort(c))
isStable(c,b)
# print(d)
# print(b)
print(*SelectSort(d))
isStable(d,b)


# Example run
# Input:
33
YQoc
# Output:
YQoc
Stable
YQoc
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:
-293149433
RH#y0
# Output:

Stable

Stable
#アルゴリズム：バブルソート
def BubbleSort(list, number):
    for i in range(0, number):
        for j in range(number-1, i, -1):
            if int(list[j][-1]) < int(list[j-1][-1]):
                list[j], list[j-1] = list[j-1], list[j]
    return list
    
#アルゴリズム：挿入ソート
def SelectionSort(list, number):
    for i in range(0, number):
        min_number = i
        for j in range(i, number):
            if int(list[min_number][-1]) > int(list[j][-1]):
                min_number = j
        list[i], list[min_number] = list[min_number], list[i]
    return list

#安定な出力か判定
def StableProcessing(list_A, list_B):
    if list_A == list_B:
        return "Stable"
    else:
        return "Not stable"


#初期data
input_number = int(input())
input_list_B = list(map(str, input().split()))
input_list_S = list(input_list_B)

#処理の実行
input_list_B = BubbleSort(input_list_B, input_number)
print(" ".join(input_list_B))
print("Stable")
input_list_S = SelectionSort(input_list_S, input_number)
print(" ".join(input_list_S))
print(StableProcessing(input_list_B, input_list_S))



# Example run
# Input:
-87
>x#!w6b>
# Output:
>x#!w6b>
Stable
>x#!w6b>
Stable
n = int(input())
a = list(input().split())
b = list(a)

#bub sort
flag = True
while flag:
  flag = False
  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]
      flag = True
print(" ".join(a))
def stable(b,a):
  for i in range(n):
    for j in range(i+1,n):
      if b[i][1] == b[j][1]:#i<j
        for k in range(n):
          for l in range(k+1,n):
            if a[k] == b[j] and a[l] == b[i]:
              print("Not stable")
              return
  print("Stable")
stable(b,a)
a = list(b)
#sel sort
for i in range(n):
    min_i = i
    for j in range(i+1,n):
        if a[j][1] < a[min_i][1]:
            min_i = j
    if i!= min_i:
        a[i],a[min_i]=a[min_i],a[i]
print(" ".join(map(str,a)))
stable(b,a)


# Example run
# Input:
-208107
rx[akum)
# Output:
rx[akum)
Stable
rx[akum)
Stable
def bubble_sort(c, n):
    for i in range(n):
        for j in range(n-1 , i, -1):
            if int(c[j][1:]) < int(c[j-1][1:]):
                c[j],c[j-1] = c[j-1],c[j]
    return c

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

import copy
n = int(input())
c = input().split()
bc = bubble_sort(copy.deepcopy(c), n)
sc = selection_sort(copy.deepcopy(c), n)
print(*bc)
print("Stable")
print(*sc)
print("Stable" if sc == bc else "Not stable")


# Example run
# Input:
-877447
Q_"A[
# Output:
Q_"A[
Stable
Q_"A[
Stable
n=int(input())
ss=[x for x in input().split()]     
ss2=ss.copy()

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]
#                 print(C, i, 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[minj], C[i] = C[i], C[minj]
    return C

ss = BubbleSort(ss, len(ss))
ss2 = SelectionSort(ss2, len(ss2))
output = [[str(t) for t in row ] for row in ss]
print(" ".join([ "".join(row) for row in output]))
print('Stable')
output = [[str(t) for t in row ] for row in ss2]
print(" ".join([ "".join(row) for row in output]))
if(ss == ss2):
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
-2
8]uPf+v
# Output:
8]uPf+v
Stable
8]uPf+v
Stable
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def SelectionSort(aa,n):
    for i in range(n):
        min_j=i
        for j in range(i+1,n):
            if int(aa[j][1])<int(aa[min_j][1]):min_j=j
        if min_j!=i:
            aa[i],aa[min_j]=aa[min_j],aa[i]
    return aa

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

def main():
    n = int(input())
    #aa = list(map(int, input().split()))
    aa=input().split()
    atoi={}
    for i,a in enumerate(aa):
        atoi[a]=i

    sorted_aa=BubbleSort(aa[:],n)
    stable=True
    for a0,a1 in zip(sorted_aa,sorted_aa[1:]):
        if a0[1]==a1[1] and atoi[a0]>atoi[a1]:
            stable=False
    print(*sorted_aa)
    print("Stable") if stable else print("Not stable")

    sorted_aa=SelectionSort(aa[:],n)
    stable=True
    for a0,a1 in zip(sorted_aa,sorted_aa[1:]):
        if a0[1]==a1[1] and atoi[a0]>atoi[a1]:
            stable=False
    print(*sorted_aa)
    print("Stable") if stable else print("Not stable")

main()



# Example run
# Input:
-74186
oBtKmC1{'
# Output:
oBtKmC1{'
Stable
oBtKmC1{'
Stable
class Card(object):
    def __init__(self, card):
        self._suit = card[0]
        self._value = int(card[1])

    def __eq__(self, other):
        if other is None:
            return False
        return self.__dict__ == other.__dict__

    def getValue(self):
        return self._value

    def toString(self):
        return self._suit + str(self._value)


def card_bubbleSort(lst, n):
    for i in range(0, n):
        for j in range(n-1, i, -1):
            if lst[j].getValue() < lst[j-1].getValue():
                tmp = lst[j]
                lst[j] = lst[j-1]
                lst[j-1] = tmp

    return lst


def card_selectionSort(lst, n):
    for i in range(0, n):
        minj = i
        for j in range(i, n):
            if lst[j].getValue() < lst[minj].getValue():
                minj = j

        if i != minj:
            tmp = lst[i]
            lst[i] = lst[minj]
            lst[minj] = tmp

    return lst


def isStable(in_lst, out_lst, n):
    for i in range(0, n):
        for j in range(i+1, n):
            for a in range(0, n):
                for b in range(a+1, n):
                    if in_lst[i].getValue() == in_lst[j].getValue() \
                            and in_lst[i] == out_lst[b] \
                            and in_lst[j] == out_lst[a]:
                                return False
    return True


if __name__ == "__main__":
    n = int(input())
    lst = input().split()
    func_table = [card_bubbleSort, card_selectionSort]
    for func in func_table:
        cards = [Card(item) for item in lst]
        result = func(cards, n)
        cards = [Card(item) for item in lst]
        print(" ".join([card.toString() for card in result]))
        if isStable(cards, result, n):
            print("Stable")
        else:
            print("Not Stable")

# Example run
# Input:
-87
141725276
# Output:
14
Stable
14
Stable
n = int(input())
a = input().split()
b = a[:]
flag = 1
while flag:
    flag = 0
    for i in range(n-1):
        if a[i][1] > a[i+1][1]:
            a[i], a[i+1] = a[i+1], a[i]
            flag = 1
print(*a)
print("Stable")

for i in range(n-1):
    min_j = i
    for j in range(i,n):
        if b[j][1] < b[min_j][1]:
            min_j = j
    b[i], b[min_j] = b[min_j], b[i]
print(*b)
if a == b:
    print("Stable")
else:
    print("Not stable")

# Example run
# Input:
-997466
VdH
# Output:
VdH
Stable
VdH
Stable
#バブルソート
def BubbleSort(C,N):
    for i in range (0,N,1):
        for j in range(N-1,i-1,-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))
        
#安定かどうかの判定
def isStable(inp, out,N):
    for i in range(0,N):
        for j in range(i+1,N):
            for a in range(0,N):
                for b in range(a+1,N):
#                     print("inp(i,j):",inp[i],inp[j],"out(b,a):",out[b],out[a]+"\n")
                    if int(inp[i][1]) == int(inp[j][1]) and inp[i] == out[b] and inp[j] == out[a]:
                        print('Not stable')
                        return
    print('Stable')



#愚直に調べるパターン
N = int(input())
A = list(input().split())
Bubble_A = A.copy()
Selection_A = A.copy()

BubbleSort(Bubble_A,N)
isStable(A,Bubble_A,N)
SelectionSort(Selection_A,N)
isStable(A,Selection_A,N)


# Example run
# Input:
-99110661
g5DK5J
# Output:
g5DK5J
Stable
g5DK5J
Stable
def BubbleSort(C,N):
    count = 0
    for i in range(N):
        j = N-1
        while True:
            if j == 0:
                break
            a,b = list(C[j]),list(C[j-1])
            if a[1] < b[1]:
                tmp = C[j-1]
                C[j-1] = C[j]
                C[j] = tmp
                count += 1
            j -= 1
    return C,count

def SelectionSort(D,N):
    count = 0
    for i in range(N):
        minj = i
        for j in range(i,N):
            a,b = list(D[j]),list(D[minj])
            if a[1] < b[1]:
                minj = j
                count += 1
        tmp = D[i]
        D[i] = D[minj]
        D[minj] = tmp
    return D,count

n = int(input())
d = input().split()
d2 = list(d)
d,c = BubbleSort(d,n)
for i in range(len(d)-1):
    print(d[i],end = ' ')
print(d[-1])
print('Stable')
d2,c_s = SelectionSort(d2,n)
for i in range(len(d2)-1):
    print(d2[i],end = ' ')
print(d2[-1])
if c_s == c:
    print('Stalbe')
else:
    print('Not stable')

# Example run
# Input:
0
d]lv%m)k
# Output:
d]lv%m)k
Stable
d]lv%m)k
Stalbe
# 配列の宣言
A = []
B = []

# 文字列の取得と加工
LENGTH =int(input())
A = input().split()
B = A.copy()

def bubble (A, LENGTH):
    N = 0
    M = LENGTH - 1
    CHANGE = 0

    while N <= LENGTH -1:
        M = LENGTH - 1
        while M >= N + 1:
            if int(A[M][1:]) < int(A[M-1][1:]):
                tmp = A[M-1]
                A[M-1] = A[M]
                A[M] = tmp
                CHANGE += 1
            M -= 1
        N += 1

    print(" ".join(map(str,A)))
    print("Stable")

def selection (B, LENGTH):
    i = 0
    CHANGE_COUNT = 0

    while i <= LENGTH -1:
        j = i + 1
        mini = i
        while j <= LENGTH -1:
            if int(B[j][1:]) < int(B[mini][1:]):
                mini = j
            j += 1
        if mini != i:
            tmp = B[i]
            B[i] = B[mini]
            B[mini] = tmp
            CHANGE_COUNT += 1
        i += 1

    print(" ".join(map(str,B)))
    if A == B:
        print("Stable")
    else:
        print("Not stable")

bubble (A, LENGTH)
selection (B, LENGTH)


# Example run
# Input:
-16371
)c6@(1
# Output:
)c6@(1
Stable
)c6@(1
Stable
N = int(input())
str_input = list(input().split())
T1 = [(S[0],int(S[1])) for S in str_input]
T2 = [(S[0],int(S[1])) for S in str_input]

def bubble_sort(N,T):
    for i in range(N):
        flag = True
        while flag:
            flag = False
            for j in range(N-1, i, -1):
                if T[j][1] < T[j-1][1]:
                    tmp = T[j]
                    T[j] = T[j-1]
                    T[j-1] = tmp
                    flag = True
    return T

def selection_sort(N,T):
    for i in range(N):
        min_index = i
        for j in range(i, N):
            if (T[j][1] < T[min_index][1]):
                min_index = j
        if (min_index != i):
            tmp = T[i]
            T[i] = T[min_index]
            T[min_index] = tmp
    return T

def is_stable(bT, sT):
    for i, st in enumerate(sT):
        if(st[0] != bT[i][0]):
            return False
    return True

def print_trump(T):
    strT = ['{}{}'.format(t[0],t[1]) for t in T]
    print(str(strT).replace(',','').replace('[','').replace(']','').replace("'",''))
    
bT = bubble_sort(N, T1)
sT = selection_sort(N, T2)
print_trump(bT)
print('Stable')
print_trump(sT)
stability = 'Stable' if is_stable(bT,sT) else 'Not stable'
print(stability)


# Example run
# Input:
-1018584
-247
# Output:
-2
Stable
-2
Stable
def select(S):
    for i in range(0, n):
        minj = i
        for j in range(i, n):
            if int(S[j][1]) < int(S[minj][1]):
                minj = j
        (S[i], S[minj]) = (S[minj], S[i])
    return S

def bubble(B):
    flag = True
    while flag:
        flag = False
        for j in reversed(range(1, n)):
            if int(B[j][1]) < int(B[j-1][1]):
                (B[j-1], B[j]) = (B[j], B[j-1])
                flag = True
    return B

def isStable(inA, out):
    for i in range(0, n):
        for j in range(i+1, n):
            for a in range(0, n):
                for b in range(a+1, n):
                    if inA[i][1] == inA[j][1] and inA[i] == out[b] and inA[j] == out[a]:
                        return "Not stable"
    return "Stable"



n = int(input())
A = input().split(' ')

B = bubble(A[:])
print(" ".join(B))
print(isStable(A, B))
S = select(A[:])
print(" ".join(S))
print(isStable(A, S))

# Example run
# Input:
-21
Q!*u_Y?|
# Output:
Q!*u_Y?|
Stable
Q!*u_Y?|
Stable
class Card:
    def __init__(self, info):
        self.suit = info[0]
        self.number = info[1]
    
    def getSuit(self):
        return self.suit
    
    def getNumber(self):
        return self.number
    
    def __repr__(self):
        return self.suit + str(self.number)
    
def isSameCard(card1, card2):
    return card1.getNumber() == card2.getNumber() and card1.getSuit() == card2.getSuit()

def bubbleSort(Ain, N):
    for i in range(0,N):
        for j in range(N-1, i, -1):
            if Ain[j].getNumber() < Ain[j-1].getNumber():
                temp = Ain[j]
                Ain[j] = Ain[j-1]
                Ain[j-1] = temp

def selectionSort(Ain, N):
    for i in range(0,N):    # iは最小のカードが入る場所
        minj = i
        for j in range(i+1,N):   # jは最小候補カードのインデックス
            if Ain[j].getNumber() < Ain[minj].getNumber():
                minj = j
        temp = Ain[i]
        Ain[i] = Ain[minj]
        Ain[minj] = temp

def printCards(Ain, N):
    for i in range(N-1):
        print(str(Ain[i]) + " ", end="")
    print(str(Ain[N-1]))

N = int(input())
Ain = [Card(info) for info in input().split()]
Ab = [i for i in Ain]
As = [i for i in Ain]
bubbleSort(Ab, N)
selectionSort(As, N)
printCards(Ab, N)
print("Stable")
printCards(As, N)
for i in range(0,N):
    if not isSameCard(Ab[i], As[i]):
        print("Not stable")
        break
    elif i != N-1:
        continue
    print("Stable")



# Example run
# Input:
1
!rJx
# Output:
!r
Stable
!r
Stable
n=int(input())
cards=input().split()
cards2=cards[:]
flag=1
while flag:
  flag=0
  for i in range(n-1,0,-1):
    if cards[i][1] < cards[i-1][1]:
      cards[i], cards[i-1]=cards[i-1],cards[i]
      flag=1
print(" ".join(cards))
print("Stable")

for i in range(n):
  minj = i
  for j in range(i,n):
    if cards2[j][1] < cards2[minj][1]:
      minj = j
  if i != minj:
    cards2[i], cards2[minj]=cards2[minj],cards2[i]
print(" ".join(cards2))
if cards == cards2:
  print("Stable")
else:
  print("Not stable")


# Example run
# Input:
1
(k9UI.C>
# Output:
(k9UI.C>
Stable
(k9UI.C>
Stable