Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
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:
19276688
0
# Output:
0
Stable
0
Stable
n = int(input())
a1 = input().split()
a2 = a1[:]
i = 0
flag = 1
while flag:
    flag = 0
    for j in range(n - 1, i, -1):
        if int(a1[j][1]) < int(a1[j - 1][1]):
            flag = 1
            a1[j], a1[j - 1] = a1[j - 1], a1[j]
    i += 1
print(" ".join(a1))
print("Stable")


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


# Example run
# Input:
-408326
5PUt(r7h
# Output:
5PUt(r7h
Stable
5PUt(r7h
Stable
class card(object):
    def __init__(self, str):
        self.symbol = str[0]
        self.num = int(str[1:])
    
    def __lt__(self,obj):
        if(self.num < obj.num):
            return True
        else:
            return False
    def __gt__(self,obj):
        if(self.num > obj.num):
            return True
        else:
            return False

    def display_card(self):
        print("{0}{1}".format(self.symbol,self.num),end="")

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

bub = list(org)
sel = list(org)

cnt = 0
#####################################
"""
Bubble sort(bub[])
"""
for i in range(0,len(bub)):
    for j in range(len(bub)-1,i-1,-1):
        if(bub[j] < bub[j-1]):
            tmp = bub[j]
            bub[j] = bub[j-1]
            bub[j-1] = tmp
"""
selection sort(sel[])
"""

for i in range(0,len(sel)-1):
    minj = i
    for j in range(i,len(sel)):
        if(sel[j] < sel[minj]):
            minj = j
    sel[i],sel[minj] = sel[minj],sel[i]
       
"""
comp org(org[])
"""


# buble

for i in range(0,len(bub)):
    bub[i].display_card()
    if (i==len(bub)-1):
        print("\n",end="")
    else :
        print(" ",end="")
print("Stable")
# selec
                
for i in range(0,len(sel)):
    sel[i].display_card()
    if (i==len(sel)-1):
        print("\n",end="")
    else :
        print(" ",end="")
if(bub == sel): 
    print("Stable")
else:
    print("Not stable")

# Example run
# Input:
-1
-3439167
# Output:
-3439167
Stable
-3439167
Stable
#! python3
# stableSort.py - 安定的なソートを行っているかどうか判別するプログラム

# インプットの例
# 5
# H4 C9 S4 D2 C3

# コマンド引数から値を受け取る
number = int(input())
array = input().split(' ')
bubble_array = array.copy()
select_array = array.copy()

# bubblesortのアルゴリズム
def bubbleSort(array, number):
    flag = 1
    i = 0
    while flag ==1:
        flag = 0
        for j in range(number-1, i, -1):
            if array[j][1] < array[j-1][1]:
                tmp = array[j]
                array[j] = array[j-1]
                array[j-1] = tmp
                flag = 1
    map_list = map(str, array)
    a = ' '.join(map_list)
    print(a)
    return array

# 選択ソートのアルゴリズム
def selectionSort(array, number):
    # counter = 0
    for i in range(number-1):
        mini_j = i
        for j in range(i + 1, number):
            if int(array[mini_j][1]) > int(array[j][1]):
                mini_j = j

        #if int(array[i][1]) > int(array[mini_j][1]):
        v = array[i]
        array[i] = array[mini_j]
        array[mini_j] = v
            # counter += 1

    map_list = map(str, array)
    a = ' '.join(map_list)
    print(a)
    return array

# 安定ソートかどうかを判別する
def isStable(input, output):
    for i in range(0, number):
        for j in range(i+1, number):
            for a in range(0, number):
                for b in range(a+1, number):
                    if input[i][1] == input[j][1] and input[i] == output[b] and input[j] == output[a]:
                        return 'Not stable'
    return 'Stable'

input = array
output_bubble = bubbleSort(bubble_array, number)
# print(output_bubble)
print(isStable(input, output_bubble))

output_select = selectionSort(select_array, number)
# print(output_select)
print(isStable(input, output_select))


# Example run
# Input:
-23909
Jq\y`
# Output:
Jq\y`
Stable
Jq\y`
Stable
def bubble_sort(a,n):
    for i in range(n):
        for j in range(n-1,i,-1):
            if a[j][1] < a[j-1][1]:
                a[j], a[j-1] = a[j-1], a[j]
    return a

def selection_sort(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]
    return a

def is_stable(a, sa, n):
    stable = True
    for i in range(n-1):
        if sa[i][1] == sa[i+1][1] and a.index(sa[i]) > a.index(sa[i+1]):
                stable = False
                break
    if stable:
        print('Stable')
    else:
        print('Not stable')

n = int(input())
a = [ (s[0], int(s[1:])) for s in input().split() ]
ba = bubble_sort(a.copy(),n)
print(*[ s[0]+str(s[1]) for s in ba])
is_stable(a,ba,n)
ia = selection_sort(a.copy(),n)
print(*[ s[0]+str(s[1]) for s in ia])
is_stable(a,ia,n)


# Example run
# Input:
-5075395
-156960
# Output:
-156960
Stable
-156960
Stable
# 配列の宣言
A = []
B = []
C = []

# 文字列の取得と加工
LENGTH =int(input())
A = input().split()
B = A.copy()
C = 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 B == C:
        print("Stable")
    else:
        print("Not stable")

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


# Example run
# Input:
0
Q\vyk`dM4
# Output:
Q\vyk`dM4
Stable
Q\vyk`dM4
Stable
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]:
                c[j], c[j-1] = c[j-1], c[j]
    return c

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


def main():
    N = int(input())
    cards1 = input().split()
    cards2 = cards1.copy()

    bubble_sorted = bubble_sort(cards1, N)
    print(*bubble_sorted)
    print("Stable")
    
    select_sorted = selection_sort(cards2, N)
    print(*select_sorted)
    if bubble_sorted == select_sorted:
        print("Stable")
    else:
        print("Not stable")


if __name__ == "__main__":
    main()



# Example run
# Input:
0
|Yc^h
# Output:
|Yc^h
Stable
|Yc^h
Stable
N = int(input())
A = input().split()
A_b = [e for e in A]
A_s = [e for e in A]


# bubble sort

flag = True
left = 0

while flag:
    flag = False
    for i in range(N-1, left, -1):
        if int(A_b[i][1]) < int(A_b[i-1][1]):
            A_b[i], A_b[i-1] = A_b[i-1], A_b[i]
            flag = True
    left += 1
print(" ".join(A_b))
print("Stable")


# selsection sort

for i in range(N):
    minj = i
    for j in range(i, N):
        if int(A_s[j][1]) < int(A_s[minj][1]):
            minj = j
    if minj != i:
        A_s[i], A_s[minj] = A_s[minj], A_s[i]
print(" ".join(A_s))

is_same = True
for i in range(N):
    if A_s[i] != A_b[i]:
        is_same = False
        break
if is_same:
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
0
&k7$an8
# Output:
&k7$an8
Stable
&k7$an8
Stable
def bubblesort(n, a):
    r = a[:]
    for i in range(n):
        for j in range(n-1, i, -1):
            if int(r[j][1]) < int(r[j-1][1]):
                r[j], r[j-1] = r[j-1], r[j]

    print(*r)
    print("Stable")


def selectionsort(n, a):
    r = a[:]
    ret = "Stable"
    for i in range(n):
        tmp = i
        for j in range(i, n):
            if int(r[j][1]) < int(r[tmp][1]):
                tmp = j
        r[i], r[tmp] = r[tmp], r[i]

    for i in range(n):
        for j in range(i+1, n):
            for k in range(n):
                for l in range(k+1, n):
                    if int(a[i][1]) == int(r[j][1]) and a[i] == r[l] and a[j] == r[k]:
                        ret = "Not Stable"

    print(*r)
    print(ret)


def main():
    n = int(input())
    a = list(input().split())

    bubblesort(n, a)
    selectionsort(n, a)


if __name__ == '__main__':
    main()


# Example run
# Input:
-5701370
k<6]
# Output:
k<6]
Stable
k<6]
Stable
def bubble_sort(data):
    for i in range(len(data) - 1):
        for j in range(len(data) - 1, i, -1):
            if int(data[j][1]) < int(data[j - 1][1]):
                data[j], data[j - 1] = data[j - 1], data[j]

