Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
def bubbleSort(A,N):
    for i in range(0,N):
        for j in range(N-1,i,-1):
            if A[j][1] < A[j-1][1]:
                v = A[j]
                A[j] = A[j-1]
                A[j-1] = v
    return A

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

if __name__ == '__main__':
    N = (int)(input())
    A1 = [[x[0],(int)(x[1])] for x in [list(x) for x in input().split()] ]
    A2 = A1.copy()

    resultA1 = bubbleSort(A1,N)
    resultA2 = selectionSort(A2,N)

    outputA1 = ' '.join( [x[0]+(str)(x[1]) for x in resultA1])
    outputA2 = ' '.join( [x[0]+(str)(x[1]) for x in resultA2])

    print(outputA1)
    print("Stable")
    print(outputA2)
    if outputA1 == outputA2 :
        print("Stable")
    else:
        print("Not stable")

# Example run
# Input:
-7606
26622290
# Output:
26
Stable
26
Stable
class Card:
    def __init__(self, suit: str, value: int):
        self.suit = suit
        self.value = value

    def __str__(self):
        return self.suit + self.value


N = int(input())
cards1 = [Card(card[0], card[1]) for card in list(map(str, input().split()))]
cards2 = [*cards1]


def bubbleSort(cards: list, n: int):
    for i in range(n):
        for j in reversed(range(i+1, n)):
            if cards[j-1].value > cards[j].value:
                cards[j-1], cards[j] = cards[j], cards[j-1]
    return cards


def selectionSort(cards: list, n: int):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if cards[minj].value > cards[j].value:
                minj = j
        cards[i], cards[minj] = cards[minj], cards[i]
    return cards


def isStable(cards1: list, cards2: list, n: int):
    for i in range(n):
        if cards1[i].suit != cards2[i].suit:
            return False
    return True


bubbleSort(cards1, N)
selectionSort(cards2, N)
print(*cards1)
print('Stable')
print(*cards2)
print('Stable' if isStable(cards1, cards2, N) else 'Not stable')



# Example run
# Input:
-114886
Crhw
# Output:
Cr
Stable
Cr
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.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:
-58867430
-56661351
# Output:
-5 
Stable
-5 
Stable
# coding: utf-8
# Here your code !
A = int(input())
N = tuple(input().split())
bs=[]
ss=[]
def isStable(a,b):
    leng = int(len(a))
    for i in range(leng):
        for j in range(i+1,leng):
            for x in range(leng):
                for y in range(x+1,leng):
                    if a[i][1]==a[j][1] and a[i]==b[y] and a[j]==b[x]:
                        return "Not stable"
    return "Stable"
    
def bSort(n,a):
    n = list(n)
    for i in range(a):
        for j in range(a-1,i,-1):
            if int(n[j][1]) < int(n[j-1][1]):
                n[j],n[j-1]=n[j-1],n[j]
    return n
    #print(" ".join(n))

    
def seleSort(n,a):
    n = list(n)
    for i in range(a):
        minj = i
        for j in range(i+1,a):
            if n[j][1]<n[minj][1]:
                minj = j
                
        n[i],n[minj]=n[minj],n[i]
    return n
    #print(" ".join(n))

bs = bSort(N,A)
ss = seleSort(N,A)
print(" ".join(bs))
print(isStable(bs,bs))
print(" ".join(ss))
print(isStable(bs,ss))

# Example run
# Input:
-27928965
%MVUC.SD+
# Output:
%MVUC.SD+
Stable
%MVUC.SD+
Stable
from copy import deepcopy

def bubblesort(C,N):
    A = deepcopy(C)
    for i in range(N):
        for j in reversed(range(i+1,N)):
            if int(A[j][1]) < int(A[j-1][1]):
                A[j],A[j-1] = A[j-1],A[j]
    return A

def selectionsort(C,N):
    A = deepcopy(C)
    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]
    return A


def main():
    N = int(input())
    C = list(input().split())
    bs = bubblesort(C,N)
    print(*bs)
    print("Stable")
    ss = selectionsort(C,N)
    print(*ss)
    if bs == ss:
        print("Stable")
    else:
        print("Not stable")

if __name__ == "__main__":
    main()



# Example run
# Input:
-172829
J\S}6A
# Output:
J\S}6A
Stable
J\S}6A
Stable
def BubbleSort(A, N):
    flag = 1
    while flag:
        flag = 0
        for j in reversed(range(1, N)):
            if A[j]['value']<A[j-1]['value']:
                A[j], A[j-1] = A[j-1], A[j]
                flag = 1
    return A

def SelectionSort(A, N):
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if A[i]['value']<A[j]['value']:
                minj = j
        if i!=minj:
            A[i], A[minj] = A[minj], A[i]
    return A

