Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
def bubbleSort(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]):
                tmp = A[j]
                A[j] = A[j-1]
                A[j-1] = tmp
                flag = 1
        i += 1
    return A


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

def isStable(ori,sorted):
    for i in range(len(ori)-1):
        for j in range(i+1, len(ori)-1):
            for a in range(len(ori)):
                for b in range(a+1, len(ori)):
                    if ori[i][1] == ori[j][1] and ori[i] == sorted[b] and ori[j] == sorted[a]:
                        return 'Not stable'
    return 'Stable'

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

if __name__ == '__main__':

    N = int(input())

    numbers = input().split(' ')
    n1 = numbers.copy()
    n2 = numbers.copy()

    A = bubbleSort(n1,N)

    output(A)
    print(isStable(numbers,A))

    B = selectionSort(n2,N)

    output(B)
    print(isStable(numbers, B))

# Example run
# Input:
-282811832
d=C>#:p
# Output:
d=C>#:p
Stable
d=C>#:p
Stable
class Card():
    def __init__(self, card):
        self.card = card
        self.mark = card[0]
        self.number = card[1]
        
    def __lt__(self, other):
        if not isinstance(other, Card):
            return NotImplemented
        return self.number < other.number
    
    def __eq__(self, other):
        if not isinstance(other, Card):
            return NotImplemented
        return self.mark == other.mark and self.number == other.number
        
    def __repr__(self):
        return '{}{}'.format(self.mark, self.number)

    def ls_sort(self):
        return


def BubbleSort(target):
    ls = target.copy()
    flag = 1
    while flag:
        flag = 0
        for i in range(len(ls)-1, 0, -1):
            if ls[i] < ls[i-1]:
                ls[i], ls[i-1] = ls[i-1], ls[i]
                flag = 1
    print(' '.join(map(str, ls)))
    return sorted(ls)


def SelectSort(target):
    ls = target.copy()
    for i in range(len(ls)):
        minj = i
        for j in range(i+1, len(ls)):
            if ls[j] < ls[minj]:
                minj = j
        if ls[i] != ls[minj]:
            ls[i], ls[minj] = ls[minj], ls[i]
    
    print(' '.join(map(str, ls)))
    return sorted(ls)


_ = int(input())
l2 =  [Card(i) for i in input().split()]
l2_sort = sorted(l2)

bubble = BubbleSort(l2)
if bubble == l2_sort:
    print('a')
else:
    print('b')

select = SelectSort(l2)
if select == l2_sort:
    print('a')
else:
    print('b')


# Example run
# Input:
-87
>x#!w6b>
# Output:
>x
a
>x
a
import copy
def bubble(box,n):
    for i in range(n):
        p=n-1
        while p!=i:
            if box[p][1]<box[p-1][1]:
                box[p],box[p-1]=box[p-1],box[p]
            p -=1
    return box

def selection(box,n):
    for i in range(n):
        mini=i
        for j in range(i,n):
            if box[j][1]<box[mini][1]:
                mini=j
        if box[i][1]>box[mini][1]:
            box[i],box[mini]=box[mini],box[i]
    return box

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

bubble=bubble(A,n)
print(*A)
print("Stable")
selection=selection(B,n)
print(*B)
print("Stable" if A==B else "Not stable")


# Example run
# Input:
-239
h-dj
# Output:
h-dj
Stable
h-dj
Stable
def print_list(array):
    for i,e in enumerate(array):
        if i == N - 1:
            print(e)
        else:
            print(e, end=" ")

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

def selectionSort():
    for i in range(N):
        min_index = i
        for j in range(i, N):
            if int(B[min_index][1:]) > int(B[j][1:]):
                min_index = j
        if i != min_index:
            w = B[i]; B[i] = B[min_index]; B[min_index] = w

N = int(input())
A = input().split()
B = list(A)
bubbleSort()
print_list(A)
print("Stable")
selectionSort()
print_list(B)
if A == B:
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
-3787895
Bt~,E,/
# Output:
Bt~,E,/ Stable
Bt~,E,/ Stable
def bubble_sort(a, n):
  for i in range(n-1, 0, -1):
    j = i
    while (j < n) and (a[j][1] < a[j-1][1]):
      tmp = a[j-1]
      a[j-1] =  a[j]
      a[j] = tmp
      j += 1
  return a

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