def selection_sort(data):
    for i in range(len(data)):
        min_j = i
        for j in range(i, len(data)):
            if int(data[j][1]) < int(data[min_j][1]):
                min_j = j
        if min_j != i:
            data[i], data[min_j] = data[min_j], data[i]

input()
cards = [x for x in input().split()]
cards_b = cards.copy()
cards_s = cards.copy()
bubble_sort(cards_b)
selection_sort(cards_s)
for data in [cards_b, cards_s]:
    print(' '.join(data))
    if data == cards_b:
        print("Stable")
    else:
        print("Not stable")

# Example run
# Input:
k`SHzjrHd
11
# Output:
11
Stable
11
Stable
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]
def SelectionSort(C, N):
    for i in range(N):
        minj = i
        for j in range(i + 1, N):
            if C[j][1] < C[minj][1]:
                minj = j
        if i != minj:
            C[i], C[minj] = C[minj], C[i]
N = int(input())
A = input().split()
B = A[:]
C = A[:]
BubbleSort(B, N)
print(*B)
print("Stable")
SelectionSort(C, N)
print(*C)
print("Stable" if B == C else "Not stable")


# Example run
# Input:
0
UUuK
# Output:
UUuK
Stable
UUuK
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:
0
A=|#RS`
# Output:
A=|#RS`
Stable
A=|#RS`
Stable
import copy
def p(a):
    for i in a[:-1]:
        print(i,end=' ')
    print(a[-1])


