Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
import copy

def stable_sort(A: list, N:int) -> list:
    """
    トランプのカードを整列しましょう。ここでは、４つの絵柄(S, H, C, D)と９つの数字(1, 2, ..., 9)から構成される計 36 枚のカードを用います。例えば、ハートの 8 は"H8"、ダイヤの 1 は"D1"と表します。
    バブルソート及び選択ソートのアルゴリズムを用いて、与えられた N 枚のカードをそれらの数字を基準に昇順に整列するプログラムを作成してください。アルゴリズムはそれぞれ以下に示す疑似コードに従うものとします。数列の要素は 0 オリジンで記述されています。
    5
    H4 C9 S4 D2 C3
    """

    def bubble_sort(A: list, N:int) -> list:
        """
        :A[N]: サイズがNの整数型配列。
        :i: 未ソートの部分の先頭を指すループ変数で、配列の先頭から末尾に向かって移動します。
        :j: 未ソートの部分の隣り合う要素を比較するためのループ変数で、Aの末尾であるN-1 から開始しi+1 まで減少します。
        """
        has_finished = True
        i = 0
        count = 0
        while has_finished and len(A) > 1:
            has_finished = False
            for j in reversed(range(i + 1, N)):
                if int(A[j][1]) < int(A[j - 1][1]):
                    # alter position
                    a, b = A[j - 1], A[j]
                    A[j - 1], A[j] = b, a
                    has_finished = True
                    count += 1
            i += 1

        return A

    def selection_sort(A: list, N:int) -> list:
        """
        :A[N]: サイズがNの整数型配列。
        :i: 未ソートの部分の先頭を指すループ変数で、配列の先頭から末尾に向かって移動する。
        :minj: 各ループの処理でi 番目からN-1 番目までの要素で最小のものの位置。j 未ソートの部分から最小値の位置（minj）を探すためのループ変数。
        """
        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
            # alter position
            if i != minj:
                a, b = A[i], A[minj]
                A[i], A[minj] = b, a

        return A

    A_1 = A.copy()
    A_2 = A.copy()
    bubble_result = bubble_sort(A_1, N)
    selection_result = selection_sort(A_2, N)


    return bubble_result, selection_result


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

bubble_result, selection_result = stable_sort(A, N)

print(*bubble_result)
print("Stable")
print(*selection_result)
if bubble_result != selection_result:
    print("Not stable")
else:
    print("Stable")


# Example run
# Input:
-185
L(?J7Ozo
# Output:
L(?J7Ozo
Stable
L(?J7Ozo
Stable
def compare_cards(a, b):
    return a[1] < b[1]

def bubble(C):
    for i in range(len(C)):
        for j in range(len(C) - 1, i, -1):
            if compare_cards(C[j], C[j - 1]):
                C[j], C[j - 1] = C[j -1], C[j]

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

bubbleC = C.copy()

bubble(bubbleC)
print(*C)

# Example run
# Input:
755
&IS)GJ`
# Output:
&IS)GJ`
def BobbleSort(C, N):
    flag = True
    while flag:
        flag = False
        for i in range(N-1,0,-1):
            if C[i-1][1] > C[i][1]:
                C[i-1], C[i] = C[i], C[i-1]
                flag = True
    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]

def Stable(C1, C2, N):
    # Stable なら True
    flag = True
    
    # C2 を並び替え後とする
    for i in range(1, N):
        if C2[i-1][1] == C2[i][1]:
            a = C1.index(C2[i-1])
            b = C1.index(C2[i])
            if a > b:
                flag = False
                break
    
    if flag:
        print("Stable")
    else:
        print("Not stable")
    
N = int(input())
orgC = [x for x in input().split()]
C = orgC.copy()

BobbleSort(C,N)
print(" ".join(C))
Stable(orgC, C, N)

C = orgC.copy()
SelectionSort(C,N)
print(" ".join(C))
Stable(orgC, C, N)


# Example run
# Input:
-16009
Y?|!V2bB
# Output:
Y?|!V2bB
Stable
Y?|!V2bB
Stable
def isStable(before_sort, after_sort):
    num = len(before_sort)
    
    for i in range(0, num-1):
        for j in range(i+1, num):
            for a in range(0, num-1):
                for b in range(a+1, num):
                    if before_sort[i][1] == after_sort[j][1] and \
                       before_sort[i] == after_sort[b] and \
                       before_sort[j] == after_sort[a]:
                        print("i=%d / j=%d / a=%d / b=%d /before=%s / after=%s" % \
                            (i, j, a, b, before_sort[i][1],  after_sort[j][1]))
                        return False
    return True

def isStable2(sorted_data, bubble_sort_data):
    for i in range(0, len(sorted_data)):
        if sorted_data[i] != bubble_sort_data[i]:
            return False
    return True
    
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]

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
        c[i], c[minj] = c[minj], c[i]
    
