Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
class Card:
    def __init__(self, suit, value):
        self.suit = suit
        self.value = value
    
def selection(ls):
    for i in range(len(ls)):
        minj = i
        
        for j in range(i, len(ls)):
            if ls[j].value < ls[minj].value:
                minj = j
        ls[i], ls[minj] = ls[minj], ls[i]

def bubblesort(ls):
    for i in range(1, len(ls)):
        for j in reversed(range(i, len(ls))):
            if ls[j].value < ls[j-1].value:
                ls[j], ls[j-1] = ls[j-1], ls[j]

def isStable(ls1, ls2):
    if ls1 == ls2:
        print("Stable")
    else:
        print("Not stable")

def printcards(cards):
    for card in cards:
        print(card.suit, card.value, ' ', sep='', end='')

    print('\n', end='')
    
def main():
    N = int(input().rstrip())

    cards = []
    for card in list(input().split(' ')):
        cards.append(Card(card[0], card[1]))

    a = [x for x in cards]
    b = [x for x in cards]
    

    bubblesort(a)
    selection(b)
    
    printcards(a)
    print("Stable")

    printcards(b)
    isStable(a,b)
    
if __name__ == '__main__':
    main()

# Example run
# Input:
-1131247330
d=C>#:p
# Output:
d= 
Stable
d= 
Stable
def s_sort(A,N):

   for i in range(N):
       min_j = i
       for j in range(i,N):
           if A[j][1:] < A[min_j][1:]:
               min_j = j

       if i != min_j:
           temp = A[i]
           A[i] = A[min_j]
           A[min_j] = temp

   return A

def b_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]
        
    return A

if __name__ == '__main__':
    n = int(input())
    R = list(map(str,input().split()))
    C = R[:]
    Sr = s_sort(R,n)
    Br = b_sort(C,n)

    fstable = Sr == Br

    print(" ".join(map(str,Br)))
    print("Stable")
    print(" ".join(map(str,Sr)))
    if(fstable == True):
       print("Stable")
    else:
       print("Not stable")



# Example run
# Input:
-45
g>xkU
# Output:
g>xkU
Stable
g>xkU
Stable
from typing import List


def bubble_sort(elems: List[str]) -> List[str]:
    for i in range(0, len(elems)):
        for j in range(len(elems) - 1, i, -1):
            if int(elems[j][1]) < int(elems[j - 1][1]):
                elems[j], elems[j - 1] = elems[j - 1], elems[j]
    return elems


def selection_sort(elems: List[str]) -> List[str]:
    for i in range(0, len(elems)):
        mini = i
        for j in range(i + 1, len(elems)):
            if int(elems[j][1]) < int(elems[mini][1]):
                mini = j
        if i != mini:
            elems[i], elems[mini] = elems[mini], elems[i]
    return elems


def is_stable(input_elems: List[str], elems: List[str]) -> bool:
    for card1, card2 in zip(elems[:-1], elems[1:]):
        if (int(card1[1]) == int(card2[1])) and (
           input_elems.index(card1) > input_elems.index(card2)):
            return False
    return True


if __name__ == "__main__":
    elem_num = int(input())
    elems = list(input().split())

    elems_bubble_sort = elems.copy()
    elems_bubble_sort = bubble_sort(elems_bubble_sort)
    print(" ".join(elems_bubble_sort))
    if is_stable(elems, elems_bubble_sort):
        print("Stable")
    else:
        print("Not stable")

    elems_selection_sort = elems.copy()
    elems_selection_sort = selection_sort(elems_selection_sort)
    print(" ".join(elems_selection_sort))
    if is_stable(elems, elems_selection_sort):
        print("Stable")
    else:
        print("Not stable")



# Example run
# Input:
-65906
}e^'y?He
# Output:
}e^'y?He
Stable
}e^'y?He
Stable
import copy


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]:
                a[j], a[j - 1] = a[j - 1], a[j]


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


n = int(input())
a = list(input().split())
b = copy.deepcopy(a)

bubbleSort(a, n)
print(*a)
print('Stable')

selectionSort(b, n)
print(*b)
print('Stable') if a == b else print('Not stable')



# Example run
# Input:
-2820
x_bA3N6k,
# Output:
x_bA3N6k,
Stable
x_bA3N6k,
Stable
n = int(input())
a = [i for i in input().split()]
b = [a[i] for i in range(n)]
def bubbleSort(A):
    for i in range(n):
        for j in range(i+1,n)[::-1]:
            if int(A[j][1]) < int(A[j-1][1]):
                A[j], A[j-1] = A[j-1], A[j]
    return A

