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



# Example run
# Input:
-1
-3439167
# Output:
-3
Stable
-3
Stable
import copy
def bubble_sort(nums,n):
    flag=1
    while flag:
        flag=0
        for i in range(n-1,0,-1):
            if int(nums[i][1])<int(nums[i-1][1]):
                flag=1
                nums[i],nums[i-1]=nums[i-1],nums[i]

    return nums

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

    return nums

n=int(input())
nums=list(input().split())
nums_2=copy.deepcopy(nums)
b_nums=bubble_sort(nums,n)
s_nums=selection_sort(nums_2,n)

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

        else:
            print(nums[i])

show(b_nums)
print("Stable")
show(s_nums)
if b_nums==s_nums:
    print("Stable")

else:
    print("Not stable")


# Example run
# Input:
-23909
Jq\y`
# Output:
Jq\y`
Stable
Jq\y`
Stable
def is_stable(oline, line):
    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 (oline[i][1] == oline[j][1]) & (oline[i] == line[b]) & (oline[j] == line[a]):
                        return False
    return True

N = int(input())
line = input().split()
oline = line.copy()
#BubbleSort
for i in range(N):
    for j in range(N-1, i, -1):
        if int(line[j][1]) < int(line[j-1][1]):
            tmp = line[j]
            line[j] = line[j-1]
            line[j-1] = tmp
print(' '.join(line))
print(('Not stable', 'Stable')[is_stable(oline, line)])

#SelectionSort
line = oline.copy()
for i in range(N):
    minj = i
    for j in range(i+1, N):
        if int(line[minj][1]) > int(line[j][1]):
            minj = j
    tmp = line[i]
    line[i] = line[minj]
    line[minj] = tmp
print(' '.join(line))

print(('Not stable', 'Stable')[is_stable(oline, line)])

# Example run
# Input:
-256478906
8P!9,=^6j
# Output:
8P!9,=^6j
Stable
8P!9,=^6j
Stable
from copy import deepcopy

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


def bubble_sort(ary):
    for i in range(N):

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


def selection_sort(ary):

    for i in range(0, N):
        minj = i

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

        ary[i], ary[minj] = ary[minj], ary[i]


def naive_check(oary, nary):
    for i in range(1, N - 1):
        for j in range(i + 1, N):
            for a in range(1, N - 1):
                for b in range(a + 1, N):

                    if int(oary[i][1:]) == int(nary[j][1:]):
                        if oary[i] == nary[b]:
                            if oary[j] == nary[a]:
                                return False

    return True


def is_stable(oary, nary):

    if naive_check(oary, nary):
        print('Stable')
    else:
        print('Not stable')


bary = deepcopy(oary)
bubble_sort(bary)
print(' '.join(bary))
print('Stable')
# is_stable(oary, bary)

sary = deepcopy(oary)
selection_sort(sary)
print(' '.join(sary))
if bary == sary:
    print('Stable')
else:
    print('Not stable')
# is_stable(oary, sary)



# Example run
# Input:
-22
LAkU
# Output:
LAkU
Stable
LAkU
Stable
import copy


def bubble_sort(n, A):
    for i in range(n):
        for j in reversed(range(i, n - 1)):
            if A[j + 1][1] < A[j][1]:
                A[j + 1], A[j] = A[j], A[j + 1]
    print(*A)


def selection_sort(n, B):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if B[j][1] < B[minj][1]:
                minj = j
        if minj > i:
            B[i], B[minj] = B[minj], B[i]
    print(*B)


def is_stable(C, S):
    result = "Stable"
    for i in range(1, 10):
        c = [n for n in C if str(i) in n]
        s = [n for n in S if str(i) in n]
        if not c == s:
            result = "Not stable"
            break
    print(result)


n = int(input())
A = input().split()
B = copy.copy(A)
C = copy.copy(A)
bubble_sort(n, A)
is_stable(C, A)
selection_sort(n, B)
is_stable(C, B)




# Example run
# Input:
-2
UKydg
# Output:
UKydg
Stable
UKydg
Stable
def BubbleSort(C, N):
    for i in range(N-1):
        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):
        min_j = i
        for j in range(i+1, N):
            if int(C[j][1]) < int(C[min_j][1]):
                min_j = j
        C[i], C[min_j] = C[min_j], C[i] 
    return C

def isStable(in_list, out_list):
    N = len(in_list)
    for i_in in range(N):
        for j_in in range(i_in+1, N):
            for i_out in range(N):
                for j_out in range(i_out+1, N):
                    if (in_list[i_in][1] == in_list[j_in][1]) and\
                       (in_list[i_in] == out_list[j_out]) and\
                       (in_list[j_in] == out_list[i_out]):
                        return False
    return True

if __name__ == "__main__":
    N = int(input())
    C = list(map(str, input().split()))
    C1 = C.copy()
    C2 = C.copy()
    Bubble_C = BubbleSort(C1, N)
    Selection_C = SelectionSort(C2, N)

    print(*Bubble_C)
    print('Stable')
    print(*Selection_C)
    if Bubble_C == Selection_C:
        print('Stable')
    else:
        print('Not stable')


# Example run
# Input:
-2147483648
xr5
# Output:
xr5
Stable
xr5
Stable
def bubble_sort(cards, n):
    for i in range(n):
        for j in range(n-1, i, -1):
            if cards[j][1] < cards[j-1][1]:
                cards[j], cards[j-1] = cards[j-1], cards[j]

    return cards

def selection_sort(cards, n):
    for i in range(n):
        minj = i

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

        if i != minj:
            cards[i], cards[minj] = cards[minj], cards[i]

    return cards

def is_stable(cards, sorted_cards):
    hashed = {}

    for m, v in cards:
        if v not in hashed:
            hashed[v] = []

        hashed[v].append((m, v))

    for sm, sv in sorted_cards:
        if hashed[sv][0] != (sm, sv):
            return False

        hashed[sv] = hashed[sv][1:]

    return True

def print_cards(cards, sorted_cards):
    print(' '.join([card[0]+str(card[1]) for card in sorted_cards]))

    if is_stable(cards, sorted_cards):
        print('Stable')
    else:
        print('Not stable')

def main():
    n = int(input())
    cards = [(card[0], int(card[1])) for card in input().split()]

    sorted_cards = bubble_sort(cards[:], n)
    print_cards(cards, sorted_cards)

    sorted_cards = selection_sort(cards[:], n)
    print_cards(cards, sorted_cards)

if __name__ == '__main__':
    main()



# Example run
# Input:
-305
-591
# Output:
-5
Stable
-5
Stable
import copy
def BubbleSort(A):
    C = copy.deepcopy(A)
    N = len(A)
    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(A):
    C = copy.deepcopy(A)
    N = len(A)
    for i in range(N):
        min_temp = i
        for j in range(i, N, 1):
            if int(C[j][1]) < int(C[min_temp][1]):
                min_temp = j
        C[min_temp], C[i] = C[i], C[min_temp]
    return C

def isStable(A, B):
    N = len(A)
    M = len(B)
    for i in range(N):
        for j in range(i+1, N, 1):
            for x in range(M):
                for y in range(x+1, M, 1):
                    if A[i][1] == A[j][1] and A[i] == B[y] and A[j] == B[x]:
                        return 'Not stable'
    else:
        return 'Stable'

N = int(input())
cards = input().split()
result1 = ' '.join(BubbleSort(cards))
result2 = ' '.join(SelectionSort(cards))
print(result1)
print(isStable(cards, BubbleSort(cards)))
print(result2)
print(isStable(cards, SelectionSort(cards)))


# Example run
# Input:
-64990941
-12142
# Output:
-12142
Stable
-12142
Stable
num_inputs = int(input())
l_origin = input().split(' ')

flag = True
l_bubble = l_origin[:]
while flag:
    flag = False
    for i in reversed(range(1, num_inputs)):
        if int(l_bubble[i][-1:]) < int(l_bubble[i - 1][-1:]):
            buf = l_bubble[i]
            l_bubble[i] = l_bubble[i - 1]
            l_bubble[i - 1] = buf
            flag = True
print(' '.join(l_bubble))
print('Stable')

l_selection = l_origin[:]
for j in range(num_inputs):
    mink = j
    for k in range(j, num_inputs):
        if int(l_selection[k][-1:]) < int(l_selection[mink][-1:]):
            mink = k
    if mink != j:
        buf = l_selection[j]
        l_selection[j] = l_selection[mink]
        l_selection[mink] = buf
print(' '.join(l_selection))

is_stable = True

for l in range(num_inputs):
    if l_bubble[l] == l_selection[l]:
        pass
    else:
        is_stable = False
        break

if is_stable:
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
-132894
MM)Y7>
# Output:
MM)Y7>
Stable
MM)Y7>
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)

prt = []
for s in bub:
    prt.append(s['str'])
print(*prt)
print(isStable(tar, bub, n))

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

prt = []
for s in bub:
    prt.append(s['str'])
print(*prt)
print(isStable(tar, bub, n))



# Example run
# Input:
1
6=;[C!,
# Output:
6=;[C!,
Stable
6=;[C!,
Stable
#coding: UTF-8

N = int(input())
A = input()
#A = list(map(int, input().split()))
IN1 = [None] * N
IN2 = [None] * N
i=0


for a in A.split():
    tmp = int(a.lstrip("SHCD"))
    IN1[i] = [tmp, i, a]
    IN2[i] = [tmp, i, a]
    i+=1

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

def InsertionSort(A,N):
    for i in range(0,N):
        minj = i
        for j in range(i, N):
            if A[j][0] < A[minj][0]:
                 minj = j
        if i != minj:
            tmp = A[i]
            A[i] = A[minj]
            A[minj] = tmp

def StableCheck(A):
    tmp = [0,0]
    for t in A:
        if(tmp[1] > t[1]):
            if(tmp[0] == t[0]):
                return False
        tmp = t
    return True


BubbleSort(IN1,N)
InsertionSort(IN2,N)

for i in range(N - 1):
    print(IN1[i][2],end=' ')
print(IN1[N - 1][2])
if(StableCheck(IN1)):print("Stable")
else:print("Not stable")

for i in range(N - 1):
    print(IN2[i][2],end=' ')
print(IN2[N - 1][2])
if(StableCheck(IN2)):print("Stable")
else:print("Not stable")

# Example run
# Input:
1
8030667
# Output:
8030667
Stable
8030667
Stable
n = int(input())
a = [i for i in input().split()]
a2 = a.copy()
for i in range(n):
    for j in reversed(range(i+1, n)):
        if a[j][1] < a[j-1][1]:
            a[j], a[j-1] = a[j-1], a[j]
for s in range(n):
    minj = s 
    for t in range(s+1, n):
        if a2[t][1] < a2[minj][1]:
            minj = t
    if a2[s] != a2[minj]:
        a2[s], a2[minj] = a2[minj], a2[s]
print(*a)
print("Stable")
print(*a2)
if a == a2:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
0
fkU
# Output:
fkU
Stable
fkU
Stable
def bubble_sort(A, n):
	flag = 1
	i = 0

	while flag:
		flag = 0
		for j in range(n-1, i, -1):
			if int(A[j][1]) < int(A[j-1][1]):
				A[j], A[j-1] = A[j-1], A[j]
				flag = 1

		i += 1
	
	return A

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

		if i != minj:
			A[i], A[minj] = A[minj], A[i]

	return A

def is_stable(A, B, 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 int(A[i][1]) == int(A[j][1]) and A[i] == B[b] and A[j] == B[a]:
						return False

	return True

def print_stable(flag):
	if flag:
		print('Stable')
	else:
		print('Not stable')

if __name__ == '__main__':
	n = int(input())
	A = list(input().split())
	A2 = A[:]

	B = bubble_sort(A, n)
	print(' '.join(B))
	print_stable(is_stable(A, B, n))

	B = selection_sort(A2, n)
	print(' '.join(B))
	print_stable(is_stable(A, B, n))

# Example run
# Input:
-11
#7f%jC
# Output:
#7f%jC
Stable
#7f%jC
Stable
n = int(input())
cards = input().split()
cards_s, cards_b = cards[:], cards[:]
flag_s, flag_b = False, False
for i in range(n):
    # for Selection Sort
    mini = i
    for j in range(i, n):
        if cards_s[j][1] < cards_s[mini][1]:
            mini = j
    if mini != i:
        cards_s[i], cards_s[mini] = cards_s[mini], cards_s[i]
    # for Bubble Sort    
    for j in range(n-1, i, -1):
        if cards_b[j][1] < cards_b[j-1][1]:
            cards_b[j], cards_b[j-1] = cards_b[j-1], cards_b[j]
for i in range(n-1):
    for j in range(i+1,n):
        # for Selection Sort
        if cards_s[i][1] == cards_s[j][1]:
            flag_s = flag_s or (cards.index(cards_s[i]) > cards.index(cards_s[j]))
        # for Bubble Sort     
        if cards_b[i][1] == cards_b[j][1]:
            flag_b = flag_b or (cards.index(cards_b[i]) > cards.index(cards_b[j]))
# for Bubble Sort 
for i in range(n-1):
    print(cards_b[i], end = ' ')
print(cards_b[n-1])
if flag_b:
    print('Not stable')
else:
    print('Stable')
# for Selection Sort
for i in range(n-1):
    print(cards_s[i], end = ' ')
print(cards_s[n-1])
if flag_s:
    print('Not stable')
else:
    print('Stable')


# Example run
# Input:
0
-+%Exq\|
# Output:
-+%Exq\|
Stable
-+%Exq\|
Stable
def bubble_sort(num_list):
    list_b = num_list[:]
    for i in range(len(list_b)-1):
        for j in range(len(list_b)-1,i,-1):
            if list_b[j][1] < list_b[j-1][1]:
                list_b[j],list_b[j-1] = list_b[j-1],list_b[j]
    return list_b

def selection_sort(num_list):
    list_s = num_list[:]
    for i in range(len(list_s)):
        minj = i
        for j in range(i,len(list_s)):
            if list_s[minj][1] > list_s[j][1]:
                minj = j
        list_s[i],list_s[minj] = list_s[minj],list_s[i]
    return list_s

def isStable(list_x, list_y):
    leng = int(len(list_x))
    for i in range(leng-1):
        for j in range(i+1, leng):
            for x in range(leng-1):
                for y in range(x+1, leng):
                    if list_x[i][1]==list_x[j][1] and list_x[i]==list_y[y] and list_x[j] == list_y[x]:
                        return "Not stable"
    return "Stable"


qnt = int(input())
num_list = input().split()

bs = bubble_sort(num_list)
ss = selection_sort(num_list)
print(" ".join(bs))
print(isStable(num_list,bs))
print(" ".join(ss))
print(isStable(num_list,ss))

# Example run
# Input:
-15220
'hNW
# Output:
'hNW
Stable
'hNW
Stable
N = int(input())
A = [x for x in input().split()]

B = [int(x[1]) for x in A]
C = [x[0] for x in A]
D = [int(x[1]) for x in A]
E = [x[0] for x in A]
F = [int(x[1]) for x in A]
G = [x[0] for x in A]

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

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

def showArray(A, B, N):
    for _ in range(N):
        if _ == N-1:
            print(A[_], sep='', end='')
            print(B[_], sep='', end='')
        else:
            print(A[_], sep='', end='')
            print(B[_], sep='', end=' ')
    print()
    return 0

def isStable(A, B, C, D, N):
    for _ in range(1, 10):
        if A.count(_) > 1:
            if [B[i] for i, x in enumerate(A) if x == _] == [D[i] for i, x in enumerate(C) if x == _]:
                continue
            else:
                return 'Not stable'
    return 'Stable'

if __name__ == '__main__':
    bubbleSort(B, C, N)
    selectionSort(D, E, N)
    
    showArray(C, B, N)
    print(isStable(B, C, F, G, N))
    showArray(E, D, N)
    print(isStable(D, E, F, G, N))


# Example run
# Input:
-117659
-217064188
# Output:

Stable

Stable
def bubble(A):
    #标记是否需要继续冒泡
    flag =True;
    n=len(A)
    i=0
    while flag:
        flag=False
        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=True
        i+=1
 
 
#选择排序法
def selection(A):
    n=len(A)
    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:
            A[i],A[minj]=A[minj],A[i]
             
   
           
n=int(input())
ss=[x for x in input().split()]     
ss2=ss.copy()
 
 
bubble(ss)
for i in range(len(ss)-1):
    print(ss[i],end=' ')
print(ss[-1])
print('Stable')
    
 
selection(ss2)
for i in range(len(ss2)-1):
    print(ss2[i],end=' ')
print(ss2[-1])
if ss==ss2:
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
-105071
cA'IQxN
# Output:
cA'IQxN
Stable
cA'IQxN
Stable
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:] :
                A[j] , A[j-1] = A[j-1] , A[j]
    return A

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
        A[i] , A[minj] = A[minj] , A[i]
    return A

N =int(input())
cards = input().split()
bub , sel =cards[:] , cards[:]
X = bubbleSort(bub , N)
print(*X)
print("Stable")
Y = selectionSort(sel,N)
print(*Y)
print("Stable" if X == Y else "Not stable")

# Example run
# Input:
-5
Ec|
# Output:
Ec|
Stable
Ec|
Stable
#coding:utf-8
#1_2_C

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

def SelectionSort(cards, n):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if cards[minj][1] > cards[j][1]:
                minj = j
        cards[i], cards[minj] = cards[minj], cards[i]
    return cards

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

print(*BubbleSort(cards, n))
print("Stable")
print(*SelectionSort(copy, n))
print("Stable" if cards == copy else "Not stable")

# Example run
# Input:
-14
W1}iQ@j
# Output:
W1}iQ@j
Stable
W1}iQ@j
Stable
class Sort():
	def __init__(self,n,cards):
		self.cards = cards
		self.n = n

	def bubble_sort(self):
		# bubble sort
		flag = 1
		while flag != 0:
			flag = 0
			rev = list(range(1,self.n))
			rev.reverse()
			for j in rev:
				if int(self.cards[j][1]) < int(self.cards[j-1][1]):
					self.cards[j],self.cards[j-1] = self.cards[j-1],self.cards[j]
					flag = 1

	def select_sort(self):
		for i in range(self.n):
			mini = i
			for j in range(i,self.n):
				if int(self.cards[j][1]) < int(self.cards[mini][1]):
					mini = j
			if i != mini:
				self.cards[i],self.cards[mini] = self.cards[mini],self.cards[i]

	def check_stable(self,origin):
		check_org = [["" for i in range(self.n)] for k in range(9)]
		check_sort = [["" for i in range(self.n)] for k in range(9)]
		for i in range(self.n):
			check_org[int(origin[i][1])-1][i] = origin[i][0]
			check_sort[int(self.cards[i][1])-1][i] = self.cards[i][0]
		flag = 0
		for i in range(self.n):
			if "".join(check_org[i]) != "".join(check_sort[i]):
				flag = 1
				break

		if flag == 0:
			print("Stable")
		else:
			print("Not stable")

	def print_card(self):
		for i in range(self.n):
			if i != self.n-1:
				print("%s" % (self.cards[i]),end=" ")
			else:
				print("%s" % (self.cards[i]))

if __name__ == '__main__':
	n = int(input())
	card = input().split()
	card2 = card.copy()
	card_origin = card.copy()
	
	bubble = Sort(n,card)
	bubble.bubble_sort()
	bubble.print_card()
	bubble.check_stable(card_origin)
	
	select = Sort(n,card2)
	select.select_sort()
	select.print_card()
	select.check_stable(card_origin)


# Example run
# Input:
-39355
QV_
# Output:
Stable
Stable
import copy

def print_list(A):
    print(*A, sep=" ")

def swap(a, b):
    return b, a

def val(str):
    return int(str[1])

def is_stable(_in, _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):
                    if val(_in[i]) == val(_in[j]) and _in[i] == _out[b] and _in[j] == _out[a]:
                        return False
    return True

def print_stable(_in, _out, n):
    if is_stable(_in, _out, n):
        print("Stable")
    else:
        print("Not stable")    

def find_minj(A, i, n):
    minj = i
    for j in range(i, n):
        if val(A[j]) < val(A[minj]):
            minj = j
    return minj        

def bubble_sort(A, n):
    A0 = copy.copy(A)
    flg = 1 #逆の隣接要素が存在する
    i = 0
    while flg:
        flg = 0
        for j in range(n-1, i, -1):
            if val(A[j-1]) > val(A[j]):
                A[j-1], A[j] = swap(A[j-1], A[j])
                flg = 1
        i += 1
    print_list(A)
    print_stable(A0, A, n)

def selection_sort(A, n):
    A0 = copy.copy(A)
    for i in range(0, n):
        minj = find_minj(A, i, n)
        if val(A[i]) > val(A[minj]):
            A[i], A[minj] = swap(A[i], A[minj])
    print_list(A)
    print_stable(A0, A, n)

n = int(input())
A = list(map(int,input().split()))
B = copy.copy(A)

bubble_sort(A, n)
selection_sort(B, n)


# Example run
# Input:
-255
2147483647
# Output:
2147483647
Stable
2147483647
Stable