Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
#! /usr/local/bin/python3
# coding: utf-8

def swap(c, i, j):
    t = c[i]
    c[i] = c[j]
    c[j] = t

def bubble_sort(cs, f):
    c = cs[:]
    for i in range(len(c) - 1):
        for j in range(i + 1, len(c)):
            # print(i, j)
            if f(c[i]) > f(c[j]):
                swap(c, i, j)
    return c

def insertion_sort(cs, f):
    c = cs[:]
    for i in range(1, len(c)):
        w = c[i]
        j = i - 1
        while j >= 0 and f(c[j]) > f(w):
            c[j + 1] = c[j]
            j -= 1
        c[j + 1] = w
    return c

def selection_sort(cs, f):
    c = cs[:]
    for i in range(len(c)):
        minj = i
        for j in range(i, len(c)):
            if f(c[j]) < f(c[minj]):
                minj = j
        swap(c, i, minj)
        # print(c)
    return c

def to_group(c):
    b = {}
    for i in c:
        if not(i[1] in b):
            b[i[1]] = [i]
        else:
            b[i[1]] = b[i[1]] + [i]
    return b

def is_stable(c, s): 
    bc = to_group(c)
    bs = to_group(s(c, lambda x: x[1]))
    # print(bc)
    # print(bs)
    for k in bc:
        if bc[k] != bs[k]:
            return "Not stable"
    return "Stable"

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

print(" ".join(bubble_sort(c, lambda x: x[1])))
print(is_stable(c, bubble_sort))

print(" ".join(selection_sort(c, lambda x: x[1])))
print(is_stable(c, selection_sort))


# Example run
# Input:
56
@&1\)C[
# Output:
@&1\)C[
Stable
@&1\)C[
Stable
def bubbleSort(A, N):
    cnt = 0
    flg = True
    while flg:
        flg = False
        for i in range(N - 1):
            if A[i][1] > A[i + 1][1]:
                tmp = A[i]
                A[i] = A[i + 1]
                A[i + 1] = tmp
                flg = True
                cnt += 1
    return A, cnt


def selectionSort(A, N):
    cnt = 0
    for i in range(N):
        minJ = i
        for j in range(i, N):
            if A[minJ][1] > A[j][1]:
                minJ = j
        if A[i][1] != A[minJ][1]:
            tmp = A[i]
            A[i] = A[minJ]
            A[minJ] = tmp
            cnt += 1
    return A, cnt


def resolve():
    import copy
    N = int(input())
    A = [i for i in input().split()]
    B = copy.deepcopy(A)
    ansA, cnt = bubbleSort(A, N)
    print(*ansA)
    print("Stable")
    ansB, cnt = selectionSort(B, N)
    print(*ansB)
    if ansA == ansB:
        print("Stable")
    else:
        print("Not stable")


resolve()



# Example run
# Input:
-5012883
%u7/
# Output:
%u7/
Stable
%u7/
Stable
n = int(input())
*bLst, = input().split()
iLst = bLst[:]

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

print(*bLst)
print("Stable")

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

print(*iLst)
if bLst == iLst:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-686
u]Dspi35v
# Output:
u]Dspi35v
Stable
u]Dspi35v
Stable
def bubbleSort(C1,N):
    for i in range(N):
        for j in range(N-1,i,-1):
            if C1[j][1] < C1[j-1][1]:
                C1[j],C1[j-1] = C1[j-1],C1[j]
    return C1[:]
    
def selectSort(C2,N):
    for i in range(0,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]
    return C2[:]

N = int(input())
C1 = input().split()
C2 = C1[:]

C1 = bubbleSort(C1,N)
C2 = selectSort(C2,N)

