Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
def BubbleSort(n, lst):
    for i in range(n):
        for j in range(n-1, i, -1):
            if lst[j][1] < lst[j-1][1]:
                lst[j-1], lst[j] = lst[j], lst[j-1]
    return lst

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

#バブルソートは必ず安定なので１つめのソート結果と比較することで
#O(N)で２つ目のソートの安定性を判定できる
def check(lst1, lst2):
    if lst1 == lst2:
        print("Stable")
    else:
        print("Not stable")

"""
def check(n, lst_o, lst):
    keeper = [[]]*10
    keeper2 = [[]]*10
    for i in range(n):
        keeper[int(lst_o[i][1])] = keeper[int(lst_o[i][1])] + [lst_o[i][0]]
        keeper2[int(lst[i][1])] = keeper2[int(lst[i][1])] + [lst[i][0]]
    if keeper == keeper2:
        print("Stable")
    else:
        print("Not stable")
"""

n = int(input())
lst = input().split()
lst1 = BubbleSort(n, lst.copy())
print(*lst1)
#check(n, lst.copy(), lst1)
print("Stable")
lst2 = SelectionSort(n, lst.copy())
print(*lst2)
check(lst1, lst2)
#check(n, lst.copy(), lst2)




# Example run
# Input:
-3843085
d-3D,
# Output:
d-3D,
Stable
d-3D,
Stable
def isStable(inlist, outlist):
	flag = True
	for i in range(0, N):
		for j in range(i+1, N):
			for a in range(0, N):
				for b in range(a+1, N):
					if int(inlist[i][1:]) == int(inlist[j][1:]) and inlist[i] == outlist[b] and inlist[j] == outlist[a]:
						flag = False
						break
				else:
					continue
				break
			else:
				continue
			break
		else:
			continue
		break

	return(flag)
N = int(input())
A = input().split()
B = A[:]
C = A[:]

flag = 1
counter = 0
while flag:
    flag = 0
    for i in reversed(range(1,N)):
        if int(C[i][1:]) < int(C[i-1][1:]):
            C[i], C[i-1] = C[i-1], C[i]
            counter += 1
            flag = 1
print(" ".join(map(str, C)))

if(isStable(A, C)):
	print("Stable")
else:
	print("Not stable")

counter=0
for i in range(N):
	Br = B[i:]
	Brr = [int(Br[j][1:]) for j in range(N-i)]
	num = Brr.index(min(Brr)) 
	if num != 0:
		B[i], B[(i+num)] = B[(i+num)], B[i]
		counter += 1
print(" ".join(map(str,B)))
if(isStable(A, B)):
	print("Stable")
else:
	print("Not stable")

# Example run
# Input:
-62
7t:
# Output:
7t:
Stable
7t:
Stable
def selection(n, data):
    __count = 0
    for i in range(n):
        min_i = i
        for j in range(i+1, n):
            if data[min_i][1] > data[j][1]:
                min_i = j
        tmp = data[i]
        data[i] = data[min_i]
        data[min_i] = tmp
        if min_i != i:
            __count += 1
    return data, __count

def bubble_sort(n, data):
    __count = 0
    for i in range(n-1):
        for j in range(n-i-1):
            if data[j][1] > data[j+1][1]:
                tmp = data[j+1]
                data[j+1] = data[j]
                data[j] = tmp
                __count += 1
    return data, __count

def show(data):
    for i in range(len(data)):
        if i != (len(data)-1):
            print(data[i], end = " ")
        else:
            print(data[i])

if "__main__" == __name__:
    n = int(input())
    data_b = input().split()
    data_s = data_b.copy()
    sort1, count = bubble_sort(n, data_b)
    show(sort1)
    print("Stable")
    sort2, count = selection(n, data_s)
    show(sort2)
    if sort1 == sort2:
        print("Stable")
    else:
        print("Not stable")



# Example run
# Input:
-235202
nzXv9U
# Output:
nzXv9U
Stable
nzXv9U
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[j-1][1]):
            m = j
    _C[i], _C[m] = _C[m], _C[i]
print(*_C)
if(C ==_C):
    print("Stable")
else:
    print("Not stable")

# Example run
# Input:
-20720
W<+
# Output:
W<+
Stable
W<+
Stable
from collections import namedtuple
from operator import itemgetter, attrgetter

