Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
N = int(input())
array = list(input().split())
array2 = array[:]
array3 = array[:]

def bubble_sort(array, N):
	flag = 1
	i = 0
	while flag:
		flag = 0 
		j = N-1
		while j > i:
			if array[j][1] < array[j-1][1]:
				array[j], array[j-1] = array[j-1], array[j]
			j -= 1
			flag = 1
		i += 1


def selection_sort(array, n):
	for i in range(n):
		minij = i 
		for j in range(i, n):
			if array[j][1] < array[minij][1]:
			    minij = j 
		array[i], array[minij] = array[minij], array[i]

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

bubble_sort(array, N)
print(' '.join(array))
print('Stable')
selection_sort(array2,N)
print(' '.join(array2))
if is_stable(array3, array2, N):
	print('Stable')
else:
	print('Not stable')







# Example run
# Input:
-6
N;Rvk
# Output:
N;Rvk
Stable
N;Rvk
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:
0
|Yc^h
# Output:
|Yc^h
stable
|Yc^h
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(*bubbleC)
print(check_stable(C, bubbleC))
print(*selectionC)
print(check_stable(C, selectionC))

# Example run
# Input:
65153902
X\&*
# Output:
X\&*
Stable
X\&*
Stable
n = int(input())
clist = list(map(list, input().split()))

def BubbleSort(C, n):
    for i in range(n-1):
        for w in range(i+1, n):
            j = n-w+i
            if (C[j][1] < C[j-1][1]):
                a = C[j]
                C[j] = C[j-1]
                C[j-1] = a
def SelectionSort(C, n):
    for i in range(n):
        mini = i
        for j in range(i+1,n):
            if (C[j][1] < C[mini][1]):
                mini = j
        if(mini != i):
            a = C[i]
            C[i] = C[mini]
            C[mini] = a
## l[1]이 str 이라는것에 주의 int(l[1])을 해줘야함 --> 이거 때문에 20분 디버깅 소비
def stable(A,B):
    count = [0 for i in range(9)]
    for l in A:
        count[int(l[1]) - 1] += 1
    ilist = [] ##安定なiのリスト
    for i in range(1,10):
        if (count[i-1] > 1):
            awlist = []
            for l in A:
                if(int(l[1]) == i):
                    awlist.append(l[0])
            bwlist = []
            for l in B:
                if(int(l[1]) == i):
                    bwlist.append(l[0])
            if (awlist == bwlist):
                ilist.append(i)
            
        else:
            ilist.append(i)
    if (len(ilist) == 9):
        print('Stable',end = '')
    else:
        print('Not stable', end = '')
                  

Blist = list(clist)
BubbleSort(Blist, n)
for i in range(n):
    if (i == n-1):
        print('{}{}'.format(Blist[i][0],Blist[i][1]), end = '')
    else : 
        print('{}{}'.format(Blist[i][0],Blist[i][1]), end = ' ')
print()
stable(clist, Blist)
print()

Slist = list(clist)
SelectionSort(Slist, n)
for i in range(n):
    if(i == n-1):
        print('{}{}'.format(Slist[i][0],Slist[i][1]), end = '')
    else:
        print('{}{}'.format(Slist[i][0],Slist[i][1]), end = ' ')
print()
stable(clist, Slist)
print()



# Example run
# Input:
-2147483648
450137
# Output:

Stable

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

flag = 1

for _ in range(n-1):
    while flag:
        flag = 0
        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]
                flag = 1
print(" ".join(map(str, a)))
print("Stable")

for i in range(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]
print(" ".join(map(str, b)))
print("Stable" if a == b else "Not stable")


# Example run
# Input:
-37
vY;
# Output:
vY;
Stable
vY;
Stable
def BubbleSort(C,N):
    for a in range(0,N-1):
        for b in range(N-1,a,-1):
            if int(C[b][1]) < int(C[b-1][1]):
                C[b],C[b-1] = C[b-1],C[b]

def SelectionSort(C,N):
    for a in range(0,N-1):
        index_min = [x[1] for x in C[(a+1):]].index(min([x[1] for x in C[(a+1):]]))+a+1
        # print(f'{min(A[a+1:])} {index_min}')
        if C[a][1] > C[index_min][1]:
            C[a],C[index_min] = C[index_min],C[a]


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

BubbleSort(A,N)
print(*A)
print('Stable')

SelectionSort(B,N)
print(*B)
if A == B:
    print('Stable')
