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 

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



Sample input:
5
H4 C9 S4 D2 C3


Sample output:
D2 C3 H4 S4 C9
Stable
D2 C3 S4 H4 C9
Not stable

Submission status: Accepted

Solution code:
import copy


def bubble(_v):
    v = copy.copy(_v)
    n = len(v)
    for i in range(n):
        for j in range(n-1, i, -1):
            if v[j][1] < v[j-1][1]:
                v[j], v[j-1] = v[j-1], v[j]
    return v


def selection(_v):
    v = copy.copy(_v)
    n = len(v)
    for i in range(n):
        mi = i
        for j in range(i, n):
            if v[j][1] < v[mi][1]:
                mi = j
        v[i], v[mi] = v[mi], v[i]
    return v


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

b = bubble(v)
s = selection(v)
print(" ".join(b))
print("Stable")
print(" ".join(s))
print("Stable" if b == s else "Not stable")

Submission status: Accepted

Solution code:
import copy

def bublesort(array, n):
    flag = 1
    while(flag):
        i=0
        flag=0
        for j in range(len(array)-1, i, -1):
            if array[j][1] < array[j-1][1]:
                array[j],array[j-1] = array[j-1],array[j]
                flag = 1
        i += 1

def selectionsort(array,n):
    for i in range(len(array)):
        minj = i
        for j in range(i,len(array)):
            if array[j][1] < array[minj][1]:
                minj = j
        array[minj],array[i] = array[i],array[minj]

factor = int(input())
numbers = input().split()
numbers_select = copy.deepcopy(numbers)


bublesort(numbers,factor)
selectionsort(numbers_select,factor)

print(" ".join(list(map(str, numbers))))
print("Stable")

print(" ".join(list(map(str, numbers_select))))
print("Stable") if numbers == numbers_select else print("Not stable")

Submission status: Accepted

Solution code:
N = int(input())
A = input()
B = A.split()
for i in range(N) :
    for j in range(N-1, i, -1) :
        if int(B[j][1]) < int(B[j-1][1]) :
            B[j], B[j-1] = B[j-1], B[j]
print(" ".join(B))
print("Stable")

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

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
n = int(input())
a1 = input().split()
a2 = a1[:]
i = 0
flag = 1
while flag:
    flag = 0
    for j in range(n - 1, i, -1):
        if int(a1[j][1]) < int(a1[j - 1][1]):
            flag = 1
            a1[j], a1[j - 1] = a1[j - 1], a1[j]
    i += 1
print(" ".join(a1))
print("Stable")


for i in range(n):
    minj = i
    for j in range(i, n):
        if int(a2[j][1]) < int(a2[minj][1]):
            minj = j
    if minj != i:
        a2[i], a2[minj] = a2[minj], a2[i]
print(" ".join(a2))
if a1 == a2:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
n = int(input())
cards = list(input().split())
cards1 = cards.copy()
# cnt = 0
# for i in range(n):
#     minj = i
#     for j in range(i,n):
#         if int(cards[minj][1]) > int(cards[j][1]):
#             minj = j
#     if i != minj:
#         cnt += 1
#     cards[i], cards[minj] = cards[minj], cards[i]
#     print(cards)

#['D2', 'C3', 'S4', 'H4', 'C9']




def BubbleSort(cards):

    for i in range(n):
        for j in range(n-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 SelectionSort(cards):
    cnt = 0
    for i in range(n):
        minj = i
        for j in range(i,n):
            if int(cards[minj][1]) > int(cards[j][1]):
                minj = j
        if i != minj:
            cnt += 1
        cards[i], cards[minj] = cards[minj], cards[i]

    return cards

a = BubbleSort(cards)
b = SelectionSort(cards1)

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

Submission status: Accepted

Solution code:
n = int(input())
c = input().split();d = c[:]
for i in range(n-1):
    for j in  range(n-i-1):
        if c[j][1] > c[j+1][1]:c[j:j+2]=c[j+1],c[j]
    m = i
    for j in range(i,n):
        if d[m][1]>d[j][1]:m=j
    d[i],d[m]=d[m],d[i]
print(*c);print("Stable")
print(*d);print(["Not s","S"][c==d]+"table")

Submission status: Accepted

Solution code:
def judegStable(A, B):
    num_dict_input = dict(zip(map(lambda x: str(x), range(1, 10)), [[]] * 9))
    num_dict_output = dict(zip(map(lambda x: str(x), range(1, 10)), [[]] * 9))

    for i in range(0, N):
        num_dict_input[A[i][1]] = num_dict_input[A[i][1]] + [A[i]]
        num_dict_output[B[i][1]] = num_dict_output[B[i][1]] + [B[i]]
    for key, val in num_dict_input.items():
        for i in range(len(val)):
            if val[i] != num_dict_output[key][i]:
                print "Not stable"
                return False
    print "Stable"
    return True


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

def selectionSort(A, N):
    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
        v = A[i]
        A[i] = A[minj]
        A[minj] = v
    return A

N = input()
line_ = raw_input()
line = line_.strip().split()
line2 = line_.strip().split()
line3 = line_.strip().split()

output_bubble = bubbleSort(line, N)
print(' '.join(output_bubble))
judegStable(line2, output_bubble)

output_select = selectionSort(line2, N)
print(' ' .join(output_select))
judegStable(line3, output_select)

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
# coding: utf-8
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")

Submission status: Accepted

Solution code:
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]):
                    # alter position
                    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
            # alter position
            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")

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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
    #i1, i2 = 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]  #i < 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)

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))