Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
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, N):
            if int(C[j][1]) < int(C[minj][1]):
                minj = j
        C[i], C[minj] = C[minj], C[i]
    return C

def isStable(B, S, N):
    for i in range(N):
        if B[i] != S[i]:
            return False
    return True

N = int(input())
C = input().split()
B = BubbleSort(C, N)
S = SelectionSort(C, N)
mes = "Stable" if isStable(B, S, N) else "Not stable"
print(" ".join(list(map(str, B))))
print("Stable")
print(" ".join(list(map(str, S))))
print(mes)

# Example run
# Input:
0
A=|#RS`
# Output:
A=|#RS`
Stable
A=|#RS`
Stable
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


class Card(object):

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

    def __str__(self):
        return str(self.card)


def print_array(a):
    print(" ".join(map(str, a)))


def bubblesort(cards, n):
    c = cards[::]
    for i in range(0, n):
        for j in range(n - 1, i, -1):
            if c[j].value < c[j - 1].value:
                (c[j], c[j - 1]) = (c[j - 1], c[j])
    return c


def selectionsort(cards, n):
    c = cards[::]
    for i in range(0, n):
        minj = i
        for j in range(i, n):
            if c[j].value < c[minj].value:
                minj = j
        (c[i], c[minj]) = (c[minj], c[i])
    return c


def main():
    n = int(input())
    cards = list(map(Card, input().split()))
    b = bubblesort(cards, n)
    print_array(b)
    print("Stable")
    s = selectionsort(cards, n)
    print_array(s)
    if b == s:
        print("Stable")
    else:
        print("Not stable")


if __name__ == "__main__":
    main()

# Example run
# Input:
-12762
25526938
# Output:
25526938
Stable
25526938
Stable
#! python3
# stable_sort.py

import copy

def num_from_card(card):
    return int(card[1:])

def bubble_sort(A, N):
    A_ = copy.copy(A)
    flag = True
    while flag:
        flag = False
        for i in range(N-1, 0, -1):
            if num_from_card(A_[i]) < num_from_card(A_[i-1]):
                A_[i-1], A_[i] = A_[i], A_[i-1]
                flag = True
    return A_

def selection_sort(A, N):
    A_ = copy.copy(A)
    for i in range(N-1):
        minj = i
        for j in range(i, N):
            if num_from_card(A_[j]) < num_from_card(A_[minj]):
                minj = j
        if i != minj:
            A_[i], A_[minj] = A_[minj], A_[i]
    return A_

def is_stable(A, sorted_A, N):
    A_nums = [int(x[1:]) for x in A]
    same_num = [x for x in set(A_nums) if A_nums.count(x) > 1]
    A_symbols, sorted_A_symbols = [], []
    flag = 'Stable'
    for num in same_num:
        if [card[0] for card in A if int(card[1:]) == num] != [card[0] for card in sorted_A if int(card[1:]) == num]:
            flag = 'Not stable'
            break
    return flag

N = int(input())
cards = [x for x in input().split(' ')]

bubble_sorted = bubble_sort(cards, N)
selection_sorted = selection_sort(cards, N)

print(' '.join(bubble_sorted))
print(is_stable(cards, bubble_sorted, N))
print(' '.join(selection_sorted))
print(is_stable(cards, selection_sorted, N))


# Example run
# Input:
-343875431
-3
# Output:
-3
Stable
-3
Stable
def BubbleSort(a, n):
    for i in range(n):
        for j in range(n-1, i, -1):
            if int(a[j][1]) < int(a[j - 1][1]):
                a[j], a[j-1] = a[j-1], a[j]
    return a


def SelectionSort(a, n):
    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 = a[:]
a = BubbleSort(a, n)
b = SelectionSort(b, n)


print(*a)
print("Stable")
print(*b)

if a == b:
    print("Stable")
else:
    print("Not Stable")

# Example run
# Input:
-114
nzXv9U
# Output:
nzXv9U
Stable
nzXv9U
Stable
def bubbleSort(a,n):
    for i in range(n):
        for j in range(n-1, i, -1):
            if a[j-1][1] > a[j][1]: #Sort by card number
                a[j-1], a[j] = a[j], a[j-1]
    print(' '.join(a))