else:
    print('Not stable')




# Example run
# Input:
-1787
,ow5{T
# Output:
,ow5{T
Stable
,ow5{T
Stable
n = int(input())
a = list(input().split())
b = a[:]
for i in range(n):
    for j in range(n-1):
        if a[j][1]>a[j+1][1]:
            a[j],a[j+1] = a[j+1],a[j]
    minj = i
    for j in range(i,n):
        if b[minj][1]>b[j][1]:
            minj = j
    b[minj],b[i] = b[i],b[minj]        
print(*a)
print('Stable')
print(*b)
print(['Not s','S'][a==b] + 'table')





# Example run
# Input:
-13
@`(RsV.z
# Output:
@`(RsV.z
Stable
@`(RsV.z
Stable
import time
import copy

def BubbleSort(A, N):
    flag = 1
    while flag:
        flag = 0
        for j in reversed(range(1, N)):
            if A[j]['value']<A[j-1]['value']:
                A[j], A[j-1] = A[j-1], A[j]
                flag = 1
    return A

def SelectionSort(A, N):
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if A[j]['value']<A[minj]['value']:
                minj = j
        if i!=minj:
            A[i], A[minj] = A[minj], A[i]
    return A

def IsStable(answer, target):
    N = len(answer)
    for i in range(N):
        if answer[i]['value'] != target[i]['value']:
            return False
    return True

# Stable Sort
def main():
    N = int(input())
    A = list(
        map(lambda x: {'body': x, 'value': int(x[1])}, input().split())
    )
    A_sortby_bubble = copy.deepcopy(A)
    A_sortby_select = copy.deepcopy(A)
    A_sortby_bubble = BubbleSort(A_sortby_bubble, N)
    A_sortby_select = SelectionSort(A_sortby_select, N)
    print(' '.join(map(lambda x: x['body'],A_sortby_bubble)))
    print('Stable')
    print(' '.join(map(lambda x: x['body'], A_sortby_select)))
    if IsStable(A_sortby_bubble, A_sortby_select):
        print('Stable')
    else:
        print('Not stable') 
    
main()


# Example run
# Input:
-72091561
-1622400
# Output:
-1622400
Stable
-1622400
Stable
def isStable(inlist, outlist):
	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 int(inlist[i][1:]) == int(inlist[j][1:]) and inlist[i] == outlist[b] and inlist[j] == outlist[a]:
						return False
						break
				else:
					continue
				break
			else:
				continue
			break
		else:
			continue
		break

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

flag = 1
counter = 0
while flag:
    flag = 0
    for i in reversed(range(1,N)):
        if int(C[i][1:]) < int(C[i-1][1:]):
            C[i], C[i-1] = C[i-1], C[i]
            counter += 1
            flag = 1
print(" ".join(map(str, C)))

if(isStable(A, C)):
	print("Stable")
else:
	print("Not Stable")

counter=0
for i in range(N):
	Br = B[i:]
	Brr = [int(Br[j][1:]) for j in range(N-i)]
	num = Brr.index(min(Brr)) 
	if num != 0:
		B[i], B[(i+num)] = B[(i+num)], B[i]
		counter += 1
print(" ".join(map(str,B)))
if(isStable(A, B)):
	print("Stable")
else:
	print("Not Stable")

# Example run
# Input:
-1
}\pKT8\G
# Output:
}\pKT8\G
Not Stable
}\pKT8\G
Not Stable
from copy import deepcopy as copy
n=int(input())
A=input().split()
C=copy(A)
for i in range(n):
  for j in range(n-1,i,-1):
    if C[j][1] < C[j-1][1]:
      k=C[j]
      C[j]=C[j-1]
      C[j-1]=k
print(*C)
for i in range(n-1):
  if C[i][1]==C[i+1][1] and A.index(C[i])>A.index(C[i+1]):
    print('Not stable')
    break
else:print('Stable')
C=copy(A)
for i in range(n):
  minj = i
  for j in range(i,n):
    if C[j][1] < C[minj][1]:
      minj = j
  k=C[i]
  C[i]=C[minj]
  C[minj]=k
print(*C)
for i in range(n-1):
  if C[i][1]==C[i+1][1] and A.index(C[i])>A.index(C[i+1]):
    print('Not stable')
    break
else:print('Stable')


# Example run
# Input:
-3766
m~%@y;
# Output:
m~%@y;
Stable
m~%@y;
Stable
# bable sort
def bubbleSort(o_nums, n):
    nums=o_nums[:]
    for i in range(len(nums)-1):
        for j in range(len(nums)-1,i,-1):
            if nums[j][1]<nums[j-1][1]:
                nums[j],nums[j-1]=nums[j-1],nums[j]  
    return nums

# selection sort
def selectionSort(o_nums,n):
    nums=o_nums[:]
    for i in range(n):
        minj=i
        for j in range(i,n):
            if nums[j][1]<nums[minj][1]:
                minj=j
        if nums[i][1]!=nums[minj][1]:
            nums[i],nums[minj]=nums[minj],nums[i]
    return nums

n=int(input())
cards=list(input().split())

b=bubbleSort(cards, n)
s=selectionSort(cards,n)
print(*b)
print("Stable")
print(*s)
if bubbleSort(cards, n) == selectionSort(cards, n):
    print("Stable")
else:
    print("Not stable")

# Example run
# Input:
-516
a-[iI
# Output:
a-[iI
Stable
a-[iI
Stable
import copy


def SelectionSort(arr, n):
    for i in range(n):
        mini = i
        for j in range(i, n):
            if arr[j]['val'] < arr[mini]['val']:
                mini = j
        if mini != i:
            arr[i], arr[mini] = arr[mini], arr[i]
    return


def BubleSort(arr, n):
    for i in range(n):
        for j in range(n - 1, i, -1):
            if arr[j]['val'] < arr[j-1]['val']:
                arr[j], arr[j-1] = arr[j-1], arr[j]
    return


def isStable(inarr, comparr, n):
    i = 0
    while i < n:
        tmpVal = comparr[i]['val']
        for j in range(n):
            if inarr[j]['val'] == tmpVal:
                if inarr[j]['crd'] == comparr[i]['crd']:
                    if i != n - 1 and comparr[i+1]['val'] == tmpVal:
                        i += 1
                    else:
                        break
                else:
                    return 'Not stable'
        i += 1
    return 'Stable'


n = int(input())
arr = input().split()
tar = []

for s in arr:
    tar.append({'crd': s[0], 'val': s[1], 'str': s})

bub = copy.copy(tar)
BubleSort(bub, n)

w = ""
for s in bub:
    w += s['str'] + ' '
print(w)
print(isStable(tar, bub, n))

bub = copy.copy(tar)
SelectionSort(bub, n)

w = ""
for s in bub:
    w += s['str'] + ' '
print(w)
print(isStable(tar, bub, n))



# Example run
# Input:
-352
fI]:p,
# Output:
fI]:p, 
Stable
fI]:p, 
Stable
N = int(input())
C1 = input().split()
C2 = C1[:]

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]):
                tmp = C[j]
                C[j] = C[j-1]
                C[j-1] = tmp
        i += 1
    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
        if minj != i:
            tmp = C[minj]
            C[minj] = C[i]
            C[i] = tmp
        i += 1
    return C

bubbleSort_result = ' '.join(bubbleSort(C1, N))
selectionSort_result = ' '.join(selectionSort(C2, N))

print(bubbleSort_result)
print('Stable')
print(selectionSort_result)
if bubbleSort_result == selectionSort_result:
    print('Stable')
else:
    print('Not stable')

# Example run
# Input:
-32633089
hj9B
# Output:
hj9B
Stable
hj9B
Stable
cardNum = lambda S:int(list(S)[1])

def bubbleSort(L, n):
  for i in range(n):
    for j in range(n-1, i, -1):
      if cardNum(L[j]) < cardNum(L[j-1]):
        L[j], L[j-1] = L[j-1], L[j]
  return L

def selectionSort(L, n):
  for i in range(n):
    minj = i
    for j in range(i, n):
      if cardNum(L[j]) < cardNum(L[minj]):
        minj = j
    L[i], L[minj] = L[minj], L[i]
  return L

def isStable(Lb, Ls):
  if Lb == Ls:
    return "Stable"
  else:
    return "Not stable"
  
N = int(input())
A = input().split()
B = [i for i in A]
LB = bubbleSort(A, N)
LS = selectionSort(B, N)
print(' '.join(map(str, LB)))
print("Stable")
print(' '.join(map(str, LS)))
print(isStable(LB, LS))


# Example run
# Input:
-2503
RQG
# Output:
RQG
Stable
RQG
Stable
def bubble_sort(card_list):
    # フラグを使わないので、card_list がどの程度ソート済みかに
    # 関わらず、常に N ^ 2 のオーダーになる。
    for i in range(len(card_list)):
        for j in range(len(card_list)-1, i, -1):
            if int(card_list[j][1]) < int(card_list[j-1][1]):
                card_list[j-1], card_list[j] = card_list[j], card_list[j-1]

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


def is_stable(before, after):
    """ソートが安定だったかどうかを判定する。

    ソート前と後のリスト in, out をとる。リスト中に全く同じカードはないと仮定している。
    """
    for i in range(len(before)):
        for j in range(i+1, len(before)):
            for a in range(len(after)):
                for b in range(a+1, len(after)):
                    if before[i][1] == before[j][1] and before[i] == after[b] and before[j] == after[a]:
                        return False

    return True



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

b_card_list = orig_card_list.copy()
s_card_list = orig_card_list.copy()

bubble_sort(b_card_list)
selection_sort(s_card_list)

print(*b_card_list)
if is_stable(orig_card_list, b_card_list):
    print('Stable')
else:
    print('Not stable')

print(*s_card_list)
if is_stable(orig_card_list, s_card_list):
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
65153902
X\&*
# Output:
X\&*
Stable
X\&*
Stable
def BubbleSort(C,N):
    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
            j -= 1
    return C

def SelectionSort(D,N):
    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
        tmp = D[i]
        D[i] = D[minj]
        D[minj] = tmp
    return D

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

# Example run
# Input:
-1628416575
+CP)0CA
# Output:
+CP)0CA
Stable
+CP)0CA
Stable
import copy

def bubble_sort(A):
    for i in range(len(A)):
        for j in range(len(A)-1, i, -1):
            if A[j]['value'] < A[j-1]['value']:
                tmp = A[j]
                A[j] = A[j-1]
                A[j-1] = tmp


def selection_sort(B):
    for i in range(len(B)):
        mini = i
        for j in range(i, len(B)):
            if B[j]['value'] < B[mini]['value']:
                mini = j
        tmp = B[i]
        B[i] = B[mini]
        B[mini] = tmp


def is_stable(A, B, n):
    for i in range(n):
        if A[i]['suit'] != B[i]['suit']:
            return False
    return True


def show_list(C):
    D = [i['suit'] + i['value'] for i in C]
    print(' '.join(D))
    
n = int(input())
A = [{'suit': i[0], 'value': i[-1]}for i in map(str, input().split())]
B = copy.deepcopy(A)

bubble_sort(A)
show_list(A)
print('Stable')

selection_sort(B)
show_list(B)
if is_stable(A, B, n):
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
-27123728
(XQ6o%K<
# Output:
(<
Stable
(<
Stable
def bubbleSort(cards):
    for i, _ in enumerate(cards):
        for j in range(len(cards) -1, i, -1):
            if int(cards[j][1]) <  int(cards[j-1][1]):
                cards[j], cards[j - 1] = cards[j - 1], cards[j]
    return cards
    
def selectionSort(cards):
    for i in range(len(cards)):
        min_j = i
        for j in range(i, len(cards)):
            if int(cards[j][1]) < int(cards[min_j][1]):
                min_j = j
        cards[i], cards[min_j] = cards[min_j], cards[i]
    return cards
    
N = int(input())
A = input().split()

temp = A.copy()
bs = bubbleSort(temp)

temp = A.copy()
ss = selectionSort(temp)

print(' '.join(bs))
print('Stable')
print(' '.join(ss))
if [a[:1] for a in bs] == [a[:1] for a in ss]:
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
-31
224
# Output:
224
Stable
224
Stable
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


class Card(object):

    def __init__(self, card):
        self.card = card
        self.suit = card[0]
        self.value = int(card[1:])

    def __str__(self):
        return str(self.card)


def print_array(a):
    print(" ".join(map(str, a)))


def bubblesort(cards, n):
    c = cards[:]
    for i in range(0, n):
        for j in range(n - 1, i - 1, -1):
            if c[j].value < c[j - 1].value:
                (c[j], c[j - 1]) = (c[j - 1], c[j])
    return c


def selectionsort(cards, n):
    c = cards[:]
    for i in range(0, 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])
    return c


def main():
    n = int(input())
    cards = list(map(Card, input().split()))
    b = bubblesort(cards, n)
    print_array(b)
    print("Stable")
    s = selectionsort(cards, n)
    print_array(s)
    if b == s:
        print("Stable")
    else:
        print("Not Stable")


if __name__ == "__main__":
    main()

# Example run
# Input:
-358903
-4422
# Output:
-4422
Stable
-4422
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:
-4
kQ@YZ@p
# Output:
kQ@YZ@p
Stable
kQ@YZ@p
Stable
import copy

class Card:
    def __init__(self, str):
        self.mark = str[0]
        self.number = int(str[1:])
        
    def __str__(self):
        return self.mark + str(self.number)
        
n = int(input())
card_list = [Card(c) for c in input().split()]

# Bubble Sort
def bubble_sort(a):
    a = copy.copy(a)
    n = len(a)
    for i in range(n):
        for j in range(0, n-i-1):
            if a[j].number > a[j+1].number:
                a[j], a[j+1] = a[j+1], a[j]
    return a

sorted_card_list1 = bubble_sort(card_list)
print(" ".join([str(c) for c in sorted_card_list1]))
print("Stable")

# Selection Sort
def selection_sort(a):
    a = copy.copy(a)
    n = len(a)
    for i in range(n):
        min_index = i
        for j in range(i+1, n):
            if a[j].number < a[min_index].number:
                min_index = j
        if i != min_index:
            a[i], a[min_index] = a[min_index], a[i]
    return a

sorted_card_list2 = selection_sort(card_list)
is_stable = sorted_card_list1 == sorted_card_list2
print(" ".join([str(c) for c in sorted_card_list2]))
print("Stable" if is_stable else "Not stable")



# Example run
# Input:
-640183291
155287
# Output:
155287
Stable
155287
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]
    return C
                
                

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


def IsStable(A, B):
    for i in range(len(A)):
        for j in range(i+1,len(A)):
            for a in range(len(B)):
                for b in range(a+1,len(B)):
                    if A[i][1] == A[j][1] and A[i] == B[b] and A[j] == B[a]:
                        return False
    return True
        
                
n = int(input())
a = input().split()
b = a.copy()
c = a.copy()
ans1 = []
ans2 = []
    
ans1 = BubbleSort(b, n)
print(*ans1)
if IsStable(a, ans1):
    print('Stable')
else:
    print('Not stable')

ans2 = SelectionSort(c, n)
print(*ans2)
if IsStable(a, ans2):
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
-182
=C>#:pjLk
# Output:
=C>#:pjLk
Stable
=C>#:pjLk
Stable
def bubble(A,n):
	A = A.copy()
	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(A,n):	
	A=A.copy()
	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()

C1,C2=bubble(A,n),selection(A,n)

print(' '.join(C1))
print('Stable')
print(' '.join(C2))
flag = 1
for i in range(n):
	if C1[i]!=C2[i]:
		flag=0
if flag:
	print('Stable')
else:
	print('Not stable')




# Example run
# Input:
0
)iTg5DK
# Output:
)iTg5DK
Stable
)iTg5DK
Stable
N = int(input())
C = [ x for x in input().split()]
C1 = C.copy()
C2 = C.copy()

def bubble_sort(N, C1):
    for i in range(N):
        for j in range(N-1, i, -1):
            if C1[j][1] < C1[j-1][1]: #2個目のカッコで文字数を指定(0スタート)
                C1[j], C1[j-1] = C1[j-1], C1[j]
    print(' '.join(map(str, C1)))   

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

    print(' '.join(map(str, C2)))


#愚直な判定
def bubble(N, C, C1):
    while True:        
        for i in range(N-1):
            for j in range(i+1, N):
                for a in range(N-1):
                    for b in range(a+1, N):
                        if C[i][1] == C[j][1] and C[i] == C1[b] and C[j] == C1[a]:
                            print('Not stable')
                            return False                            
        print('Stable')
        break

def selection(N, C, C2):
    while True:        
        for i in range(N-1):
            for j in range(i+1, N):
                for a in range(N-1):
                    for b in range(a+1, N):
                        if C[i][1] == C[j][1] and C[i] == C2[b] and C[j] == C2[a]:
                            print('Not stable')
                            return False                            
        print('Stable')
        break


bubble_sort(N, C1)
bubble(N, C, C1)
selection_sort(N, C2) 
selection(N, C, C2)                       



# Example run
# Input:
-2
1{h
# Output:
1{h
Stable
1{h
Stable