Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
def selection(a, n):
    """
    Selection Sort of array a, n=len(a)
    
    配列aｆは参照渡しなのでa自身が変化する（ソートされる）
    """
    cnt = 0
    for i in range(n):
        flag = 0
        minj = i
        for j in range(i+1,n):
            if int(a[j][1]) < int(a[minj][1]):
                minj = j
                flag = 1
        if flag == 1:
            temp = a[minj]
            a[minj] = a[i]
            a[i] = temp
            cnt += 1
    return cnt

def bubble(a, n):
    cnt = 0
    for i in range(n):
        for j in reversed(range(i+1,n)):
            if int(a[j][1]) < int(a[j-1][1]):
                temp = a[j]
                a[j] = a[j-1]
                a[j-1] = temp
                cnt += 1
    return cnt

def print_array(a):
    ans = str(a[0])
    for i in range(1,n):
        ans += ' '+str(a[i])  
    print(ans)

def is_stable(a, b):
    for card1 in range(len(a)):
        for card2 in range(card1+1,len(a)):
            if a[card1][1] == a[card2][1]:
                if b.index(a[card1]) > b.index(a[card2]):
                    return 'Not Stable'
    return 'Stable'

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

bub = a[:]
cnt = bubble(bub, n)   
print_array(bub)
print(is_stable(a, bub))

sel = a[:]
cnt = selection(sel, n)   
print_array(sel)
print(is_stable(a, sel))


# Example run
# Input:
-17880
eGk~W?w|n
# Output:
eGk~W?w|n
Stable
eGk~W?w|n
Stable
N = int(input())
C = input().split()
_C = C.copy()

for i in range(N):
    for j in range(N-1, i, -1):
        if (C[j][1] < C[j-1][1]):
            C[j][1], C[j-1][1] = C[j-1][1], C[j][1]
print(*C)
print("Stable")

for j in range(N):
    m = i
    for j in range(i, N):
        if (_C[j][1] < _C[j-1][1]):
            m = j
    _C[i][1], _C[m][1] = _C[m][1], _C[i][1]
print(*_C)
if(C ==_C):
    print("Stable")
else:
    print("Not stable")

# Example run
# Input:
-1
mY%@Uzn-T
# Output:
mY%@Uzn-T
Stable
mY%@Uzn-T
Stable
import copy

class Cards:
    value = 0
    suit = ""

    def __init__(self,su,val):
        self.suit = su
        self.value = val
    
    def __str__(self):
        return f"{self.suit}{self.value}"

    def __eq__(self,other):
        if not isinstance(other, Cards):
            return NotImplemented
        
        return self.value == other.value and self.suit == other.suit


def cards_stablesort(C):
    lst = copy.deepcopy(C)
    n = len(lst)
    for i in range(1,n):
        j = i
        while(j > 0):
            if lst[j-1].value > lst[j].value:
                lst[j-1],lst[j] = lst[j],lst[j-1] #SWAP
                j -= 1
            else:
                break

    return lst

def cards_bubblesort(C):
    lst = copy.deepcopy(C)
    n = len(lst)

    for i in range(n):
        for j in range(n-1,i,-1):
            if lst[j].value < lst[j-1].value:
                lst[j],lst[j-1] = lst[j-1],lst[j]

    return lst

def cards_selectionsort(C):
    lst = copy.deepcopy(C)
    n = len(lst)

    for i in range(n):
        minj = i

        for j in range(i,n):

            if lst[j].value < lst[minj].value:
                minj = j
        
        lst[i],lst[minj] = lst[minj],lst[i]

    return lst
    


n = int(input())

l = input().split()

C = []
for cd in l:
    C.append(Cards(cd[:1],int(cd[1:])))

stable_list = cards_stablesort(C)
bubble_list = cards_bubblesort(C)
select_list = cards_selectionsort(C)

print(*bubble_list)

if stable_list == bubble_list:
    print("Stable")
else:
    print("Not stable")

print(*select_list)

if stable_list == select_list:
    print("Stable")