def selectionSort(A):
    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

bubbleSort(a)
selectionSort(b)

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



# Example run
# Input:
-27
VI3R
# Output:
VI3R
Stable

Not stable
class Card:
    def __init__(self, mark, value):
        self.mark = mark
        self.value = value

    def __eq__(self, other):
        if not isinstance(other, Card):
            return NotImplemented
        return self.value == other.value and self.mark == other.mark

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

    def __str__(self):
        return self.mark + str(self.value)


def BubbleSort(arr):
    res = [Card(c.mark, c.value) for c in arr]
    swap_flg = True
    i = 0
    while swap_flg:
        swap_flg = False
        for j in range(len(res) - 1, i, -1):
            if (res[j] < res[j - 1]):
                res[j], res[j - 1] = res[j - 1], res[j]
                swap_flg = True
        i += 1
    return res


def SelectionSort(arr):
    res = [Card(c.mark, c.value) for c in arr]
    for i in range(0, len(res)):
        minj = i
        for j in range(i, N):
            if res[j] < res[minj]:
                minj = j
        if (i != minj):
            res[i], res[minj] = res[minj], res[i]
    return res


def isStable(in_arr, out_arr):
    stable_arr = BubbleSort(in_arr)
    return all(out_arr[i] == stable_arr[i] for i in range(0, len(out_arr)))


N = int(input())
arr = [Card(s[0], int(s[1])) for s in input().split()]
b_arr = BubbleSort(arr)
print(' '.join(map(str, b_arr)))
print('Stable' if isStable(arr, b_arr) else 'Not stable')
s_arr = SelectionSort(arr)
print(' '.join(map(str, s_arr)))
print('Stable' if isStable(arr, s_arr) else 'Not stable')



# Example run
# Input:
-24
-35784
# Output:
-3
Stable
-3
Stable
from typing import Any,Sequence
import  copy


def selectionSort(A:Sequence, N:int) -> None:

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

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



def bubble_sort(A:Sequence, N:int) -> None:

    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]


def bool_isStable(C1:Sequence, C2:Sequence, N:int) -> bool:
    for i in range(N):
        if C1[i] != C2[i]:
            return False
    return  True


n = int(input())
B = list(map(str, input().split()))
C1 = n * []
C2 = n * []

C1 = copy.copy(B)
C2 = copy.copy(B)


bubble_sort(C1, n)
selectionSort(C2, n)


print(' '.join(map(str, C1)))
print('Stable')


print(' '.join(map(str, C2)))
if bool_isStable(C1, C2, n) == True:
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
-31081879
7BJLT
# Output:
7BJLT
Stable
7BJLT
Stable
import copy
N = int(input())
A = list(input().split())
B = []
for i in A:
    temp = list(i)
    B.append(temp)
C = copy.copy(B)

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

def selection_sort(A):
    for i in range(len(A)):
        minj = i
        for j in range(i+1,len(A)):
            if int(A[minj][1]) > int(A[j][1]):
                minj = j
        A[minj],A[i] = A[i],A[minj]
    return A

ans = []
for k in bubble_sort(B):
    ans.append(k[0]+k[1])
print(*ans)
print("Stable")

ans_2 = []
for k in selection_sort(C):
    ans_2.append(k[0]+k[1])

print(*ans_2)

