Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
import copy

def bubble_sort(a):
    ba = copy.copy(a)
    flag = True
    for i in range(0, n):
        if not flag:
            break
        flag = False
        for j in range(n-1, 0, -1):
            if int(ba[j][1]) < int(ba[j-1][1]):
                ba[j], ba[j-1] = ba[j-1], ba[j]
                flag = True

    return ba

def selection_sort(a):
    sa = copy.copy(a)
    for i in range(n):
        flag = False
        minj = i
        for j in range(i, n):
            if int(sa[j][1]) < int(sa[minj][1]):
                minj = j
                flag = True
        if flag:
            sa[i], sa[minj] = sa[minj], sa[i]

    return sa

def is_stable(ba, sa):
    for b, s in zip(ba, sa):
        if b != s:
            return 'Not stable'
    return 'Stable'


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

ba = bubble_sort(a)
print(' '.join(map(str, ba)))
print('Stable')

sa = selection_sort(a)
print(' '.join(map(str, sa)))
print(is_stable(ba, sa))



# Example run
# Input:
-195897
*TOvk|
# Output:
*TOvk|
Stable
*TOvk|
Stable
# -*- coding: utf-8 -*-


def BubbleSort(C, N):
    flag = 1
    while flag == 1:
        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):
    flag = 0

    for i in range(N):

        if N == 1:
            break

        minj = i
        for j in range(i, N):
            if int(C[j][1]) < int(C[minj][1]):
                minj = j
                flag = 1

        if flag == 1:
            C[i], C[minj] = C[minj], C[i]

        flag = 0

    return C


def print_line(A):
    for i in range(len(A)):
        if i == len(A) - 1:
            print('{0}{1}'.format(A[i][0], A[i][1]))
        else:
            print('{0}{1} '.format(A[i][0], A[i][1]), end='')


def check_stable(Bubble_A, Select_A):
    for i in range(len(Select_A)):
        if Bubble_A[i][0] != Select_A[i][0]:
            print('Not stable')
            break
        elif i == len(Select_A) - 1:
            print('Stable')


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

A = [A[i:i+2] for i in range(0, len(A), 3)]

Bubble_A = BubbleSort(A[:], N)
Select_A = SelectionSort(A[:], N)

print_line(Bubble_A)
print('Stable')
print_line(Select_A)
check_stable(Bubble_A, Select_A)



# Example run
# Input:
-2147483648
450137
# Output:
45 13
Stable
45 13
Stable
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
		if i != minj:
			tmp = A[i]
			A[i] = A[minj]
			A[minj] = tmp

	return A

def bubbleSort(A, N):
	for i in range(N):
		for j in range(N - 1, i, -1):
			if A[j][1:] < A[j - 1][1:]:
				tmp = A[j]
				A[j] = A[j - 1]
				A[j - 1] = tmp

	return A

if __name__ == '__main__':
	n = int(input())
	R = list(map(str, input().split()))
	C = R[:]
	SR = selectionSort(R, n)
	BR = bubbleSort(C, n)

	fStable = SR == BR

	print(" ".join(map(str, BR)))
	print("Stable")
	print(" ".join(map(str, SR)))
	if (fStable == True):
		print("Stable")
	else:
		print("Not stable")


# Example run
# Input:
-299483
~vkXMy>
# Output:
~vkXMy>
Stable
~vkXMy>
Stable
def is_stable(A, B, n):
    for i in range(n):
        for j in range(i+1, n):
            if A[i]['value'] == A[j]['value']:
                for a in range(n):
                    for b in range(a+1, n):
                        if A[i] == B[b] and A[j] == B[a]:
                            return False
    return True


def show(Card, n):
    for i in range(n):
        if i != n-1:
            print(Card[i]['suit'] + str(Card[i]['value']), end=' ')
        else:
            print(Card[i]['suit'] + str(Card[i]['value']))


def bubble_sort(A, n):
    Card = A.copy()
    flag = 1
    while flag:
        flag = 0
        for i in range(n-1):
            if Card[i]['value'] > Card[i+1]['value']:
                Card[i], Card[i+1] = Card[i+1], Card[i]
                flag = 1
    show(Card, n)
    return Card


def selection_sort(A, n):
    Card = A.copy()
    for i in range(n-1):
        min_j = i
        for j in range(i+1, n):
            if Card[min_j]['value'] > Card[j]['value']:
                min_j = j
        if min_j != i:
            Card[i], Card[min_j] = Card[min_j], Card[i]
    show(Card, n)
    return Card