else:
    print("Not stable")





# Example run
# Input:
-87
141725276
# Output:
141725276
Stable
141725276
Stable
# -*- coding: utf-8 -*-


def bubbleSort(A, N):

    flag = True  # 未ソートの可能性があるか
    i = 0  # 未ソート部分の先頭
    inv_num = 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
                inv_num += 1
        i += 1

    return A, inv_num


def selectionSort(A, N):
    count = 0

    for i in range(N):

        minj = i
        for j in range(i, N):
            if A[j][1] < A[minj][1]:
                minj = j
        if minj != i:
            count += 1

        A[i], A[minj] = A[minj], A[i]

    return A, count


if __name__ == '__main__':

    N = int(input())
    A = [(a[0], int(a[1])) for a in input().split(" ")]

    A_bubble, _ = bubbleSort(A.copy(), N)
    A_selection, _ = selectionSort(A.copy(), N)

    A_bubble = [a[0] + str(a[1]) for a in A_bubble]
    A_selection = [a[0] + str(a[1]) for a in A_selection]

    print(' '.join(A_bubble))
    print("Stable")
    print(" ".join(A_selection))
    if A_selection == A_bubble:
        print("Stable")
    else:
        print("Not stable")



# Example run
# Input:
-442
1367105004
# Output:
13
Stable
13
Stable
# coding: utf-8
# Here your code !

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

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 i != minj:
            C[i],C[minj] = C[minj],C[i]
    return C


if __name__ == '__main__':
    n = int(input())
    data = input().split()
    selection = data[:]
    print(" ".join(BubbleSort(data,n)))
    print("Stable")
    print(" ".join(SelectionSort(selection,n)))
    if BubbleSort(data,n) == SelectionSort(selection,n):
	    print("Stable")
    else:
	    print("Not Stable")

# Example run
# Input:
-17925
l,k!bg;T>
# Output:
l,k!bg;T>
Stable
l,k!bg;T>
Stable
def print_list(array, N):
    for i in range(N):
        if i == N-1:
            print(array[i])
        else:
            print(array[i], end=" ")
            
def stable_sort(array_a, array, N):
    for i in range(N-1):
        if array[i][1] == array[i+1][1]:
            index_1 = array.index(array[i])
            index_2 = array.index(array[i+1])
            index_a1 = array_a.index(array[i])
            index_a2 = array_a.index(array[i+1])
            #print(index_1, index_2, index_a1, index_a2)
            if index_1 < index_2\
            and index_a1 < index_a2:
                print("Stable")
            else:
                print("Not stable")
                break
        
            
N = int(input())
a = input().split()
b = [s for s in a]
for i in range(N-1):
    for j in range(N-1, i, -1):
        if b[j][1] < b[j-1][1]:
            t = b[j]
            b[j] = b[j-1]
            b[j-1] = t
print_list(b, N)
stable_sort(a, b, N)

c = [s for s in a]
for i in range(N-1):
    min_i = c[i][1]
    change = "no"
    for j in range(i+1, N):
        if min_i > c[j][1]:
            min_i = c[j][1]
            index = c.index(c[j])
            change = "ok"
    if change == "ok":
        t = c[i]
        c[i] = c[index]
        c[index] = t
print_list(c, N)
stable_sort(a, c, N)

# Example run
# Input:
-59158
cQG
# Output:
import copy

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

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

n = int(input())
c = input().split()
c2 = copy.copy(c)

bubble(c,n)
selection(c2,n)
print(" ".join(c))
print("Stable")
print(" ".join(c2))
if c==c2:
    print("Stable")
else:
    print("Not stable")


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

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] を交換
                C[j] , C[j-1] = C[j-1] , C[j]
    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] を交換
        C[i] , C[minj] = C[minj] , C[i]
    ret = " ".join(C)
    print(ret)
    return ret

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