if ans == ans_2:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-1596917
Z9g.
# Output:
Z9
Stable
Z9
Stable
def bubble(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(c):
	for i in range(len(c)):
		mini = i
		for j in range(i,len(c)):
			if int(c[j][-1])<int(c[mini][-1]):
				mini = j
	c[i],c[mini]=c[mini],c[i]
	return c

n = int(input())
card = list(map(str,input().split()))
card1 = card
bubble(card)
selection(card1)
print(" ".join(map(str,card)))
print("Stable")
print(" ".join(map(str,card1)))
print("Stable") if card==card1 else print("Not stable")

# Example run
# Input:
-1836
-168854
# Output:
-168854
Stable
-168854
Stable
#!/usr/bin/env python
# encoding: utf-8

import copy


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

        bubble_result = self.bubble_sort(b_array=b_array, array_length=array_length)
        selection_result = self.selection_sort(s_array=s_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(s_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 s_array[j][1] < s_array[min_j][1]:
                    min_j = j
            s_array[i], s_array[min_j] = s_array[min_j], s_array[i]
            if i != min_j:
                selection_count += 1

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

    @staticmethod
    def bubble_sort(b_array, array_length):
        flag, bubble_count, cursor = 1, 0, 0
        while flag:
            flag = 0
            for j in range(array_length - 1, cursor, -1):
                if b_array[j][1] < b_array[j - 1][1]:
                    b_array[j], b_array[j - 1] = b_array[j - 1], b_array[j]
                    flag = 1
                    bubble_count += 1
        cursor += 1
        result = " ".join(map(str, b_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
N = int(input())
A = input().split()

def b_sort(a):
	while True:
		for n in reversed(range(1, len(a))):
			if a[n][1] < a[n - 1][1]:
				a[n - 1], a[n] = a[n], a[n - 1]
				break
		else:
			return

def s_sort(a):
	for n in range(len(a)):
		min_n = n
		for m in range(n, len(a)):
			if a[m][1] < a[min_n][1]:
				min_n = m
		if n != min_n:
			a[n], a[min_n] = a[min_n], a[n]
	return

a_b = A.copy()
b_sort(a_b)
print(*a_b)
print("Stable")

a_s = A.copy()
s_sort(a_s)
print(*a_s)
print(["Stable", "Not stable"][not(a_b == a_s)])



# Example run
# Input:
-155785153
<+c9'r
# Output:
<+c9'r
Stable
<+c9'r
Stable
#coding:UTF-8
def BS(N,A):
    for i in range(N):
        for j in reversed(range(i+1,N)):
            if int(A[j][1:])<int(A[j-1][1:]):
                swap=A[j]
                A[j]=A[j-1]
                A[j-1]=swap
    return A

def SS(N,A):
    for i in range(N):
        minj=i
        for j in range(i,N):
            if int(A[j][1:])<int(A[minj][1:]):
                minj=j
        swap=A[i]
        A[i]=A[minj]
        A[minj]=swap
    return A

def Stable(A1,A2):
    ans="Stable"
    for i in range(len(A1)):
        if A1[i][1:]==A2[i][1:] and A1[i][:1]!=A2[i][:1]:
            ans="Not stable"
    return ans

def SS2(N,A):
    A1=BS(N,A)
    print(" ".join(A1))
    print("Stable")
    A2=SS(N,A)
    print(" ".join(A2))
    print(Stable(A1,A2))

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

# Example run
# Input:
-17367
k^C
# Output:
k^C
Stable
k^C
Stable
import copy
def bubble(array):
    flag = set()
    for i in range(n):
        for j in range(1, n):
            if (array[j-1][1] > array[j][1]):
                tmp = array[j-1]
                array[j-1] = array[j]
                array[j] = tmp

    return array

def selection(array):
    flag = set()
    for i in range(0, n):
        minimum = i
        for j in range(i, n):
            if (array[j][1] < array[minimum][1]):
                minimum = j
        tmp = array[minimum]
        array[minimum] = array[i]
        array[i] = tmp

    return array

n = int(input())
array = input().split(" ")

for alg in [bubble, selection]:
    thirteen = [[] for _ in range(13)]
    for elmnt in array:
        thirteen[int(elmnt[1])-1].append(elmnt)
    sorted_ary = alg(copy.copy(array))

    sorted13 = [[] for _ in range(13)]
    for elmnt in sorted_ary:
        sorted13[int(elmnt[1])-1].append(elmnt)

    isStable = True
    print(" ".join(sorted_ary))
    for x, y in zip(thirteen, sorted13):
        if (x != y):
            isStable = False
    if isStable:
        print("Stable")
    else:
        print("Not stable")



# Example run
# Input:
-7038374
-6
# Output:
-6
Stable
-6
Stable
# coding: utf-8

def BubbleSort(A, n):
    for i in range(n-1):
        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]
    return A


def SelectionSort(A, n):
    mini = 1
    for i in range(n):
        mini = i
        for j in range(i, n):
            if int(A[j][1]) < int(A[mini][1]):
                mini = j
        A[i], A[mini] = A[mini], A[i]
    return A

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

b_ans = BubbleSort(A[:], n)
s_ans = SelectionSort(A[:], n)

print(" ".join(b_ans))
print("Stable")
print(" ".join(s_ans))
if b_ans == s_ans:
    print("Stable")
else:
    print("Not stable")

# Example run
# Input:
-3753932
4EPy8r+|E
# Output:
4EPy8r+|E
Stable
4EPy8r+|E
Stable
class card:
    def __init__(self, card):
        self.suit = card[0]
        self.value = int(card[1])

    def __repr__(self):
        return self.suit + str(self.value)


def selectionSort(a, n):
    r = 0
    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]


def bubbleSort(a, n):
    flag = True
    while flag:
        flag = False
        for j in range(n - 1, 0, -1):
            if a[j].value < a[j - 1].value:
                a[j], a[j - 1] = a[j - 1], a[j]
                flag = True


def copycard(cards):
    r = []
    for c in cards:
        r.append(card(c.suit + str(c.value)))
    return r


def compareCard(c1,c2):
    for i in range(len(c1)):
        if c1[i].suit != c2[i].suit or c1[i].value != c2[i].value:
            return False
    return True


n = int(input())
cards = list(map(card, input().split()))
cards1 = copycard(cards)
cards2 = copycard(cards)
bubbleSort(cards1, n)
print(*cards1)
print("Stable")
selectionSort(cards2, n)
print(*cards2)
if compareCard(cards1,cards2):
    print("Stable")
else:
    print("Not stable")




# Example run
# Input:
-307
-227999
# Output:
-2
Stable
-2
Stable
# 配列の宣言
A = []
B = []
C = []

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

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

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

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

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

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

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

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


# Example run
# Input:
-92190875
?m5v{UU
# Output:
?m5v{UU
Stable
?m5v{UU
Stable
n = int(input())
C = list(map(str,input().split()))
data = [[] for i in range(9)]
for i in C:
    data[int(i[1])-1].append(i[0])
D = [s for s in C]
#print(data)
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]
print(" ".join(C))
flag = True
for i in range(9):
    if len(data[i]) >= 2:
        for j in range(len(data[i])-1):
            if C.index(data[i][j]+"{}".format(i+1)) > C.index(data[i][j+1]+"{}".format(i+1)):
                print("Not stable")
                flag = False
                break
        if not flag:
            break
else:
    print("Stable")
for i in range(n):
    minj = i
    for j in range(i,n):
        if int(D[j][1]) < int(D[minj][1]):
            minj = j
    else:
        D[i],D[minj] = D[minj],D[i]
print(" ".join(D))
flag = True
for i in range(9):
    if len(data[i]) >= 2:
        for j in range(len(data[i])-1):
            if D.index(data[i][j]+"{}".format(i+1)) > D.index(data[i][j+1]+"{}".format(i+1)):
                print("Not stable")
                flag = False
                break
        if not flag:
            break
else:
    print("Stable")


# Example run
# Input:
-2031692
-1843740
# Output:
-1843740
Stable
-1843740
Stable
import copy
def inputInline():
    N = int(input())
    cards = input().split(" ")
    return cards

def selectionSort(list):
    cards=copy.deepcopy(list)
    n = len(cards)
    count = 0
    for i in range(n):
        min_j = i
        for j in range(i + 1, n):
            if int(cards[j][1]) < int(cards[min_j][1]):
                min_j = j
        if min_j != i:
            temp = cards[i]
            cards[i] = cards[min_j]
            cards[min_j] = temp
            count += 1
    return (" ".join(cards), count)

def bubbleSort(list):
    cards=copy.deepcopy(list)
    N = len(cards)
    count = 0
    flag = True
    while flag:
        flag = False
        for i in range(N - 1):
            if int(cards[i][1]) > int(cards[i + 1][1]):
                temp = cards[i]
                cards[i] = cards[i + 1]
                cards[i + 1] = temp
                flag = True
                count += 1
    return (" ".join(cards), count)
cards=inputInline()
sortedbubble=bubbleSort(cards)[0]
sortedselection=selectionSort(cards)[0]
print(sortedbubble)
print("Stable")
print(sortedselection)
if sortedbubble==sortedselection:
    print("Stable")
else:
    print("Not stable")

# Example run
# Input:
32
.)t
# Output:
.)t
Stable
.)t
Stable
import copy

n = int(input())
c = input().split()
bubble = copy.copy(c)
select = copy.copy(c)

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]):
                temp = C[j]
                C[j] = C[j-1]
                C[j-1] = temp
    return C