def selection_sort(a):
    cnt = 0
    for i in range(len(a)-1):
        fl = 0
        min = i
        for j in range(i+1,len(a)):
            if a[j][1]<a[min][1]:
                fl=1
                min = j
        cnt+=fl
        tmp = a[min]
        a[min] = a[i]
        a[i] = tmp


def bubble_sort(a):
    for i in range(len(a)-1):
        for j in range(i+1,len(a))[::-1]:
            if a[j-1][1]>a[j][1]:
                tmp = a[j]
                a[j] = a[j-1]
                a[j-1] = tmp


n = int(input())
l = list(input().split())
a = copy.copy(l)
bubble_sort(l)
selection_sort(a)
p(l)
print('Stable')
p(a)
if a==l:
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
-1
hd](
# Output:
hd](
Stable
hd](
Stable
def bubble_sort(a, n):
    for i in range(n-1):
        for j in range(n-1, i, -1):
            if a[j-1][1] > a[j][1]:
                a[j-1], a[j] = a[j], a[j-1]

    return a


def selection_sort(a, n):
    for i in range(n-1):
        min_j = i
        for j in range(i+1, n):
            if a[min_j][1] > a[j][1]:
                min_j = j
        if min_j != i:
            a[min_j], a[i] = a[i], a[min_j]

    return a


if __name__ == "__main__":
    n = int(input())
    a = input().split()

    result1 = bubble_sort(a[:], n)
    result2 = selection_sort(a[:], n)
    print(*result1)
    print("Stable")
    print(*result2)
    print("Stable" if result1 == result2 else "Not stable")


# Example run
# Input:
-84559984
K$sfphu"3
# Output:
K$sfphu"3
Stable
K$sfphu"3
Stable
def bubble_sort(a_list):
    n = len(a_list)
    for i in range(0, n):
        for j in reversed(range(i + 1, n)):
            if a_list[j - 1][1] > a_list[j][1]:
                a_list[j - 1], a_list[j] = a_list[j], a_list[j - 1]
    return a_list


def selection_sort(a_list):
    n = len(a_list)
    for i in range(0, n):
        mini = i
        for j in range(i, n):
            if a_list[j][1] < a_list[mini][1]:
                mini = j
        if i != mini:
            a_list[i], a_list[mini] = a_list[mini], a_list[i]
    return a_list


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

bubble_sorted = bubble_sort(a_list[:])
print(' '.join(map(str, bubble_sorted)))
print('Stable')
selection_sorted = selection_sort(a_list[:])
print(' '.join(map(str, selection_sorted)))
if bubble_sorted == selection_sorted:
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
1947279
Qeh54C"e
# Output:
Qeh54C"e
Stable
Qeh54C"e
Stable
n = int(input())
c = input().split()

cb = c[:]
for i in range(n):
	for j in range(n-1,i,-1):
		if cb[j][1] < cb[j-1][1]:
			cb[j-1],cb[j] = cb[j],cb[j-1]
print(*cb)
print('Stable')

cs = c[:]
for i in range(n):
	m = min(range(i,n), key=lambda j: cs[j][1])
	if i != m:
		cs[i],cs[m] = cs[m],cs[i]
print(*cs)
print(('' if cb == cs else 'Not ') + 'stable')


# Example run
# Input:
-26
!;Qz4_LrU
# Output:
!;Qz4_LrU
Stable
!;Qz4_LrU
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):
    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(' '.join(a))