n = int(input())
input1 = input().split()
a = list(input1)
b = a[:]
a = bubble_sort(a, n)
b = selection_sort(b, n)


#*をつけることでタプル（の中に入れた型）として実行が可能になる　タプルはオブジェクトの変更ができない
print(*a)
print("Stable")
print(*b)

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


#a = b[:]とは何か：リストのindexとobjectをまんまコピー
#print(*aとは) タプルとして出力



# Example run
# Input:
-31
6ej=k^S/8
# Output:
6ej=k^S/8
Stable
6ej=k^S/8
Stable
# 配列の宣言
A = []
B = []
C = []

# 文字列の取得と加工
LENGTH =int(input())
A = input().split()
B = A.copy()
C = A.copy()

def bubble (A, LENGTH):
    N = 0
    M = LENGTH - 1
    CHANGE = 0

    while N <= LENGTH -1:
        M = LENGTH - 1
        while M >= N + 1:
            if int(A[M][1:]) < int(A[M-1][1:]):
                tmp = A[M-1]
                A[M-1] = A[M]
                A[M] = tmp
                CHANGE += 1
            M -= 1
        N += 1

    print(" ".join(map(str,A)))
    print("Stable")

def selection (B, LENGTH):
    i = 0
    CHANGE_COUNT = 0

    while i <= LENGTH -1:
        j = i + 1
        mini = i
        while j <= LENGTH -1:
            if int(B[j][1:]) < int(B[mini][1:]):
                mini = j
            j += 1
        if mini != i:
            tmp = B[i]
            B[i] = B[mini]
            B[mini] = tmp
            CHANGE_COUNT += 1
        i += 1

    print(" ".join(map(str,B)))
    if B == C:
        print("Stable")
    else:
        print("Not Stable")

bubble (A, LENGTH)
selection (B, LENGTH)


# Example run
# Input:
-12503953
7.**G\f
# Output:
7.**G\f
Stable
7.**G\f
Stable
def showList(A, N):
    for i in range(N-1):
        print(A[i],end=' ')
    print(A[N-1])

def get_intlist(A):
    list_int = [int(x[1:]) for x in A]
    return list_int 

def bubbleSort(A, N):
    """
    バブルソート
    O(n^2)のアルゴリズム
    """
    B = get_intlist(A)
    flag = 1
    count = 0
    while flag:
        flag = 0
        for i in range(N-1, 0, -1):
            if B[i] < B[i-1]:
                v = A[i]
                A[i] = A[i-1]
                A[i-1] = v

                v = B[i]
                B[i] = B[i-1]
                B[i-1] = v
                flag = 1
    return A

def selectionSort(A, N):
    """
    選択ソート
    O(n^2)のアルゴリズム
    """
    B = get_intlist(A)
    for i in range(N):
        minj = i
        for j in range(i,N):
            if B[j] < B[minj]:
                minj = j
        if minj != i:
            t = B[minj]
            B[minj] = B[i]
            B[i] = t

            t = A[minj]
            A[minj] = A[i]
            A[i] = t
    return A

N = int(input())
A = [x for x in input().split(' ')]
A_ss = A.copy()
bub = bubbleSort(A,N)
showList(bub,N)
print('Stable')
sel = selectionSort(A_ss,N)
showList(sel,N)
if sel == bub:
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
1
-1
# Output:
-1
Stable
-1
Stable
import copy
def selection_sort(A):
    global c
    c=0 
    for i in range(0,len(A)-1):
        selection(A,i)
        
        
    return A

def selection(A,i):
    global c
    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]
    if not A[i]==A[min]:
        c+=1
    
def bubble_sort(A):
    for i in range(0,len(A)-1):
        bubble(A,i)
        
    return A

def bubble(A,i):
    for j in range(0,len(A)-1-i):
        if A[j][1]>A[j+1][1]:
            A[j],A[j+1]=A[j+1],A[j]
            
            
def is_stable(A, B):
    for i in range(len(B) - 1):
        if B[i][1] == B[i + 1][1]:
            if A.index(B[i]) > A.index(B[i + 1]):
                return 'Not stable'
    return 'Stable'