def bubble_sort(a):
    a = a[:]
    n = len(a)

    for i in range(n):
        for j in range(n - 1, i, -1):
            if a[j].value < a[j - 1].value:
                a[j], a[j - 1] = a[j - 1], a[j]
    return a


def selection_sort(a):
    a = a[:]
    n = len(a)

    for i in range(n):
        minj = i
        for j in range(i, n):
            if a[j].value < a[minj].value:
                minj = j
        a[i], a[minj] = a[minj], a[i]

    return a

class Card(namedtuple('Card', ['suit', 'value'])):
    def __str__(self):
        return '{0}{1}'.format(self.suit, self.value)

parser = lambda s: Card(s[0], int(s[1:]))

n = int(input())
a = list(map(parser, input().split()))

stable_sorted = sorted(a, key = attrgetter('value'))
bubble_sorted = bubble_sort(a)
selection_sorted = selection_sort(a)

print(' '.join(list(map(str, bubble_sorted))))
if stable_sorted == bubble_sorted:
    print('Stable')
else:
    print('Not stable')

print(' '.join(list(map(str, selection_sorted))))
if stable_sorted == selection_sorted:
    print('Stable')
else:
    print('Not stable')

# Example run
# Input:
-640183291
155287
# Output:
155287
Stable
155287
Stable
#stable sort Taka
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]):
                c[j], c[j-1] = c[j-1], c[j]
    return c

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
        c[i], c[minj] = c[minj], c[i]
    return c

def is_stable(original_list, sorted_list):
    for target in sorted_list:
        for original in original_list:
            #print(target, original)
            if target[1] == original[1]:
                if target[0] != original[0]:
                    return "Not stable"
                original_list.remove(original)
                break
    return "Stable"

if __name__ == "__main__":
    import copy
    n = int(input())
    c = input().split()
    bubble_list = bubble_sort(copy.deepcopy(c), n)
    print(*bubble_list)
    print(is_stable(copy.deepcopy(c), bubble_list))
    selection_list = selection_sort(copy.deepcopy(c), n)
    print(*selection_list)
    print(is_stable(copy.deepcopy(c), selection_list))


# Example run
# Input:
1
j5jF/6=;
# Output:
j5jF/6=;
Stable
j5jF/6=;
Stable
# -*- coding:utf8 -*-

import copy

n = int(input())
l1 = list(map(str, input().split()))
l2 = copy.deepcopy(l1)

flag = 1
while flag:
    flag = 0
    for i in reversed(range(1, n)):
        if l1[i][-1] < l1[i - 1][-1]:
            l1[i], l1[i - 1] = l1[i - 1], l1[i]
            flag = 1
print(' '.join(map(str, l1)))
print('Stable')

for i in range(n):
    minj = i + l2[i:].index(min(l2[i:], key = lambda x : x[-1]))
    if minj != i:
        l2[i], l2[minj] = l2[minj], l2[i]
print(' '.join(map(str, l2)))
print('Stable' if l1 == l2 else 'Not stable')


# Example run
# Input:
-330190783
u+a
# Output:
u+a
Stable
u+a
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:
-139093888
VLLU9,h&
# Output:
VLLU9,h&
Stable
VLLU9,h&
Stable
n=int(input())
a=[i for i in input().split(" ")]
b=a.copy()
flg=1

while flg:
    flg=0
    for j in range(n-1,0,-1):
        if a[j][1] < a[j-1][1]:
           a[j-1],a[j]=a[j],a[j-1]
           flg=1  

for i in range(n):
    mi=i
    for j in range(i,n):
        if b[j][1] < b[mi][1]:
            mi = j
    if i != mi:
        b[i],b[mi]=b[mi],b[i]

print(" ".join([str(i) for i in a]))
print("Stable")
print(" ".join([str(i) for i in b]))
if a==b:
    print("Stable")
else:
    print("Not stable")

# Example run
# Input:
-8439645
Y)lx&:Sr
# Output:
Y)lx&:Sr
Stable
Y)lx&:Sr
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:
-3766
m~%@y;
# Output:
m~%@y;
Stable
m~%@y;
Stable
def bubbleSort(l, n):
    for i in range(n):
        for j in range(n-1-i):
            if l[j][0] > l[j+1][0]:
                l[j], l[j+1] = l[j+1], l[j]
    return l[:]

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

n = int(input())
l = []
for c in input().split():
    l.append((int(c[1]), c[0]))
    