def main():
    n = int(input())
    A = list(input().split())
    Card = [
        {'value': int(a[1]), 'suit': a[0]}
        for a in A
    ]
    Card_bubble = bubble_sort(Card, n)
    if is_stable(Card, Card_bubble, n):
        print('Stable')
    else:
        print('Not stable')
    Card_selection = selection_sort(Card, n)
    if is_stable(Card, Card_selection, n):
        print('Stable')
    else:
        print('Not stable')


if __name__ == "__main__":
    main()



# Example run
# Input:
1
-513425
# Output:
-5
Stable
-5
Stable
import re
import copy

N = int(input())
list = list(input().split())
pattern = '[DHSC]'

def bubble_sort(N, cards):
  flag = 1
  while flag == 1:
    flag = 0
    for i in range(N - 1, 0, -1):
      if int(re.sub(pattern, '', cards[i])) < int(re.sub(pattern, '', cards[ i - 1])):
        cards[i], cards[i - 1] = cards[i - 1], cards[i]
        flag = 1
  print(' '.join(cards))
  print('Stable')
  return cards

def selection_sort(N, cards):
  for i in range(N):
    minj = i
    for j in range(i, N):
      # print(j)
      if int(re.sub(pattern, '', cards[j])) < int(re.sub(pattern, '', cards[minj])):
        minj = j

    cards[i], cards[minj] = cards[minj], cards[i]

  print(' '.join(cards))
  return cards

bubblelist = bubble_sort(N, copy.deepcopy(list))
selectionlist = selection_sort(N, copy.deepcopy(list))

print('Not stable') if bubblelist != selectionlist else print('Stable')


# Example run
# Input:
-114
nzXv9U
# Output:
nzXv9U
Stable
nzXv9U
Stable
N = int(input())
a = [(s[0], int(s[1])) for s in input().split()]

def bubble(a):
    n = len(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]
    return a

def selection(a):
    n = len(a)
    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

b_a = bubble(a[:])
s_a = selection(a[:])

print(" ".join([p[0]+str(p[1]) for p in b_a]))
print("Stable")
print(" ".join([p[0]+str(p[1]) for p in s_a]))
print("Stable" if b_a==s_a else "Not stable")

# Example run
# Input:
4345
-8164991
# Output:
-8
Stable
-8
Stable
n = int(input())
card_input = list(input().split())

# bubble
card_bubble = card_input.copy()
for i in range(n):
    for j in range(n-1,i,-1):
        if int(card_bubble[j][1])<int(card_bubble[j-1][1]):
            card_bubble[j], card_bubble[j-1] = card_bubble[j-1], card_bubble[j]

# select
card_select = card_input.copy()
for i in range(n):
    mini = i
    for j in range(i,n):
        if  int(card_select[j][1])<int(card_select[mini][1]):
            mini = j
    card_select[mini], card_select[i] = card_select[i], card_select[mini]


    
def output(card):
    string = ''
    for i in card[:-1]:
        string += i + ' '
    string += card[-1]
    print(string)
    
output(card_bubble)
print('Stable')
output(card_select)
if card_bubble==card_select:print('Stable')
else:print('Not stable')


# Example run
# Input:
-755
Ze8P!
# Output:
Ze8P!
Stable
Ze8P!
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:
1
z_LW!F-
# Output:
z_LW!F-
Stable
z_LW!F-
Stable
def bubble_sort(A):
    for i in range(len(A)):
        for j in range(len(A) - 1, i, -1):
            if int(A[j][1]) < int(A[j - 1][1]):
                A[j], A[j - 1] = A[j - 1], A[j]
    return A


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

n = int(input())
A = input().split()
B = bubble_sort(A)
C = selection_sort(A)
print(' '.join(B))
print('Stable')
print(' '.join(C))
if B == C:
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
-1057486868
10366
# Output:
10366
Stable
10366
Stable
N = int(input())
A = list(input().split())
A_copy = A[:]

def bubble_sort(N, A):
  flag = 1
  sorted_index = 0
  while flag:
    flag = 0
    for i in range(N-1, sorted_index, -1):  # N-1からソート済みのインデックス番号まで降順
      if A[i][1] < A[i-1][1]:
        temp = A[i]
        A[i] = A[i-1]
        A[i-1] = temp
        flag = 1
    sorted_index += 1