n=int(input())
A=input().split()
A_t=[(i[0],int(i[1])) for i in A]
A_t2=copy.copy(A_t)
B_t=bubble_sort(A_t)
B=[i[0]+str(i[1]) for i in B_t]
print(' '.join(B))
print(is_stable(A_t,B_t))

S_t=selection_sort(A_t2)
S=[i[0]+str(i[1]) for i in S_t]

print(' '.join(S))
print(is_stable(A_t,S_t))


# Example run
# Input:
479
-21519471
# Output:
-2
Stable
-2
Stable
def BubbleSort(C, N):
    for i in range(0, 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(C, N):
    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 C[i][1] != C[minj][1]:
            C[i], C[minj] = C[minj], C[i]
    return C

N = int(input())
C = list(input().split())
C_dash = C.copy()

b = BubbleSort(C, N)
s = SelectionSort(C_dash, N)

print(" ".join(b))
print("Stable")
print(" ".join(s))
if b == s:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-1378702
m)kG*SX
# Output:
m)kG*SX
Stable
m)kG*SX
Stable
def bubble(A0):
    A = A0.copy()
    N = len(A)
    flag = True
    while(flag):
        flag = False
        for i in range(N-1):
            if A[i][1] > A[i+1][1]:
                A[i], A[i+1] = A[i+1], A[i]
                flag = True
    return A

def select(A0):
    A = A0.copy()
    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]
    return A

if __name__ == '__main__':
    N = int(input())
    A = list(map(str, input().split()))
    A_sort = bubble(A)
    print(*A_sort)
    
    flag = True
    for i in range(N-1):
        if A_sort[i][1] == A_sort[i+1][1]:
            if A.index(A_sort[i]) > A.index(A_sort[i+1]):
                flag = False
                break
    if flag:
        print('Stable')
    else:
        print('Not stable')
    
    A_sort = select(A)
    print(*A_sort)
    flag = True
    for i in range(N-1):
        if A_sort[i][1] == A_sort[i+1][1]:
            if A.index(A_sort[i]) > A.index(A_sort[i+1]):
                flag = False
                break

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


# Example run
# Input:
-47889782
50,
# Output:
50,
Stable
50,
Stable
import re


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


def selection_sort(C, N):
    for i in range(N):
        # i ?????????????????¨????????????
        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 is_stable(C, sorted):
    # ????????°???????????????????¨???????????????????????´???????????????????
    c_container = []
    s_container = []
    for i in range(len(C)):
        c_container.append(C[i][0])
        # C ??§ i ????????\?????????????????§????????°????????????????????¢???
        for j in range(i+1, len(C)):
            # ????????°???????????????????????£?????´???
            if C[i][1] == C[j][1]:
                # C ????????????????¨?????????????
                c_container.append(C[j][0])
        # ????????°???????????????????????¨????????´???
        if len(c_container) >= 2:
            # C ??§ i ???????????????????????°?????¨????????°????????????????????¢???
            for k in range(len(sorted)):
                # ????±??????????????????°?????¨????????°???????¨?????????????????????????????????????????????????????´?
                if sorted[k][1] == C[i][1]:
                    s_container.append(sorted[k][0])
            # ??????????????´?????????????????£?????´???
            if c_container != s_container:
                # Not Stable
                return False
        # ?????????????????????
        c_container = []
        s_container = []

    return True


if __name__ == '__main__':
    N = int(input())
    # ??????????????????????????????????????¨?????¨??°?????¨?????????????????????????´?
    cards = input().split()
    C = [[] for i in range(N)]
    for i in range(N):
        # ??????????¨??????¨??°????????????
        symbol_and_num = re.findall(r'(\d+|\D+)', cards[i])
        C[i] = [symbol_and_num[0], int(symbol_and_num[1])]

    # ??????????????????????????????
    bubble_sorted = bubble_sort(C.copy(), N)
    # ?¨??????¨???????????????
    bubble_sorted_cards = [val[0] + str(val[1]) for val in bubble_sorted]
    # ?????????????????????
    print(' '.join(bubble_sorted_cards))
    # stable or not stable
    print('Stable' if is_stable(C, bubble_sorted) else 'Not stable')

    # ?????????????????????
    selection_sorted = selection_sort(C.copy(), N)
    # ?¨??????¨???????????????
    selection_sorted_cards = [val[0] + str(val[1]) for val in selection_sorted]
    # ?????????????????????
    print(' '.join(selection_sorted_cards))
    # stable or not stable
    print('Stable' if is_stable(C, selection_sorted) else 'Not stable')

