Problem:
Stable Sort Let's arrange a deck of cards. There are totally 36 cards of 4 suits(S, H, C, D) and 9 values (1, 2, ... 9). For example, 'eight of heart' is represented by H8 and 'one of diamonds' is represented by D1 . Your task is to write a program which sorts a given set of cards in ascending order by their values using the Bubble Sort algorithms and the Selection Sort algorithm respectively. These algorithms should be based on the following pseudocode: BubbleSort(C)
1 for i = 0 to C.length-1
2     for j = C.length-1 downto i+1
3         if C[j].value < C[j-1].value
4             swap C[j] and C[j-1] SelectionSort(C)
1 for i = 0 to C.length-1
2     mini = i
3     for j = i to C.length-1
4         if C[j].value < C[mini].value
5             mini = j
6     swap C[i] and C[mini] Note that, indices for array elements are based on 0-origin. Input The first line contains an integer N , the number of cards.  N cards are given in the following line. Each card is represented by two characters. Two consecutive cards are separated by a space character. Output In the first line, print the arranged cards provided by the Bubble Sort algorithm. Two consecutive cards should be separated by a space character. In the second line, print the stability (" Stable " or " Not stable ") of this output. In the third line, print the arranged cards provided by the Selection Sort algorithm. Two consecutive cards should be separated by a space character. In the fourth line, print the stability (" Stable " or " Not stable ") of this output. Constraints 1 ≤ N ≤ 36 Sample Input 1 5
H4 C9 S4 D2 C3 Sample Output 1 D2 C3 H4 S4 C9
Stable
D2 C3 S4 H4 C9
Not stable Sample Input 2 2
S1 H1 Sample Output 2 S1 H1
Stable
S1 H1
Stable

Solution (Python):
cards_num = input()                                                                                                                                                                                         
cards_str = input()                                                                                                                                                                                         
cards_words_list = cards_str.split(' ')                                                                                                                                                                     
cards_numbers_list = [cards_words_list[idx_num][1] for idx_num in range(0, int(cards_num))]                                                                                                                 
val_list1 = cards_words_list[:], cards_numbers_list[:]                                                                                                                                                      
val_list2 = cards_words_list[:], cards_numbers_list[:]                                                                                                                                                      
                                                                                                                                                                                                            
def Bubble_Sort(list_size, val_list):                                                                                                                                                                       
    def swap(first_idx, second_idx, val_list):                                                                                                                                                              
        val = val_list[first_idx]                                                                                                                                                                           
        val_list[first_idx] = val_list[second_idx]                                                                                                                                                          
        val_list[second_idx] = val                                                                                                                                                                          
                                                                                                                                                                                                            
    swap_counter = 0                                                                                                                                                                                        
    while(True):                                                                                                                                                                                            
        finish = True                                                                                                                                                                                       
        for idx_num in range(0, int(list_size) - 1):                                                                                                                                                        
            if val_list[1][idx_num + 1] < val_list[1][idx_num]:                                                                                                                                             
                swap(idx_num, idx_num + 1, val_list[1])                                                                                                                                                     
                swap(idx_num, idx_num + 1, val_list[0])                                                                                                                                                     
                finish = False                                                                                                                                                                              
                swap_counter += 1                                                                                                                                                                           
        if finish == True: break                                                                                                                                                                            
                                                                                                                                                                                                            
def Selection_Sort(list_size, val_list):                                                                                                                                                                    
    def where_is_the_first_lowest_val(List): return List.index(min(List))                                                                                                                                   
                                                                                                                                                                                                            
    def swap(idx_num, lowest_val_index, List):                                                                                                                                                              
        val = List[idx_num]                                                                                                                                                                                 
        List[idx_num] = List[lowest_val_index + idx_num]                                                                                                                                                    
        List[lowest_val_index + idx_num] = val                                                                                                                                                              
                                                                                                                                                                                                            
    swap_num = 0                                                                                                                                                                                            
    for idx_num in range(0, int(list_size) - 1):                                                                                                                                                            
        unsorted_list = val_list[1][idx_num : int(list_size)]                                                                                                                                               
        lowest_val_index = where_is_the_first_lowest_val(unsorted_list)                                                                                                                                     
        if val_list[1][idx_num] != val_list[1][lowest_val_index + idx_num]:                                                                                                                                 
            swap(idx_num, lowest_val_index, val_list[1])                                                                                                                                                    
            swap(idx_num, lowest_val_index, val_list[0])                                                                                                                                                    
            swap_num += 1                                                                                                                                                                                   
                                                                                                                                                                                                            
