Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
from typing import List


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


def selection_sort(A: List[str], N: int) -> List[str]:
    for i in range(N - 1):
        tmp_min_index: int = i
        for j in range(i + 1, N):
            if A[tmp_min_index][1] > A[j][1]:
                tmp_min_index = j
        A[i], A[tmp_min_index] = A[tmp_min_index], A[i]
    return A


def is_stable(A: List[str], A_sorted: List[str], N: int) -> bool:
    for i in range(N - 1):
        for j in range(i + 1, N):
            # for a in range(N - 1):
            #     for b in range(a + 1, N):
            #         if A[i][1] == A[j][1] and A_sorted[a] == A[j] and A_sorted[b] == A[i]:
            #             return False
            if A[i][1] == A[j][1] and A_sorted.index(A[j]) < A_sorted.index(A[i]):
                return False
    return True


def main():
    N: int = int(input())
    A: List[str] = list(input().split())

    A_bubble = bubble_sort(A[:], N)
    A_selection = selection_sort(A[:], N)

    print(*A_bubble, sep=" ")
    print("Stable")
    print(*A_selection, sep=" ")
    print("Stable") if A_bubble == A_selection else print("Not stable")

    # print("Stable") if is_stable(A, A_bubble,
    #                              N) else print("Not stable")
    # print("Stable") if is_stable(A, A_selection,
    #                              N) else print("Not stable")


if __name__ == "__main__":
    main()



# Example run
# Input:
-27123728
(XQ6o%K<
# Output:
(XQ6o%K<
Stable
(XQ6o%K<
Stable
def bubbleSort(c):
    for i in range(0, len(c) - 1):
        for j in range(len(c)-1, i, -1):
            if c[j][1] < c[j-1][1]:
                c[j], c[j-1] = c[j-1], c[j]


def selectionSort(c):
    for i in range(0, len(c)):
        minj = i
        for j in range(i, len(c)):
            if c[j][1] < c[minj][1]:
                minj = j
        c[i], c[minj] = c[minj], c[i]


def isStable(c1, c2):
    for i in range(0, len(c1)):
        if c1[i][0] != c2[i][0]:
            return False
    return True


import copy
n = int(input())
c1 = input().split()
c2 = copy.copy(c1)

bubbleSort(c1)
selectionSort(c2)
print(*c1)
print("Stable")
print(*c2)
print("Stable") if isStable(c1, c2) else print("Not stable")



# Example run
# Input:
116
MzRwa
# Output:
MzRwa
Stable
MzRwa
Stable
def BubbleSort(C, N):
    for i in range(0,N):
        for j in range(N-1,i,-1):
            if C[j][1:] < C[j-1][1:]:
                #  C[j] と C[j-1] を交換
                tmp = C[j]
                C[j] = C[j-1]
                C[j-1] = tmp
    ret = " ".join(C)
    print(ret)
    print("Stable")
    return ret

def SelectionSort(C, N):
    for i in range(0,N):
        minj = i
        for j in range(i,N):
            if C[j][1:] < C[minj][1:]:
                minj = j
        # C[i] と C[minj] を交換
        tmp = C[i]
        C[i] = C[minj]
        C[minj] = tmp
    ret = " ".join(C)
    print(ret)
    return ret

N = int(input())
C = input().split(" ")
ret_B = BubbleSort(C,N)
ret_S = SelectionSort(C,N)
if ret_B == ret_S:
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
0
UUuK
# Output:
UUuK
Stable
UUuK
Stable
def BubbleSort(C, N):
    for i in range(0,N):
        for j in range(N-1,i,-1):
            if C[j][1:] < C[j-1][1:]:
                #  C[j] と C[j-1] を交換
                tmp = C[j]
                C[j] = C[j-1]
                C[j-1] = tmp
    ret = " ".join(C)
    print(ret)
    print("Stable")
    return ret

def SelectionSort(C, N):
    for i in range(0,N):
        minj = i
        for j in range(i,N):
            if C[j][1:] <= C[minj][1:]:
                minj = j
        # C[i] と C[minj] を交換
        tmp = C[i]
        C[i] = C[minj]
        C[minj] = tmp
    ret = " ".join(C)
    print(ret)
    return ret

N = int(input())
C = input().split(" ")
ret_B = BubbleSort(C,N)
ret_S = SelectionSort(C,N)
if ret_B == ret_S:
    print("stable")
else:
    print("Not stable")



# Example run
# Input:
-2147483648
%f%0M@q
# Output:
%f%0M@q
Stable
%f%0M@q
stable
N = int(input())
A = input().split(" ")

def bubble_sort(A):
  N = len(A)
  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 - 1], A[j] = A[j], A[j - 1]
  return A

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

def is_stable(A, B):
  map_a = {}
  map_b = {}
  for i in range(len(A)):
    s_a = A[i][0]
    s_b = B[i][0]
    v_a = A[i][1]
    v_b = B[i][1]
    if v_a in map_a:
      map_a[v_a].append(s_a)
    else:
      map_a[v_a] = [s_a]
    if v_b in map_b:
      map_b[v_b].append(s_b)
    else:
      map_b[v_b] = [s_b]

  result = True
  for k in map_a:
    if len(map_a[k]) > 1:
      result = result and (map_a[k] == map_b[k])

  return result

A_sorted = bubble_sort(A[:])
print(" ".join(A_sorted))
print("Stable") if is_stable(A, A_sorted) else print("Not stable")

A_sorted = selection_sort(A[:])
print(" ".join(A_sorted))
print("Stable") if is_stable(A, A_sorted) else print("Not stable")

# Example run
# Input:
-224484380
kF,}Eok"$
# Output:
kF,}Eok"$
Stable
kF,}Eok"$
Stable
def bubbleSort(list_a, n):
    flag = 1
    i = 0
    while flag:
        flag = 0
        for j in list(range(i+1,n))[::-1]:
            if list_a[j][1] < list_a[j-1][1]:
                (list_a[j], list_a[j-1]) = (list_a[j-1], list_a[j])
                flag = 1
    return list_a

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