def selectionSort(a,n):
    for i in range(n):
        minj = i
        for j in range(i,n):
            if a[j][1] < a[minj][1]: #Sort by card number
                minj = j
        if minj != i:
            a[i],a[minj] = a[minj],a[i]
    a = [str(s) for s in a]
    print(' '.join(a))

def isStable(a, a2):
    """
    :param a: Stable-sorted list (Bubble sort)
    :param a2: List to check if isStable
    :return: Boolean
    """
    if a == a2:
        return True
    else:
        return False

n = int(input())
a = list(input().split())
a2 = a[::]

bubbleSort(a,n)
print('Stable')
selectionSort(a2,n)
print('Stable' if isStable(a, a2) else 'Not stable')


# Example run
# Input:
-927746
chf
# Output:
chf
Stable
chf
Stable
import copy

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

if __name__ == '__main__':
    n = int(input())
    B = input().split()
    C_bubble = bubble_sort(copy.deepcopy(B))
    print(*C_bubble)
    print('Stable')
    C_selection = selection_sort(copy.deepcopy(B))
    print(*C_selection)
    if C_bubble == C_selection:
        print('Stable')
    else:
        print('Not stable')



# Example run
# Input:
176191212
197383
# Output:
197383
Stable
197383
Stable
def bubble_sort(c, n):
    is_swapped = True
    i = 0
    while is_swapped:
        is_swapped = False
        for j in range(n-1, i, -1):
            if c[j][1] < c[j-1][1]:
                tmp = c[j]
                c[j] = c[j-1]
                c[j-1] = tmp
                is_swapped = True
        i += 1