print('Stable' if b == a else 'Not stable')

# Example run
# Input:
-15
px%pJ{Q
# Output:
px%pJ{Q
Stable
px%pJ{Q
Stable
def bubblesort_re(A,N):
    count = 0
    #A[i] > A[i+1]の状態がある→交換する必要がある：flag = True
    #交換する必要が無いとbreak→値の無駄な比較をしない
    flag = True
    while flag:
        flag = False
        # for i in range(N-1):
        #     if A[i][1] > A[i+1][1]:
        #         A[i],A[i+1] = A[i+1],A[i]
        #         count += 1
        #         flag = True
        for i in range(N-1,0,-1):
            if A[i][1] < A[i-1][1]:
                A[i],A[i-1] = A[i-1],A[i]
                count += 1
                flag = True

    return A,count

def min_index(A):
    index = 0
    m = A[0][1]
    for i in range(1,len(A)):
        if A[i][1] < m:
            m = A[i][1]
            index = i

    return index

# def selectionsort(A,N):
#     count = 0
#     for i in range(N-1):
#         j = min_index(A[i+1:])
#         if int(A[i][1]) > int(A[i+j+1][1]):
#             A[i],A[i+j+1] = A[i+j+1],A[i]
#             count += 1
#
#     return A,count

def selectionsort(A,N):
    count = 0
    for i in range(N):
        minj = i
        #最小値を見つけるfor文：O(n)
        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,count

if __name__ == '__main__':
    import copy

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

    X = A.copy()
    s,t = bubblesort_re(X,N)
    for i in range(N):
        if i != N - 1:
            print(s[i],end = " ")
        else:
            print(s[i])
    print("Stable")

    X = A.copy()
    u,v = selectionsort(X,N)
    for i in range(N):
        if i != N - 1:
            print(u[i],end = " ")
        else:
            print(u[i])
    if s == u:
        print("Stable")
    else:
        print("Not stable")



# Example run
# Input:
-299483
~vkXMy>
# Output:
Stable
Stable
# coding: utf-8
# Here your code !
n=int(input())
cards=input().split()

def bubble_sort(cards,n):
    for i in range(n):
        for j in range(-1,-i,-1):
            a=int(cards[j][1])
            b=int(cards[j-1][1])
            if a<b:
                cards[j],cards[j-1]=cards[j-1],cards[j]
    return cards

def selection_sort(cards,n):
    for i in range(n):
        minv=i
        for j in range(i,n):
            a=int(cards[minv][1])
            b=int(cards[j][1])
            if a>b:
                minv=j
        cards[minv],cards[i]=cards[i],cards[minv]
    return cards

ans_1=bubble_sort(cards,n)
ans_2=selection_sort(cards,n)

print(*ans_1)
print("Stable")
print(*ans_2)
if ans_1!=ans_2:
    print("Not stable")
else:
    print("Stable")

# Example run
# Input:
-28193
`e@@)}rTV
# Output:
`e@@)}rTV
Stable
`e@@)}rTV
Stable
import copy

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

def BubbleSort(NUM_LIST):
    for i in range(1, len(NUM_LIST)):
        for j in range(len(NUM_LIST)-1, i-1, -1):
            if NUM_LIST[j-1][1] >NUM_LIST[j][1]:
                NUM_LIST[j], NUM_LIST[j-1] = NUM_LIST[j-1], NUM_LIST[j]

def SelectionSort(NUM_LIST):
    for i in range(len(NUM_LIST)):
        minj = i
        for j in range(i, len(NUM_LIST)):
            if NUM_LIST[minj][1] > NUM_LIST[j][1]:
                minj = j
        NUM_LIST[minj], NUM_LIST[i] = NUM_LIST[i], NUM_LIST[minj]

bubble_cards = copy.copy(cards)
selection_cards = copy.copy(cards)

BubbleSort(bubble_cards)
SelectionSort(selection_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:
51
FbP\cnh
# Output:
FbP\cnh
Stable
FbP\cnh
Stable
class Card():
    def __init__(self, card):
        self.card = card
        self.mark = card[0]
        self.number = card[1]
        
    def __lt__(self, other):
        if not isinstance(other, Card):
            return NotImplemented
        return self.number < other.number
        
    def __repr__(self):
        return '{}{}'.format(self.mark, self.number)


def BubbleSort(target):
    ls = target.copy()
    flag = 1
    while flag:
        flag = 0
        for i in range(len(ls)-1, 0, -1):
            if ls[i] < ls[i-1]:
                ls[i], ls[i-1] = ls[i-1], ls[i]
                flag = 1
    print(' '.join(map(str, ls)))
    return sorted(ls)


def SelectSort(target):
    ls = target.copy()
    for i in range(len(ls)):
        minj = i
        for j in range(i+1, len(ls)):
            if ls[j] < ls[minj]:
                minj = j
        if ls[i] != ls[minj]:
            ls[i], ls[minj] = ls[minj], ls[i]
    
    print(' '.join(map(str, ls)))
    return sorted(ls)

def judge(original, sorted_list):
    if original == sorted_list:
        print('Stable')
    else:
        print('Not stable')


_ = int(input())
l2 =  [Card(i) for i in input().split()]
l2_sort = sorted(l2)

bubble = BubbleSort(l2)
judge(l2_sort, bubble)

select = SelectSort(l2)
judge(l2_sort, select)



# Example run
# Input:
-1015053308
YQocc[TJS
# Output:
YQ
Stable
YQ
Stable
import copy
def BubbleSort(C, N):
    for i in range(N):
        for j in reversed(range(i+1, N)):
            if C[j][1:2] <  C[j-1][1:2]:
                C[j], C[j-1] = C[j-1], C[j]

    print(*C)
    stableCheck(C, N)

def SelectionSort(C, N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if C[j][1:2] <  C[minj][1:2]:
                minj = j
        C[i], C[minj] = C[minj], C[i]
    print(*C)
    stableCheck(C, N)

def stableCheck(C, N):
    global lst
    flag = 1
    for i in range(N):
        for j in range(i+1, N):
            if lst[i][1:2] == lst[j][1:2]:
                fir = lst[i]
                sec = lst[j]
                for k in range(N):
                    if C[k] == fir:
                        recf = k

                    if C[k] == sec:
                        recs = k
                
                if recf > recs:
                    print("Not stable")
                    flag = 0
                    break
        
        if flag ==0:
            break

    if flag :
        print("Stable")

N = int(input())
lst = list(map(str, input().split()))
lst1 = copy.deepcopy(lst)
lst2 = copy.deepcopy(lst)

BubbleSort(lst1, N)
SelectionSort(lst2, N)


# Example run
# Input:
-2031692
`eo2UER
# Output:
`eo2UER
Stable
`eo2UER
Stable
import copy
N = int(input())
C = input().split()
D = copy.copy(C)
for i in range(N):
    for j in range(i+1,N):
        k = N-j+i
        if int(C[k][1]) < int(C[k-1][1]):
            dummy = C[k]
            C[k] = C[k-1]
            C[k-1] = dummy

for i in range(N-1):
    print(f"{C[i]}",end =" ")
print(f"{C[N-1]}\nStable")
for i in range(N):
    minj = i
    for j in range(i,N):
        if int(D[j][1]) < int(D[minj][1]):
            minj = j
    dummy = D[i]
    D[i] = D[minj]
    D[minj] = dummy
for i in range(N-1):
    print(f"{D[i]}",end =" ")
flag = 0
for i in range(N):
    if C[i] != D[i]:
        flag = 1
        print(f"{D[N-1]}\nNot stable")
        break
if flag == 0:
    print(f"{D[N-1]}\nStable")


# Example run
# Input:
0
1k"I%%}x
# Output:
1k"I%%}x
Stable
1k"I%%}x
Stable
import copy
N = int(input())
bscs = [(int(c[-1]), c) for c in input().split(" ")]
sscs = copy.copy(bscs)
for i in range(N):
    j = N - 1
    while j > i:
        if bscs[j][0] < bscs[j - 1][0]:
            tmp = bscs[j]
            bscs[j] = bscs[j - 1]
            bscs[j - 1] = tmp
        j -= 1
print(" ".join([c[1] for c in bscs]))
print("Stable")
for i in range(N):
    minj = i
    for j in range(i, N):
        if sscs[j][0] < sscs[minj][0]:
            minj = j
    tmp = sscs[i]
    sscs[i] = sscs[minj]
    sscs[minj] = tmp
print(" ".join([c[1] for c in sscs]))
print("Stable" if bscs == sscs else "Not stable")

# Example run
# Input:
-7916
376395
# Output:
376395
Stable
376395
Stable
from copy import deepcopy


def printer(A):
    ret = str(A[0][1]) + str(A[0][0])
    for i in range(1, len(A)):
        ret += " " + str(A[i][1]) + str(A[i][0])
    print(ret)
    return True


def devide(card):
    ret = []
    for c in card:
        num = int(c[1])
        pic = c[0]
        ret.append((num, pic))
    return ret


def bubblesort(A):
    ret = 0
    flag = True
    num = len(A)
    while flag is True:
        flag = False
        for i in reversed(range(1, num)):
            if A[i - 1][0] > A[i][0]:
                tmp = A[i - 1]
                A[i - 1] = A[i]
                A[i] = tmp
                flag = True
                ret += 1
                # print(A)
        # num -= 1
    return ret


def selection_sort(A):
    ans = 0
    for i in range(len(A)):
        minj = i
        for j in range(i, len(A)):
            if A[minj][0] > A[j][0]:
                minj = j
        if i != minj:
            ans += 1
            tmp = A[i]
            A[i] = A[minj]
            A[minj] = tmp
    return ans


def isStable(card, sorted_card):
    if len(card) != len(sorted_card):
        return False
    for i in range(len(card)):
        c = card[i]
        s = sorted_card[i]
        if c[0] != s[0] or c[1] != s[1]:
            return False
    return True


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

card = devide(card)
card_bubble = deepcopy(card)
card_selection = deepcopy(card)

bubblesort(card_bubble)
selection_sort(card_selection)

# print(card_bubble)
printer(card_bubble)
print("Stable")

printer(card_selection)
if isStable(card_bubble, card_selection) is True:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-1
-4
# Output:
-4
Stable
-4
Stable