def selection_sort(N, A):
  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
    if i is not minj:
      temp = A[i]
      A[i] = A[minj]
      A[minj] = temp

bubble_sort(N, A)
selection_sort(N,A_copy)
print(' '.join(map(str, A)))
print('Stable')
print(' '.join(map(str, A_copy)))
if A == A_copy:
  print('Stable')
else:
  print('Not stable')



# Example run
# Input:
-5654
5A|aI
# Output:
5A|aI
Stable
5A|aI
Stable
N = int(input())
A1 = list(map(str,input().split()))
A2 = A1[:]

def bubbleSort(A, N):
 flag = 0
 i = 0
 while flag == 0:
  flag = 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]
    flag = 0
  i += 1
 return A

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

def stable(Ab, As, N):
 for i in range(N):
  if Ab[i] != As[i]:
   return False
 return True

bubbleSort(A1, N)
selectSort(A2, N)
print(" ".join(map(str, A1)))
print("Stable")
print(" ".join(map(str, A2)))
if stable(A1, A2, N):
 print("Stable")
else:
 print("Not stable")

# Example run
# Input:
-2110968
lOdc
# Output:
lOdc
Stable
lOdc
Stable
#70
#ALDS1_2_C
n=int(input())
*temp,=input().split()
a=temp[:]
b=temp[:]
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]

for i in range(n):
    m=i
    for j in range(i,n):
        if b[m][1]>b[j][1]:
            m=j
    if i!=m:
         b[m],b[i]=b[i],b[m]

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


# Example run
# Input:
-28028
9_j
# Output:
9_j
Stable
9_j
Stable
def sep(Nf, Mf):
    mm = [[] for _ in range(9)]
    for m in range(len(Nf)):
        for i in range(9):
            if Nf[m] == i+1:
                mm[i].append(Mf[m])
    return mm


def ssort(L, N, M):
    for i in range(len(N)-1):
        x = N[i+1:].index(min(N[i+1:])) + i + 1
        if N[i] > N[x]:
            L[i], L[x] = L[x], L[i]
            N[i], N[x] = N[x], N[i]
            M[i], M[x] = M[x], M[i]


def bsort(L, N, M):
    for i in range(len(N)-1):
        for j in range(len(N)-1-i):
            if N[j] > N[j+1]:
                L[j], L[j+1] = L[j+1], L[j]
                N[j], N[j+1] = N[j+1], N[j]
                M[j], M[j+1] = M[j+1], M[j]


n = int(input())
L = list(input().split())
N = [int(i[1]) for i in L]
M = [i[0] for i in L]
marks = ['S', 'H', 'C' ,'D']
Lb, Nb, Mb = L[:], N[:], M[:]
bsort(Lb, Nb, Mb)
print(' '.join(Lb))
if sep(N, M) == sep(Nb, Mb):
    print('Stable')
else:
    print('Not stable')

Ls, Ns, Ms = L[:], N[:], M[:]
ssort(Ls, Ns, Ms)
print(' '.join(Ls))
if sep(N, M) == sep(Ns, Ms):
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
-299483
83
# Output:
83
Stable
83
Stable
import copy
n=int(input())
a=list(input().split())
def BubbleSort(l,n):
    a=copy.deepcopy(l)
    for i in range(n):
        for j in reversed(range(i+1,n)):
            if int(a[j][1])<int(a[j-1][1]):
                a[j],a[j-1]=a[j-1],a[j]
    return a

def SelectionSort(l,n):
    a=copy.deepcopy(l)
    for i in range(n):
        minj=i
        for j in range(i,n):
            if int(a[j][1])<int(a[minj][1]):
                minj=j
        a[i],a[minj]=a[minj],a[i]
    return a

def SP(l):
    for i in range(len(l)):
        if i !=len(l)-1:
            print(l[i],end=' ')
        else:
            print(l[i]) 

BS=BubbleSort(a,n)
SS=SelectionSort(a,n)
SP(BS)
print('Stable')
SP(SS)
if BS==SS:
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
-18644718
Vml
# Output:
Vml
Stable
Vml
Stable
import copy 
n = int(input())
#*L, = map(str, input().split())
#L = [int(i) for i in input().split()]
*L, = input().split()

A1 = copy.copy(L)
A2 = copy.copy(L)

def bubble_sort(A,N):
	for i in range(N):
		for j in reversed(range(i+1,N)):
			if int(A[j][1]) < int(A[j-1][1]):
				key = A[j]
				A[j] = A[j-1]
				A[j-1] = key
				#print("b",A)