bl = ' '.join([k + str(n) for n, k in bubbleSort(l[:], n)])
sl = ' '.join([k + str(n) for n, k in selectionSort(l[:], n)])
print(bl)
print('Stable')
print(sl)
print('Stable' if sl == bl else 'Not stable')

# Example run
# Input:
-7737
-126905272
# Output:
-1
Stable
-1
Stable
#!/usr/bin/env python
# encoding: utf-8

import copy


class Solution:
    def stable_sort(self):
        # write your code here
        array_length = int(input())
        array = [str(x) for x in input().split()]

        bubble_result = self.bubble_sort(array=array, array_length=array_length)
        selection_result = self.selection_sort(array=copy.deepcopy(array), array_length=array_length)

        # check whether selection sort is stable
        if bubble_result == selection_result:
            print("Stable")
        else:
            print("Not stable")

    @staticmethod
    def selection_sort(array, array_length):
        # selection sort
        selection_count = 0
        for i in range(array_length):
            min_j = i
            for j in range(i, array_length):
                if array[j][1] < array[min_j][1]:
                    min_j = j
            array[i], array[min_j] = array[min_j], array[i]
            if i != min_j:
                selection_count += 1

        result = " ".join(map(str, array))
        print(result)
        return result

    @staticmethod
    def bubble_sort(array, array_length):
        flag, bubble_count, cursor = 1, 0, 0
        while flag:
            flag = 0
            for j in range(array_length - 1, cursor, -1):
                if array[j][1] < array[j - 1][1]:
                    array[j], array[j - 1] = array[j - 1], array[j]
                    flag = 1
                    bubble_count += 1
        cursor += 1
        result = " ".join(map(str, array))
        print(result)
        print("Stable")
        return result


if __name__ == '__main__':
    solution = Solution()
    solution.stable_sort()

# Example run
# Input:
-16371
)c6@(1
# Output:
)c6@(1
Stable
)c6@(1
Stable
def bubble_sort(C, N):
    card = []
    for c in C:
        card.append({'suit': c[0], 'value': int(c[1])})
            
    for i in range(N):
        for j in range(N-1, i, -1):
            if card[j]['value'] < card[j-1]['value']:
                card[j], card[j-1] = card[j-1], card[j]

    new_C = []
    for i in range(N):
        new_C.append(card[i]['suit'] + str(card[i]['value']))
        
    return new_C


def selection_sort(C, N):
    card = []
    for c in C:
        card.append({'suit': c[0], 'value': int(c[1])})

    for i in range(N):
        min_j = i
        for j in range(i, N):
            if card[j]['value'] < card[min_j]['value']:
                min_j = j
        card[i], card[min_j] = card[min_j], card[i]
        
    new_C = []
    for i in range(N):
        new_C.append(card[i]['suit'] + str(card[i]['value']))
        
    return new_C


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

C_b = bubble_sort(C, N)
C_s = selection_sort(C, N)

print(' '.join(C_b))
print('Stable')

print(' '.join(C_s))
if C_s == C_b:
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
-1041
-13
# Output:

Stable

Stable
from copy import copy
from collections import defaultdict


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]
    return C


def selectionsort(C, N):
    for i in range(N):
        minj = i
        for j in range(i+1, N):
            if int(C[j][-1]) < int(C[minj][-1]):
                minj = j
        C[i], C[minj] = C[minj], C[i]
    return C
  

def soot_order(C):
    ret = defaultdict(list)
    for c in C:
        soot = c[0]
        number = c[1]
        ret[number].append(soot)
    return ret


def judge_stable(C, N, order):
    
    cursor = 0
    stable = True
    while cursor < N:
        number = C[cursor][1]
        soots = order[number]
        for soot in soots:
            if C[cursor][0] != soot:
                print("Not stable")
                stable = False
                cursor += N
                break
            else:
                cursor += 1
    if stable:
        print("Stable")
        

def main():
    N = int(input())
    C = [c for c in input().split()]    
    
    order = soot_order(C)
    
    _C = copy(C)
    C_order = bubblesort(_C, N)
    print(' '.join(C_order))
    
    judge_stable(C_order, N, order)
    
    C_order = selectionsort(C, N)
    print(' '.join(C_order))
    
    judge_stable(C_order, N, order)
    
    
if __name__=="__main__":
    main()