def IsStable(answer, target):
    N = len(answer)
    for i in range(N):
        if answer[i]['value'] != target[i]['value']:
            return False
    return True

# Stable Sort
N = int(input())
A = list(
    map(lambda x: {'body': x, 'value': int(x[1])}, input().split())
)
bubble = BubbleSort(A, N)
selection = SelectionSort(A, N)
print(' '.join(map(lambda x: x['body'],bubble)))
print('Stable')
print(' '.join(map(lambda x: x['body'], selection)))
if IsStable(bubble, selection):
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
-1893070
10823
# Output:
10823
Stable
10823
Stable
def readInt():
  return int(input())


def bubleSort(l, n):
    for i in range(1, n):
        for j in range(n - i):
            if l[j][1] > l[j + 1][1]:
                l[j], l[j + 1] = l[j + 1], l[j]
    return l


def selectionSort(l, n):
    for i in range(n):
        mini = i
        for j in range(i, n):
            if l[j][1] < l[mini][1]:
                mini = j
        l[i], l[mini] = l[mini], l[i]
    return l

def readInts():
  return [int(i) for i in input().split()]
N = readInt()
AS = input().split()

import copy

stable = bubleSort(copy.deepcopy(AS), N)
notstable = selectionSort(AS, N)

print(*stable)
print('Stable')
print(*notstable)
if stable == notstable:
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
-65906
}e^'y?He
# Output:
}e^'y?He
Stable
}e^'y?He
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]:
                        return 'Not stable'
    return '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)
    print(is_stable(cards, cards_for_bubble, num))

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

# Example run
# Input:
-30
dI*Lez,sS
# Output:
dI*Lez,sS
Stable
dI*Lez,sS
Stable
# coding: utf-8

def returnInt(x):
    return int(x[-1])

def bubbleSort(A, N):
    flag = 1
    while flag:
        flag = 0
        for i in range(N - 1, 0, -1):
            if returnInt(A[i]) < returnInt(A[i - 1]):
                A[i], A[i - 1] = A[i - 1], A[i]
                flag = 1
    print(' '.join(A))
    return A

def selectionSort(A, N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if returnInt(A[j]) < returnInt(A[minj]):
                minj = j
        A[i], A[minj] = A[minj], A[i]
    print(' '.join(A))
    return A

if __name__ == "__main__":
    N = int(input())
    A = input().split()
    B = [i for i in A]

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


# Example run
# Input:
-1
xn%P
# Output:
xn%P
Stable
xn%P
Stable
n = int(input())
c = list(input().split())
c1, c2 = c[:], c[:]

def bubbleSort():
  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]

def selectionSort():
  for i in range(n):
    minj = i
    for j in range(i, n):
      if c2[j][-1]<c2[minj][-1]:
        minj = j
    c2[i], c2[minj] = c2[minj], c2[i]

bubbleSort()
selectionSort()
print(" ".join(map(str, c1)))
print("Stable")
print(" ".join(map(str, c2)))
if c1==c2:
  print("Stable")
else:
  print("Not stable")


# Example run
# Input:
-4
C"e
# Output:
C"e
Stable
C"e
Stable
def bubblesort(c, n):
    for i in range(n):
        for j in range(n-1, i, -1):
            if int(c[j][1]) < int(c[j-1][1]):
                c[j], c[j-1] = c[j-1], c[j]
def 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
        c[i], c[minj] = c[minj], c[i]
n = int(input())
a = list(input().split())
b = [i for i in a]
bubblesort(a, n)
selectionsort(b, n)
print(' '.join(a))
print('Stable')
print(' '.join(b))
print('Stable' if a == b else 'Not stable')


# Example run
# Input:
-3843085
d-3D,
# Output:
d-3D,
Stable
d-3D,
Stable
def bubble(A, N):
    flag = True
    while flag:
        flag = False
        for j in range(N-1, 0, -1):
            if int(A[j][-1]) < int(A[j-1][-1]):
                A[j], A[j-1] = A[j-1], A[j]
                flag = True
    return A

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

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

    A_bubble = bubble(A[:], N)
    print (*A_bubble)
    print ("Stable")

    A_selection = selection(A[:], N)
    print (*A_selection)
    if A_bubble == A_selection:
        print ("Stable")
    else:
        print ("Not stable")

