Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
# coding: utf-8
# Here your code !
n=int(input())
cards=input().split()

def bubble_sort(cards_b,n):
    for i in range(n):
        for j in range(-1,-n,-1):
            a=int(cards_b[j][1])
            b=int(cards_b[j-1][1])
            if a<b:
                cards_b[j],cards_b[j-1]=cards_b[j-1],cards_b[j]
    return cards_b

def selection_sort(cards_s,n):
    for i in range(n):
        minv=i
        for j in range(i,n):
            a=int(cards_s[minv][1])
            b=int(cards_s[j][1])
            if a>b:
                minv=j
        cards_s[minv],cards_s[i]=cards_s[i],cards_s[minv]
    return cards_s


dummy=cards.copy()
ans_1=bubble_sort(cards,n)

ans_2=selection_sort(dummy,n)

print(*ans_1)
print("Stable")
print(*ans_2)
if ans_1!=ans_2:
    print("Not stable")
else:
    print("Stable")

# Example run
# Input:
-40780112
f*R:
# Output:
f*R:
Stable
f*R:
Stable
def bubbleSort(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 0

def selectionSort(b):
  for i in range(len(b)):
    minIndex = i
    for j in range(i+1,len(b)):
      if(int(b[j][1])<int(b[minIndex][1])):
        minIndex = j
        
    b[i],b[minIndex] = b[minIndex],b[i]
    
  return 0
        

n = input()
a = input().split()
b = a[:]

bubbleSort(a)
print(*a)
print("Stable")

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


# Example run
# Input:
bzVvX+;\M
3"Fn!
# Output:
3"Fn!
Stable
3"Fn!
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
        else:
            print("Stable")
            
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:
-765
l"h
# Output:
#!/usr/bin/env python
import copy

def bubble_sort(card, N):
    for i in range(0, N):
        for j in range(N-1, i, -1):
            if value(card[j]) < value(card[j-1]):
                card[j], card[j-1] = card[j-1], card[j]
    return " ".join(map(str, card))


def selection_sort(card, N):
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if value(card[j]) < value(card[minj]):
                minj = j
        card[i], card[minj] = card[minj], card[i]
    return " ".join(map(str, card))


# check method
# insertion sort is a stable sort.
def insertion_sort(card, N):
    for i in range(1, N):
        v = card[i]
        j = i - 1
        while j >= 0 and value(card[j]) > value(v):
            card[j+1] = card[j]
            j -= 1
        card[j+1] = v
    return " ".join(map(str, card))


def value(elem):
    return elem[1]


def main():
    size = int(input())
    line = input().split()
    gold_standard = insertion_sort(copy.deepcopy(line), copy.deepcopy(size))

    bubble_ans = bubble_sort(copy.deepcopy(line), copy.deepcopy(size))
    print(bubble_ans)
    if bubble_ans == gold_standard:
        print('Stable')
    else:
        print('Not stable')

    selection_ans = selection_sort(copy.deepcopy(line), copy.deepcopy(size))
    print(selection_ans)
    if selection_ans == gold_standard:
        print('Stable')
    else:
        print('Not stable')


if __name__ == '__main__':
    main()

# Example run
# Input:
-106
=(B?CZ
# Output:
=(B?CZ
Stable
=(B?CZ
Stable
# -*- coding: utf-8 -*-


def bubble_sort(cards, num):
    for left in range(num-1):
        for right in range(left+1, num):
            if cards[right][1] < cards[left][1]:
                cards[left], cards[right] = cards[right], cards[left]

    print(list_to_str(cards))


def selection_sort(cards, num):
    for head in range(num):
        min_i = head

        for target in range(head+1, num):
            if cards[target][1] < cards[min_i][1]:
                min_i = target
        cards[head], cards[min_i] = cards[min_i], cards[head]

    print(list_to_str(cards))


def is_stable(before, after, num):
    for i in range(num):
        for j in range(i+1, num):
            for a in range(num):
                for b in range(a+1, num):
                    if before[i][1] == before[j][1]\
                    and before[i] == after[b]\
                    and before[j] == after[a]:
                        print('Not stable')
    print('Stable')


def list_to_str(l, delimiter=' '):
    # The default delimiter is one space.
    return delimiter.join([str(v) for v in l])


if __name__ == '__main__':
    num = int(input())
    cards = input().split()
    cards_for_bubble = cards.copy()
    cards_for_selection = cards.copy()

    bubble_sort(cards_for_bubble, num)
    is_stable(cards, cards_for_bubble, num)

    selection_sort(cards_for_selection, num)
    is_stable(cards, cards_for_selection, num)

# Example run
# Input:
-119796
$hF;EkO
# Output:
$hF;EkO
Stable
$hF;EkO
Stable
def cardnum(c):
    cc = list(c)
    return int(cc[1])

def cardlabel(c):
    cc = list(c)
    return cc[0]

def bubleSort(c, n):
    for i in range(n):
        for j in range(n-1, i, -1):
            if cardnum(c[j]) < cardnum(c[j-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 cardnum(c[j]) < cardnum(c[minj]):
                minj = j
        if minj != i:
            (c[i], c[minj]) = (c[minj], c[i])
    return c

def isStable(c1, c0):
    l0 = []
    l1 = []
    for i in range(1, 10):
        for j in range(len(c0)):
            if (cardnum(c0[j])==i):
                l0.append(cardlabel(c0[j]))
            if (cardnum(c1[j])==i):
                l1.append(cardlabel(c1[j]))
#    print(l0)
#    print(l1)
#    print(l0==l1)
    return l0 == l1
     

n = int(input())
cards = input().split()
c1 = cards.copy()
c1ret = bubleSort(c1, n)
print(' '.join(c1ret))
if (isStable(c1ret, cards)):
    print('Stable')
else:
    print('Not stable')

#print(c1, c1ret, cards)

c2 = cards.copy()
c2ret = selectionSort(c2, n)
print(' '.join(c2ret))
if (isStable(c2ret, cards)):
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
-74186
465
# Output:
465
Stable
465
Stable
def bubble(A):
    flag = 1
    n = len(A)
    cnt = 0
    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 += 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
      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:
17852
`(m.
# Output:
`(m.
Stable
`(m.
Stable
def insertionSort(A, N):
    for i in range(1, N):
        v = A[i]
        j = i-1
        while A[j] > v and j >= 0:
            A[j+1], A[j] = A[j], A[j+1]
            j -= 1


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


def bubbleSort_card(C, N):
    flag = 1
    while flag:
        flag = 0
        for j in range(N-1, 0, -1):
            if C[j][1] < C[j-1][1]:
                C[j], C[j-1] = C[j-1], C[j]
                flag = 1

def selectionSort_card(A, N):
    for i in range(N):
        minidx = i
        for j in range(i, N):
            if A[j][1] < A[minidx][1]:
                minidx = j
        A[i], A[minidx] = A[minidx], A[i]

def selectionSort(A, N):
    for i in range(N):
        minidx = i
        for j in range(i, N):
            if A[j] < A[minidx]:
                minidx = j
        A[i], A[minidx] = A[minidx], A[i]


N = int(input())
A = list(input().split())
C = A.copy()
bubbleSort_card(C,N)
selectionSort_card(A,N)
print(" ".join(C))
print('Stable')
print(" ".join(A))
for i in range(N):
    if A[i] != C[i]:
        print('Not stable')
        break
else:
    print('Stable')




# Example run
# Input:
-1
{6v5PUt(
# Output:
{6v5PUt(
Stable
{6v5PUt(
Stable
N = int(input())
A = list(input().split())
B = A[:]

def bubbleSort(A, N):
    flag = 1
    
    while flag:
        flag = 0
        for i in range(N-1, 0, -1):
            if A[i][1] < A[i-1][1]:
                temp = A[i]
                A[i] = A[i-1]
                A[i-1] = temp
                flag = 1
    return " ".join(map(str, A))
    
bubbleSort(A, N)
print(bubbleSort(A, N))
print("Stable")

def selectionSort(A, N):
    for j in range(N):
        C = []
        for i in range(N):
            C.append((A[i][1]))
            
        idx = C[j:].index(min(C[j:])) + j
        
        if A[idx][1] < A[j][1]:
            temp = A[j]
            A[j] = A[idx]
            A[idx] = temp

    return " ".join(map(str, A))

print(selectionSort(B, N))
if bubbleSort(A, N) == selectionSort(B, N):
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-929
tx=.[pSe
# Output:
tx=.[pSe
Stable
tx=.[pSe
Stable
# Stable sort
class Card:
    def __init__(self, c):
        self.suit = c[0]
        self.value = int(c[1])
def toi(c):
    return c.value
def toStr(c):
    return c.suit + str(c.value)
def bubble_sort(C,N):
    for i in range(0, N):
        for j in range(N-1,i,-1):
            if C[j].value < C[j-1].value:
                tmp = C[j]
                C[j] = C[j-1]
                C[j-1] = tmp
    return (C,True)
def selection_sort(C,N):
    st = True
    for i in range(0,N):
        minj = i
        for j in range(i,N):
            # ????????§??????????´??????????????????°??????????????§?????????????????????????????????
            if C[j].value < C[minj].value:
                minj = j
        if not i == minj:
            if (list(map(toi, C[i:]))).count(C[i].value) > 1: st = False
            tmp = C[i]
            C[i] = C[minj]
            C[minj] = tmp
    return (C, st)
N = int(input())
C = [Card(i) for i in input().split(' ')]
C1, isstable1 = bubble_sort(C[:],N)
print(' '.join(list(map(toStr, C1))))
if isstable1: print('Stable')
else: print('Not stable')
C2, isstable2 = selection_sort(C[:],N)
print(' '.join(list(map(toStr, C2))))
if isstable2: print('Stable')
else: print('Not stable')


# Example run
# Input:
-39
669923085
# Output:
66
Stable
66
Stable
def selection_sort(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
        temp = c[i]
        c[i] = c[minj]
        c[minj] = temp
    return c


def bubble_sort(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]):
                temp = c[j]
                c[j] = c[j-1]
                c[j-1] = temp
    return c


def is_stable(a, b):
    for i in range(len(a)):
        if a[i] != b[i]:
            print('Not stable')
            return
    print('Stable')


def main():
    n = int(input())
    nums = input().split(' ')
    bubble_nums = [i for i in nums]
    select_nums = [i for i in nums]
    bubble_nums = bubble_sort(bubble_nums, n)
    select_nums = selection_sort(select_nums, n)

    print(' '.join(bubble_nums))
    print('Stable')
    print(' '.join(select_nums))
    is_stable(bubble_nums, select_nums)


if __name__ == "__main__":
    main()



# Example run
# Input:
-16371
)c6@(1
# Output:
)c6@(1
Stable
)c6@(1
Stable
def selectionSort(n, A):
    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 i != minj:
            A[i], A[minj] = A[minj], A[i]
            cnt += 1
    return A


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


def stableSort(input, output):
    n = len(input)
    for i in range(n):
        for j in range(i + 1, n):
            for a in range(n):
                for b in range(a + 1, n):
                    if input[i][1] == input[j][1] and input[i] == output[b] and input[j] == output[a]:
                        return print("Not stable")
    return print("Stable")


if __name__ == '__main__':
    n = int(input())
    R = list(map(str, input().split()))
    C = R[:]
    D = R[:]  #????????¨?????????
    SR = selectionSort(n, R)
    BR = bubbleSort(n, C)
    print(*BR)
    stableSort(D,BR)
    print(*SR)
    stableSort(D,SR)

# Example run
# Input:
-12142
?H1R!dT
# Output:
?H1R!dT
Stable
?H1R!dT
Stable
def bubble_sort(C, key):
    n = len(C)
    flag = True
    i = 0
    while flag:
        flag = False
        for j in range(n - 1, i, -1):
            if key(C[j]) < key(C[j - 1]):
                C[j - 1], C[j] = C[j], C[j - 1]
                flag = True
        i += 1

def selection_sort(C, key):
    n = len(C)
    for i in range(n):
        minj = i
        for j in range(i, n):
            if key(C[j]) < key(C[minj]):
                minj = j
        if i != minj:
            C[i], C[minj] = C[minj], C[i]

def chk_stable(org_arr, sorted_arr):
    n = len(org_arr)

    org_num_cnt = {}
    for i in range(n):
        num = org_arr[i][1]
        if num in org_num_cnt:
            org_num_cnt[num].append(i)
        else:
            org_num_cnt[num] = [i]

    is_stable = True
    _j = 0
    for i in range(1, n):
        if _j > 0:
            _j -= 1
            continue

        if sorted_arr[i-1][1] == sorted_arr[i][1]:
            idx_list = org_num_cnt[sorted_arr[i][1]]
            for j in range(len(idx_list)):
                if org_arr[idx_list[j]][0] != sorted_arr[i-1+j][0]:
                    is_stable = False
                    break
            _j = len(idx_list)-1
        if not is_stable:
            break

    return is_stable

n = int(input())

A = input().split()
C1 = A[:]
C2 = A[:]

bubble_sort(C1, lambda x: x[1])
print(*C1)
if chk_stable(A, C1) == True:
    print("Stable")
else:
    print("Not stable")

selection_sort(C2, lambda x: x[1])
print(*C2)
if chk_stable(A, C2) == True:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
6534
}iQ
# Output:
}iQ
Stable
}iQ
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] = '''5
H4 C9 S4 D2 C3'''
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 = 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:
-11909
866
# Output:
86
Stable
86
Stable
def BubbleSort(C, N):
    for i in range(0,N):
        for j in range(N-1,i,-1):
            if C[j][1:] < C[j-1][1:]:
                #  C[j] と C[j-1] を交換
                tmp = C[j]
                C[j] = C[j-1]
                C[j-1] = tmp
    ret = " ".join(C)
    print(ret)
    print("stable")
    return ret

def SelectionSort(C, N):
    for i in range(0,N):
        minj = i
        for j in range(i,N):
            if C[j][1:] <= C[minj][1:]:
                minj = j
        # C[i] と C[minj] を交換
        tmp = C[i]
        C[i] = C[minj]
        C[minj] = tmp
    ret = " ".join(C)
    print(ret)
    return ret

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



# Example run
# Input:
0
?HeBTkW0}
# Output:
?HeBTkW0}
stable
?HeBTkW0}
stable
N = int(input())
A = input().split()
A1 = [a for a in A]
A2 = [a for a in A]

# Bubble Sort
flag = True
i = 0
while flag:
    flag = False
    for j in range(1, N - i):
        if int(A1[j][1]) < int(A1[j - 1][1]):
            A1[j - 1], A1[j] = A1[j], A1[j  -1]
            flag = True
    i += 1

print(*A1)
print('Stable')

# Selection Sort
for i in range(N - 1):
    mni = i
    for j in range(i + 1, N):
        if int(A2[j][1]) < int(A2[mni][1]):
            mni = j
    if mni != i:
        A2[i], A2[mni] = A2[mni], A2[i]

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


# Example run
# Input:
-233787
YVxv>z%!
# Output:
YVxv>z%!
Stable
YVxv>z%!
Stable
def BubbleSort(N, C):
    C = [] + C
    for i in range(N):
        for j in range(N-1, i, -1):
            if C[j][1] < C[j-1][1]:
                C[j], C[j-1] = C[j-1], C[j]
    return C

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

def CompareSuit(L1, L2):
    suit1, suit2 = "", ""
    for i in range(len(L1)):
        suit1 = suit1 + L1[i]
        suit2 = suit2 + L2[i]
    if suit1 == suit2:
        return "Stable"
    else:
        return "Not stable"

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

C1 = BubbleSort(N, C)
C2 = SelectionSort(N, C)

print(" ".join(C1))
print(CompareSuit(C1, C1))
print(" ".join(C2))
print(CompareSuit(C1, C2))

# Example run
# Input:
-2610757
El>b{
# Output:
El>b{
Stable
El>b{
Stable
n = int(input())
l = []
for i in input().split():
  t = []
  for j in i: t += [j]
  l += [t]

t = l[:]
f = 0
for i in range(n):
  for j in range(n-1, 0, -1):
    if t[j][1] < t[j-1][1]:
      t[j], t[j-1] = t[j-1], t[j]
    elif t[j][1] == t[j-1][1]:
      f += 1 if l.index(t[j-1]) > l.index(t[j]) else 0
print(*["{0}{1}".format(i[0], i[1]) for i in t])
print("Not stable" if f > 0 else "Stable")

x = l[:]
f = 0
for i in range(n):
  m = i
  for j in range(i, n):
    if x[j][1] < x[m][1]:
      m = j
    elif x[j][1] == x[m][1]:
      f += 1 if l.index(x[j-1]) > l.index(x[j]) else 0
  x[i], x[m] = x[m], x[i]
print(*["{0}{1}".format(i[0], i[1]) for i in x])
print("Not stable" if f > 0 else "Stable")


# Example run
# Input:
-61
f'_no
# Output:
f'
Stable
f'
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][1] < d[j - 1][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][1] < c[minj][1]:
            minj = j
    c[i], c[minj] = c[minj], c[i]

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

# Example run
# Input:
-372018900
AhnEV<
# Output:
AhnEV<
Stable
AhnEV<
Stable
def bubbleSort( cards ):
    n = len( cards )
    for i in range( 0, 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]
 
    print( " ".join( map( str, cards ) ) )
 
def selectionSort( cards ):
	n = len( cards )
	for i in range( 0, n ):
		mini = i
		for j in range( i , n ):
			if int( cards[j][1] ) < int( cards[ mini ][1] ):
				mini = j
		if mini != i:
			cards[i], cards[ mini ] = cards[ mini ], cards[i]

	print( " ".join( map( str, cards ) ) )


n = int( input( ) )
cards = input( ).split( " " )
cards2 = list( cards )
bubbleSort( cards )
print( "Stable" )
selectionSort( cards2 )
if " ".join( map( str, cards2 ) ) == " ".join( map( str, cards ) ):
	print( "Stable" )
else:
	print( "Not stable" )

# Example run
# Input:
-28028
-640183291
# Output:
-640183291
Stable
-640183291
Stable
def bubble_sort(A):
    cnt = 0
    for i in range(0, len(A) - 1):
        for j in range(len(A) - 1, i, -1):
            if A[j][1] < A[j - 1][1]:
                A[j - 1], A[j] = A[j], A[j - 1]
                cnt += 1


def selection_sort(A):
    for i in range(0, len(A)):
        min = i
        for j in range(i + 1, len(A)):
            if A[min][1] > A[j][1]:
                min = j
        A[i], A[min] = A[min], A[i]


def isStable(before, after):
    for i in range(0, len((before))):
        for j in range(i + 1, len(before)):
            for a in range(0, len(after)):
                for b in range(a + 1, len(after)):
                    if before[i][1] == before[j][1]:
                        if before[i] == after[b] and before[j] == after[a]:
                            return False
    return True


if __name__ == '__main__':
    n = int(input())
    l = input().split()
    m = l.copy()
    n = l.copy()
    bubble_sort(m)
    selection_sort(n)
    print(' '.join(m))
    print('Stable' if isStable(l, m) else 'Not stable')
    print(' '.join(n))
    print('Stable' if isStable(l, n) else 'Not stable')



# Example run
# Input:
496
."p~(
# Output:
."p~(
Stable
."p~(
Stable