Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
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]
    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)

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


# Example run
# Input:
1
eR-D}_=3
# Output:
eR-D}_=3
Stable
eR-D}_=3
Stable
n = int(input())
card1 = list(input().split())
card2 = [i for i in card1]
def bubbleSort(c1:list, n:int):
    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]
    return c1

def selectionSort(c2:list, n:int):
    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]
    return c2

bubblesort = bubbleSort(card1, n)
selectionsort = selectionSort(card2, n)

flag = 0
for i in range(n):
    if bubblesort[i] != selectionsort[i]:
        flag = 1

print(" ".join(bubblesort))
print("Stable")
print(" ".join(selectionsort))
if flag:
    print("Not stable")
else:
    print("Stable")



# Example run
# Input:
0
8\G<E[
# Output:
8\G<E[
Stable
8\G<E[
Stable
n = int(input())
R = [x for x in input().split()]#リスト内包表記
R2=R.copy()

def selected_sort(a,n):
    for i in range(0,n-1):#一個前までやれば全てソートが完了する
        minj=i#未ソート部の先頭をminとみなす
        for j in range(i,n):
            if a[j][1]<a[minj][1]:#
                minj=j#最小インデックスの更新
                judge=True#インデックスが更新されたかどうかの判定
        a[i],a[minj]=a[minj],a[i]#最小値と未ソートの先頭をswap
    print(*a)

def bubble_sort(r,n):
    flag=True
    i=0
    count=0
    while flag:
        flag=False
        for i in range(n-1,i,-1):#iは1でとまらないとi-1が-1となってしまう
            if r[i][1]<r[i-1][1]:
                r[i],r[i-1]=r[i-1],r[i]#swap
                count+=1
                flag=True#入れ替える条件があって初めてtrueになる
    print(*r)

def isStable(a,b):
    if R==R2:
        print("Stable")
    else:
        print("Not stable")


bubble_sort(R,n)
print("Stable")

selected_sort(R2,n)
isStable(R,R2)



# Example run
# Input:
-465
c>{cUl
# Output:
c>{cUl
Stable
c>{cUl
Stable
def swap(a, i, j):
    k = a[j]
    a[j] = a[i]
    a[i] = k


def bubbleSort(A, N):
    flag = True
    while flag:
        flag = False
        for j in reversed(range(1, N)):
            if A[j][1] < A[j-1][1]:
                swap(A, j, j-1)
                flag = True


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
        swap(A, i, minj)


N = int(input())
A = list(input().split())
B = A[:]

bubbleSort(A, N)
print(*A)
print("Stable")
selectionSort(B, N)
print(*B)
if A == B:
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
0
Ssm`%X6*v
# Output:
Ssm`%X6*v
Stable
Ssm`%X6*v
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(' '.join(b))
print(stable(c, b))
print(' '.join(s))
print(stable(c, s))



# Example run
# Input:
-22914821
cLg*7.
# Output:
cLg*7.
Stable
cLg*7.
Stable
import sys
import math
import bisect
import copy
sys.setrecursionlimit(1000000)
from collections import deque

def bubble(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(a,n):
    for i in range(n):
        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]

def main():
    n = int(input())
    a = list(input().split())
    b = copy.copy(a)
    bubble(a,n)
    selection(b,n)
    print (' '.join(a))
    print ('Stable')
    print (' '.join(b))
    if a==b:print ('Stable')
    else   :print ('Not stable')



if __name__ == '__main__':
    main()




# Example run
# Input:
-11329
og5S
# Output:
og5S
Stable
og5S
Stable
import copy
N = int(input())
A = input().split()
B = copy.copy(A)
boo = 1
while boo:
    boo = 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]
            boo = 1
print(*A)
print("Stable")
for i in range(N-1):
    mi = i
    for j in range(i,N):
        if B[i][1] > B[j][1]:
            mi = j
    B[i], B[mi] = B[mi], B[i]
if A==B:
    print(*B)
    print("Stable")
else:
    print(*B)
    print("Not stable")



# Example run
# Input:
-3391654
Xg<'3O.+[
# Output:
Xg<'3O.+[
Stable
Xg<'3O.+[
Stable
import copy


def BubbleSort(C, n):
    flag = 1
    while flag:
        flag = 0
        for i in range(n-1, 0, -1):
            if int(C[i][1]) < int(C[i - 1][1]):
                C[i], C[i-1] = C[i-1], C[i]
                flag = 1
    return C


def SelectionSort(C, n):
    for i in range(n-1):
        minj = i
        for j in range(i, n):
            if int(C[j][1]) < int(C[minj][1]):
                minj = j
        if minj != i:
            C[i], C[minj] = C[minj], C[i]
    return C


n = int(input())
C = list(input().split())
C2 = C.copy()

print(*BubbleSort(C, n), sep=' ')
print("Stable")
print(*SelectionSort(C2, n), sep=' ')
if C ==C2:
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
-121
OLH
# Output:
OLH
Stable
OLH
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 BubbleSort(C,N):
    flag = 1
    while flag:
        flag = 0
        for j in range(N-1,0,-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
                flag = 1
    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:
-3
M]::5
# Output:
M]::5
Stable
M]::5
Stable
def is_stable(bubble, selection, _N):
    for i in range(N):
        if bubble[i][0] != selection[i][0]:
            return False
    return True


def bubble(N_input, A_input):
    count = 0
    flag = 1
    _A = list(A_input)

    while flag:
        flag = 0
        for i in range(N_input-1, 0, -1):
            _A_i = int(_A[i][1])
            _A_i_1 = int(_A[i-1][1])

            if _A_i < _A_i_1:
                _A[i], _A[i-1] = _A[i-1], _A[i]

                flag = 1
                count += 1

    return _A


def selection(inN, inA):
    _A = list(inA)

    for i in range(0, inN-1, 1):
        minj = i
        for j in range(i+1, inN, 1):
            if int(_A[j][1]) < int(_A[minj][1]):
                minj = j
        _A[i], _A[minj] = _A[minj], _A[i]

    return _A


N = int(input())
# A = list(map(int, input().split()))
A = input().split()
# print(N, A)

A_bubble = bubble(N, A)
A_bubble_str = map(str, A_bubble)
print(' '.join(A_bubble_str))
print('Stable')

A_selection = selection(N, A)
A_selection_str = map(str, A_selection)
print(' '.join(A_selection_str))
if is_stable(A_bubble, A_selection, N):
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
-1530217
Jq\y`
# Output:
Jq\y`
Stable
Jq\y`
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:
-3
-2260822
# Output:
-2
Stable
-2
Stable
# Problem - 安定なソート

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

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

def stable_check(check_dic, ans_list):
    is_ok = True
    for a in ans_list:
        v = a[0]
        k = a[1]
        if check_dic[k][0]==v:
            check_dic[k].pop(0)
        else:
            is_ok = False
    return is_ok

# input
N = int(input())
cards = input().split()
check_dic = {}
check_dic_2 = {}
cards_1 = ['']*N
cards_2 = ['']*N
for i in range(N):
    # dictionaly create
    c_list = list(cards[i])
    if not c_list[1] in check_dic:
        check_dic[c_list[1]] = [c_list[0]]
        check_dic_2[c_list[1]] = [c_list[0]]
    else:
        check_dic[c_list[1]].append(c_list[0])
        check_dic_2[c_list[1]].append(c_list[0])
    cards_1[i] = cards[i]
    cards_2[i] = cards[i]

# bubble sort
ans = bubble_sort(cards_1, N)
is_stable = stable_check(check_dic, ans)
print(" ".join(list(map(str, ans))))
if is_stable:
    print("Stable")
else:
    print("Not stable")

# selection sort
ans = selection_sort(cards_2, N)
is_stable = stable_check(check_dic_2, ans)
print(" ".join(list(map(str, ans))))
if is_stable:
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
-77
hwBFf0"Tm
# Output:

Stable

Stable
def bubble(c):
	for i in range(len(c)):
		for j in range(len(c)-1,i,-1):
			if int(c[j][-1]) < int(c[j-1][-1]):
				c[j],c[j-1] = c[j-1],c[j]
	return c

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

n = int(input())
card = list(map(str,input().split()))
card1 = card[:]
bubble(card)
selection(card1)
print(" ".join(map(str,card)))
print("Stable")
print(" ".join(map(str,card1)))
print("Stable") if card==card1 else print("Not stable")

# Example run
# Input:
-30
119
# Output:
119
Stable
119
Stable
def chk_stable(re):
    for i in range(N-1):
        re_chk = list()
        re_chk.append(re[i])
        for j in range(i+1, N):
            if int(re[i][1]) == int(re[j][1]):
                re_chk.append(re[j])
        if len(re_chk) >= 2:
            for j in range(1, len(re_chk)):
                if A.index(re_chk[j]) < A.index(re_chk[j-1]):
                    return 'Not stable'
    return 'Stable'


def bubble():
    b_list = [i for i in A]
    flag = True
    while flag:
        flag = False
        for i in reversed(range(1, N)):
            if int(b_list[i][1]) < int(b_list[i-1][1]):
                tmp = b_list[i]
                b_list[i] = b_list[i-1]
                b_list[i-1] = tmp
                flag = True
    print(' '.join(b_list))
    return chk_stable(b_list)


def selection():
    s_list = [i for i in A]
    for i in range(N):
        min_i = i
        for j in range(i, N):
            if int(s_list[min_i][1]) > int(s_list[j][1]):
                min_i = j
        tmp = s_list[i]
        s_list[i] = s_list[min_i]
        s_list[min_i] = tmp
    print(' '.join(s_list))
    return chk_stable(s_list)


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

print(bubble())
print(selection())



# Example run
# Input:
-1787
,ow5{T
# Output:
,ow5{T
Stable
,ow5{T
Stable
def BubbleSort(A,B,N):
    for i in range(N):
        for j in range(N-1,i,-1):
            if B[j] < B[j-1]:
                A[j],A[j-1]=A[j-1],A[j]
                B[j],B[j-1]=B[j-1],B[j]

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

N = int(input())
A = list(input().split())
A_BubbleSort = A[:]
A_SelectionSort = A[:]
B=[0 for i in range(N)]
for i in range(N):
    B[i] = int(A[i][1])
B_BubbleSort = B[:]
B_SelectionSort = B[:]
BubbleSort(A_BubbleSort,B_BubbleSort,N)
SelectionSort(A_SelectionSort,B_SelectionSort,N)
print(*A_BubbleSort)
print("Stable")
print(*A_SelectionSort)
if A_BubbleSort == A_SelectionSort:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-114
nzXv9U
# Output:
nzXv9U
Stable
nzXv9U
Stable
N = int(input())
A = list(input().split())

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

C1 = BubbleSort(A[:], N)
C2 = SelectionSort(A[:], N)
print(' '.join(map(str,C1)))
print('Stable')
print(' '.join(map(str,C2)))
if C1 == C2:
    print('Stable')
else:
    print('Not stable')



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

bubbleC = C.copy()
selectionC = C.copy()

bubble(bubbleC)
#selection(selectionC)
print(*C)

# Example run
# Input:
-3636
h&KOE@z
# Output:
h&KOE@z
def getInput():
    n = int(input())
    a = [i for i in input().split(" ")]
    return n, a

def getNum(s):
    return int(s[1])

def swap(x, y):
    v = x
    x = y
    y = v
    return x, y

def bubbleSort(n, a):
    cnt = 0
    for j in range(n):
        init = True
        for i in range(n-1, -1, -1):
            if init:
                init = False
                continue
            if getNum(a[i]) > getNum(a[i+1]):
                a[i], a[i+1] = swap(a[i], a[i+1])
                cnt += 1
    print(" ".join([str(i) for i in a]))
    return a

def selectionSort(n, a):
    cnt = 0
    for i in range(n):
        id_min = i
        for j in range(i+1, n):
            if getNum(a[j]) < getNum(a[id_min]):
                id_min = j
        if id_min != i:
            a[i], a[id_min] = swap(a[i], a[id_min])
            cnt += 1
    print(" ".join([str(i) for i in a]))
    return a

def checkStability(n, a_sample, a):
    for i in range(n-1):
        flag1 = False
        flag2 = False
        if getNum(a_sample[i]) == getNum(a_sample[i+1]):
            for j in range(n):
                if a[j] == a_sample[i+1]:
                    flag1 = True
                if a[j] == a_sample[i]:
                    flag2 = True
                if (flag1==True)&(flag2==False):
                    print("Not stable")
                    return
    print("Stable")
    return


from copy import deepcopy
N, A = getInput()
a_bs = bubbleSort(deepcopy(N), deepcopy(A))
checkStability(deepcopy(N), deepcopy(a_bs), deepcopy(A))
a_ss = selectionSort(deepcopy(N), deepcopy(A))
checkStability(deepcopy(N), deepcopy(a_ss), deepcopy(A))



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

def bubble(A, N):
    for i in range(0, N-1):
        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]
    return A

def selction(A, N):
    for i in range(0, 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 = list(map(str, input().split()))

b = copy.copy(a)
c = copy.copy(a)
bubble(b, n)
print(*b)
print("Stable")
selction(c, n)
print(*c)
if c == b:
    print("Stable")
else:
    print("Not stable")


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

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

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



# Example run
# Input:
-1
eXf?
# Output:
eXf?
stable
eXf?
stable
#coding:UTF-8
def BS(N,A):
    for i in range(N):
        for j in reversed(range(i+1,N)):
            if int(A[j][1:])<int(A[j-1][1:]):
                swap=A[j]
                A[j]=A[j-1]
                A[j-1]=swap
    return A

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

def Stable(A1,A2):
    ans="Stable"
    for i in range(len(A1)):
        if A1[i][1:]==A2[i][1:] and A1[i][:1]!=A2[i][:1]:
            ans="Not stable"
    return ans

def SS2(N,A,B):
    print(A,B)
    A1=BS(N,A)
    print(" ".join(A1))
    print("Stable")
    A2=SS(N,B)
    print(" ".join(A2))
    print(Stable(A1,A2))

if __name__=="__main__":
    N=int(input())
    a=input()
    A=a.split(" ")
    B=a.split(" ")
    SS2(N,A,B)

# Example run
# Input:
-887629
AuCf6uR><
# Output:
['AuCf6uR><'] ['AuCf6uR><']
AuCf6uR><
Stable
AuCf6uR><
Stable
N = int(input())
A = []
for card in input().split():
    A.append([card[0], int(card[1])])
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-1], A[j] = A[j], A[j-1]
A = " ".join([i + str(j) for i, j in A])
print(A)   
print("Stable")
for i in range(N-1):
    minj = i
    for j in range(i, N):
        if B[minj][1] > B[j][1]:
            minj = j
    B[i], B[minj] = B[minj], B[i]
B = " ".join([i + str(j) for i, j in B])
print(B)

if B == A:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-28797
607509343
# Output:
60
Stable
60
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:
-879
Ju,Rn\\
# Output:
Ju,Rn\\
Stable
Ju,Rn\\
Stable
import copy

def BubbleSort(card):
    card_b = []
    card_b = copy.deepcopy(card)
    for i in range(len(card_b)-1):
        j = len(card_b)-1
        while i+1 <= j:
            if list(card_b[j])[1] < list(card_b[j-1])[1]:
                w = card_b[j]
                card_b[j] = card_b[j-1]
                card_b[j-1] = w
            j -= 1
    return card_b

def SelectionSort(card):
    card_s = []
    card_s = copy.deepcopy(card)
    for i in range(len(card_s)-1):
        mini = i
        j = i
        while len(card_s)-1 >= j:
            if list(card_s[j])[1] < list(card_s[mini])[1]:
                mini = j
            j += 1
        w = card_s[i]
        card_s[i] = card_s[mini]
        card_s[mini] = w
    return card_s

def CardPrint(card):
    i = 0
    for c in card:
        if i != n-1:
            print("{} ".format(c), end="")
        elif i == n-1:
            print(c)
        i += 1


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

r1 = []
r1 = BubbleSort(card)
CardPrint(r1)
print("Stable")

r2 = []
r2 = SelectionSort(card)
CardPrint(r2)
if r1 == r2:
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
-1018584
C^/f+5I'
# Output:
C^/f+5I' Stable
C^/f+5I' Stable