"""
for i in range(N):
	for j in reversed(range(i+1,N)):
		if int(A[j][1]) < int(A[j-1][1]):
			key = A
			A[j] = A[j][0] + A[j-1][1]
			A[j-1] = key[j-1][0] + key[j][1]
			print(A)
"""


def selection_sort(A,N):
	for i in range(N):
		minj = i
		for j in range(i,N):
			if A[j][1] < A[minj][1]:
				minj = j
		if A[i][1] > A[minj][1]:
			key = A[i]
			A[i] = A[minj]
			A[minj] = key
			#print(A)

"""
def isStable(input,output):
	for i in range(len(inp)):
		if inp[i][1] == oup[i][1] and inp[i][0] != oup[i][0]:
			#print("False")
			return False
		else:
			True
"""



"""
if inp[i][1] == oup[i][1] and inp[i][0] != oup[i][0]:
	print("False")

print(inp[i][1])
print(oup[i][1])
print(inp[i][0])
print(oup[i][0])
"""

bubble_sort(A1,n)
selection_sort(A2,n)

print(*A1)
print("Stable")
print(*A2)
if A1 == A2:
	print("Stable")
else:
	print("Not stable")






# Example run
# Input:
-29082932
P~H
# Output:
P~H
Stable
P~H
Stable
import copy

def Bubble_Sort(n,cards):

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

def Selection_Sort(n,cards):

	for i in range(n):
		mini = i
		for j in range(i,n):
			if int(cards[j][1]) < int(cards[mini][1]):
				mini = j
		cards[i],cards[mini] = cards[mini],cards[i]

def Print_cards(n,cards):

	for i in range(n-1):
		print(f"{cards[i][0]}{cards[i][1]} ",end='')
	print(f"{cards[n-1][0]}{cards[n-1][1]}")


def isStable(n,original,sorted):

	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 int(original[i][1]) == int(original[j][1]) and original[i] == sorted[b] and original[j] == sorted[a]:
						return False

	return True

def test():

	n = int(input())
	cards_original = input().split()
	cards_for_Bubble = copy.deepcopy(cards_original)
	cards_for_Selection = copy.deepcopy(cards_original)

	Bubble_Sort(n,cards_for_Bubble)
	Print_cards(n,cards_for_Bubble)
	if isStable(n,cards_original,cards_for_Bubble) == True:
		print("Stable")
	else:
		print("Not stable")

	Selection_Sort(n,cards_for_Selection)
	Print_cards(n,cards_for_Selection)
	if isStable(n,cards_original,cards_for_Selection) == True:
		print("Stable")
	else:
		print("Not stable")

if __name__ == "__main__":
	test()




# Example run
# Input:
0
4G9
# Output:
4G
Stable
4G
Stable
N = int(input())
A = list(map(lambda x: (x[0],int(x[1])),input().split()))

def BubbleSort(A,N):
    C = [[0,0] for _ in range(N)]
    for i in range(N):
        C[i][0] = A[i][0]
        C[i][1] = A[i][1]
    for i in range(N):
        for j in range(i+1,N)[::-1]:
            if C[j][1] < C[j-1][1]:
                C[j-1],C[j] = C[j],C[j-1]
    return C

def SelectionSort(A,N):
    C = [[0,0] for _ in range(N)]
    for i in range(N):
        C[i][0] = A[i][0]
        C[i][1] = A[i][1]
    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]
    return C

B = BubbleSort(A,N)
S = SelectionSort(A,N)

print(*list(map(lambda x:''.join(map(str,x)),B)))
print('Stable')
print(*list(map(lambda x:''.join(map(str,x)),S)))
print('Stable' if B==S else 'Not stable')


# Example run
# Input:
-52564348
-7737
# Output:

Stable

Stable
def bubble_sort(A, N):
    cnt = 0
    flag = True
    while flag:
        flag = False
        for j in range(N - 1, 0, -1):
            if int(A[j - 1][1]) > int(A[j][1]):
                A[j - 1], A[j] = A[j], A[j - 1]
                flag = True
                cnt += 1
    return A

def selection_sort(A, N):
    cnt = 0
    for i in range(N):
        minj = i
        for j in range(i, N):
            if int(A[j][1]) < int(A[minj][1]):
                minj = j
        A[i], A[minj] = A[minj], A[i]
        if i != minj:
            cnt += 1
    return A