# Example run
# Input:
0
7<>\;
# Output:

Stable

Stable
N = int(input())
A = [ x for x in input().split(" ")]
orig_A = A[:]

#bubblesort
for i in range(0, 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]

print(*A)
print("Stable")


#selectionsort
for i in range(0, N):
    minj = i
    for j in range(i, N):
        if int(orig_A[j][1]) < int(orig_A[minj][1]):
            minj = j
    orig_A[i], orig_A[minj] = orig_A[minj], orig_A[i]


print(*orig_A)
print("Stable" if A == orig_A else "Not stable")

# Example run
# Input:
0
g>!d1,AY
# Output:
g>!d1,AY
Stable
g>!d1,AY
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(B)
print('Stable')
print(C)
if B == C:
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
21643
-887384
# Output:
['-887384']
Stable
['-887384']
Stable
import copy

def bubble_sort(a, n):
    a = copy.deepcopy(a)
    count = 0
    flag = 1
    
    while flag:
        flag = 0
        
        for j in range(n-1, 0, -1):
            if int(a[j][1]) < int(a[j-1][1]):
                a[j-1], a[j] = a[j], a[j-1]
                flag = 1
                count += 1
                
    return a, count

def selection_sort(a, n):
    a = copy.deepcopy(a)
    
    count = 0
    for i in range(n):
        
        minj = i
        for j in range(i, n):
            if int(a[j][1]) < int(a[minj][1]):
                minj = j
        
        if minj != i:
          count += 1
          a[minj], a[i] = a[i], a[minj]
        
    return a, count

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

bubble_sorted, _ = bubble_sort(a=cards, n=n)
selection_sorted, _ = selection_sort(a=cards, n=n)


print(" ".join(bubble_sorted))
print("Stable")
print(" ".join(selection_sorted))

stable_flag = True
for i in range(n):
    if bubble_sorted[i] != selection_sorted[i]:
      stable_flag = False
      

if stable_flag:
  print("Stable")
else:
  print("Not stable")
    


# Example run
# Input:
-2
4L-)iTg
# Output:
4L-)iTg
Stable
4L-)iTg
Stable
import copy
def bubbleSort(B, N):
    stable = True
    flag = 1
    while flag:
        flag = 0
        for j in range(N-1, 0, -1):
            if B[j][1] < B[j-1][1]:
                if B[j][1] == B[j-1][1] and j != j-1:
                    stable = False

                B[j-1], B[j] = B[j], B[j-1]
                flag = 1

    return B

def selectionSort(S, N):
    stable = True
    for i in range(N):
        minj = i
        for j in range(i,N):
            if S[j][1] < S[minj][1]:
                minj = j
        if S[i][1] == S[minj][1] and i != minj:
            stable = False

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

    return S

N = int(input())
A = list(input().split())
B = A.copy()

out_A = selectionSort(A,N)
out_B = bubbleSort(B,N)

print(" ".join(out_B))
print("Stable")

