Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
N = int(input())
A = input()
B = A.split()
for i in range(N) :
    for j in range(N-1, i, -1) :
        if int(B[j][1]) < int(B[j-1][1]) :
            B[j], B[j-1] = B[j-1], B[j]
print(" ".join(B))
print("Stable")

C = A.split()
for i in range(N) :
    mini = i
    for j in range(i, N) :
        if int(C[j][1]) < int(C[mini][1]) :
            mini = j
    C[i], C[mini] = C[mini], C[i]
print(" ".join(C))
if B == C :
    print("Stable")
else :
    print("Not stable")


# Example run
# Input:
-227062494
/DJd,
# Output:
/DJd,
Stable
/DJd,
Stable
def BubbleSort(C,n):
	for i in range(n):
		for j in range(i+1,n)[::-1]:
			if C[j][1] < 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 C[j][1] < C[minj][1]:
				minj = j
		C[i],C[minj] = C[minj],C[i]
	return C

def stable(C):
	new = []
	for i in range(1,10):
		Ci = [cc for cc in C if cc[1]==str(i)]
		new += Ci
	return new

n = int(input())
C = input().split()
x,y,z = C[:],C[:],C[:]
bubble = BubbleSort(x,n)
selection = SelectionSort(y,n)
sta = stable(z)

print(' '.join(bubble))
print({True:'Stable',False:'Not stable'}[sta==bubble])
print(' '.join(selection))
print({True:'Stable',False:'Not stable'}[sta==selection])

# Example run
# Input:
-31
1,AYZUHn6
# Output:
1,AYZUHn6
Not stable
1,AYZUHn6
Not stable
def to_int(A):
    return int(A[1])

def bubble_sort(N, A):
    for i in range(N):
        for j in range(i+1, N)[::-1]:
            if to_int(A[j]) < to_int(A[j-1]):
                aj = A[j]
                A[j] = A[j-1]
                A[j-1] = aj
    return A

def selection_sort(N, A):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if to_int(A[j]) < to_int(A[minj]):
                minj = j
        a = A[i]
        A[i] = A[minj]
        A[minj] = a
    return A

def is_stable(bubble, selection):
    if bubble == selection:
        return "Stable"
    else:
        return "Not stable"

if __name__ == "__main__":
    N = int(input())
    A = input().split(" ")
    bubble = bubble_sort(N, A[:])
    selection = selection_sort(N, A[:])
    print(" ".join(bubble))
    print("Stable")
    print(" ".join(selection))
    print(is_stable(bubble, selection))



# Example run
# Input:
-6431
JW<m]
# Output:
JW<m]
Stable
JW<m]
Stable
n=int(input())
c=input().split();d=c[:]
for i in range(n-1):
 for j in range(0,n-i-1):
  if c[j][1]>c[j+1][1]:c[j],c[j+1]=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:
0
UUuK
# Output:
UUuK
Stable
UUuK
Stable
n = int(input())
A = [x for x in input().split()]
B = A.copy()
for i in range(n):
    for j in range(i+1,n)[::-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):
    minj = i
    for j in range(i,n):
        if B[j][1] < B[minj][1]:
            minj = j
    if minj != i:
        B[i],B[minj] = B[minj],B[i]
    
print(*B)

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


# Example run
# Input:
-52
Sz50Gg>x
# Output:
Sz50Gg>x
Stable
Sz50Gg>x
Stable
# Aizu Problem ALDS_1_2_C: Stable Sort
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input2.txt", "rt")


def printA(A):
    print(' '.join([str(a) for a in A]))


def bubble_sort(A):
    for i in range(len(A) - 1):
        for j in range(len(A) - 1, i, -1):
            if A[j][1] < A[j - 1][1]:
                A[j], A[j - 1] = A[j - 1], A[j]
    return A

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

def is_stable(A, B):
    for val in range(1, 10):
        v = str(val)
        if [a[0] for a in A if a[1] == v] != [b[0] for b in B if b[1] == v]:
            return False
    return True
        