N = int(input())
A = input().split()
order_A = [[] for _ in range(10)]
for s in A:
    order_A[int(s[1])].append(s)

order_bubble = [[] for _ in range(10)]
b_sorted = bubble_sort(A[:], N)
for s in b_sorted:
    order_bubble[int(s[1])].append(s)
print(*b_sorted)
print('Stable' if order_A == order_bubble else 'Not stable')

s_stability = [[] for _ in range(10)]
s_sorted = selection_sort(A[:], N)
for s in s_sorted:
    s_stability[int(s[1])].append(s)
print(*s_sorted)
print('Stable' if order_A == s_stability else 'Not stable')


# Example run
# Input:
-887629
-154
# Output:
-154
Stable
-154
Stable
def bubble_sort(seq):
    for i in range(len(seq)):
        flag = 0
        for j in range(len(seq)-1,i,-1):
            if seq[j-1][1] > seq[j][1]:
                seq[j-1],seq[j] = seq[j],seq[j-1]
                flag = 1
        if flag == 0: break
    return seq


def selection_sort(seq):
    for i in range(len(seq)):
        mini = i
        for j in range(i,len(seq)):
            if seq[mini][1] > seq[j][1]:mini = j
        seq[i],seq[mini] = seq[mini],seq[i]
    return seq



n = int(input())
*seq,= input().split()
seq2 = seq[:]

bl = bubble_sort(seq)
print(*bl)
print("Stable")
sl = selection_sort(seq2)
print(*sl)
if bl == sl:print("Stable")
else:print("Not stable")



# Example run
# Input:
3708297
OX]._
# Output:
OX]._
Stable
OX]._
Stable
# ALDS1_2_C.
# バブルソートと選択ソートの安定性。
from math import sqrt, floor

class card:
    def __init__(self, _str):
        # S3とかH8をもとに初期化。
        self.kind = _str  # 出力用。
        self.suit = _str[0]
        self.value = int(_str[1])

def cardinput():
    # カードの配列からオブジェクトの配列を生成。
    a = input().split()
    cards = []
    for i in range(len(a)):
        cards.append(card(a[i]))
    return cards

def show(a):
    # 配列の中身を出力する。
    _str = ""
    for i in range(len(a) - 1):
        _str += a[i].kind + " "
    _str += a[len(a) - 1].kind
    print(_str)

def bubble_sort(a):
    # aをバブルソートする(交換回数をreturnする)。
    count = 0
    for i in range(1, len(a)):
        k = i - 1
        while k >= 0:
            # a[i]を前の数と交換していき、前の方が小さかったら止める。
            if a[k].value > a[k + 1].value:
                a[k], a[k + 1] = a[k + 1], a[k]
                count += 1
            else: break
            k -= 1
    return count

def selection_sort(a):
    # 選択ソート。その番号以降の最小値を順繰りにもってくる。
    # 交換回数は少ないが比較回数の関係で結局O(n^2)かかる。
    count = 0
    for i in range(len(a)):
        # a[i]からa[len(a) - 1]のうちa[j]が最小っていうjを取る。
        # このときiとjが違うならカウントする。
        # というかa[i]とa[j]が違う時カウントでしたね。
        minj = i
        for j in range(i, len(a)):
            if a[j].value < a[minj].value: minj = j
        if a[i].value > a[minj].value: count += 1; a[i], a[minj] = a[minj], a[i]
    return count

def main():
    N = int(input())
    cards = cardinput()
    # バブルソートは安定。同じvalueなら団子のようにくっつくから。
    # 選択ソートは交換が飛び越えるので不安定。よって、
    # バブルの結果と比較すれば安定か不安定かが分かる。
    _copy = [cards[i] for i in range(N)]

    bubble_sort(cards)
    selection_sort(_copy)

    show(cards)
    print("Stable")
    show(_copy)

    is_stable = True
    for i in range(N):
        for j in range(i + 1, N):
            if _copy[i].value != _copy[j].value: continue
            if _copy[i].suit != cards[i].suit: is_stable = False; break
    if is_stable: print("Stable")
    else: print("Not stable")

if __name__ == "__main__":
    main()


# Example run
# Input:
1
-3108573
# Output:
-3108573
Stable
-3108573
Stable
N = int(input())
A = list(map(str, input().split()))