def show(List):                                                                                                                                                                                             
    print_list = ','.join(list(map(str, List)))                                                                                                                                                             
    print_list = print_list.replace(',', ' ')                                                                                                                                                               
    print(print_list)                                                                                                                                                                                       
                                                                                                                                                                                                            
def Is_stable(list1, list2): return list1 == list2                                                                                                                                                          
                                                                                                                                                                                                            
Bubble_Sort(cards_num, val_list1)                                                                                                                                                                           
show(val_list1[0])                                                                                                                                                                                          
print('Stable')                                                                                                                                                                                             
Selection_Sort(cards_num, val_list2)                                                                                                                                                                        
show(val_list2[0])                                                                                                                                                                                          
if Is_stable(val_list1, val_list2) == False:                                                                                                                                                                
    print('Not stable')                                                                                                                                                                                     
else:                                                                                                                                                                                                       
    print('Stable')

Solution (Python):

import copy
class Card:
    def __init__(self, card, initial):
        self.card = card
        self.mark = card[0]
        self.number = int(card[1])
        self.initial = initial

def bubbleSort(c, n):
    for i in range(n):
        for j in range(n-1, i, -1):
            if c[j].number < c[j-1].number:
                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].number < c[minj].number:
                minj = j
        c[i], c[minj] = c[minj], c[i]

def printCards(cards, n):
    for i in range(n):
        print(cards[i].card,end="")
        if i == n -1:
            print()
        else:
            print(" ",end="")

def isStable(cards, n):
    for i in range(n-1):
        if cards[i].number == cards[i+1].number and cards[i].initial > cards[i+1].initial:
            return False
    return True

n = int(input().rstrip())
data = input().rstrip().split()
cards = []
for i in range(n):
    cards.append(Card(data[i], i))

init = copy.copy(cards)
bubbleSort(cards, n)
printCards(cards, n)
print("Stable" if isStable(cards, n) else "Not stable")
selectionSort(init, n)
printCards(init, n)
print("Stable" if isStable(init, n) else "Not stable")

Solution (Python):
import copy

def stable_sort(A: list, N:int) -> list:
    """
    トランプのカードを整列しましょう。ここでは、４つの絵柄(S, H, C, D)と９つの数字(1, 2, ..., 9)から構成される計 36 枚のカードを用います。例えば、ハートの 8 は"H8"、ダイヤの 1 は"D1"と表します。
    バブルソート及び選択ソートのアルゴリズムを用いて、与えられた N 枚のカードをそれらの数字を基準に昇順に整列するプログラムを作成してください。アルゴリズムはそれぞれ以下に示す疑似コードに従うものとします。数列の要素は 0 オリジンで記述されています。
    5
    H4 C9 S4 D2 C3
    """

    def bubble_sort(A: list, N:int) -> list:
        """
        :A[N]: サイズがNの整数型配列。
        :i: 未ソートの部分の先頭を指すループ変数で、配列の先頭から末尾に向かって移動します。
        :j: 未ソートの部分の隣り合う要素を比較するためのループ変数で、Aの末尾であるN-1 から開始しi+1 まで減少します。
        """
        has_finished = True
        i = 0
        count = 0
        while has_finished and len(A) > 1:
            has_finished = False
            for j in reversed(range(i + 1, N)):
                if int(A[j][1]) < int(A[j - 1][1]):
                    
                    a, b = A[j - 1], A[j]
                    A[j - 1], A[j] = b, a
                    has_finished = True
                    count += 1
            i += 1

        return A

    def selection_sort(A: list, N:int) -> list:
        """
        :A[N]: サイズがNの整数型配列。
        :i: 未ソートの部分の先頭を指すループ変数で、配列の先頭から末尾に向かって移動する。
        :minj: 各ループの処理でi 番目からN-1 番目までの要素で最小のものの位置。j 未ソートの部分から最小値の位置（minj）を探すためのループ変数。
        """
        for i in range(0, N):
            minj = i
            for j in range(i, N):
                if int(A[j][1]) < int(A[minj][1]):
                    minj = j
            
            if i != minj:
                a, b = A[i], A[minj]
                A[i], A[minj] = b, a

        return A

    A_1 = A.copy()
    A_2 = A.copy()
    bubble_result = bubble_sort(A_1, N)
    selection_result = selection_sort(A_2, N)


    return bubble_result, selection_result


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