print(" ".join(out_A))
if out_A == out_B:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-1
hd](
# Output:
hd](
Stable
hd](
Stable
from copy import copy
from collections import defaultdict  

def bubble_sort(collection):
    collection = copy(collection)
    for i in range(len(collection)):
        for j in range(len(collection)-1, i, -1):
            if collection[j] < collection[j-1]:
                collection[j], collection[j-1] = collection[j-1], collection[j]
    return collection
    
def selection_sort(collection):
    collection = copy(collection)
    for i in range(len(collection)):
        mini = i
        for j in range(i, len(collection)):
            if collection[j] < collection[mini]:
                mini = j
        collection[i], collection[mini] = collection[mini], collection[i]
        
    return collection
    
def print_cards(cards):
    for card in cards[:-1]:
        print(card, end=' ')
    print(cards[-1])

def find_card_order(cards):
    duplicate_numbers = defaultdict(list)
    for card in cards:
        duplicate_numbers[card.number].append(card.suit)
    duplicate_numbers = {k: v for k, v in duplicate_numbers.items() if len(v) >= 2}
    return duplicate_numbers



class Card:
    def __init__(self, card):
        self._suit = card[0]
        self._number = int(card[1])
    
    def __str__(self):
        return self.card
    
    def __lt__(self, other):
        return self._number < other._number
        
    @property
    def card(self):
        return self._suit + str(self._number)
    
    @property
    def number(self):
        return self._number
    @property
    def suit(self):
        return self._suit
        
nums_card = int(input())
cards = list(map(Card, input().split()))
duplicate_cards =  find_card_order(cards)
bubble_sorted = bubble_sort(cards)
selection_sorted = selection_sort(cards)


print_cards(bubble_sorted)

stable = 'Stable'
for k, v in duplicate_cards.items():
    sorted_order = [card.suit for card in bubble_sorted if card.number == k]
    if duplicate_cards[k] != sorted_order:
        stable = 'Not stable'
print(stable)

print_cards(selection_sorted)
stable = 'Stable'
for k, v in duplicate_cards.items():
    sorted_order = [card.suit for card in selection_sorted if card.number == k]
    if duplicate_cards[k] != sorted_order:
        stable = 'Not stable'
print(stable)


# Example run
# Input:
-77
17147623
# Output:
17
Stable
17
Stable
# coding: utf-8
import copy
class Card:
    def __init__(self, card, initial):
        self.card = card
        self.mark = card[0]
        self.number = int(card[1])
        self.initial = initial

def bubbleSort(c, n):
    for i in range(n):
        for j in range(n-1, i, -1):
            if c[j].number < c[j-1].number:
                c[j], c[j-1] = c[j-1], c[j]

def selectionSort(c, n):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if c[j].number < c[minj].number:
                minj = j
        c[i], c[minj] = c[minj], c[i]

def printCards(cards, n):
    for i in range(n):
        print(cards[i].card,end="")
        if i == n -1:
            print()
        else:
            print(" ",end="")

def isStable(cards, n):
    for i in range(n-1):
        if cards[i].number == cards[i+1].number and cards[i].initial > cards[i+1].initial:
            return False
    return True

n = int(input().rstrip())
data = input().rstrip().split()
cards = []
for i in range(n):
    cards.append(Card(data[i], i))

init = copy.copy(cards)
bubbleSort(cards, n)
printCards(cards, n)
print("Stable" if isStable(cards, n) else "Not stable")
selectionSort(init, n)
printCards(init, n)
print("Stable" if isStable(init, n) else "Not stable")


# Example run
# Input:
-155785153
<+c9'r
# Output:
Stable
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:
-14500158
NU~
# Output:
NU~
Stable
NU~
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:
-182
-407
# Output:
-407
Stable
-407
Stable
import copy

def show(C):
    N=len(C)
    for i in range(N):
        if i<N-1:
            print(C[i][0]+str(C[i][1]),end=' ')
        else:
            print(C[i][0]+str(C[i][1]))
    
def BubbleSort(C,N):
    for i in range(N):
        for j in reversed(range(i+1,N)):
            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):
        minj=i
        for j in range(i,N):
            if int(C[minj][1])>int(C[j][1]):
                minj=j
        C[i],C[minj]=C[minj],C[i]
    return C

def compare(C1,C2):
    for i in range(1,10):
        l1=[]
        for c in C1:
            if int(c[1])==i:
                l1.append(c)
        l2=[]
        for c in C2:
            if int(c[1])==i:
                l2.append(c)
        for j in range(min(len(l1),len(l2))):
            if l1[j][0]!=l2[j][0]:
                return False
    return True
   
N=int(input())
l=list(input().split())
deck=[]
for c in l:
    deck.append((c[0],c[1]))

deck1=copy.copy(deck)
deck2=copy.copy(deck)

deck1=BubbleSort(deck1,N)
deck2=SelectionSort(deck2,N)

show(deck1)
compare(deck,deck1)
print('Stable' if compare(deck,deck1) else 'Not stable')
show(deck2)
print('Stable' if compare(deck,deck2) else 'Not stable')


# Example run
# Input:
-118998188
-337
# Output:
-3
Stable
-3
Stable