num = int(input())
data = input().split(' ')

copy_data = data.copy()
BubbleSort(copy_data, num)
print(copy_data)
if isStable(copy_data, copy_data):
    print("Stable")
else:
    print("Not stable")

bubble_sort_data = data.copy()
SelectionSort(bubble_sort_data, num)
print(bubble_sort_data)
if isStable(bubble_sort_data, copy_data):
    print("Stable")
else:
    print("Not stable")

# Example run
# Input:
-27
VI3R
# Output:
['VI3R']
Stable
['VI3R']
Stable
n = int(input())
cards = list(map(str, input().split()))


def bubble(a):
    num = [int(i[1]) for i in a]
    char = [i[0] for i in a]
    for i in range(n):
        for j in range(n-1, i, -1):
            if num[j] < num[j-1]:
                num[j], num[j-1] = num[j-1], num[j]
                char[j], char[j-1] = char[j-1], char[j]
    else:
        a_new = [char[i] + str(num[i]) for i in range(n)]
        return a_new


def selection(a):
    num = [int(i[1]) for i in a]
    char = [i[0] for i in a]
    minj = 0
    stay = True
    same_exi = False
    for i in range(n):
        minj = i
        for j in range(i, n):
            if num[minj] > num[j]:
                minj = j
                if same_exi:
                    stay = False
            if num[i] == num[j]:
                same_exi = True
        else:
            num[i], num[minj] = num[minj], num[i]
            char[i], char[minj] = char[minj], char[i]
    else:
        a_new = [char[i] + str(num[i]) for i in range(n)]
        return a_new, stay


def print_space(li):
    for i in range(len(li)-1):
        print(li[i], end=' ')
    else:
        print(li[-1])



cards_bu = bubble(cards)
cards_sl = selection(cards)

sl_list = cards_sl[0]
sl_stay = cards_sl[1]

print_space(cards_bu)
print('Stable')

print_space(sl_list)
if sl_list == cards_bu:
    print('Stable')
else:
    print('Not stable')
    





# Example run
# Input:
1
-227348
# Output:
-2
Stable
-2
Stable
def main():
    N = int(input())
    A = input().split()
    B = A.copy()
    
    A = BubbleSort(A, N)
    print(*A)
    print('Stable')
    B = SelectionSort(B, N)
    print(*B)
    if A == B:
        print('Stable')
    else:
        print('Not stable')

def BubbleSort(A, N):
    count = 0
    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]
                count += 1
    return A

def SelectionSort(A, N):
    count = 0
    
    for i in range(N):
        mini = i
        for j in range(i,N):
            if A[j][1] < A[mini][1]:
                mini = j
        if A[i][1] > A[mini][1]:
            A[i], A[mini] = A[mini], A[i]
            count += 1
    return A

main()