bubble_result, selection_result = stable_sort(A, N)

print(*bubble_result)
print("Stable")
print(*selection_result)
if bubble_result != selection_result:
    print("Not stable")
else:
    print("Stable")

Solution (Python):
import copy

def bubble_sort(array):
    N = len(array)
    unsorted_num_exist = True
    for i in range(N):
        unsorted_num_exist = False
        for j in reversed(range(i, N - 1)):
            if array[j][1] > array[j + 1][1]:
                unsorted_num_exist = True
                array[j], array[j + 1] = array[j + 1], array[j]
        if not unsorted_num_exist:
            break

def selection_sort(array):
    N = len(array)
    for i in range(N):
        min_index = i
        for j in range(i, N):
            if array[j][1] < array[min_index][1]:
                min_index = j
        array[i], array[min_index] = array[min_index], array[i]
 

def putsarray(array):
    for i in range(len(array) - 1):
        print(array[i][0] + str(array[i][1]), end=' ')
    print(array[-1][0] + str(array[-1][1]))

def check_stable(origin, sorted):
    dict_origin = {}
    for e in origin:
        num = e[1]
        if num in dict_origin.keys():
            dict_origin[num].append(e[0])
        else:
            dict_origin[num] = [e[0]]
    dict_sorted = {}
    for e in sorted:
        num = e[1]
        if num in dict_sorted.keys():
            dict_sorted[num].append(e[0])
        else:
            dict_sorted[num] = [e[0]]
    
    return all(dict_origin[key] == dict_sorted[key] for key in dict_origin.keys())

if __name__ == "__main__":
    N = int(input())
    array = input().split()
    array = [[s[0], int(s[1])] for s in array]
    array2 = copy.deepcopy(array)
    array3 = copy.deepcopy(array)
    bubble_sort(array2)
    putsarray(array2)
    print("Stable" if check_stable(array, array2) else "Not stable")
    selection_sort(array3)
    putsarray(array3)
    print("Stable" if check_stable(array, array3) else "Not stable")

Solution (Python):
def show (nums):
    for i in range(len(nums)):
        if i!=len(nums)-1:
            print(nums[i],end=' ')
        else :
            print(nums[i])

def bubble(A):
    flag = True
    i = 0
    n = len(A)
    while(flag):
        flag = False
        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]
                flag = True
        i += 1

def selection(A):
    n = len(A)
    for i in range(0,n):
        minj = i
        for j in range(i,n):
            if A[j][1] < A[minj][1]:
                minj = j
        if i != minj:
            A[i],A[minj] = A[minj],A[i]

n = int(input())
A = list(input().split())
B = A.copy()

bubble(A)
selection(B)

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

Solution (Python):
def BubbleSort(C, N):
    '''C: list of str((S|H|C|D)+str(int)) -> list of str, str
    '''
    cli = C.copy()
    for i in range(N):
        for j in range(N - 1, i, -1):
            if int(cli[j][1:]) < int(cli[j - 1][1:]):
                cli[j], cli[j-1] = cli[j-1], cli[j]
    return cli, "Stable"

def SelectionSort(C,N):
    '''C: list of str((S|H|C|D)+str(int)) -> list of str, str
    '''
    cli = C.copy()
    for i in range(N):
        minj = i
        for j in range(i, N):
            if int(cli[j][1:]) < int(cli[minj][1:]):
                minj = j
        cli[i], cli[minj] = cli[minj], cli[i]
    return cli, isStable(cli, C)
def isStable(L1, L2):
    '''list of str(sorted), list of str -> str('Stable' or 'Not stable')
    '''
    s1, s2 = None, None
    
    for i in range(len(L1)-1):
        for j in range(i+1, len(L1)):
            if int(L1[i][1:]) == int(L1[j][1:]):
                s1, s2 = L1[i], L1[j]  
                if L2.index(s1) >= L2.index(s2):
                    return 'Not stable'
    return 'Stable'
def printlist(L):
    for itm in L[:-1]:
        print(itm, end = ' ')
    print(L[-1])

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

L, s = BubbleSort(C, N)
printlist(L)
print(s)
L, s = SelectionSort(C, N)
printlist(L)
print(s)

Solution (Python):
class Card:
        def __init__(self, suit, num):
                self.suit = suit
                self.num = num