# Example run
# Input:
-766277028
.mMD~_Bg
# Output:
.mMD~_Bg
Stable
.mMD~_Bg
Stable
class card:

    def __init__(self,cv):
        c = cv[0:1]
        v = int(cv[1:2])
        self.c = c
        self.v = v
    

    def self_str(self):
        q = str(str(self.c) + str(self.v))
        return q


n = int(input())
a = list(map(card, input().split()))


b = a[:]
c = a[:]

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

print(" ".join(x.self_str() for x in b))

coua = ""
coub = ""
conb = ""
for i in range(n):
    for j in range(n):
        if i != j:
            if a[i].v == a[j].v:
                coua += a[i].c
            if b[i].v == b[j].v:
                coub += b[i].c
if coua == coub:
     conb = "Stable"
else:
    conb = "Not stable"
print(conb)





for i in range(n):
    mini = i
    for j in range(i, n):
        if c[j].v < c[mini].v:
            mini = j
    c[mini], c[i] = c[i], c[mini]

print(" ".join(x.self_str() for x in c))

couc = ""
conc = ""
for i in range(n):
    for j in range(n):
        if i != j:
            if c[i].v == c[j].v:
                couc += c[i].c
if coua == couc:
     conc = "Stable"
else:
    conc = "Not stable"

print(conc)

# Example run
# Input:
-519560
-58471
# Output:
-5
Stable
-5
Stable
import copy
num =int(input())

l = input().split()

def ccompare( p, q):
    return ord(p[1]) - ord(q[1])


def bsort(l):
    a = copy.copy(l)
    for i in range(len(a)):
        for j in reversed(range(i+1,len(a))):
            if ccompare(a[j],a[j-1]) < 0:
                tmp = a[j-1]
                a[j-1] = a[j]
                a[j] = tmp
    return a
def ssort(l):
    b = copy.copy(l)
    for i in range(len(b)):
        minj = i
        for j in range(i,len(b)):
            if ccompare(b[j], b[minj]) < 0:
                minj = j
        tmp = b[minj]
        b[minj] = b[i]
        b[i] = tmp
    return b
    
def show(lst):
    for i in range(len(lst)):
        print(lst[i], end="")
        if i < len(lst)-1:
            print(" ", end="")
        else:
            print()

def complist(s,t):
    for i in range(len(s)):
        if s[i] != t[i]:
            return False
    return True

bres = bsort(l)
sres = ssort(l)
show(bres)
print("Stable")
show(sres)
if complist(bres, sres):
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
174025
5mY%@Uz
# Output:
5mY%@Uz
Stable
5mY%@Uz
Stable
def bubbleSort(A):
    N = len(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]
    return A


def selectionSort(A):
    N = len(A)
    for i in range(N):
        min_i = i
        for j in range(i, N):
            if A[j][1] < A[min_i][1]:
                min_i = j
        if min_i != i:
            A[i], A[min_i] = A[min_i], A[i]
    return A


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 False
    return True


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

B = bubbleSort(A[:])
print(*B)
if is_stable(A, B):
    print('Stable')
else:
    print('Not stable')

S = selectionSort(A[:])
print(*S)
if is_stable(A, S):
    print('Stable')
else:
    print('Not stable')

# Example run
# Input:
76
i97lD/+AU
# Output:
i97lD/+AU
Stable
i97lD/+AU
Stable
def bubbleSort(l, n):
    for i in range(n):
        for j in range(i, n-1):
            if l[j][0] > l[j+1][0]:
                l[j], l[j+1] = l[j+1], l[j]
    return l[:]

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

n = int(input())
l = []
for c in input().split():
    l.append((int(c[1]), c[0]))
    
bl = ' '.join([k + str(n) for n, k in bubbleSort(l, n)])
sl = ' '.join([k + str(n) for n, k in selectionSort(l, n)])
print(bl)
print('Stable')
print(sl)
print('Stable' if sl == bl else 'Not stable')

# Example run
# Input:
-371
-1177
# Output:
-1
Stable
-1
Stable
from copy import deepcopy

def BubbleSort(a, N):
    for i in range(N):
        for j in range(N-1, i, -1):
            if a[j][1] < a[j-1][1]:
                a[j], a[j-1] = a[j-1], a[j]
    return a

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

def isStable(x, bubble):
    if x == bubble: return "Stable"
    else: return "Not stable"