# Example run
# Input:
1
/YB4tA{A
# Output:
/YB4tA{A
Stable
/YB4tA{A
Stable
n = int(input())
c = input().split();d = c[:]
for i in range(n-1):
    for j in  range(n-i-1):
        if c[j][1] > c[j+1][1]:c[j:j+2]=c[j+1],c[j]
    m = i
    for j in range(i,n):
        if d[m][1]>d[j][1]:m=j
    d[i],d[m]=d[m],d[i]
print(*c);print("Stable")
print(*d);print(["Not s","S"][c==d]+"table")



# Example run
# Input:
-887629
AuCf6uR><
# Output:
AuCf6uR><
Stable
AuCf6uR><
Stable
def SelectionSort(A):
    n = len(A)
    for i in range(n-1):
        mini = i
        for j in range(i+1, n):
            if int(A[j][1]) < int(A[mini][1]):
                mini = j
        if i != mini:
            A[i], A[mini] = A[mini], A[i]
    print(' '.join(A))
    return A

def BubbleSort(A):
    n = len(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]
    print(' '.join(A))
    return A

_ = input()
lines = input().split()
a = BubbleSort(lines.copy())
print('Stable')
b = SelectionSort(lines.copy())
ans = 'Stable' if a == b else 'Not stable'
print(ans)



# Example run
# Input:
wLj^Y8ba
TcL
# Output:
TcL
Stable
TcL
Stable
import copy

n=int(input())
s=input().split(' ')
s1=[]
s2=[]
s1=copy.deepcopy(s)
s2=copy.deepcopy(s)

def Bubble_Sort(n,s1):
	m=0
	flag=1
	while flag:
		flag=0
		for i in range(1,n):
			j=n-i
			if int(s1[j][1])<int(s1[j-1][1]):
				a=s1[j]
				s1[j]=s1[j-1]
				s1[j-1]=a
				m+=1
				flag=1
	b=s1
	return(b)

def Selection_Sort(n,s2):
	m=0
	for i in range(n):
		minj=i
		for j in range(i,n):
			if int(s2[j][1])<int(s2[minj][1]):
				minj=j
		if i!=minj:
			a=s2[minj]
			s2[minj]=s2[i]
			s2[i]=a
			m+=1
	b=s2
	return(b)

s1=Bubble_Sort(n,s1)
s2=Selection_Sort(n,s2)

print(' '.join(s1))
print('stable')
print(' '.join(s2))
if s1==s2:
	print('Stable')
else:
	print('Not stable')


# Example run
# Input:
-887629
AuCf6uR><
# Output:
AuCf6uR><
stable
AuCf6uR><
Stable
# coding: UTF-8

#共通関数と演算
def pprint(numlist):
  print(" ".join(map(str,numlist)))
def greater(s,t):
  if s[1] > t[1]:
    return True
  else:
    return False
def equal(s,t):
  if s[1] == t[1]:
    return True
  else:
    return False
def wasStable(Ans,Initial,N):
  I = Initial.copy()
  for i in range(N-1):
    if equal(Ans[i],Ans[i+1]):
      for x in I:
        if equal(Ans[i],x):
          if(Ans[i][0] != x[0]):
            return False
          else:
            I.remove(x)
            break
  return True
  
#input
N = int(input())
A = input().split()
Initial = A.copy()
B = A.copy()

#バブルソート
count = 0
flag = True
while flag:
  flag = False
  j = N - 1
  while j >= 1:
    if greater(A[j-1],A[j]):
      v = A[j]
      A[j] = A[j-1]
      A[j-1] = v
      flag = True
      count += 1
    j -= 1
pprint(A)
print("Stable")

#選択ソート
count = 0
for i in range(N):
  j=i
  minj=i
  while j<= N-1:
    if greater(B[minj],B[j]):
      minj = j
    j += 1
  if i != minj:
    v=B[i]
    B[i]=B[minj]
    B[minj]=v
    count += 1
    
print(" ".join(map(str,B)))
if wasStable(B,Initial,N):
  ans = "Stable"
else:
  ans = "Not stable"
print(ans)

    



# Example run
# Input:
-58867430
k^S/8NM/
# Output:
k^S/8NM/
Stable
k^S/8NM/
Stable
# 比较冒泡排序和选择排序

def bubble_sort(arr):
    no_swap = True
    #swap_cnt = 0
    for i in range(len(arr), 0, -1):
        if not no_swap:
            break
        for j in range(0, i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                #swap_cnt += 1
            no_swap = True
    #return swap_cnt

def selection_sort(arr):
    #swap_cnt = 0
    for i in range(0, len(arr)):
        min_index = i
        for j in range(i + 1, len(arr)):
            if arr[min_index] > arr[j]:
                min_index = j
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]
            #swap_cnt += 1
    #return swap_cnt

# n^4 method
def is_stable(raw, sort_):
    N = len(raw)
    for i in range(N):
        for j in range(i + 1, N):
            for m in range(N):
                for n in range(m + 1, N):
                    if (raw[i].value == raw[j].value) and (raw[i] == sort_[n]) and (raw[j] == sort_[m]):
                        return 'Not stable'
    return 'Stable'

class Card:
    suit = ''
    value = 0

    def __init__(self, val):
        self.suit = val[0]
        self.value = int(val[1])

    def __lt__(self, rhv):
        return self.value < rhv.value

    def __eq__(self, rhv):
        return self.suit == rhv.suit and self.value == rhv.value

    def __ne__(self, rhv):
        return not (self == rhv)

    def __str__(self):
        return '%s%d'%(self.suit, self.value)

if __name__ == '__main__':
    N = int(input())
    raw = list(map(Card, input().split()))
    arr1 = []
    arr2 = []
    for i in raw:
        arr1.append(i)
        arr2.append(i)
    bubble_sort(arr1)
    result = is_stable(raw, arr1)
    print(' '.join(map(str, arr1)))
    # print('Stable')
    print(result)
    selection_sort(arr2)
    print(' '.join(map(str, arr2)))
    result = is_stable(raw, arr2)
    print(result)
    # for i in range(len(arr1)):
    #     if arr1[i] != arr2[i]:
    #         print('Not stable')
    #         break
    #     if i == len(arr1) - 1:
    #         print('Stable')



# Example run
# Input:
-18103719
55
# Output:
55
Stable
55
Stable
n=int(input())
num_list1=list(map(str,input().split()))
num_list2=[]
input_list=[]

for k in num_list1:
    num_list2.append(k)
    input_list.append(k)


def bubble(num_list):
    i=0
    flag=True
    while flag:
        flag=False
        for j in range(len(num_list)-1,i,-1):
            if int(num_list[j-1][1])>int(num_list[j][1]):
                tmp=num_list[j-1]
                num_list[j-1]=num_list[j]
                num_list[j]=tmp
                flag=True
    return num_list 

def select(num_list):
    for i in range(0,len(num_list)):
        min=i
        for j in range(min+1,len(num_list)):
            if int(num_list[min][1])>int(num_list[j][1]):
                min=j
        tmp=num_list[i]
        num_list[i]=num_list[min]
        num_list[min]=tmp
    return num_list



def stable(input_list,output_list):
    for i in range(0,len(input_list)):
        for j in range(i+1,len(output_list)):
            for k in range(0,len(output_list)):
                for l in range(k+1,len(output_list)):
                    if input_list[i][1]==input_list[j][1] and input_list[i]==output_list[l] and input_list[j]==output_list[k]:
                        return "Not stable"
    return "Stable"

bubble=bubble(num_list1)
select=select(num_list2)


print(" ".join(bubble))
print(stable(input_list,bubble))
print(" ".join(select))
print(stable(input_list,select))


# Example run
# Input:
6
tQHWPR
# Output:
tQHWPR
Stable
tQHWPR
Stable
def bubble(A):
    #标记是否需要继续冒泡
    flag =True;
    n=len(A)
    i=0
    while flag:
        flag=False
        for j in range(n-1,i,-1):
           if A[j][1]<A[j-1][1]:
               A[j],A[j-1]=A[j-1],A[j]
               flag=True
        i+=1


#选择排序法
def selection(A):
    n=len(A)
    for i in range(n):
        minj=i
        for j in range(i,n):
            if A[j][1]<A[minj][1]:
                minj=j
        if i!=minj:
            A[i],A[minj]=A[minj],A[i]
            
  
          
n=int(input())
ss=[x for x in input().split()]     
ss2=ss.copy()


bubble(ss)
for i in range(len(ss)-1):
    print(ss[i],end=' ')
print(ss[-1])
print('Stable')
   

selection(ss2)
for i in range(len(ss2)-1):
    print(ss2[i],end=' ')
print(ss2[-1])
if ss==ss2:
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
7
K$.dV#s;5
# Output:
K$.dV#s;5
Stable
K$.dV#s;5
Stable
def isStable(lis1, lis2):
    ret = True
    for i in range(len(lis1)-1):
        if lis1[i][1] == lis1[i+1][1]:
           ret = lis1[i+1] in lis2[(lis2.index(lis1[i])):]
    return ret
    
N = int(input())
cards = input().split()

B = list(cards)
for i in range(N):
    for j in range(N-1, i, -1):
        if B[j][1] < B[j-1][1]:
            temp = B[j]
            B[j] = B[j-1]
            B[j-1] = temp

print(' '.join(B))
print('Stable' if isStable(B, cards) else 'Not stable')

S = list(cards)
for i in range(N):
    minj = i
    for j in range(i, N):
        if S[j][1] < S[minj][1]:
            minj = j
    temp = S[i]
    S[i] = S[minj]
    S[minj] = temp

print(' '.join(S))
print('Stable' if isStable(S, cards) else 'Not stable')


    

# Example run
# Input:
-84521052
an8/8]u
# Output:
an8/8]u
Stable
an8/8]u
Stable
n = int(input())