def bubbleSort(C, N):
        for i in range(N): 
                for j in range(N - 1, i, -1):
                        if C[j].num < C[j - 1].num:
                                C[j].num, C[j - 1].num = C[j - 1].num, C[j].num
                                C[j].suit, C[j - 1].suit = C[j - 1].suit, C[j].suit

def selectionSort(C, N):
        for i in range(N):
                minID = i
                for j in range(i, num):
                        if C[j].num  < C[minID].num:
                                minID = j
                C[i].num, C[minID].num = C[minID].num, C[i].num
                C[i].suit, C[minID].suit = C[minID].suit, C[i].suit

num = int(input())
list = input().split()

cardListA = []
cardListB = []
sortA = []
sortB = []

isSame = True

for i in range(num):
        cardListA.append(Card(list[i][0], list[i][1]))
        cardListB.append(Card(list[i][0], list[i][1]))

bubbleSort(cardListA, num)
selectionSort(cardListB, num)


for i in range(num):
        sortA.append(cardListA[i].suit + cardListA[i].num)
        sortB.append(cardListB[i].suit + cardListB[i].num)
        if sortA[i] != sortB[i]:
                isSame = False

print(" ".join(sortA))
print("Stable")
print(" ".join(sortB))
if isSame:
        print("Stable")
else:
        print("Not stable")

Solution (Python):
import copy


def bubble_sort(n, A):
    for i in range(n):
        for j in reversed(range(i, n - 1)):
            if A[j + 1][1] < A[j][1]:
                A[j + 1], A[j] = A[j], A[j + 1]
    print(*A)


def selection_sort(n, B):
    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)


def is_stable(C, S):
    result = "Stable"
    for i in range(1, 10):
        c = [n for n in C if str(i) in n]
        s = [n for n in S if str(i) in n]
        if not c == s:
            result = "Not stable"
            break
    print(result)


n = int(input())
A = input().split()
B = copy.copy(A)
C = copy.copy(A)
bubble_sort(n, A)
is_stable(C, A)
selection_sort(n, B)
is_stable(C, B)

Solution (Python):
def BubbleSort(c,n):
 for i in range(n):
  for j in range(n-i-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):
  m=i
  for j in range(i,n):
   if c[j][1]<c[m][1]:m=j
  c[i],c[m]=c[m],c[i]
 return c