n = int(input())
list_a_origin = list(map(str, input().split()))
list_a = list_a_origin.copy()
bubbleSort(list_a, n)
list_a_pre = list_a.copy()
print(" ".join(list_a))
bubbleSort(list_a, n)
if list_a_pre == list_a:
    print("Stable")
else:
    print("Not stable")

list_a2 = list_a_origin.copy()
selectionSort(list_a2, n)
list_a_pre2 = list_a2.copy()
print(" ".join(list_a2))
selectionSort(list_a2, n)
if list_a_pre2 == list_a:
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
-13
%MVUC.SD+
# Output:
%MVUC.SD+
Stable
%MVUC.SD+
Stable
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]):
                c[j], c[j-1] = c[j-1], c[j]

    return c


def selectionsort(c, n):
    for i in range(0, n):
        min_j = i
        for j in range(i, n):
            if int(c[j][1]) < int(c[min_j][1]):
                min_j = j

        c[i], c[min_j] = c[min_j], c[i]

    return c


n = int(input())
c_to_bubble = list(map(str, input().split()))
c_to_selection = c_to_bubble.copy()

bubblesorted = bubblesort(c_to_bubble, n)
selectionsorted = selectionsort(c_to_selection, n)

print(' '.join(bubblesorted))
print('Stable')
print(' '.join(selectionsorted))
if bubblesorted == selectionsorted:
    print('Stable')
else:
    print('Not stable')






# Example run
# Input:
-7
'VhS
# Output:
'VhS
Stable
'VhS
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:
-3433
@c!;Qz
# Output:
@c!;Qz
Stable
@c!;Qz
Stable
import copy
def bs(array):
    for i in range(len(array)-1):
        for c in range(len(array)-1, i,-1):
            if array[c][1] < array[c-1][1]:
                swap = array[c]
                array[c] = array[c-1]
                array[c-1] = swap
    return array