def SelectionSort(C, N):
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if int(C[j][1]) < int(C[minj][1]):
                minj = j
        temp = C[i]
        C[i] = C[minj]
        C[minj] = temp
    return C

BubbleSort(bubble, n)
SelectionSort(select, n)

print(*bubble)
print("Stable")
print(*select)

def isSame(C1, C2):
    for i in range(0, len(C1)):
        if C1[i] != C2[i]:
            return False
    return True

if isSame(bubble, select):
    print("Stable")
else:
    print("Not stable")
    
         



# Example run
# Input:
-2500715
L-)iTg5DK
# Output:
L-)iTg5DK
Stable
L-)iTg5DK
Stable
class Card:
    def __init__(self, suit, value):
        self.suit = suit
        self.value = value
    
def selection(ls):
    for i in range(len(ls)):
        minj = i
        
        for j in range(i, len(ls)):
            if ls[j].value < ls[minj].value:
                minj = j
        ls[i], ls[minj] = ls[minj], ls[i]

def bubblesort(ls):
    for i in range(1, len(ls)):
        for j in reversed(range(i, len(ls))):
            if ls[j].value < ls[j-1].value:
                ls[j], ls[j-1] = ls[j-1], ls[j]

def isStable(ls1, ls2):
    if ls1 == ls2:
        print("Stable")
    else:
        print("Not stable")