import copy
A1 = copy.copy(A)
A2 = copy.copy(A)
# バブルソート
flag = 1
while flag:
    flag = 0
    for j in range(N-1, 0, -1):
        if int(A1[j][1]) < int(A1[j-1][1]):
            # A1[j]とA1[j-1]を交換する
            A1[j], A1[j-1] = A1[j-1], A1[j]
            flag = 1    # このフラグは、逆の隣接要素があるかどうかのフラグ
                        # 一回操作したあとはもう一回全体を走査して、逆の隣接要素があるかを確かめる

# セレクションソート
for i in range(0, N):
    minj = i
    for j in range(i, N): # minjを探す
        if int(A2[j][1]) < int(A2[minj][1]): 
            minj = j
    A2[i], A2[minj] = A2[minj], A2[i]

print(*A1)
print('Stable')
print(*A2)

if A1 == A2:
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
-129636061
-m~gdN[/
# Output:
-m~gdN[/
Stable
-m~gdN[/
Stable
def bubble_sort(n, key=0):
    c = 0
    r = [x if isinstance(x, list) else [x] for x in n[:]]
    l = len(r) - 1
    for i in range(0, l):
        for j in range(l, i, -1):
            if r[j][key] < r[j-1][key]:
                r[j], r[j-1] = r[j-1], r[j]
                c += 1
    r = [x[0] if len(x) == 1 else x for x in r]
    return {'list': r, 'count': c}

def selection_sort(n, key=0):
    c = 0
    r = [x if isinstance(x, list) else [x] for x in n[:]]
    l = len(r)
    for i in range(0, l):
        mini = i
        for j in range(i, l):
            if (r[j][key] < r[mini][key]):
                mini = j
        if mini != i:
            r[i], r[mini] = r[mini], r[i]
            c += 1
    r = [x[0] if len(x) == 1 else x for x in r]
    return {'list': r, 'count': c}

def card_format(cards):
    return ' '.join([x[0] + str(x[1]) for x in cards])

if __name__ == '__main__':
    n = int(input())
    c = list(map(list, input().split(' ')))
    c = [[x[0], int(x[1])] for x in c]
    bsc = card_format(bubble_sort(c, 1)['list'])
    ssc = card_format(selection_sort(c, 1)['list'])
    print(bsc)
    print('Stable')
    print(ssc)
    print('Stable' if bsc == ssc else 'Not stable')



# Example run
# Input:
298151
-755
# Output:
-7
Stable
-7
Stable
import copy 

n = int(input())
c = input().split()
c_sel = copy.deepcopy(c)

# check stability of default array
ord_dict_def = {}
for i in range(n) :
    if int(c[i][1]) in ord_dict_def.keys() :
        ord_dict_def[int(c[i][1])] += c[i][0]
    else :
        ord_dict_def[int(c[i][1])] = c[i][0]
        
# do bubble 
for i in range(n) :
    for j in range(n - 1, i, -1) :
        if int(c[j - 1][1]) > int(c[j][1]) :
            c[j - 1], c[j] = c[j], c[j - 1]

# check stability for bubble
ord_dict_bubble = {}

for i in range(n) :
    if int(c[i][1]) in ord_dict_bubble.keys() :
        ord_dict_bubble[int(c[i][1])] += c[i][0]
    else :
        ord_dict_bubble[int(c[i][1])] = c[i][0]
        
# do selection
for i in range(n) :
    cmin = i
    for j in range(i + 1, n) :
        if int(c_sel[j][1]) < int(c_sel[cmin][1]) :
            cmin = j
            
    if i != cmin :
        c_sel[i], c_sel[cmin] = c_sel[cmin], c_sel[i]

# check stability for selection
ord_dict_selection = {}

for i in range(n) :
    if int(c_sel[i][1]) in ord_dict_selection.keys() :
        ord_dict_selection[int(c_sel[i][1])] += c_sel[i][0]
    else :
        ord_dict_selection[int(c_sel[i][1])] = c_sel[i][0]
        
stability_bubble = "Stable"
stability_selection = "Stable"

for i in ord_dict_bubble.keys() :
    if ord_dict_def[i] != ord_dict_bubble[i] :
        stability_bubble = "Not stable"
        
    if ord_dict_def[i] != ord_dict_selection[i] :
        stability_selection = "Not stable"
        
print(" ".join(c))
print(stability_bubble)
print(" ".join(c_sel))
print(stability_selection)


# Example run
# Input:
-30
rX`wLl:
# Output:
rX`wLl:
Stable
rX`wLl:
Stable