N = int(input())
A = list(input().split())
A_bubble = bubble_sort(A[:])
printA(A_bubble)
print("Stable" if is_stable(A, A_bubble) else "Not stable")
A_select = selection_sort(A[:])
printA(A_select)
print("Stable" if is_stable(A, A_select) else "Not stable")

# Example run
# Input:
80731065
-[i
# Output:
-[i
Stable
-[i
Stable
import sys
import copy

def print_data(data):
    last_index = len(data) - 1
    
    for idx, item in enumerate(data):
        print(item, end='')
        if idx != last_index:
            print(' ', end='')

    print('')

def bubbleSort(data, N):
    for i in range(N):
        j = N -1
        while j >= i+1:
            if data[j][1] < data[j-1][1]:
                hoge = data[j]
                data[j] = data[j-1]
                data[j-1] = hoge
            j -= 1
    return data

def selectSort(data, N):
    for i in range(N):
        mini = i
        for j in range(i, N):
            if data[j][1] < data[mini][1]:
                mini = j
        if i == mini:
            pass
        else:
            hoge = data[mini]
            data[mini] = data[i]
            data[i] = hoge
    
    return data

def isStable(inData, outData, N):
    for i in range(N):
        for j in range(i+1, N):
            if inData[i][1] == inData[j][1]:
                a = outData.index(inData[i])
                b = outData.index(inData[j])
                if a > b :
                    return False
    return True




def main():
    N = int(input())
    data0 = list(input().split())
    data1 = copy.deepcopy(data0)
    data2 = copy.deepcopy(data0)
    
    bubbleData = bubbleSort(data1, N)
    selectData = selectSort(data2, N)
    
    
                  
        
    print_data(bubbleData)
    if isStable(data0, bubbleData, N):
        print('Stable')
    else:
        print('Not stable')
    
        
    print_data(selectData)
    if isStable(data0, selectData, N):
        print('Stable')
    else:
        print('Not stable')

            
if __name__ == '__main__':
    main()


# Example run
# Input:
-352
fI]:p,
# Output:
fI]:p,
Stable
fI]:p,
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()]
        array_2 = copy.deepcopy(array)

        bubble_result = self.bubble_sort(array=array, array_length=array_length)
        selection_result = self.selection_sort(array=array_2, 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:
-127034
U9|Au
# Output:
U9|Au
Stable
U9|Au
Stable
import math
import itertools

def getNum(card: str) -> int:
  return int(card[1])

def checkStable(origin: list, sorted: list) -> str: # Stable or Not stable
  N_origin = [[] for _ in range(9)]
  for item in origin:
    num = getNum(item)
    N_origin[num-1].append(item)

  for item in sorted:
    num = getNum(item)    

    if N_origin[num-1][0] != item:
      return False
    else:
      N_origin[num-1].pop(0)

  return True

def main():
  n = int(input())
  A = list(input().split())
  len_A = len(A)  
  B = list(A)
  C = list(A)

  # bubble sort
  for i in range(len_A): 
    for j in reversed(range(i+1, len_A)):
      if getNum(B[j]) < getNum(B[j-1]):
        tmp = B[j]
        B[j] = B[j-1]
        B[j-1] = tmp

  # select sort
  for i in range(len_A):
    min = i
    for j in range(i, len_A):
      if getNum(C[j]) < getNum(C[min]):
        min = j
    
    if min != i:
      tmp = C[min]
      C[min] = C[i]
      C[i] = tmp

  print(*B) #bubble sort
  if checkStable(A, B):
    print('Stable')
  else:
    print('Not stable')
  print(*C) #select sort
  if checkStable(A, C):
    print('Stable')
  else:
    print('Not stable')

if __name__ == '__main__':
  main()


# Example run
# Input:
35
161887817
# Output:
161887817
Stable
161887817
Stable
n=int(input())
#A=list(map(int, input().split()))
B=list(input().split())
C=B.copy()

def bubblesort(A,n):
    #print(A)
    count=0
    flag=1
    while flag:
        flag=0
        for j in reversed(range(1,len(A))):
            if int(A[j][1])<int(A[j-1][1]):
                tmp=A[j-1]
                A[j-1]=A[j]
                A[j]=tmp
                flag=1
                count+=1
    return(A,count)

def selectsort(A,n):
    count=0
    for i in range(len(A)):
        minj=i
        #flag=0
        for j in range(i,len(A)):
            if int(A[j][1])<int(A[minj][1]):
                minj=j
                #flag=1
        if i!=minj:
            A[i],A[minj]=A[minj],A[i]
            count+=1
    #print(A)
    return(A,count)

#バブルソートの結果と比較する
def isStable(result1, result2):
    if result1 == result2:
        return True
    return False


result1,count1=bubblesort(B,n)
print(" ".join([str(i) for i in result1]))
print("Stable")
result2,count2=selectsort(C,n)
print(" ".join([str(i) for i in result2]))
if isStable(result1, result2) == True:
    print("Stable")
else:
    print("Not stable")

#print(count)



# Example run
# Input:
23
-3964499
# Output:
-3964499
Stable
-3964499
Stable
def compare_cards(a, b):
    return int(a[1]) < int(b[1])

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

bubbleC = C.copy()

#compare_cards(C[0],C[1])
print(*C)

# Example run
# Input:
-13840614
Ju.
# Output:
Ju.
import copy
n = int(input())
inp = []
inp = input().split()

class card:
    def __init__(self, suitin, numin):
        self.suit = suitin
        self.num = numin

a = []
for i in range(n):
    a.append(card(inp[i][0], inp[i][1]))

bubble = copy.deepcopy(a)

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

print(bubble[0].suit, end="")
print(bubble[0].num, end="")

for i in range(1, len(bubble)):
    print(" ", end="")
    print(bubble[i].suit, end="")
    print(bubble[i].num, end="")
print("\n", end="")
print("Stable")

select = copy.deepcopy(a)

for i in range(n):
    minj = i
    for j in range(i, n):
        if select[j].num < select[minj].num:
            minj = j
   # if i != minj:
    select[i], select[minj] = select[minj], select[i]


print(select[0].suit, end="")
print(select[0].num, end="")

for i in range(1, len(select)):
    print(" ", end="")
    print(select[i].suit, end="")
    print(select[i].num, end="")
print("\n", end="")

flag = 1
for i in range(n):
    if bubble[i].suit != select[i].suit:
        flag = 0

if flag == 1:
    print("Stable")
else:
    print("Not stable")




# Example run
# Input:
1
S[L8#?H
# Output:
S[
Stable
S[
Stable
n=int(input())
bubble=input().split()
select=bubble[:]
for i in range(n):
    for j in range(n-1,i,-1):
        if int(bubble[j][1])<int(bubble[j-1][1]):
            bubble[j],bubble[j-1]=bubble[j-1],bubble[j]

for i in range(n-1):
    minj=i
    for j in range(i+1,n):
        if int(select[j][1])<int(select[minj][1]):
            minj=j
    select[i],select[minj]=select[minj],select[i]

for i in range(n-1):
    print(bubble[i],end=" ")
print(bubble[n-1])
print("Stable")
for i in range(n-1):
    print(select[i],end=" ")
print(select[n-1])
if bubble==select:
    print("Stable")
else:
    print("Not stable")




# Example run
# Input:
0
fZv`:{qO
# Output:
fZv`:{qO
Stable
fZv`:{qO
Stable
def b_sort(alist):
    for i in range(len(alist)):
        for j in range(len(alist)-1, i, -1):
            if alist[j][1] < alist[j-1][1]:
                alist[j], alist[j-1] = alist[j-1], alist[j]
        alist[i] = alist[i][0] + alist[i][1]
    return ' '.join(alist)


def s_sort(alist):
    for x in range(len(alist)):
        currentmin = x
        for y in range(x+1, len(alist)):
            if alist[y][1] < alist[currentmin][1]:
                currentmin = y
        if x != currentmin:
            alist[x], alist[currentmin] = alist[currentmin], alist[x]
        alist[x] = alist[x][0] + alist[x][1]
    return ' '.join(alist)


if __name__ == '__main__':
    N = int(input())
    alist = [list(x) for x in list(input().split())]
    clist = alist.copy()
    ans_b = b_sort(alist)
    ans_s = s_sort(clist)
    print(ans_b)
    print('Stable')
    print(ans_s)
    print('Stable' if ans_b == ans_s else "Not stable")



# Example run
# Input:
-1181
$P#554h
# Output:
$P
Stable
$P
Stable
length = int(input())
eles = [l for l in input().split()]
is_stable = 'Stable'

_copy = 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 = eles[::]
for i in range(length-1):
    _min = i
    for l in range(i, length):
        if __copy[l][1] < __copy[_min][1]:
            _min = l
    if __copy[i][1] > __copy[_min][1]:
        __copy[i], __copy[_min] = __copy[_min], __copy[i]

print(*__copy)

for i in range(length -1):
    if _copy[i] != __copy[i]:
        is_stable = 'Not stable'

print(is_stable)

# Example run
# Input:
-11
7.**G\f
# Output:
7.**G\f
Stable
7.**G\f
Stable
n = int(input())
deck = input().split()

bd = list(deck)
for i in range(n):
    for j in reversed(range(i + 1, n)):
        if bd[j][1] < bd[j - 1][1]:
            bd[j], bd[j - 1] = bd[j - 1], bd[j]
print(' '.join(bd))
print('Stable')

sd = list(deck)
for i in range(n):
    mi = i
    for j in range(i, n):
        if sd[j][1] < sd[mi][1]:
            mi = j
    sd[i], sd[mi] = sd[mi], sd[i]
print(' '.join(sd))

if (bd == sd):
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
-1
<W_KbTdvT
# Output:
<W_KbTdvT
Stable
<W_KbTdvT
Stable
N = int(input())
SI = list(input().split())
SB = SI.copy()

# bubble sort
for i in range(N):
	for j in range(N - 1, i, -1):
		if SB[j - 1][1] > SB[j][1]:
			x = SB[j - 1]
			SB[j - 1] = SB[j]
			SB[j] = x

# insertion sort
for i in range(N):
	ptr = i
	for j in range(i + 1, N):
		if SI[ptr][1] > SI[j][1]:
			ptr = j
	x = SI[i]
	SI[i] = SI[ptr]
	SI[ptr] = x

# print the answer!
for i in range(N):
	print(SB[i] + " " if i != N - 1 else str(SB[i]) + "\n", end='')
print("Stable")
for i in range(N):
	print(SI[i] + " " if i != N - 1 else str(SI[i]) + "\n", end='')
print("Stable" if SI == SB else "Not stable")



# Example run
# Input:
-3964499
fXDkP^#{
# Output:
Stable
Stable
import copy

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


A1 = copy.deepcopy(A)
for i in range(N-1):
    for j in reversed(range(i+1, N)):
        if A1[j][1] < A1[j-1][1]:
            A1[j], A1[j-1] = A1[j-1], A1[j]
print(*A1)
print('Stable')

A2 = copy.deepcopy(A)
for i in range(N-1):
    minj = i
    for j in range(i+1, N):
        if A2[j][1] < A2[minj][1]:
            minj = j
    A2[i], A2[minj] = A2[minj], A2[i]
print(*A2)

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


# Example run
# Input:
-1
mY%@Uzn-T
# Output:
mY%@Uzn-T
Stable
mY%@Uzn-T
Stable
import copy
def bubblesort(c, n):
    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]
                
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
        if i != minj:
            c[i], c[minj] = c[minj], c[i]
            
            
n = int(input())
a = input().split()
b = copy.copy(a)

bubblesort(a,n)
for i in range(n-1):
    print(a[i], end=' ')
print(a[-1])
print('Stable')
selectionsort(b,n)
for i in range(n-1):
    print(b[i], end=' ')
print(b[-1])
if a == b:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-25166
j9Bc
# Output:
j9Bc
Stable
j9Bc
Stable
count = int(input());
data = input().split(" ");

def bubble_sort(data):
    # print(data);
    count = len(data);
    for i in range(count):
        for j in range(count - 1, i, -1):
            if data[j][1] < data[j - 1][1]:
                data[j], data[j - 1] = data[j - 1], data[j];
        # print(data);

def selection_sort(data):
    count = len(data);
    # print(data);
    for i in range(count - 1):
        minI = i;
        for j in range(i + 1, count):
            if data[j][1] < data[minI][1]:
                minI = j;
        if i != minI:
            data[i], data[minI] = data[minI], data[i];
        # print(data);

def show(data):
    print(" ".join(data));

A = list(data);
bubble_sort(A);
show(A);
print("Stable");

B = list(data);
selection_sort(B);
show(B);
if A == B:
    print("Stable");
else:
    print("Not stable");


# Example run
# Input:
-80
Og\?C
# Output:
Og\?C
Stable
Og\?C
Stable
def selection(l):
	lists = l[:]
	N = len(lists)

	for i in range(N):
		minj = i

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

	return lists


def bubble(l):
	lists = l[:]
	N = len(lists)
	flag = 1

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

	return lists


def output(l):
	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:
		print("Not stable")



# Example run
# Input:
-256478906
-8056
# Output:
-8056
Stable
-8056
Stable
import copy

class StableSort():
    def __init__(self):
        self.N = n
        self.C = copy.copy(c) #こうしないと書き換わってしまう


    def BS(self):
        A = [self.C[i][1] for i in range(self.N)] #数値
        if self.N == 1:
            C = " ".join(self.C)
            return C
        else:
            for i in range(self.N): #比較は常にリストの一番後ろからはじまる
                for j in range(self.N - i - 1):
                    if A[self.N - j - 1] < A[self.N - j - 2]: #常に安定である 
                        A[self.N - j - 1], A[self.N - j - 2] = A[self.N - j - 2], A[self.N - j - 1] 
                        self.C[self.N - j - 1], self.C[self.N - j - 2] = self.C[self.N - j - 2], self.C[self.N - j - 1] 

            C = " ".join(self.C)
            return C


    def SS(self):
        A = [self.C[i][1] for i in range(self.N)] #数値
        if self.N == 1:
            print(self.C[0] + "\n" + "stable")
        else:
            for i in range(self.N - 1):
                A_r = A[i:] #確定してないAの右側の領域
                mini = min(A_r)
                #AとA_rのインデックスは違うので，抜いた左側の分の+iの補正が必要
                mini_index = i + A_r.index(mini) 
                if A[i] > mini:
                    A[i], A[mini_index] = A[mini_index], A[i] 
                    self.C[i], self.C[mini_index] = self.C[mini_index], self.C[i] 

            C = " ".join(self.C) 
            return C

n = int(input())
c = list(input().split()) #トランプ

BS = StableSort().BS()
SS = StableSort().SS()

print(str(BS) + "\n" + "Stable")
if BS != SS:
    print(str(SS) + "\n" + "Not stable")
else:
    print(str(SS) + "\n" + "Stable")



# Example run
# Input:
-84564737
!8'gg[Y)
# Output:
!8'gg[Y)
Stable
!8'gg[Y)
Stable
def bubble_sort(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]

	print(' '.join(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

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

	print(' '.join(A))

if __name__ == '__main__':
	n = int(input())
	A = list(input().split())
	B = A[:]

	bubble_sort(A, n)
	print('Stable')

	selection_sort(B, n)
	print('Stable' if A == B else 'Not stable')

# Example run
# Input:
-497
g},,YvY
# Output:
g},,YvY
Stable
g},,YvY
Stable
n=int(input())
b=input().split()
s=b[:]
for i in range(n):
    for j in range(n-1,i,-1):
        if b[j][1]<b[j-1][1]:b[j],b[j-1]=b[j-1],b[j]
    m=i
    for j in range(i,n):
        if s[m][1]>s[j][1]:m=j
    s[m],s[i]=s[i],s[m]
print(*b)
print('Stable')
print(*s)
print(['Not s','S'][b==s]+'table')

# Example run
# Input:
-740
85[tBatc
# Output:
85[tBatc
Stable
85[tBatc
Stable
import copy as cp

n = int(input())
A = [str(x) for x in input().split()]
AS = cp.copy(A)


def bubble(X):
    for i in range(n):
        X[i] = list(X[i])
        X[i][1] = int(X[i][1])

    for i in range(n):
        for j in range(n-1):
            if (X[j+1][1] < X[j][1]):
                X[j],X[j+1] = X[j+1],X[j]

    for i in range(n):
        X[i][1] = str(X[i][1])
        X[i] = "".join(X[i])
    return(X)


BA = bubble(A)



def minsort():

    for i in range(n):
        AS[i] = list(AS[i])
        AS[i][1] = int(AS[i][1])

    for i in range(n):
        minj = i
        for j in range(i,n):
            if (AS[j][1] < AS[minj][1]):
                minj = j

        if (minj != i):
            AS[i],AS[minj] = AS[minj],AS[i]

    for i in range(n):
        AS[i][1] = str(AS[i][1])
        AS[i] = "".join(AS[i])

    return(AS)

MA = minsort()


for k in range(n-1):
    print(str(BA[k])+" ",end = "")
print(str(BA[n-1]))
print("Stable")

for k in range(n-1):
    print(str(MA[k])+" ",end = "")
print(str(MA[n-1]))
if (BA == MA):
    print("Stable")
else :
    print("Not stable")



# Example run
# Input:
0
guBxEO`F
# Output:
guBxEO`F
Stable
guBxEO`F
Stable
import copy
class Card:
    def __init__(self, str):
        self.mark = str[0]
        self.number = int(str[1:])
        
    def __str__(self):
        return self.mark + str(self.number)
        
n = int(input())
card_list = [Card(c) for c in input().split()]

def bubble_sort(a):
    a = copy.copy(a)
    n = len(a)
    for i in range(n):
            for j in range(0, n-i-1):
                if a[j].number > a[j+1].number:
                    a[j], a[j+1] = a[j+1], a[j]
    return a
    
sorted_card_list1 = bubble_sort(card_list)
print(*sorted_card_list1)
print("Stable")

def selection_sort(a):
    a = copy.copy(a)
    n = len(a)
    for i in range(n):
        min_index = i
        for j in range(i+1,n):
            if a[j].number < a[min_index].number:
                min_index = j
        if i != min_index:
            a[i],a[min_index] = a[min_index],a[i]
    return a

    
sorted_card_list2 = selection_sort(card_list)
print(*sorted_card_list2)
if sorted_card_list1 == sorted_card_list2:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
471619987
-3753932
# Output:
-3753932
Stable
-3753932
Stable
n = int(input())
a = [i for i in input().split()]
a2 = a.copy()
for i in range(n):
    for j in reversed(range(i, n)):
        if a[j][1] < a[j-1][1]:
            a[j], a[j-1] = a[j-1], a[j]
for s in range(n):
    minj = s 
    for t in range(s+1, n):
        if a2[t][1] < a2[minj][1]:
            minj = t
    if a2[s] != a2[minj]:
        a2[s], a2[minj] = a2[minj], a2[s]
print(*a)
print("Stable")
print(*a2)
if a == a2:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-101281970
NtQ5EY{
# Output:
NtQ5EY{
Stable
NtQ5EY{
Stable