# Example run
# Input:
-221907
AuCf6uR><
# Output:
AuCf6uR><
Stable
AuCf6uR><
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 i in range(N):
    m = i
    for j in range(i, N):
        if (_C[j][1] < _C[m][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:
-1759593
.z0k`S
# Output:
.z0k`S
Stable
.z0k`S
Stable
N = int(input())
C1 = list(input().split()) 
C2 = C1[:]

def get_card_suit(card):
    return card[:1]

def get_card_value(card):
    return card[1:]

def bubble_sort(card):
    r_exists = True

    while r_exists == True:

        r_exists = False

        i = N - 1

        while i >= 1:

            if get_card_value(card[i]) < get_card_value(card[i - 1]):
                
                card[i], card[i - 1] = card[i - 1], card[i]

                r_exists = True
            
            i -= 1

def select_sort(card):
    i = 0

    while i < N:

        min_j = i
        j = i

        while j < N:

            if get_card_value(card[j]) < get_card_value(card[min_j]):

                min_j = j

            j += 1

        card[i], card[min_j] = card[min_j], card[i]

        i += 1

def output(card):
    s = ''

    for x in card:

        s = s + str(x) + ' '

    print(s.rstrip())

def is_stable():
    i = 0

    while i < N:
        if get_card_suit(C1[i]) != get_card_suit(C2[i]):
            return False
        i += 1
    
    return True

bubble_sort(C1)
select_sort(C2)

output(C1)
print('Stable')

output(C2)
if is_stable() == True:
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
-23909
Jq\y`
# Output:
Jq\y`
Stable
Jq\y`
Stable
def selection(l):
	N = len(l)

	for i in range(N):
		minj = i

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

	return l


def bubble(l):
	N = len(l)
	flag = 1

	while flag:
		flag = 0
		for j in range(N - 1, 1 - 1, -1):
			if int(l[j][1]) < int(l[j - 1][1]):
				l[j], l[j + 1] = l[j + 1], l[j]
				flag = 0

	return l


def output(lists):
	count = 0
	leng = len(l)
	for i in l:
		count += 1
		if count < leng:
			print(i, end =' ')
		else:
			print(i)




if __name__ == '__main__':
	n = int(input())
	l = input().split()
	l_1 = bubble(l)
	l_2 = selection(l)
	output(l_1)
	print("Stable")
	output(l_2)
	if l_1 == l_2:
		print("Stable")
	else:
		prin("Not stable")



# Example run
# Input:
42339391
-80
# Output:
-80
Stable
-80
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):
    mj = i
    for j in range(i, n):
        if B[j][1] < B[mj][1]:
            mj = j
    B[i], B[mj] = B[mj], B[i]
print(*B)
if A == B:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-54544899
Sz50Gg>x
# Output:
Sz50Gg>x
Stable
Sz50Gg>x
Stable
def bubble_sort(card, n):
    flag = 1
    while flag:
        flag = 0
        for i in range(n-1, 0, -1):
            if card[i][1] < card[i-1][1]:
                card[i], card[i-1] = card[i-1], card[i]
                flag = 1
    print(' '.join(map(str, card)))
    return card

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

    print(' '.join(map(str, card)))
    return card

def isStable(stable_sorted, target):
    for i in range(len(stable_sorted)):
        if stable_sorted[i] != target[i]:
            return "Not stable"
    return "Stable"

def main():
    n = int(input())
    card = input().split()

    bubble_sorted_card = bubble_sort(card.copy(), n)
    print(isStable(bubble_sorted_card, bubble_sorted_card))

    selection_sorted_card = selection_sort(card.copy(), n)
    print(isStable(bubble_sorted_card, selection_sorted_card))

if __name__ == "__main__":
    main()


# Example run
# Input:
-23909
Jq\y`
# Output:
Jq\y`
Stable
Jq\y`
Stable
num = int(input())
A = input().split(" ")
B = A.copy()

#bubble sort
for i in range(num):
	for j in range(num-1,i,-1):
		#英字ではなく、数字で比較する
		m1 = int(A[j][1:])
		m2 = int(A[j-1][1:])
		if m1 < m2:
			A[j],A[j-1] = A[j-1],A[j]

print(*A)
print("Stable")

#selection sort
for i in range(num):
	minv = i
	for j in range(i+1,num):
		m1 = int(B[minv][1:])
		m2 = int(B[j][1:])
		if m1 > m2:
			minv = j
	B[i],B[minv] = B[minv],B[i]

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




# Example run
# Input:
0
p2<j
# Output:
p2<j
Stable
p2<j
Stable
# Algorithms and Data Structures 1
# Stable Sort
# Name: Ryuya Asada
# ID: s1260064


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


def SelectionSort(A: list):
    for i in range(0, len(A)):
        minj = i
        for j in range(i, len(A)):
            if A[j][1] < A[minj][1]:
                minj = j

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


def isEqual(a: list, b: list) -> bool:
    if len(a) != len(b):
        return False

    elif a == []:
        return True

    return (a.pop() == b.pop()) and isEqual(a, b)


def main():
    number_of_cards = int(input())
    cards = input().split(" ")

    cards_b = cards.copy()
    BubbleSort(cards_b)
    print(*cards_b, sep=" ")
    print("Stable")
    cards_s = cards.copy()
    SelectionSort(cards_s)
    print(*cards_s, sep=" ")
    if isEqual(cards_b, cards_s):
        print("Stable")
    else:
        print("Not stable")
    pass


if __name__ == "__main__":
    main()



# Example run
# Input:
-7
'7s,N
# Output:
'7s,N
Stable
'7s,N
Stable
def bubblesort(c, n):
	for i in range(n):
		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]

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 output(c):
	for i in range(len(c)):
		if i != 0: print(" ", end="")
		print("{}{}".format(c[i][0], c[i][1]), end="")
	print()

def main():
	n = int(input())
	data = input().split()
	cards = []

	for c in data:
		cards.append((c[0],int(c[1])))
	cards1 = cards[:]
	cards2 = cards[:]

	bubblesort(cards1, n)
	output(cards1)
	print("Stable")

	selectionsort(cards2, n)
	output(cards2)
	if (cards1 == cards2):
		print("Stable")
	else:
		print("Not stable")

if __name__ == "__main__":
	main()

# Example run
# Input:
-812896393
-97075663
# Output:
-9
Stable
-9
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:
            #times += 1
        A[i], A[minj] = A[minj], A[i]
    return A

def BubbleSort(A, N):
    for i in range(N):
        for j in reversed(range(i+1, N)):
            if A[j][1:] < A[j-1][1]:
                A[j], A[j-1] = A[j-1], A[j]

    return A

N = int(input())
A = [str(x) for x in input().split()]
#print(*A)
print(*BubbleSort(A, N))
print('Stable')
print(*SelectionSort(A, N))
if BubbleSort(A, N) == SelectionSort(A, N):
    print('Stable')
else:
    print('Not stable')

# Example run
# Input:
-1837384013
g@Ckzb@K
# Output:
g@Ckzb@K
Stable
g@Ckzb@K
Stable
import copy

def bubble_sort(A, N):
	cnt = 0
	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 A

def selection_sort(A, N):
	cnt = 0
	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]

	return A

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

B = bubble_sort(copy.copy(A), N)
print(' '.join(B))
print('Stable')
C = selection_sort(copy.copy(A), N)
print(' '.join(C))
if B==C:
	print('Stable')
else:
	print('Not stable')


# Example run
# Input:
-1
hd](
# Output:
hd](
Stable
hd](
Stable
def bubble(n,c):
    for i in range(n):
        ch=True
        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]
                ch=False
        if ch:
            break
    return c

def selection(n,c):
    for i in range(n-1):
        id=i
        for j in range(i,n):
            if int(c[id][1])>int(c[j][1]):
                id=j
        c[i],c[id]=c[id],c[i]
        
    return c


n=int(input())
c=list(input().split())
c2=c[:]
ba=bubble(n,c2)
print(*ba)
print("Stable")
sa=selection(n,c)
print(*sa)
print("Stable" if sa==ba else "Not stable")


# Example run
# Input:
-8397164
'nKFpWex\
# Output:
'nKFpWex\
Stable
'nKFpWex\
Stable
def BubbleSort(C,N):
    for i in range(N):
        for j in range(i+1, N)[::-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(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]

N = int(input())
C = (input()).split()
ORG = C[:]
BubbleSort(C,N)
print (" ".join(C))
print ("Stable")
C2=ORG
SelectionSort(C2,N)
print(" ".join(C2))
if C == C2:
    print ("Stable")
else:
    print ("Not stable")

# Example run
# Input:
-16075232
'y*`
# Output:
'y*`
Stable
'y*`
Stable
def bubble_sort(c, n):
    x = c[:]
    for i in range(n):
        for k in range(n-1, i, -1):
            if x[k][1] < x[k-1][1]:
                x[k], x[k-1] = x[k-1], x[k]
    return x

def selection_sort(c, n):
    x = c[:]
    for i in range(n):
        mink = i
        for k in range(i, n):
            if x[k][1] < x[mink][1]:
                mink = k
        x[i], x[mink] = x[mink], x[i]
    return x

n = int(input())
c = []
for i in list(input().split()):
    c.append((i[0], int(i[1]))) # tupleで渡す

b = bubble_sort(c, n)
print(" ".join(map(str, [i[0]+str(i[1]) for i in b])))
# bubble_sortは常に安定なソート
stable = True
print("Stable")

s = selection_sort(c, n)
print(" ".join(map(str, [i[0]+str(i[1]) for i in s])))
if b != s:
    stable = False
if stable:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-208107
-83
# Output:
-8
Stable
-8
Stable