if __name__ ==  "__main__":
    N = int(input())
    a = list(map(str, input().split()))
    bubble, selection = deepcopy(a), deepcopy(a)
    bubble = BubbleSort(bubble, N)
    selection = SelectionSort(selection, N)
    print(*bubble)
    print(isStable(bubble, bubble))
    print(*selection)
    print(isStable(selection, bubble))



# Example run
# Input:
-3471
xs$
# Output:
xs$
Stable
xs$
Stable
# -*- coding: utf-8 -*-


def bubble_sort(c):
    c = list(c)
    for i in range(len(c)):
        for j in range(len(c)-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 selection_sort(c):
    c = list(c)
    for i in range(len(c)):
        minj = i
        for j in range(i+1, len(c)):
            if int(c[j][1]) < int(c[minj][1]):
                minj = j
        c[i], c[minj] = c[minj], c[i]
    return c

input_num = int(input())
input_list = input().split()
bubble_list = bubble_sort(input_list)
selection_list = selection_sort(input_list)
for c in bubble_list:
    print(c, end=' ')
print("\nStable")
stable_flg = True
for i in range(len(input_list)):
    if bubble_list[i] != selection_list[i]:
        stable_flg = False
    print(selection_list[i], end=' ')
if stable_flg:
    print("\nStable")
else:
    print("\nNot stable")

# Example run
# Input:
869
XfyV
# Output:
XfyV 
Stable
XfyV 
Stable
n=int(input())
B=list(input().split())
A=[[0 for i in range(n)]for j in range(n)]
C=[[0 for i in range(n)]for j in range(n)]
for i in range(n):
    A[i]=B[i]
    C[i]=B[i]
flag=1
while flag==1:
    flag=0
    for i in range(n-1):
        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=1
for i in range(n-1):
    print(A[i],end=" ")
print(A[n-1])
print("Stable")

for i in range(n):
    min=i
    for j in range(i,n):
        if int(C[j][1])<int(C[min][1]):
            min=j
    if min!=i:
        C[i],C[min]=C[min],C[i]
for i in range(n-1):
    print(C[i],end=" ")
print(C[n-1])
flag=1
for i in range(n):
    if A[i]!=C[i]:
        flag=0
        break
if flag==1:
    print("Stable")
elif flag==0:
    print("Not stable")


# Example run
# Input:
1
e8YVK$.
# Output:
e8YVK$.
Stable
e8YVK$.
Stable
length = int(input())
eles = [int(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:
-2334
-158606
# Output:
-158606
Stable
-158606
Stable
N = int(input())

C = input().split()

B = C[:]
S = C[:]

# bubble sort
flag = 1
while(flag):
    flag = 0
    for x in range(1, N):
        if B[x][1:] < B[x-1][1:]:
            B[x], B[x-1] = B[x-1], B[x]
            flag = 1

# sectionSot
for x in range(0,N):
    minj = x
    for j in range(x,N):
        if S[j][1:] < S[minj][1:]:
            minj = j
    if minj != x:
        S[x], S[minj] = S[minj], S[x]


if(B == S):
    print(" ".join(b for b in S))
    print("Stable")
else:
    print(" ".join(b for b in S))
    print("Not stable")

# Example run
# Input:
-54544899
Sz50Gg>x
# Output:
Sz50Gg>x
Stable
import copy
N=int(input())
c1=list(input().split())
c2=copy.deepcopy(c1)
c3=copy.deepcopy(c1)
def bubble(card):
    for i in range(N):
        for j in [N-x for x in range(1,N-i)]:
            if int(card[j][1]) < int(card[j-1][1]):
                s= card[j]
                card[j]=card[j-1]
                card[j-1]=s
    return card
def selection(card):
    for i in range(N):
        minj = i
        for j in range(i,N):
            if int(card[j][1]) < int(card[minj][1]):
                minj = j
        s = card[i]
        card[i]=card[minj]
        card[minj]=s
    return card
def stable(card):
    j=0
    for i in range(N-1):
        if int(card[i][1]) == int(card[i+1][1]):
            if c3.index(card[i]) > c3.index(card[i+1]):
                j=1
                break
    if j == 0:
        return 'Stable'
    else:
        return 'Not stable' 
print(*bubble(c1))
print(stable(bubble(c1)))
print(*selection(c2))
print(stable(selection(c2)))


# Example run
# Input:
-728818981
$[><G
# Output:
$[><G
Stable
$[><G
Stable