def printcards(cards):
    for card in cards:
        print(card.suit, card.value, ' ', sep='', end='')

    print('\n', end='')
    
def main():
    N = int(input().rstrip())

    cards = []
    for card in list(input().split(' ')):
        cards.append(Card(card[0], card[1]))

    a = [x for x in cards]
    b = [x for x in cards]
    
    selection(a)
    bubblesort(b)

    printcards(a)
    print("Stable")

    printcards(b)
    isStable(a,b)
    
if __name__ == '__main__':
    main()

# Example run
# Input:
0
Du7u+aa~!
# Output:
Du 
Stable
Du 
Stable
n = int(input())
lst = input().split()
bub, sel = lst[:], lst[:]
def stable(sls):
    s, i = 1, n-1
    while s*i:
        if sls[i][1] == sls[i-1][1]:
            if lst.index(sls[i]) < lst.index(sls[i-1]) :
                s = 0
        i -= 1
    print('Stable' if s else 'Not stable')

for i in range(n):
    m = i
    for j in range(n-1,i,-1):
        if bub[j][1] < bub[j-1][1]:
            bub[j-1:j+1] = bub[j], bub[j-1]
    for k in range(i, n):
        if sel[k][1] < sel[m][1]:
            m = k
    if m != i:
        sel[i], sel[m] = sel[m], sel[i]

print(*bub)
stable(bub)
print(*sel)
stable(sel)

# Example run
# Input:
1
i8gz<>-
# Output:
i8gz<>-
Stable
i8gz<>-
Stable
n=int(input())
l1=list(input().split())
l2=l1.copy()
 
def bubble(L,N):
    c=0
    for i in range(N):
        j=N-1
        while j>0:
            if int(L[j][1])<int(L[j-1][1]):
                L[j],L[j-1]=L[j-1],L[j]
            j-=1
    print(" ".join(L))

bubble(l1,n)
print("Stable")

def select(L,N):
    for i in range(N):
        L2=[int(L[k][1]) for k in range(N)]
        j = L2[i:].index(min(L2[i:])) + i
        L[i], L[j] = L[j], L[i]
    print(" ".join(map(str,L)))

select(l2,n)
if l1==l2:
    print("Stable")
else:
    print("Not stable")


# Example run
# Input:
-11989124
=C>#:pjLk
# Output:
=C>#:pjLk
Stable
=C>#:pjLk
Stable
_, cards = input(), input().split()

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

def selection_sort(array):
    A = array[:]
    for i in range(len(A)):
        minn = i
        for j in range(i, len(A)):
            if int(A[j][1]) < int(A[minn][1]): minn = j
        A[i], A[minn] = A[minn], A[i]
    return A
def is_stable(org, sorted):

    def get_same_numbers(array):
        result = {}
        for i in range(1, 10):
            result[i] = []
            for j in range(len(array)):
                if int(array[j][1]) == i:
                    result[i].append(array[j])
        return [cards for _, cards in result.items() if len(cards) >= 2]

    return "Stable" if get_same_numbers(org) == get_same_numbers(sorted) else "Not stable"

a = bubble_sort(cards)
print(" ".join(a))
print(is_stable(cards, a))
b = selection_sort(cards)
print(" ".join(b))
print(is_stable(cards, b))


# Example run
# Input:
ydgbn
-213932
# Output:
-213932
Stable
-213932
Stable