print(*C1)
print("Stable")
print(*C2)
if C1 == C2:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-1423
(BCk|{`
# Output:
(BCk|{`
Stable
(BCk|{`
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[:]
    data = BubbleSort(data, n)
#    print(" ".join(BubbleSort(data, n)))
    print(" ".join(data))
    print("Stable")
    selection = SelectionSort(selection, n)
    print(" ".join(selection))
    if data == selection:
        print("Stable")
    else:
        print("Not Stable")

# Example run
# Input:
-21000
/8]
# Output:
/8]
Stable
/8]
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:
            A[i], A[minj] = A[minj], A[i]

    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:]:
                A[j], A[j - 1] = A[j - 1], A[j]

    return A


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

    fStable = SR == BR

    print(*BR)
    print("Stable")
    print(*SR)
    if (fStable == True):
        print("Stable")
    else:
        print("Not stable")


# Example run
# Input:
-21000
/8]
# Output:
/8]
Stable
/8]
Stable
def bubble_sort(A, n):
	for i in range(n):
		for j in range(n-1, i, -1):
			if A[j][1] < A[j-1][1]:
				A[j], A[j-1] = A[j-1], A[j]

	print(' '.join(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

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

	print(' '.join(A))

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

	bubble_sort(A, n)
	print('Stable')

	selection_sort(B, n)
	print('Stable' if A == B else 'Not stable')

# Example run
# Input:
-4
@lUI}r=
# Output:
@lUI}r=
Stable
@lUI}r=
Stable
def bubblesort(n, a):
    r = a[:]
    for i in range(n):
        for j in range(n-1, i, -1):
            if int(r[j][1]) < int(r[j-1][1]):
                r[j], r[j-1] = r[j-1], r[j]

    print(*r)
    print("Stable")


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

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

    print(*r)
    print(ret)


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

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


if __name__ == '__main__':
    main()


# Example run
# Input:
-63063063
9\60Qh=t8
# Output:
9\60Qh=t8
Stable
9\60Qh=t8
Stable
from copy import copy


def bubble_sort(org_A):
    A = copy(org_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(org_A):
    A = copy(org_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:
-12757070
-16
# Output:
-16
Stable
-16
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], C[j-1] = C[j-1], C[j]
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], _C[m] = _C[m], _C[i]
print(*_C)
if(C ==_C):
    print("Stable")
else:
    print("Not stable")

# Example run
# Input:
-208107
rx[akum)
# Output:
rx[akum)
Stable
rx[akum)
Stable
n = int(input())
*A, = input().split()
B = 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]
print(*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(*B)
if A == B:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-58138
F:i
# Output:
F:i
Stable
F:i
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:
-26
!;Qz4_LrU
# Output:
!;Qz4_LrU
Stable
!;Qz4_LrU
Stable
def main():
    N = int(input())
    CARD = tuple(input().split())

    sort_ = []
    for i in range(1, 10):
        for s in CARD:
            if str(i) in s:
                sort_.append(s)

    sort_ = tuple(sort_)
    a = list(CARD)
    bsort = tuple(bubbleSort(a, N))
    ssort = tuple(selectionSort(a, N))

    for s in (bsort, ssort):
        print(*s, sep=' ')
        if s == sort_:
            print('Stable')
        else:
            print('Not stable')

def bubbleSort(c, n):
    flag = 1
    while flag:
        flag = 0
        for i in range(1, n):
            if c[i][1] < c[i-1][1]:
                c[i], c[i-1] = c[i-1], c[i]
                flag = 1
    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

main()

# Example run
# Input:
-568
-30134546
# Output:
-30134546
Not stable
-30134546
Not stable
n = int(input())
s = input()
a = s.split()

def value(a, i):
    return int(a[i][-1])

def isstable(s, a, n):
    for i in range(n - 1):
        if value(a, i) == value(a, i + 1):
            v1 = s.index(a[i])
            v2 = s.index(a[i + 1])
            if v1 > v2:
                return "Not stable"
    return "Stable"

for i in range(n - 1):
    for j in range(i + 1, n)[::-1]:
        if value(a, j) < value(a, j - 1):
            a[j], a[j - 1] = a[j - 1], a[j]
print(" ".join(a))
print(isstable(s.split(), a, n))

a = s.split()

for i in range(n - 1):
    minj = i
    for j in range(i + 1, n):
        if value(a, j) < value(a, minj):
            minj = j
    a[i], a[minj] = a[minj], a[i]
print(" ".join(a))
print(isstable(s.split(), a, n))


# Example run
# Input:
-5559
oo'V
# Output:
oo'V
Stable
oo'V
Stable
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_C&lang=jp
sample_input = list(range(3))
sample_input[0] = '''5
H4 C9 S4 D2 C3'''
sample_input[1] = '''2
S1 H1'''
sample_input[2] = ''''''
give_sample_input = None
if give_sample_input is not None:
    sample_input_list = sample_input[give_sample_input].split('\n')
    def input():
        return sample_input_list.pop(0)
        
# main
import copy

def swap_list_item(lst, i, j):
    tmp = lst[i]
    lst[i] = lst[j]
    lst[j] = tmp
    
class Card:
    number = None
    mark = None
    def __init__(self, str_card):
        self.number = int(str_card[1])
        self.mark = str_card[0]
        pass
    def __eq__(self, other):
        return self.number == other.number
    def __lt__(self, other):
        return self.number < other.number
    def to_str(self):
        return self.mark + str(self.number)

def selection_sort(list_of_data):
    num_of_data = len(list_of_data)
    for i in range(num_of_data):
        minj = i
        for j in range(i, num_of_data):
            if list_of_data[minj] > list_of_data[j]:
                minj = j
        if not minj == i:
            swap_list_item(list_of_data, i, minj)
            
def bubble_sort(list_of_data):
    flag = True
    while flag:
        flag = False
        n = num_of_data - 1
        while n >= 1:
            if list_of_data[n] < list_of_data[n-1]:
                swap_list_item(list_of_data, n, n-1)
                flag = True
            n -= 1
        
def get_mark_order_info(card_list, number):
    result = ''
    for card in card_list:
        if card.number == number:
            result += card.mark
    return result

def print_card_list(card_list):
    output = ''
    for card in card_list:
        output += card.to_str() + ' '
    output.rstrip()
    print(output)

num_of_data = int(input())
data_list_str = input().split()
data_cards = [Card(str) for str in data_list_str]
data_cards_bubble = copy.copy(data_cards)
data_cards_selection = copy.copy(data_cards)

mark_order_info = []
for number in [n+1 for n in range(13)]:
    mark_order_info.append(get_mark_order_info(data_cards, number))
    
bubble_sort(data_cards_bubble)
selection_sort(data_cards_selection)

mark_order_info_bubble = []
for number in [n+1 for n in range(13)]:
    mark_order_info_bubble.append(get_mark_order_info(data_cards_bubble, number))

mark_order_info_selection = []
for number in [n+1 for n in range(13)]:
    mark_order_info_selection.append(get_mark_order_info(data_cards_selection, number))
    
print_card_list(data_cards_bubble)
if (mark_order_info == mark_order_info_bubble):
    print('Stable')
else:
    print('Not Stable')
    
print_card_list(data_cards_selection)
if (mark_order_info == mark_order_info_selection):
    print('Stable')
else:
    print('Not Stable')

# Example run
# Input:
-2701677
-5
# Output:
-5 
Stable
-5 
Stable
def bubbleSort(C, N):
    for i in range(0, N):
        for j in range(i+1, N):
            if int(C[N-j+i][1]) < int(C[N-j+i-1][1]):
                (C[N-j+i], C[N-j+i-1]) = (C[N-j+i-1], C[N-j+i])
    print(" ".join(C))

def selectionSort(C, N):
    count = 0
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if int(C[j][1])<int(C[minj][1]):
                minj = j
        if minj != i:
            (C[i], C[minj]) = (C[minj], C[i])
            count += 1
    print(" ".join(C))

def isStable(C1, C2, N):
    for i in range(N):
        if C1[i] != C2[i]:
            return "Not stable"
    return "Stable"

n = int(input())
card = list(input().split())
card2 = card[:]

bubbleSort(card, n)
print("Stable")
selectionSort(card2, n)
print(isStable(card, card2, n))







# Example run
# Input:
-6098
.x928p?
# Output:
.x928p?
Stable
.x928p?
Stable
def bubble_sort(c, n):
  for i in range(0,n):
    for j in range(n-1,i-1,-1):
      if c[j][1] < c[j-1][1]:
        w = c[j]
        c[j] = c[j-1]
        c[j-1] = w

def selection_sort(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
      w = c[i]
      c[i] = c[minj]
      c[minj] = w


def isStable(inn, 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 inn[i] == inn[j] and inn[i] == out[b] and inn[j] == out[a]:
            return print("Not stable")
  return print("Stable")

n = int(input())
c = list(map(str, input().split()))
before_c = list(c)
bubble_sort(c,n)
print(" ".join(map(str, c)))
isStable(before_c, bubble_sort(c,n), n)
selection_sort(c,n)
print(" ".join(map(str, c)))
isStable(before_c, selection_sort(c,n), n)


# Example run
# Input:
-3
WIDt
# Output:
WIDt
Stable
WIDt
Stable
import copy

n = int(input())
cards = input().split()
#print(cards)
def bubble_sort(cards, n):
    c = copy.copy(cards)
    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
    return c
    
bubble = bubble_sort(cards, n)
#print(cards)
#print(bubble)
print(' '.join(bubble))

def is_stable(o, s):
    for i in range(n - 1):
        if int(s[i][1]) == int(s[i+1][1]):
            if o.index(s[i]) > o.index(s[i+1]):
                return False
    return  True

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


def selection_sort(cards, n):
    c = copy.copy(cards)
    for i in range(n):
        minj = i
        for j in range(i, n):
            if int(c[j][1]) < int(c[minj][1]):
                minj = j
        tmp = c[i]
        c[i] = c[minj]
        c[minj] = tmp
    return c

selection = selection_sort(cards, n)
print(' '.join(selection))

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



# Example run
# Input:
-230914
{=7
# Output:
{=7
Stable
{=7
Stable
def bubble_sort(c, n):
    c = c.copy()
    for i in range(n):
        for j in range(0, n - 1):
            if c[j][1] > c[j + 1][1]:
                c[j], c[j + 1] = c[j + 1], c[j]
    return c


def selection_sort(a, n):
    a = a.copy()
    for i in range(n):
        min_index = i
        for j in range(i, n):
            if a[j][1] < a[min_index][1]:
                min_index = j
        a[i], a[min_index] = a[min_index], a[i]
    return a


def print_list(a):
    print(" ".join([s + v for s, v in a]))


def is_stable(l1, l2):
    def get_original_index(v):
        for i, e in enumerate(l1):
            if v == e:
                return i
        return Exception("bug")

    before = l2[0]
    for e in l2[1:]:
        if before[1] == e[1]:
            # print(before, e)
            bi = get_original_index(before)
            ei = get_original_index(e)
            # print(bi, ei)
            if bi > ei:
                return False
        before = e

    return True


n = int(input())
tmp = input().split()
a = []
for v in tmp:
    a.append((v[0], v[1]))

bs_result = bubble_sort(a, n)
ss_result = selection_sort(a, n)

print_list(bs_result)
if is_stable(a, bs_result):
    print("Stable")
else:
    print("Not stable")

print_list(ss_result)
if is_stable(a, ss_result):
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
-1
Z0JCNR
# Output:
Z0
Stable
Z0
Stable
n = int(input())
a = input().split()
b=a[:]
for i in range(n):
    for j in range(n-1,i,-1):
        if a[j][1]<a[j-1][1]:
            a[j-1],a[j]=a[j],a[j-1]

print(*a)
print('Stable')

for i in range(n):
    min=i
    for j in range(i,n):
        if b[min][1]>b[j][1]:
            min=j
    b[i],b[min]=b[min],b[i]
print(*b)
if a==b:
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
-182
=C>#:pjLk
# Output:
=C>#:pjLk
Stable
=C>#:pjLk
Stable
#coding:utf-8
from copy import deepcopy

n = int(input())
A = list(input().split())
B = deepcopy(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]:
                A[j], A[j-1] = A[j-1], A[j]


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]
        
                
BubbleSort(A,n)
SelectionSort(B,n)
A = " ".join([data for data in A])
B = " ".join([data for data in B])

print(A)
print("Stable")

print(B)
if A == B:
    print("Stable")
else:
    print("No stable")



# Example run
# Input:
-8056
=^6jj+C
# Output:
=^6jj+C
Stable
=^6jj+C
Stable
import re

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:        
            ho = A[i]
            A[i] = A[minj]
            A[minj] = ho
    return A
def bubblesort(A,N):
    flag = 1 
    while flag:
        flag = 0
        for j in range(N-1,0,-1):
           if A[j][1] < A[j-1][1]:
                ho = A[j]
                A[j] = A[j-1]
                A[j-1] = ho
                flag = 1
    return A

n = int(input())
a = [i for i in input().split()]
c = a.copy()
e = a.copy()
b = bubblesort(a,n)
for i in range(len(b)):
    if i == len(b)-1:
        print(b[i])
    else:
        print(b[i],end=' ')            
f = sorted(e, key=lambda x:int((re.search(r"[0-9]+", x)).group(0)))
D = 0
for i in range(len(b)):
    if f[i] != b[i]:
        print('Not stable')
        D = 1
        break
if D == 0:
    print('Stable')
d = selectionSort(c,n)
for i in range(len(d)):
    if i == len(d)-1:
        print(d[i])
    else:
        print(d[i],end=' ')            
D = 0
for i in range(len(d)):
    if f[i] != d[i]:
        print('Not stable')
        D = 1
        break
if D == 0:
    print('Stable')


# Example run
# Input:
-217064188
-237211342
# Output:
-237211342
Stable
-237211342
Stable
def BubbleSort(N, A):
    for i in range(N):
        flag = True
        while flag:
            flag = False
            for j in range(1, N):
                if int(A[j][1]) < int(A[j - 1][1]):
                    A[j], A[j - 1] = A[j - 1], A[j]
                    flag = True


def SelectionSort(N, A):
    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]


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


N = int(input())
A = [str(i) for i in input().split()]


A1 = A.copy()

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

SelectionSort(N, A1)
trace(A1)

same = True
for i in range(N):
    if A[i] != A1[i]:
        same = False
if same:
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
-23909
Jq\y`
# Output:
Jq\y`
Stable
Jq\y`
Stable
class Card:
    def __init__(self):
        self.suit = ""
        self.value = ""

def bubbleSort(C, N):
    flag = 1
    while flag:
        flag = False
        for j in reversed(range(1,N)):
            if C[j][1] < C[j-1][1]:
                C[j],C[j-1] = C[j-1],C[j]
                flag = True

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]

def check(L1,L2):
    if L1 == L2:
        return 'Stable'
    else:
        return 'Not stable'

N = int(input())
C = list(input().split())
from copy import deepcopy
L1 = deepcopy(C)
L2 = deepcopy(C)

bubbleSort(L1,N)
selectionSort(L2,N)

print(*L1)
print('Stable')
print(*L2)
print(check(L1,L2))


# Example run
# Input:
-16329982
Br7-
# Output:
Br7-
Stable
Br7-
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:
1414
869
# Output:
869
Stable
869
Stable
n = int(input())
c = input().split()

d = c[:]

# bubblesort
for i in range(n):
    for j in range(n - 1, i, -1):
        if d[j] < d[j - 1]:
            d[j], d[j - 1] = d[j - 1], d[j]
print(*d)
print("Stable")

# selectionsort
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]

print(*c)
print("Stable" if c == d else "Not stable")

# Example run
# Input:
-1
hd](
# Output:
hd](
Stable
hd](
Stable