cards_b = input().split()
cards_s = list(cards_b)

# BubbleSort
for i in range(n):
    for j in range(n - 1, i, -1):
        if int(cards_b[j][1]) < int(cards_b[j - 1][1]):
            cards_b[j], cards_b[j - 1] = cards_b[j - 1], cards_b[j]

#SelectionSort
for i in range(n):
    min_i = i
    for j in range(i, n):
        if int(cards_s[j][1]) < int(cards_s[min_i][1]):
            min_i = j
    cards_s[i], cards_s[min_i] = cards_s[min_i], cards_s[i]

print(" ".join(cards_b))
print("Stable")
print(" ".join(cards_s))

if cards_b == cards_s:
    print("Stable")
else:
    print("Not stable")

# Example run
# Input:
-54266464
Xg<'3O.+[
# Output:
Xg<'3O.+[
Stable
Xg<'3O.+[
Stable
N = int(input())
lst = list(input().split())
lst2 = []
for i in lst:
    lst2.append(i)

def bubble_sort(lst):

    flag = 1
    while flag:
        flag = 0
        for i in reversed(list(range(1,len(lst)))):
            if int(lst[i-1][1])>int(lst[i][1]):
                lst[i-1],lst[i] = lst[i],lst[i-1]
                flag = 1

    return lst