def ss(array):
    for i in range(len(array)):
        minj = i
        for c in range(i+1,len(array)):
            if array[minj][1] > array[c][1]:
                minj = c
        swap = array[i]
        array[i] = array[minj]
        array[minj] = swap
    return array
def isStable(ar1,ar2):
    flag = 0
    for (x,y) in zip(ar1,ar2):
        if x != y:
            flag = 1
            break
    if flag == 0:
        print('Stable')
    else:
        print('Not stable')


n = input()
arr = [[i[0],int(i[1])] for i in input().split()]
arr1 = copy.deepcopy(arr)
arr2 = copy.deepcopy(arr)

bsarr = bs(arr2)
ssarr = ss(arr1)
print(' '.join([''.join([ x[0], str(x[1]) ]) for x in bsarr]))
print('Stable')
print(' '.join([''.join([ x[0], str(x[1]) ]) for x in ssarr]))
isStable(bsarr,ssarr)

# Example run
# Input:
k5)"q
-43332
# Output:
-4
Stable
-4
Stable
def ssort(L, n):
    L = L[:]
    for i in range(n):
        minj = i
        for j in range(i, n):
            if L[j][1] < L[minj][1]:
                minj = j
        L[i], L[minj] = L[minj], L[i]
    return L

def bsort(L, n):
    L = L[:]
    for _ in L:
        for j in range(n-1, 0, -1):
            if L[j][1] < L[j-1][1]:
                L[j], L[j-1] = L[j-1], L[j]
    return L

def is_stable(L_in, L_out):
    in_pair_list= []
    out_pair_list= []
    for i, e1 in enumerate(L_in):
        for j, e2 in enumerate(L_in[i+1:]):
            if e1[1] == e2[1]:
                in_pair_list.append((e1, e2))
    for i, e1 in enumerate(L_out):
        for j, e2 in enumerate(L_out[i+1:]):
            if e1[1] == e2[1]:
                out_pair_list.append((e1, e2))
    return not bool(set(in_pair_list) - set(out_pair_list))

def print_stable(b):
    print('Stable' if b else 'Not stable')

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

b = bsort(L, n)
print(*b)
print_stable(is_stable(L, b))
s = ssort(L, n)
print(*s)
print_stable(is_stable(L, s))