# Example run
# Input:
-758403
85[tBatc
# Output:
85[tBatc
Stable
85[tBatc
Stable
import re

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

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

if __name__ == '__main__':
    #print(list(range(0,5,1)))
    N = int(input())
    A = input()
    C = list(map(int,re.sub(r'\D', ' ', A).split()))
    CC = list(re.sub(r'[^A-Z]', ' ', A).split())
    A = A.split()

    BSA = BubbleSort(C[:],N,A[:])
    print(' '.join(BSA))
    print('Stable')
    SSA = SelectionSort(C[:],N,A[:])
    print(' '.join(SSA))
    print('Stable' if (BSA == SSA) else 'Not stable')
    








# Example run
# Input:
-116671
`Hf
# Output:
`Hf
Stable
`Hf
Stable
def card_encoder(a):
  result = []
  for i in a:
    s = list(map(str,i))
    c_attr = s[0]
    s.pop(0)
    c_num = int(''.join(s))
    result.append([c_attr,c_num])
  return result

def card_encoder2(a):
  result = []
  for i in a:
    s = list(map(str,i))
    s.pop(0)
    c_num = int(''.join(s))
    result.append(c_num)
  return result

def card_decoder(a):
  result = []
  for t in a:
    result.append(t[0] + str(t[1]))
  return result

def bubble_sort(a,n):
  a = card_encoder(a)
  flag = 1
  while flag:
    flag = 0
    for i in range(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
  a = card_decoder(a)
  return a
  
def selection_sort(a,n):
  a = card_encoder(a)
  for i in range(0,n):
    minv = i
    for j in range(i,n):
      if a[j][1] < a[minv][1]:
        minv = j
    if a[i][1] != a[minv][1]:
      temp = a[i]
      a[i] = a[minv]
      a[minv] = temp
  a = card_decoder(a)
  return a

def main():
  num = int(input())
  s = list(input().split())
  bubble1 = bubble_sort(s,num)
  select1 = selection_sort(s,num)
  print(' '.join(bubble1))
  print(is_stable(s,bubble1))
  print(' '.join(select1))
  print(is_stable(s,select1))

def is_stable(a_in, a_out):
  v_in = card_encoder2(a_in)
  n = len(a_in)
  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 v_in[i] == v_in[j] and a_in[i] == a_out[b] and a_in[j] == a_out[a]:
            return 'Not stable'
  return 'Stable'

main()


# Example run
# Input:
-294226159
84
# Output:
84
Stable
84
Stable
import copy
def bubbleSort(A, N):
    cnt = 0
    flag = 1
    while flag:
        flag = 0
        for j in range(N - 1, 0, -1):
            if A[j][1] < A[j - 1][1]:
                A[j], A[j - 1] = A[j - 1], A[j]
                flag = 1
                cnt = cnt + 1
    return cnt


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

def prArr(A, N):
    for i in range(N):
        if i != 0:
            print(" ", end = "")
        print(A[i], end = "")
    print()

    
N = int(input())
A = [i for i in input().split()]
B = copy.deepcopy(A)

bubbleSort(A, N)
selectionSort(B, N)

prArr(A, N)
print("Stable")

prArr(B, N)
print("Stable" if A == B else "Not stable")



# Example run
# Input:
0
A9?b;/#NX
# Output:

Stable

Stable
def BubbleSort(C,n):
	for i in range(n):
		for j in range(i+1,n)[::-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):
	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

def stable(C):
	new = []
	for i in range(1,10):
		Ci = [cc for cc in C if cc[1]==str(i)]
		new += Ci
	return C

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

print(' '.join(BubbleSort(C,n)))
print({True:'Stable',False:'Not stable'}[stable(C)==BubbleSort(C,n)])
print(' '.join(SelectionSort(C,n)))
print({True:'Stable',False:'Not stable'}[stable(C)==SelectionSort(C,n)])

# Example run
# Input:
-7038374
.z0k`S
# Output:
.z0k`S
Stable
.z0k`S
Stable
class Card:
    def __init__(self, name):
        self.name = name
        self.value = int(name[1])
    def __lt__(self, other):
        return self.value < other.value
    def __repr__(self):
        return self.name

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

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

n = int(input())
cards = [Card(s) for s in input().split()]

bubbled_cards = bubble_sort(cards[:], n)
selected_cards = selection_sort(cards[:], n)
print(' '.join(str(s) for s in bubbled_cards))
print('Stable')
print(' '.join(str(s) for s in selected_cards))
if bubbled_cards == selected_cards:
    print('Stable')
else:
    print('Not stable')

# Example run
# Input:
-80
-7517
# Output:
-7517
Stable
-7517
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(str,input().split()))
B = copy.copy(A)

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


# Example run
# Input:
-210
ma;M
# Output:
ma;M
Stable
ma;M
Stable
length = int(input())
eles = [l for l in input().split()]
is_stable = 'Stable'

import copy
_copy = copy.deepcopy(eles)

for i in range(length):
    for j in range(length-1, 0, -1):
        if _copy[j][1] < _copy[j-1][1]:
            _copy[j], _copy[j-1] = _copy[j-1], _copy[j]

print(*_copy)
print(is_stable)

__copy = copy.deepcopy(eles)

for i in range(length-1):
    _min = i
    for l in range(i, length):
        if __copy[l][1] < __copy[_min][1]:
            _min = l
            is_stable = 'Not Stable'
    __copy[i], __copy[_min] = __copy[_min], __copy[i]

print(*__copy)
print(is_stable)

# Example run
# Input:
-10
ayU[S!:U
# Output:
ayU[S!:U
Stable
ayU[S!:U
Stable
n=int(input())
b=input().split()
s=b[:]
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]
    m=i
    for j in range(i,n):
        if s[m][1]>s[j][1]:m=j
    s[m],s[i]=s[i],s[m]
print(*b)
print('Stable')
print(*s)
print(['Not s','S'][b==s]+'table')


# Example run
# Input:
1
+[3a?Sh
# Output:
+[3a?Sh
Stable
+[3a?Sh
Stable
def show(array):
    for i in range(len(array)):
        if (i+1) >= len(array):
            print(array[i])
        else:
            print(array[i], end=' ')


def bubble_sort(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] = c[j-1], c[j]

    return c

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


def main():
    N = int(input())
    cards = list(input().split(' '))
    cards2 = cards.copy()

    # value_sorted = sorted(cards, key=lambda x: x[1:])
    bubble_result = bubble_sort(cards, N)
    print(cards2)
    selection_result = selection_sort(cards2, N)

    show(bubble_result)
    print('Stable')
    show(selection_result)
    if bubble_result == selection_result:
        print('Stable')
    else:
        print('Not stable')


main()


# Example run
# Input:
-1596917
Z9g.
# Output:
['Z9g.']
Z9g.
Stable
Z9g.
Stable
N = int(input())
B = input().split()
S = B[:]

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]
    
    m = i
    for j in range(i, N):
        if S[m][1] > S[j][1]:
            m = j
    S[m], S[i] = S[i], S[m]

print(*B)
print('Stable')
print(*S)
print(['Not s', 'S'][B==S] + 'table')

# Example run
# Input:
-112
{=7
# Output:
{=7
Stable
{=7
Stable
n=int(input())
a=list(map(str,input().split()))
import copy
b=copy.copy(a)
k=copy.copy(a)
for i in range(n):
	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]
for i in range(n):
	mini=i
	for j in range(i,n):
		if int(b[j][1])<int(b[mini][1]):
			mini=j
	b[i],b[mini]=b[mini],b[i]
print(*a)
print("Stable")
print(*b)
r=True
for i in range(n):
	if not r:
		break
	for j in range(i+1,n):
		for aa in range(n):
			for bb in range(aa+1,n):
				if k[i][0]==k[j][0] and k[i]==b[bb] and k[j]==a[aa]:
					r=False
					break
if r==False:
	print("Not stable")
else:
	print("Stable")




# Example run
# Input:
-2031692
`eo2UER
# Output:
`eo2UER
Stable
`eo2UER
Stable
n = int(input())
A = list(input().split())

BS = A[::]
SS = A[::]

#BS
for i in range(0, n):
  for j in range(n-1, i, -1):
    if int(BS[j][1]) < int(BS[j-1][1]):
      BS[j], BS[j-1] = BS[j-1], BS[j]
print(*BS, sep=" ")
print("Stable")

#SS
for i in range(0, n):
  minj = i
  for j in range(i, n):
    if int(SS[j][1]) < int(SS[minj][1]):
      minj = j
  SS[i], SS[minj] = SS[minj], SS[i]
print(*SS, sep=" ")
if SS == BS:
  print("Stable")
else:
  print("Not stable")


# Example run
# Input:
-12762
,MZ0JCNR'
# Output:
,MZ0JCNR'
Stable
,MZ0JCNR'
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:
-10
13637464
# Output:
13637464
Stable
13637464
Stable
N = int(input())
A = list(input().split())

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

def bubble_sort(A, N):
    x = A.copy()
    for i in range(N):
        for j in range(N-1, i, -1):
            if val(x[j]) < val(x[j-1]):
                x[j], x[j-1] = x[j-1], x[j]
    return x

def selection_sort(A, N):
    x = A.copy()
    for i in range(N):
        mini = i
        for j in range(i, N):
            if val(x[j]) < val(x[mini]):
                mini = j
        x[i], x[mini] = x[mini], x[i]
    return x
    
A_bubble = bubble_sort(A, N)
A_selection = selection_sort(A, N)

print(' '.join(map(str, A_bubble)))
print("Stable")
print(' '.join(map(str, A_selection)))
if A_bubble == A_selection:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-452
[85gm4p
# Output:
[85gm4p
Stable
[85gm4p
Stable
n = int(input())
a = input().split()
b = a

for i in range(n):
    for j in range(i + 1, n):
        if int(a[j - 1][1]) > int(a[j][1]):
            tmp = a[j - 1]
            a[j - 1] = a[j]
            a[j] = tmp

ra = " ".join(a)

print(ra)
print("Stable")

for i in range(n - 1):
    minj = i
    for j in (i + 1, n):
        if int(b[j][1]) < int(b[minj][1]):
            minj = j
    if minj != i:
        tmp = b[i]
        b[i] = b[minj]
        b[minj] = tmp

rb = " ".join(b)
print(rb)

if ra == rb:
    print("Stable")
else:
    print("Not Stable")

# Example run
# Input:
-29392
*Lez,
# Output:
*Lez,
Stable
*Lez,
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 = bub = sel = list(map(card,s.split()))  

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)):
    minj = i
    for j in range(i,len(sel)):
        if(sel[j] < sel[minj]):
            minj = j
        tmp = sel[i]
        sel[i] = sel[minj]
        sel[minj] = tmp

            
"""
comp org(org[])
"""

# buble
notStable = 0
for i in range(1,len(bub)):
    if(bub[i-1].num == bub[i].num):
        firstCard = bub[i-1]
        for j in range(0,len(bub)):
            if(org[j].num == firstCard.num):
                if(org[j] == firstCard):
                    pass
                    break
                else:
                    notStable = 1
                    break    
for i in range(0,len(bub)):
    bub[i].display_card()
    if (i==len(bub)-1):
        print("\n",end="")
    else :
        print(" ",end="")
if notStable == 0:
    print("Stable")
else:
    print("Not stable")
# selec
notStable = 0
for i in range(1,len(sel)):
    if(sel[i-1].num == sel[i].num):
        firstCard = sel[i-1]
        for j in range(0,len(sel)):
            if(org[j].num == firstCard.num):
                if(org[j] == firstCard):
                    pass
                    break
                else:
                    notStable = 1
                    break
                
for i in range(0,len(sel)):
    sel[i].display_card()
    if (i==len(sel)-1):
        print("\n",end="")
    else :
        print(" ",end="")
if notStable == 0:
    print("Stable")
else:
    print("Not stable")

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