n=int(input());c=input().split()
b=BubbleSort(c.copy(),n)
s=SelectionSort(c.copy(),n)
print(*b)
print("Stable")
print(*s)
print(["Not s","S"][b==s]+"table")

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

                a[j], a[j-1] = a[j-1], a[j]
                
                flag = 1
        i += 1
    print(' '.join(map(str, 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]:
                minj = j
        a[i], a[minj] = a[minj], a[i]
    printArray(a)
    

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)

Solution (Python):
cardNum = lambda S:int(list(S)[1])

def bubbleSort(L, n):
  for i in range(n):
    for j in range(n-1, i, -1):
      if cardNum(L[j]) < cardNum(L[j-1]):
        L[j], L[j-1] = L[j-1], L[j]
  return L

def selectionSort(L, n):
  for i in range(n):
    minj = i
    for j in range(i, n):
      if cardNum(L[j]) < cardNum(L[minj]):
        minj = j
    L[i], L[minj] = L[minj], L[i]
  return L

def isStable(Lb, Ls):
  if Lb == Ls:
    return "Stable"
  else:
    return "Not stable"
  
N = int(input())
A = input().split()
B = [i for i in A]
LB = bubbleSort(A, N)
LS = selectionSort(B, N)
print(' '.join(map(str, LB)))
print("Stable")
print(' '.join(map(str, LS)))
print(isStable(LB, LS))

Solution (Python):
N = int(input())
str_input = list(input().split())
T1 = [(S[0],int(S[1])) for S in str_input]
T2 = [(S[0],int(S[1])) for S in str_input]

def bubble_sort(N,T):
    for i in range(N):
        flag = True
        while flag:
            flag = False
            for j in range(N-1, i, -1):
                if T[j][1] < T[j-1][1]:
                    tmp = T[j]
                    T[j] = T[j-1]
                    T[j-1] = tmp
                    flag = True
    return T

def selection_sort(N,T):
    for i in range(N):
        min_index = i
        for j in range(i, N):
            if (T[j][1] < T[min_index][1]):
                min_index = j
        if (min_index != i):
            tmp = T[i]
            T[i] = T[min_index]
            T[min_index] = tmp
    return T

def is_stable(bT, sT):
    for i, st in enumerate(sT):
        if(st[0] != bT[i][0]):
            return False
    return True

def print_trump(T):
    strT = ['{}{}'.format(t[0],t[1]) for t in T]
    print(str(strT).replace(',','').replace('[','').replace(']','').replace("'",''))
    
bT = bubble_sort(N, T1)
sT = selection_sort(N, T2)
print_trump(bT)
print('Stable')
print_trump(sT)
stability = 'Stable' if is_stable(bT,sT) else 'Not stable'
print(stability)

Solution (Python):
import copy
def selection_sort(A):
    global c
    c=0 
    for i in range(0,len(A)-1):
        selection(A,i)
        
        
    return A

def selection(A,i):
    global c
    min=i
    for j in range(i+1,len(A)):
        if A[min][1]>A[j][1]:
            min=j
            
            
    A[i],A[min]=A[min],A[i]
    if not A[i]==A[min]:
        c+=1
    
def bubble_sort(A):
    for i in range(0,len(A)-1):
        bubble(A,i)
        
    return A

def bubble(A,i):
    for j in range(0,len(A)-1-i):
        if A[j][1]>A[j+1][1]:
            A[j],A[j+1]=A[j+1],A[j]
            
            
def is_stable(A, B):
    for i in range(len(B) - 1):
        if B[i][1] == B[i + 1][1]:
            if A.index(B[i]) > A.index(B[i + 1]):
                return 'Not stable'
    return 'Stable'



n=int(input())
A=input().split()
A_t=[(i[0],int(i[1])) for i in A]
A_t2=copy.copy(A_t)
B_t=bubble_sort(A_t)
B=[i[0]+str(i[1]) for i in B_t]
print(' '.join(B))
print(is_stable(A_t,B_t))

S_t=selection_sort(A_t2)
S=[i[0]+str(i[1]) for i in S_t]

print(' '.join(S))
print(is_stable(A_t,S_t))

Solution (Python):
import copy


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


n = int(input())
c = input().split()
b = BubbleSort(copy.deepcopy(c), n)
print(" ".join(b))
print("Stable")
s = SelectionSort(copy.deepcopy(c), n)
print(" ".join(s))
if b == s:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
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]
    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(A, B):
    for i in range(len(A)):
        for j in range(i+1,len(A)):
            for a in range(len(B)):
                for b in range(a+1,len(B)):
                    if A[i][1] == A[j][1] and A[i] == B[b] and A[j] == B[a]:
                        return False
    return True
        
                
n = int(input())
a = input().split()
b = a.copy()
c = a.copy()
ans1 = []
ans2 = []
    
ans1 = BubbleSort(b, n)
print(*ans1)
if IsStable(a, ans1):
    print('Stable')
else:
    print('Not stable')

ans2 = SelectionSort(c, n)
print(*ans2)
if IsStable(a, ans2):
    print('Stable')
else:
    print('Not stable')

Solution (Python):
def bubbleSort(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 0

def selectionSort(b):
  for i in range(len(b)):
    minIndex = i
    for j in range(i+1,len(b)):
      if(int(b[j][1])<int(b[minIndex][1])):
        minIndex = j
        
    b[i],b[minIndex] = b[minIndex],b[i]
    
  return 0
        

n = input()
a = input().split()
b = a[:]

bubbleSort(a)
print(*a)
print("Stable")

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

Solution (Python):
from sys import stdin
from copy import deepcopy

N = int(stdin.readline().rstrip())
C = [x for x in stdin.readline().rstrip().split()]

def sortBubble(C, N):
    c = deepcopy(C)
    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 sortSelect(C, N):
    c = deepcopy(C)
    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]

    return c

def isStable(Cin, Cout):
    stable = sortBubble(Cin, len(Cin))
    if len(stable) != len(Cout):
        return False
    else:
        for i in range(len(Cin)):
            if Cout[i][0] != stable[i][0]:
                return False
        else:
            return True
            
def output(C, N, *f):
    for fn in f:
        sortedC = fn(C, N)
        print(*sortedC)
        if isStable(C, sortedC):
            print("Stable")
        else:
            print("Not stable")

output(C, N, sortBubble, sortSelect)

Solution (Python):
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)