# Example run
# Input:
-74186
oBtKmC1{'
# Output:
oBtKmC1{'
Stable
oBtKmC1{'
Stable
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	stable_sort
# CreatedDate:  2020-07-08 14:29:32 +0900
# LastModified: 2020-07-08 14:56:46 +0900
#


import os
import sys
from copy import deepcopy
# import numpy as np
# import pandas as pd


def BubbleSort(a, n):
    for i in range(n-1):
        for j in range(n-1, i, -1):
            if a[j-1][1] > a[j][1]:
                tmp = a[j-1]
                a[j-1] = a[j]
                a[j] = tmp


def SelectionSort(b, n):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if b[j][1] < b[minj][1]:
                minj = j
        tmp = b[minj]
        b[minj] = b[i]
        b[i] = tmp



def main():
    n = int(input())
    s = list(map(str, input().split()))
    a = deepcopy(s)
    b = deepcopy(s)
    BubbleSort(a, n)
    print(a[0], end='')
    for i in range(1, n):
        print(" {}".format(a[i]), end='')
    print()
    print("Stable")

    SelectionSort(b, n)
    print(b[0], end='')
    for i in range(1, n):
        print(" {}".format(b[i]), end='')
    print()
    for a_, b_ in zip(a, b):
        if a_!=b_:
            print("Not stable")
            return
    print("Stable")


if __name__ == "__main__":
    main()



# Example run
# Input:
-86077887
i[%sQ
# Output:
i[%sQ
Stable
i[%sQ
Stable
#coding:utf-8
from copy import deepcopy

n = int(input())
A = list(input().split())
B = deepcopy(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]:
                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]
        
                
BubbleSort(A,n)
SelectionSort(B,n)
A = " ".join([data for data in A])
B = " ".join([data for data in B])

print(A)
print("Stable")

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



# Example run
# Input:
-31
6ej=k^S/8
# Output:
6ej=k^S/8
Stable
6ej=k^S/8
Stable
def bubble_sort(c, n):
    x = c[:]
    for i in range(n):
        for k in range(n-1, i, -1):
            if x[k][1] < x[k-1][1]:
                x[k], x[k-1] = x[k-1], x[k]
    return x

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

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

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

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


# Example run
# Input:
-1
3478382
# Output:
34
Stable
34
Stable
def isStable(before_sort, after_sort):
    num = len(before_sort)
    
    for i in range(0, num-1):
        for j in range(i+1, num):
            for a in range(0, num-1):
                for b in range(a+1, num):
                    if before_sort[i][1] == after_sort[j][1] and \
                       before_sort[i] == after_sort[b] and \
                       before_sort[j] == after_sort[a]:
                        return False
    return True

def isStable2(sorted_data, bubble_sort_data):
    for i in range(0, len(sorted_data)):
        if sorted_data[i] != bubble_sort_data[i]:
            return False
    return True
    
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]):
                c[j], c[j-1] = c[j-1], c[j]

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
        c[i], c[minj] = c[minj], c[i]
    
num = int(input())
data = input().split(' ')

copy_data = data.copy()
BubbleSort(copy_data, num)
print(copy_data)
if isStable(copy_data, copy_data):
    print("Stable")
else:
    print("Not stable")

bubble_sort_data = data.copy()
SelectionSort(bubble_sort_data, num)
print(bubble_sort_data)
if isStable(bubble_sort_data, copy_data):
    print("Stable")
else:
    print("Not stable")

# Example run
# Input:
0
-+%Exq\|
# Output:
['-+%Exq\\|']
Stable
['-+%Exq\\|']
Stable
def bubble(n, A):
    flag = True
    i = 0
    while (flag):
        flag = False
        for j in reversed(range(i+1, n)):
            if (A[j-1][1] > A[j][1]):
                A[j-1], A[j] = A[j], A[j-1]
                flag = True
        i += 1
    return A

def selection(n, A):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if (A[minj][1] > A[j][1]):
                minj = j
        A[minj], A[i] = A[i], A[minj]
    return A

def judge(A, B):
    for i in range(n):
        if (bubble(n, A)[i] != selection(n, B)[i]):
            return "Not stable"
    return "Stable"

n = int(input())
A = input().split(" ")
B = A.copy()
print (" ".join(bubble(n, A)))
print ("Stable")
print (" ".join(selection(n, B)))
print (judge(bubble(n, A), selection(n, B)))


# Example run
# Input:
-11385106
oo'V
# Output:
oo'V
Stable
oo'V
Stable
import copy

array_to_str = lambda A: ' '.join([str(a) for a in A])
input_number = lambda: int(input())
input_num_array = lambda: [int(a) for a in input().split()]
input_array = lambda: input().split()

def bubble_sort(C, A, N):
  flag = 1
  while flag:
    flag = 0
    for j in range(N)[:0:-1]:
      if A[j] < A[j-1]:
        A[j],A[j-1] = A[j-1], A[j]
        C[j],C[j-1] = C[j-1], C[j]
        flag = 1
  print(' '.join(C))
  print('Stable')

def selection_sort(C, A, N):
  stability = True
  for i in range(N):
    minj = i
    for j in range(i,N):
      if A[j] < A[minj]:
        minj = j

    # if i > minj and A[minj] == A[i]:
    #   stability = not stability

    C[i], C[minj] = C[minj], C[i]
    A[i], A[minj] = A[minj], A[i]
        
  print(' '.join(C))
  # print('Stable' if stability else 'Not stable')

N = input_number()
C = input_array()
A = [int(c[1]) for c in C]
A_copy = copy.copy(A)
C_copy = copy.copy(C)
bubble_sort(C_copy, A_copy, N)
selection_sort(C, A, N)
print('Stable' if C == C_copy else 'Not stable')


# Example run
# Input:
-9225256
339175880
# Output:
339175880
Stable
339175880
Stable
#coding: UTF-8

import copy
class Algo:
  @staticmethod
  def bubbleSort(r, c, n):
    print(r)
    print(c)
    flag = 1
    while flag:
      flag = 0
      for j in range(n-1, 0, -1):
        if c[j] < c[j-1]:
          c[j], c[j-1] = c[j-1], c[j]
          r[j], r[j-1] = r[j-1], r[j]
          flag = 1
    return r

  def selectionSort(r, c, n):
    print(r)
    print(c)
    for i in range(0,n):
      minj = i
      for j in range(i,n):
        if c[j] < c[minj]:
          minj = j
      if c[i] != c[minj]:
        c[i], c[minj] = c[minj], c[i]
        r[i], r[minj] = r[minj], r[i]
    return r

  def createIntList(r, n):
    c = []
    for i in range(0,n):
      c.append(r[i][1])
    return c

  def printList(r, n):
    for i in range(0,n):
      if i == n-1:
        print(r[i])
      else:
        print(r[i], " ", sep="", end="")

n = int(input())
r = list(map(str,input().split()))
c = Algo.createIntList(r, n)
br = Algo.bubbleSort(copy.deepcopy(r), copy.deepcopy(c), n)
ir = Algo.selectionSort(copy.deepcopy(r), copy.deepcopy(c), n)
Algo.printList(br, n)
print("Stable")
Algo.printList(ir, n)
if br == ir:
  print("Stable")
else:
  print("Not stable")

# Example run
# Input:
-4
kQ@YZ@p
# Output:
['kQ@YZ@p']
[]
['kQ@YZ@p']
[]
Stable
Stable
import re

def bubbleSort(A, n):
    flag = True
    while flag:
        flag = False
        for j in range (1,n)[::-1]:
            if int(re.sub("\\D", "", A[j])) < int(re.sub("\\D", "", A[j-1])):
                A[j],A[j-1] = A[j-1],A[j]
                flag = True
    return [str(a) for a in A]


def selectionSort(A, n):
    for i in range (n):
        minj = i
        for j in range (i,n):
            if int(re.sub("\\D", "", A[j])) < int(re.sub("\\D", "", A[minj])):
                minj = j
        A[i],A[minj] = A[minj],A[i]
    return [str(a) for a in A]



n = int(input())
A = input().split()
B = [str(a) for a in A]

if bubbleSort(A, n) == selectionSort(B, n):
    print(" ".join(bubbleSort(A, n)))
    print("Stable")
    print(" ".join(selectionSort(A, n)))
    print("Stable")
else:
    print(" ".join(bubbleSort(A, n)))
    print("Stable")
    print(" ".join(selectionSort(B, n)))
    print("Not stable")



# Example run
# Input:
-108610
tGi/0zig(
# Output:
tGi/0zig(
Stable
tGi/0zig(
Stable
def print_list(array):
    for i,e in enumerate(array):
        if i == N - 1:
            print(e)
        else:
            print(e, end=" ")

def bubbleSort():
    for i in range(N-1):
        for j in range(N-1, i, -1):
            if int(A[j][1:]) < int(A[j-1][1:]):
                w = A[j]; A[j] = A[j-1]; A[j-1] = w

def selectionSort():
    for i in range(N):
        min_index = i
        for j in range(i, N):
            if int(B[min_index][1:]) > int(B[j][1:]):
                min_index = j
        if i != min_index:
            w = B[i]; B[i] = B[min_index]; B[min_index] = w

N = int(input())
A = input().split()
B = list(A)
bubbleSort()
print_list(A)
print("Stable")
selectionSort()
print_list(B)
if A == B:
    print("Stable")
else:
    print("Not Stable")



# Example run
# Input:
-10841372
F!2eKDu
# Output:
F!2eKDu Stable
F!2eKDu Stable
def bubble_sort(A,N,M):
    flag = 1
    while flag:
        flag = 0
        for i in range(N-1,0,-1):
            if A[i] < A[i-1]:
                tmp = A[i]
                tmp2 = M[i]
                A[i] = A[i-1]
                M[i] = M[i-1]
                A[i-1] = tmp
                M[i-1] = tmp2
                flag = 1
    return M

def choice_sort(A,N,M):
    for i in range(N):
        top = A[i]
        tp = M[i]
        mini = min(A[i:])
        if top > mini:
            tmp = top
            tmpIndex = A[i:].index(mini) + i
            A[i] = mini
            A[tmpIndex] = tmp
            M[i] = M[tmpIndex]
            M[tmpIndex] = tp
    return M

time = int(input())
nums = list(input().split(" "))
numnum = []
for i in nums:
    numnum.append(list(i)[1])
numnum2 = numnum.copy()
memo = []
for i in range(time):
    memo.append(i)
memo2 = memo.copy()

bubble_order = bubble_sort(numnum,time,memo)
answer = ""
for i in bubble_order:
    answer += str(nums[i])
    answer += ' '
print(answer[:-1])
print("Stable")

choice_order = choice_sort(numnum2,time,memo2)
answer2 = ""
for i in choice_order:
    answer2 += str(nums[i])
    answer2 += ' '
print(answer2[:-1])


if answer[:-1] == answer2[:-1]:
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
-233
o/$h8z
# Output:

Stable

Stable
import copy

class Card():
    def __init__(self, str):
        self.id = str
        self.sort = str[0]
        self.value = int(str[1])


def selectionSort(A, N):
    for i in range(N-1):
        minj = i
        for j in range(i, N):
            if A[j].value < A[minj].value:
                minj = j
        if i != minj:
            temp = A[i]
            A[i] = A[minj]
            A[minj] = temp

def bubbleSort(l, n):
    flag = 1
    while flag:
        flag = 0
        for i in range(n-1, 0, -1):
            if l[i].value < l[i-1].value:
                temp = l[i]
                l[i] = l[i-1]
                l[i-1] = temp
                flag = 1

def isStable(input, output, N):
    for i in range(N-1):
        for j in range(i+1, N):
            for a in range(N-1):
                for b in range(a+1, N):
                    if input[i].value == input[j].value and input[i] == output[b] and input[j] == output[a]:
                        return False
    return True

N = int(input())
A = list(map(Card, input().split()))
A_b = copy.copy(A)
A_s = copy.copy(A)

bubbleSort(A_b, N)
print(" ".join(map(lambda x: x.id, A_b)))
if isStable(A, A_b, N):
    print("Stable")
else:
    print("Not stable")

selectionSort(A_s, N)
print(" ".join(map(lambda x: x.id, A_s)))
if isStable(A, A_s, N):
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
-40
-18579092
# Output:
-18579092
Stable
-18579092
Stable
import copy

n=int(input())
s=input().split(' ')
s1=[]
s2=[]
s1=copy.deepcopy(s)
s2=copy.deepcopy(s)

def Bubble_Sort(n,s1):
	m=0
	flag=1
	while flag:
		flag=0
		for i in range(1,n):
			j=n-i
			if int(s1[j][1])<int(s1[j-1][1]):
				a=s1[j]
				s1[j]=s1[j-1]
				s1[j-1]=a
				m+=1
				flag=1
	b=s1
	return(b)

def Selection_Sort(n,s2):
	m=0
	for i in range(n):
		minj=i
		for j in range(i,n):
			if int(s2[j][1])<int(s2[minj][1]):
				minj=j
		if i!=minj:
			a=s2[minj]
			s2[minj]=s2[i]
			s2[i]=a
			m+=1
	b=s2
	return(b)

s1=Bubble_Sort(n,s1)
s2=Selection_Sort(n,s2)

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


# Example run
# Input:
-28
56)B`
# Output:
56)B`
Stable
56)B`
Stable