def selection_sort(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:
            tmp = c[i]
            c[i] = c[minj]
            c[minj] = tmp


def make_dict(l):
    result = {}
    for v in l:
        num = v[1]
        if num in result:
            result[num].append(v)
        else:
            result[num] = [v]
    result = {k: v for k, v in result.items() if len(v) >= 2}

    return result


def print_is_stable(before, after):
    is_stable = True
    before_dict = make_dict(before)
    after_dict = make_dict(after)
    for k in before_dict:
        if before_dict[k] != after_dict[k]:
            is_stable = False
            break

    if is_stable:
        print('Stable')
    else:
        print('Not stable')


n = int(input())
a = [i for i in input().split()]
c = a[:]

bubble_sort(c, n)
print(' '.join([str(i) for i in c]))
print_is_stable(a, c)

c = a[:]
selection_sort(c, n)
print(' '.join([str(i) for i in c]))
print_is_stable(a, c)


# Example run
# Input:
-105988
F%Ue
# Output:
F%Ue
Stable
F%Ue
Stable
N = int(input())
C = [x for x in input().split()]

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

def SelectionSort(C):
    N = len(C)
    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

D1 = C[:]
#注：D1 = Cだと参照渡しになる. つまり, D1を変更するとCも変更される
#C[:]を代入すると値渡しになる.
D1 = BubbleSort(D1)
for i in range(N-1):
    print(D1[i], end=" ")
print(D1[N-1])
print("Stable")

D2 = C[:]
D2 = SelectionSort(D2)
for i in range(N-1):
    print(D2[i], end=" ")
print(D2[N-1])
if D1 ==D2:
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
0
iWEj0(
# Output:
iWEj0(
Stable
iWEj0(
Stable
def bubbleSort(c, n):
    flag = 1
    while(flag) :
        flag = 0
        for i in reversed(range(1,n)):
            if(c[i][1] < c[i-1][1]):
                c[i], c[i-1] = c[i-1], c[i]
                flag = 1
    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 isStable(c1, c2, n):
    for i in range(n):
        if(c1[i] != c2[i]):
            return False
    return True

n = int(input())
c = input().split(' ')
trump = [list(i) for i in c]
bubble = ["".join(s) for s in bubbleSort(trump, n)]
selection = ["".join(s) for s in selectionSort(trump, n)]
str_bubble = " ".join(bubble)
str_selection = " ".join(selection)
print(str_bubble)
print('Stable')
print(str_selection)
if isStable(bubble, selection, n):
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
-1062073697
2<jugY\e+
# Output:
2<jugY\e+
Stable
2<jugY\e+
Stable
def bubblesort(n, a):
    r = a[:]
    for i in range(n):
        for j in range(n-1, i, -1):
            if int(r[j][1]) < int(r[j-1][1]):
                r[j], r[j-1] = r[j-1], r[j]

    print(*r)
    print("Stable")


def selectionsort(n, a):
    r = a[:]
    ret = "Stable"
    for i in range(n):
        tmp = i
        for j in range(i, n):
            if int(r[j][1]) < int(r[tmp][1]):
                tmp = j
        r[i], r[tmp] = r[tmp], r[i]

    for i in range(n):
        for j in range(i+1, n):
            for k in range(n):
                for l in range(k+1, n):
                    if int(a[i][1]) == int(a[j][1]) and a[i] == r[l] and a[j] == r[k]:
                        ret = "Not stable"

    print(*r)
    print(ret)


def main():
    n = int(input())
    a = list(input().split())

    bubblesort(n, a)
    selectionsort(n, a)


if __name__ == '__main__':
    main()


# Example run
# Input:
-802
{aD*M?G
# Output:
{aD*M?G
Stable
{aD*M?G
Stable
import sys
import copy
sys.setrecursionlimit(10 ** 7)

def bubbleSort(L):
    flg = True
    while flg:
        flg = False
        i = 0
        for j in range(len(L)-1,i,-1):
            if L[j][1] < L[j-1][1]:
                L[j] , L[j-1] = L[j-1], L[j]
                flg = True
        i += 1
    return L

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

N = int(input())
C1 = list(input().split())
C2 = copy.deepcopy(C1)
bC = bubbleSort(C1)
sC = selectionSort(C2)

print(*bC)
s = "Stable" #BubbleSort is stable sort!
print(s)

print(*sC)
s = "Stable"
for i in range(len(sC)-1):
    if sC[i][1] == bC[i][1] and sC[i][0] != bC[i][0]:
        s = "Not stable"
        break
print(s)


# Example run
# Input:
-6815
SE\wL
# Output:
SE\wL
Stable
SE\wL
Stable
n = int(input())
*s1, = input().split()
s2 = s1[:]

def bubbleSort(s):
    flag = True
    while flag:
        flag = False
        for i in range(n-1):
            if int(s[i][1]) > int(s[i+1][1]):
                s[i],s[i+1] = s[i+1],s[i]
                flag = True
    return s

def selectionSort(s):
    for i in range(n):
        minj = i
        for j in range(i+1,n):
            if int(s[minj][1]) > int(s[j][1]):
                minj = j
        s[i],s[minj] = s[minj],s[i]
    return s

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



# Example run
# Input:
-84564737
!8'gg[Y)
# Output:
!8'gg[Y)
Stable
!8'gg[Y)
Stable
N = int(input())
C = list(input().split())
_C = C.copy()

for i in range(N):
    for j in range(N-1, i, -1):
        if (C[j] < C[j-1]):
            C[j], C[j-1] = C[j-1], C[j]
print(*C)
print("Stable")

for j in range(N):
    m = i
    for j in range(i, N):
        if (_C[j] < _C[j-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:
-39355
QV_
# Output:
QV_
Stable
QV_
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:
			tmp = A[i]
			A[i] = A[minj]
			A[minj] = tmp

	return A

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:]:
				tmp = A[j]
				A[j] = A[j - 1]
				A[j - 1] = tmp

	return A

if __name__ == '__main__':
	n = int(input())
	R = list(map(str, input().split()))
	C = R[:]
	SR = selectionSort(R, n)
	BR = bubbleSort(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:
-213932
bJ)
# Output:
bJ)
Stable
bJ)
Stable
from collections import namedtuple


def BubbleSort(C, N):
    for i in range(N):
        for j in range(N-1, i, -1):
            if C[j].value < C[j-1].value:
                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].value < C[minj].value:
                minj = j
        C[i], C[minj] = C[minj], C[i]


Card = namedtuple('Card', 'mark value')
n = int(input())
a = [Card(i[0], int(i[1])) for i in input().split()]
b = a[:]

BubbleSort(a, n)
SelectionSort(b, n)

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

# Example run
# Input:
-2173169
-474368936
# Output:
-4
Stable
-4
Stable
import copy
n = int(input())
b = list(map(str, input().split()))
a = copy.copy(b)
c = copy.copy(b)
k = 'Stable'

flag = 1
i = 0
while flag:
    flag = 0
    for j in range(n - 1, i, -1):
        if b[j][1] < b[j - 1][1]:
            t = b[j]
            b[j] = b[j - 1]
            b[j - 1] = t
            flag = 1
    i += 1

for i in range(0, n - 1):
    print(b[i], end=' ')
print(b[n - 1])
print(k)

for i in range(0, n):
    minj = i
    for j in range(i + 1, n):
        if a[j][1] < a[minj][1]:
            minj = j
    t = a[i]
    a[i] = a[minj]
    a[minj] = t

fl = 0
for i in range(0, n):
    for j in range(i+1, n):
        if a[i][1] == a[j][1]:
            for q in range(0, n):
                if c[q][1] == a[i][1]:
                    if c[q][0] == a[i][0]:
                        break
                    else:
                        fl = 1
if fl == 1:
    k = 'Not stable'


for i in range(0, n - 1):
    print(a[i], end=' ')
print(a[n - 1])
print(k)


# Example run
# Input:
0
-x4d
# Output:
-x4d
Stable
-x4d
Stable
import copy
N = int(input())
bscs = [(int(c[-1]), c) for c in input().split(" ")]
sscs = copy.copy(bscs)
for i in range(N):
    j = N - 1
    while j > i:
        if bscs[j][0] < bscs[j - 1][0]:
            tmp = bscs[j]
            bscs[j] = bscs[j - 1]
            bscs[j - 1] = tmp
        j -= 1
print(bscs)
print("Stable")
for i in range(N):
    minj = i
    for j in range(i, N):
        if sscs[j][0] < sscs[minj][0]:
            minj = j
    tmp = sscs[i]
    sscs[i] = sscs[minj]
    sscs[minj] = tmp
print(sscs)
print("Stable" if bscs == sscs else "Not Stable")

# Example run
# Input:
-426204934
-83
# Output:
[(3, '-83')]
Stable
[(3, '-83')]
Stable
n = int(input())
c = list(map(str, input().split()))
c_copy = list(c)

def bubble_sort(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]
    return c

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

def is_stable(c1, c2):
    if c1 == c2:
        print("Stable")
    else:
        print("Not stable")

c1 = bubble_sort(c, n)
print(' '.join(c1))
print('Stable')
c2 = selection_sort(c_copy, n)
print(' '.join(c2))
is_stable(c1,c2)


# Example run
# Input:
0
UUuK
# Output:
UUuK
Stable
UUuK
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:
-252699780
WIDt
# Output:
WIDt
Stable
WIDt
Stable
def bubble_sort(cards):
    list_length = len(cards)

    for i in range(list_length):
        for j in range(list_length-1,i,-1):
            if int(cards[j][1:]) < int(cards[j-1][1:]):
                cards[j],cards[j-1] = cards[j-1],cards[j]
    return cards

def selection_sort(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())
cards = input().split()
bubble_cards = [i for i in bubble_sort(cards)]
selection_cards = [i for i in selection_sort(cards,n)]

print(' '.join(bubble_cards))
print('Stable')
print(' '.join(selection_cards))
if bubble_cards == selection_cards:
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
-13048871
`A_\6MN
# Output:
`A_\6MN
Stable
`A_\6MN
Stable
def bubbleSort(a, n):   #n個の要素を持つ配列a
    flag = 1    #逆の隣接要素あり
    i = 0       #未ソートの先頭
    #count = 0
    while flag:
        flag = 0
        for j in range(n-1, i, -1): #j n-1...i+1
            if a[j][1] < a[j-1][1]:

                a[j], a[j-1] = a[j-1], a[j]
                #count += 1
                flag = 1
        i += 1
    print(' '.join(map(str, a)))
    #print(count)

def selectionSort(a, n):
    #count = 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]
    printArray(a)
    #print(count)

def isStable(a1, a2):
    if a1 == a2:
        print("Stable")
    else:
        print("Not stable")


#配列の出力
def printArray(a):
    print(' '.join(map(str, a)))

#配列の要素数と要素の入力
n = int(input())
a = list(input().split())
a2 = a.copy()

bubbleSort(a, n)
print("Stable")
selectionSort(a2, n)
isStable(a, a2)


# Example run
# Input:
-2040
RN-`2,MZ0
# Output:
RN-`2,MZ0
Stable
RN-`2,MZ0
Stable
import copy
def bubblesort(card,maisu):
    for i in range(maisu):
        for j in reversed(range(i+1,maisu)):
            if card[j][1]<card[j-1][1]:
                card[j-1],card[j]=card[j],card[j-1]

def selectionsort(card,maisu):
    for i in range(maisu):
        mini=i
        for j in range(i,maisu):
            if card[j][1]<card[mini][1]:
                mini=j
        card[i],card[mini]=card[mini],card[i]

def output(card,maisu):
    joutai="Stable"
    for i in range(maisu):
        if i>0:
            print(" ",end="")
        print(card[i][0]+card[i][1],end="")
        if i<=maisu-2:
            if card[i][1]==card[i+1][1] and card[i][2]>card[i+1][2]:
                joutai="Not stable"
    print()
    print(joutai)
    
maisu=int(input())
card=list(map(str,input().split()))
for i in range(maisu):
    a=[]
    for j in card[i]:
        a.append(j)
    a.append(i)
    card[i]=a
    
card_bubble=copy.deepcopy(card)
card_selection=copy.deepcopy(card)

bubblesort(card_bubble,maisu)
output(card_bubble,maisu)

selectionsort(card_selection,maisu)
output(card_selection,maisu)



# Example run
# Input:
0
8\G<E[
# Output:

Stable

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,B):
    A1=BS(N,A)
    print(" ".join(A1))
    print("Stable")
    A2=SS(N,B)
    print(" ".join(A2))
    print(Stable(A1,A2))

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

# Example run
# Input:
-3
ADFb)W
# Output:
ADFb)W
Stable
ADFb)W
Stable
# -*- coding:utf-8 -*-

import copy

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

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

def is_stable(before_sort, after_sort):
    current_num = 0
    same_number_card = list()
    for num in after_sort:
        if current_num == int(num[1]):
            for same_card in same_number_card:
                if before_sort.index(same_card) > before_sort.index(num):
                    return False
            same_number_card.append(num)
        else:
            current_num = int(num[1])
            same_number_card = [num,]
    return True

def show_list(list):
    i = 0;
    while(i < len(list)-1):
        print(list[i], end=" ")
        i = i + 1
    print(list[i])

def show_stable(flag):
    if flag:
        print('Stable')
    else:
        print('Not stable')

num = int(input())
input_card = [x for i, x in enumerate(input().split()) if i < num]
bubble_sort_card = bubble_sort(copy.deepcopy(input_card))
show_list(bubble_sort_card)
show_stable(is_stable(input_card, bubble_sort_card))
selection_sort_card = selection_sort(copy.deepcopy(input_card))
show_list(selection_sort_card)
show_stable(is_stable(input_card, selection_sort_card))

# Example run
# Input:
3
I8vL
# Output:
I8vL
Stable
I8vL
Stable
def swap(a, i, j):
    # list aのi番目の要素とj番目の要素を交換する関数
    k = a[j]
    a[j] = a[i]
    a[i] = k


def selectionSort(a, n):
    for i in range(n):
        minj = i
        for j in range(i,n):
            if a[j][1] < a[minj][1]: #数字が１桁なのでstrのまま比較可能
                minj = j
        swap(a, i, minj)


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


n = int(input())
a = list(input().split())
b = a[:]
bubbleSort(a, n)
print(' '.join(a))
print('Stable')
selectionSort(b, n)
print(' '.join(b))
if a == b:
    print('Stable')
else:
    print('Not stable')



# Example run
# Input:
-6
hZFv
# Output:
hZFv
Stable
hZFv
Stable
import copy

N = int(input())

def hoge(arg):
    return [arg[0], int(arg[1])]

A = list(map(hoge, map(str, input().split())))
A1 = copy.deepcopy(A)
A2 = copy.deepcopy(A)

def bsort(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 ssort(C, N):
    for i in range(N):
        minj = i
        for j in range(i, N, 1):
            if C[j][1] < C[minj][1]:
                minj = j
        C[i], C[minj] = C[minj], C[i]

def judge(A, A1):
    for i in range(len(A) - 1):
        if A1[i][1] != A1[i+1][1]:
            continue
        a = A.index(A1[i])
        b = A.index(A1[i+1])
        if a > b:
            return 'Not stable'
    return 'Stable'

def toString(A):
    return A[0] + str(A[1])

bsort(A1, N)
print(' '.join(list(map(toString, A1))))
print(judge(A, A1))
ssort(A2, N)
print(' '.join(list(map(toString, A2))))
print(judge(A, A2))



# Example run
# Input:
-13840614
2147483647
# Output:
21
Stable
21
Stable