def selection_sort(lst):


    for i in range(len(lst)):
        min_i = i
        for j in range(i+1,len(lst)):
            if int(lst[j][1]) < int(lst[min_i][1]):
                min_i = j
        lst[i],lst[min_i] = lst[min_i],lst[i]

    return lst

list1 = bubble_sort(lst)
list2 = selection_sort(lst2)

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



# Example run
# Input:
156713
w'<6/6[d
# Output:
w'<6/6[d
Stable
w'<6/6[d
Stable
def bubble_sort(a, n):
  for i in range(0,n):
    for j in range(n-1,i-1,-1):
      if a[j][1] < a[j-1][1]:
        a[j], a[j-1] = a[j-1], a[j]
  return a

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

if __name__ == '__main__':
  n = int(input())
  a = list(map(str, input().split()))
  b = a[:]
  buble = bubble_sort(a,n)
  select = selection_sort(b,n)
  print(" ".join(map(str, buble)))
  print("Stable")
  print(" ".join(map(str, select)))
  if select == buble:
    print("Stable")
  else:
    print("Not stable")


# Example run
# Input:
-16733
XA](k9UI.
# Output:
XA](k9UI.
Stable
XA](k9UI.
Stable
#安定なソート判定
def print_output(_list):
    for index in range(len(_list)):
        if index == len(_list) - 1:
            print(_list[index])
        else:
            print(_list[index],end=' ')

def bubble(_target_list):
    target_list = _target_list.copy()
    for index in range(1, len(target_list)):
        for compare_index in reversed(range(index)):
            if target_list[compare_index + 1][1] < target_list[compare_index][1]:
                target_list[compare_index + 1] ,target_list[compare_index] = target_list[compare_index] ,target_list[compare_index + 1]
            else:            
                break
    return target_list

def selection(_target_list):
    target_list = _target_list.copy()
    for i in range(len(target_list)):
        minj = i
        for j in range(i, len(target_list)):
            if target_list[j][1] < target_list[minj][1]:
                minj = j
        if i != minj:
            target_list[i], target_list[minj] = target_list[minj], target_list[i]
    return target_list

target_length = int(input())
target_list = [x for x in input().split()]

bubble_list = bubble(target_list)
print_output(bubble_list)
print("Stable")
selection_list = selection(target_list)
print_output(selection_list)
if bubble_list == selection_list:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-58867430
k^S/8NM/
# Output:
k^S/8NM/
Stable
k^S/8NM/
Stable
n = int(input())
a1 = list(input().split())
a2 = a1[:]
for i in range(0, n):
    for j in range(1, n-i):
        if int(a2[j][1])<int(a2[j-1][1]):
            a2[j], a2[j-1] = a2[j-1], a2[j]
print (*a2)
print ("Stable")

a3 = a1[:]
for i in range(0, n):
    minj = i
    for j in range(i, n):
        if int(a3[j][1])<int(a3[minj][1]):
            minj = j
    a3[i], a3[minj] = a3[minj], a3[i]
print(*a3)
if a2 == a3:
    print("Stable")
else:
    print("Not stable")
       




# Example run
# Input:
-147113079
KwaL\@l6
# Output:
KwaL\@l6
Stable
KwaL\@l6
Stable
import copy

N = int(input())
A = list(map(str, input().split()))
bub = []
sel = []
bub = copy.copy(A)
sel = copy.copy(A)

# Bubble Sort
for i in range(N - 1, 0, -1):
    for j in range(N - 1, N - i - 1, -1):
        if bub[j][1] < bub[j - 1][1]:
            v = bub[j]
            bub[j] = bub[j - 1]
            bub[j - 1] = v

s_bub = [str(a) for a in bub]
s_bub = " ".join(s_bub)
print(s_bub)
print("Stable")

# Selection Sort
for i in range(N):  # i に、それ以降の最小値を持ってくる
    min_a = sel[i]  # 先頭を最小値として設定
    num = i
    for j in range(i + 1, N):  # 以下for内で、(i, N)における最小値をmin_aに取得
        if min_a[1] > sel[j][1]:
            min_a = sel[j]
            num = j
    if min_a[1] < sel[i][1]:
        sel[num] = sel[i]
        sel[i] = min_a

s_sel = [str(a) for a in sel]
s_sel = " ".join(s_sel)
print(s_sel)

if sel == bub:
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
-30
YQocc[TJS
# Output:
YQocc[TJS
Stable
YQocc[TJS
Stable
def compare_cards(a, b):
    return a[1] < b[1]

def bubble(C):
    for i in range(len(C)):
        for j in range(len(C) - 1, i, -1):
            if compare_cards(C[j], C[j - 1]):
                C[j], C[j - 1] = C[j -1], C[j]

def selection(C):
    for i in range(len(C)):
        mini = i
        for j in range(i, len(C)):
            if compare_cards(C[j], C[mini]):
                mini = j
        C[i], C[mini] = C[mini], C[i]

def check_stable(originC, sortedC):
    for i in range(len(originC) - 1):
        if not compare_cards(sortedC[i], sortedC[i + 1]):
            if originC.index(sortedC[i]) > originC.index(sortedC[i + 1]):
                return 'Not stable'
    return 'Stable'

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

bubbleC = list(C)
selectionC = list(C)

bubble(bubbleC)
selection(selectionC)

print(*bubbleC)
print(check_stable(C, bubbleC))
print(*selectionC)
print(check_stable(C, selectionC))

# Example run
# Input:
6611401
8\G<E[
# Output:
8\G<E[
Stable
8\G<E[
Stable
import copy


def bubbleSort(sort_list, N):

    before = copy.deepcopy(sort_list)

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

    print(' '.join(sort_list))
    print(checkStable(before, sort_list))


def selectionSort(sort_list, N):
    before = copy.deepcopy(sort_list)

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

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

        if minj != i:
            tmp = sort_list[i]
            sort_list[i] = sort_list[minj]
            sort_list[minj] = tmp

    print(' '.join([str(i) for i in sort_list]))
    print(checkStable(before, sort_list))


def checkStable(before_list, sorted_list):

    for val in sorted_list:
        same_list = [
            i for i in sorted_list if (int(val[1]) == int(i[1])) and val != i
        ]
        if len(same_list) == 0:
            continue

        for data in same_list:
            bef = before_list.index(val) - before_list.index(data)
            aft = sorted_list.index(val) - sorted_list.index(data)

            if (bef > 0 and aft < 0) or (bef < 0 and aft > 0):
                return 'Not stable'

    return 'Stable'


if __name__ == "__main__":
    N = int(input())
    sort_list = input().split()

    sort_list2 = copy.deepcopy(sort_list)
    bubbleSort(sort_list, N)
    selectionSort(sort_list2, N)



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