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):
def insertionSort(A, N):
    for i in range(1, N):
        v = A[i]
        j = i-1
        while A[j] > v and j >= 0:
            A[j+1], A[j] = A[j], A[j+1]
            j -= 1


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


def bubbleSort_card(C, N):
    flag = 1
    while flag:
        flag = 0
        for j in range(N-1, 0, -1):
            if C[j][1] < C[j-1][1]:
                C[j], C[j-1] = C[j-1], C[j]
                flag = 1

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

def selectionSort(A, N):
    for i in range(N):
        minidx = i
        for j in range(i, N):
            if A[j] < A[minidx]:
                minidx = j
        A[i], A[minidx] = A[minidx], A[i]


N = int(input())
A = list(input().split())
C = A.copy()
bubbleSort_card(C,N)
selectionSort_card(A,N)
print(" ".join(C))
print('Stable')
print(" ".join(A))
for i in range(N):
    if A[i] != C[i]:
        print('Not stable')
        break
else:
    print('Stable')

Solution (Python):
import copy

n = int(input())

l = list(input().split())
C1 = []

for v in l:
    s = v[0]
    m = int(v[1])
    C1.append((s, m))

C2 = copy.deepcopy(C1)

for i in range(n):
    for j in range(n-1, i, -1):
        if C1[j][1] < C1[j-1][1]:
            C1[j], C1[j-1] = C1[j-1], C1[j]

for i in range(n):
    minj = i
    for j in range(i,n):
        if C2[j][1] < C2[minj][1]:
            minj = j
    C2[i], C2[minj] = C2[minj], C2[i]

result1 = [t[0]+str(t[1]) for  t in C1]
result2 = [t[0]+str(t[1]) for  t in C2]

print(" ".join(result1))
print("Stable")
print(" ".join(result2))
if result1 == result2:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
import copy


def BubbleSort(C, n):
    flag = 1
    while flag:
        flag = 0
        for i in range(n-1, 0, -1):
            if int(C[i][1]) < int(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-1):
        minj = i
        for j in range(i, n):
            if int(C[j][1]) < int(C[minj][1]):
                minj = j
        if minj != i:
            C[i], C[minj] = C[minj], C[i]
    return C


n = int(input())
C = list(input().split())
C2 = C.copy()

print(*BubbleSort(C, n), sep=' ')
print("Stable")
print(*SelectionSort(C2, n), sep=' ')
if C ==C2:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
from copy import copy

n = int(input())
cards = [(s[0],int(s[1])) for s in input().split()]

cards_1 = copy(cards)
cards_2 = copy(cards)

need_to_sort = True
while need_to_sort:
    need_to_sort = False
    for index in range(len(cards_1) - 1, 0, -1):
        if cards_1[index][1] < cards_1[index-1][1]:
            cards_1[index], cards_1[index-1] = cards_1[index-1], cards_1[index]
            need_to_sort = True

print(" ".join([s[0]+ str(s[1]) for s in cards_1]))
print("Stable")

for idx1 in range(len(cards_2)):
    mins = idx1
    for idx2 in range(idx1, len(cards_2)):
        if cards_2[idx2][1] < cards_2[mins][1]:
            mins = idx2
    
    if mins != idx1:
        cards_2[idx1], cards_2[mins] = cards_2[mins], cards_2[idx1]

print(" ".join([s[0]+ str(s[1]) for s in cards_2]))

is_stable = True
for index in range(n):
    if cards_1[index] != cards_2[index]:
        is_stable = False
        break

print("Stable" if is_stable else "Not stable")

Solution (Python):









import os
import sys
from copy import deepcopy




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()

Solution (Python):
n, *aa = open(0).read().split()

def bubble(aa):
    aa = list(map(list, aa))
    n = len(aa)
    for i in range(n):
        for j in range(n-1, i, -1):
            if aa[j-1][1] > aa[j][1]:
                aa[j-1], aa[j] = aa[j], aa[j-1]
    aa = list(map(lambda x: ''.join(x), aa))
    return aa

def selection(aa):
    aa = list(map(list, aa))
    n = len(aa)
    for i in range(n):
        mini = i
        for j in range(i, n):
            if aa[j][1] < aa[mini][1]:
                mini = j
        aa[mini], aa[i] = aa[i], aa[mini]
    aa = list(map(lambda x: ''.join(x), aa))
    return aa

bres = bubble(aa)
sres = selection(aa)

print(*bres)
print('Stable')
print(*sres)
if bres == sres:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
import copy
import sys
input = sys.stdin.readline


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


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


def main():
    _ = input()
    A = input().strip().split()
    b_A = copy.deepcopy(A)
    bubble_sort(b_A)
    print(" ".join(b_A))
    print("Stable")

    selection_sort(A)
    print(" ".join(A))
    for b, s in zip(b_A, A):
        if b == s:
            continue
        else:
            print("Not stable")
            return
    print("Stable")
    return


if __name__ == "__main__":
    main()

Solution (Python):
def bubble_sort(A):
    cnt = 0
    for i in range(0, len(A) - 1):
        for j in range(len(A) - 1, i, -1):
            if A[j][1] < A[j - 1][1]:
                A[j - 1], A[j] = A[j], A[j - 1]
                cnt += 1


def selection_sort(A):
    for i in range(0, len(A)):
        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]


def isStable(before, after):
    for i in range(0, len((before))):
        for j in range(i + 1, len(before)):
            for a in range(0, len(after)):
                for b in range(a + 1, len(after)):
                    if before[i][1] == before[j][1]:
                        if before[i] == after[b] and before[j] == after[a]:
                            return False
    return True


if __name__ == '__main__':
    n = int(input())
    l = input().split()
    m = l.copy()
    n = l.copy()
    bubble_sort(m)
    selection_sort(n)
    print(' '.join(m))
    print('Stable' if isStable(l, m) else 'Not stable')
    print(' '.join(n))
    print('Stable' if isStable(l, n) else 'Not stable')

Solution (Python):
from copy import deepcopy as copy
n=int(input())
A=input().split()
C=copy(A)
for i in range(n):
  for j in range(n-1,i,-1):
    if C[j][1] < C[j-1][1]:
      k=C[j]
      C[j]=C[j-1]
      C[j-1]=k
print(*C)
for i in range(n-1):
  if C[i][1]==C[i+1][1] and A.index(C[i])>A.index(C[i+1]):
    print('Not stable')
    break
else:print('Stable')
C=copy(A)
for i in range(n):
  minj = i
  for j in range(i,n):
    if C[j][1] < C[minj][1]:
      minj = j
  k=C[i]
  C[i]=C[minj]
  C[minj]=k
print(*C)
for i in range(n-1):
  if C[i][1]==C[i+1][1] and A.index(C[i])>A.index(C[i+1]):
    print('Not stable')
    break
else:print('Stable')

Solution (Python):
from collections import namedtuple
C = namedtuple("C", "m v")


def bubble_sort(A0):
    A = A0.copy()
    for i in range(n - 1):
        for j in range(n - 1, i, -1):
            if A[j].v < A[j - 1].v:
                A[j], A[j - 1] = A[j - 1], A[j]
    return A, True


def selection_sort(A0):
    A = A0.copy()
    for i in range(n - 1):
        k = i
        for j in range(i + 1, n):
            if A[k].v > A[j].v:
                k = j
        if k != i:
            A[k], A[i] = A[i], A[k]
    return A


lst = ["Not stable", "Stable"]
n = int(input())
A = [C(x[0], x[1]) for x in input().split()]

B, j = bubble_sort(A)
print(*[(B[i].m + B[i].v) for i in range(n)])
print(lst[j])

S = selection_sort(A)
print(*[(S[i].m + S[i].v) for i in range(n)])
print(lst[B == S])

Solution (Python):
n=int(input())
num_list1=list(map(str,input().split()))
num_list2=[]
input_list=[]

for k in num_list1:
    num_list2.append(k)
    input_list.append(k)


def bubble(num_list):
    i=0
    flag=True
    while flag:
        flag=False
        for j in range(len(num_list)-1,i,-1):
            if int(num_list[j-1][1])>int(num_list[j][1]):
                tmp=num_list[j-1]
                num_list[j-1]=num_list[j]
                num_list[j]=tmp
                flag=True
    return num_list 

def select(num_list):
    for i in range(0,len(num_list)):
        min=i
        for j in range(min+1,len(num_list)):
            if int(num_list[min][1])>int(num_list[j][1]):
                min=j
        tmp=num_list[i]
        num_list[i]=num_list[min]
        num_list[min]=tmp
    return num_list



def stable(input_list,output_list):
    for i in range(0,len(input_list)):
        for j in range(i+1,len(output_list)):
            for k in range(0,len(output_list)):
                for l in range(k+1,len(output_list)):
                    if input_list[i][1]==input_list[j][1] and input_list[i]==output_list[l] and input_list[j]==output_list[k]:
                        return "Not stable"
    return "Stable"

bubble=bubble(num_list1)
select=select(num_list2)


print(" ".join(bubble))
print(stable(input_list,bubble))
print(" ".join(select))
print(stable(input_list,select))

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


def main():
    N = int(input())
    cards1 = input().split()
    cards2 = cards1.copy()

    bubble_sorted = bubble_sort(cards1, N)
    print(*bubble_sorted)
    print("Stable")
    
    select_sorted = selection_sort(cards2, N)
    print(*select_sorted)
    if bubble_sorted == select_sorted:
        print("Stable")
    else:
        print("Not stable")


if __name__ == "__main__":
    main()

Solution (Python):
class Trump(str):
    def __init__(self, card):
        super().__init__()
        self.num = int(card[1])

def trump_bubble_sort(A, N):
    flg = True
    while flg:
        flg = False
        for i in range(1, N):
            if A[i - 1].num > A[i].num:
                A[i], A[i - 1] = A[i - 1], A[i]
                flg = True
    return A


def trump_selection_sort(A, N):
    for i in range(0, N-1):
        min_idx = i
        for j in range(i+1, N):
            if A[min_idx].num > A[j].num:
                min_idx = j
        A[i], A[min_idx] = A[min_idx], A[i]
        
    return A

N = int(input().rstrip())
A = [Trump(a) for a in input().rstrip().split()]
A_2 = A.copy()

bubble_result = trump_bubble_sort(A, N)
selection_result = trump_selection_sort(A_2, N)

stable = True
for i in range(0, N):
    if bubble_result[i] != selection_result[i]:
        stable = False
        break
print(" ".join(bubble_result))
print("Stable")
print(" ".join(selection_result))
print("Stable" if stable else "Not stable")

Solution (Python):
import copy
def BubbleSort(C, N):
    for i in range(N):
        for j in reversed(range(i+1, N)):
            if C[j][1:2] <  C[j-1][1:2]:
                C[j], C[j-1] = C[j-1], C[j]

    print(*C)
    stableCheck(C, N)

def SelectionSort(C, N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if C[j][1:2] <  C[minj][1:2]:
                minj = j
        C[i], C[minj] = C[minj], C[i]
    print(*C)
    stableCheck(C, N)

def stableCheck(C, N):
    global lst
    flag = 1
    for i in range(N):
        for j in range(i+1, N):
            if lst[i][1:2] == lst[j][1:2]:
                fir = lst[i]
                sec = lst[j]
                for k in range(N):
                    if C[k] == fir:
                        recf = k

                    if C[k] == sec:
                        recs = k
                
                if recf > recs:
                    print("Not stable")
                    flag = 0
                    break
        
        if flag ==0:
            break

    if flag :
        print("Stable")

N = int(input())
lst = list(map(str, input().split()))
lst1 = copy.deepcopy(lst)
lst2 = copy.deepcopy(lst)

BubbleSort(lst1, N)
SelectionSort(lst2, N)

Solution (Python):
import copy
n = int(input())
c = input().split()
c = [[c[i][0], int(c[i][1])] for i in range(n)]
ba = copy.deepcopy(c)
sa = copy.deepcopy(c)

def bubble_sort(a, n):
    flag = 1
    i = 0
    while flag:
        flag = 0
        for j in reversed(range(i+1, n)):
            if a[j][1] < a[j-1][1]:
                a[j], a[j-1] = a[j-1], a[j]
                flag = 1
        i += 1
    return a

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

ba = bubble_sort(ba, n)
sa = selection_sort(sa, n)

def is_stable(x, y):
    for i in range(n):
        if x[i][0] != y[i][0]:
            return False
    return True

fba = [i[0] + str(i[1]) for i in ba]
print(' '.join(fba))
print('Stable')
fsa = [i[0] + str(i[1]) for i in sa]
print(' '.join(fsa))
print('Stable' if is_stable(ba, sa) else 'Not stable')

Solution (Python):
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(lambda x: (int(x[1]), x), input().split()))

    
    B = A.copy()
    at_least_once = True
    while at_least_once:
        at_least_once = False
        for i in range(N - 1):
            if B[i][0] > B[i + 1][0]:
                B[i], B[i + 1] = B[i + 1], B[i]
                at_least_once = True
    print(" ".join(map(lambda x: x[1], B)))
    print("Stable")

    
    B = A.copy()
    stability = "Stable"
    for i in range(N - 1):
        min_j = i
        for j in range(i, N):
            if B[j][0] < B[min_j][0]:
                min_j = j
        if min_j != i:
            if B[i][0] in list(map(lambda x: x[0], B[i + 1: min_j])):
                stability = "Not stable"
            B[i], B[min_j] = B[min_j], B[i]
    print(" ".join(map(lambda x: x[1], B)))
    print(stability)


if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin


def bubble_sort(A, N):
    for i in range(N-1):
        for j in range(N-1,0,-1):
            if int(A[j-1][1]) > int(A[j][1]):
                A[j], A[j-1] = A[j-1], A[j]
    return 'Stable'
                
def selection_sort(A, N, B):
    for i in range(N):
        minj = i
        for j in range(i,N):
            if int(A[j][1]) < int(A[minj][1]):
                minj = j
        A[i], A[minj] = A[minj], A[i]


    if A == B:
        return 'Stable'
    else:
        return 'Not stable'

    
def main():
    read = stdin.readline
    N = int(read())
    data_for_bubble = list(map(str, read().split('\n')[0].split(' ')))
    data_for_selection = data_for_bubble.copy()
    bubble_result = bubble_sort(data_for_bubble, N)
    for i in range(N-1):
        print(data_for_bubble[i], end = ' ')
    print(data_for_bubble[N-1])
    print(bubble_result)
    selection_result = selection_sort(data_for_selection, N, data_for_bubble)
    for i in range(N-1):
        print(data_for_selection[i], end = ' ')
    print(data_for_selection[N-1])
    print(selection_result)
    
    
if __name__ == '__main__':
    main()

Solution (Python):


from copy import deepcopy
def selectionSort(A,N):
    lst=deepcopy(A)
    for i in range(N):
        minj=i
        for j in range(i,N):
            if int(lst[j][1])<int(lst[minj][1]):
                minj=j
        lst[i],lst[minj]=lst[minj],lst[i]
    return(lst)

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

a=int(input())
b=input().split(" ")
Selected=selectionSort(b,a)
Bubbled=bubbleSort(b,a)
IsStable="Stable"
for i in range(a):
    if Selected[i] != Bubbled[i]:
        IsStable="Not stable"

print(" ".join(Bubbled),"Stable"," ".join(Selected),IsStable,sep="\n")

Solution (Python):


n=int(input())
A=input().split()
C=A[:] 

def bubble_sort(n,A):
  flag=True
  i=0
  while flag:
    flag=False
    for j in reversed(range(i+1,n)):
      if int(A[j][1])<int(A[j-1][1]):
        tmp=A[j]
        A[j]=A[j-1]
        A[j-1]=tmp
        flag=True
    i+=1
  return A

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

x=bubble_sort(n,A)
y=selection_sort(n,C)
print(*x) 
print('Stable')
print(*y) 
print('Stable' if x==y else 'Not stable')

Solution (Python):
def bubleSort(table):
    table = table.copy()
    for nAchieve in range(len(table)):
        for i in range(len(table) - 1, nAchieve, -1):
            if table[i][1] < table[i - 1][1]:
                table[i], table[i - 1] = table[i - 1], table[i]
    return table


def selectionSort(table):
    table = table.copy()
    for nAchieve in range(len(table)):
        minimum_index = nAchieve
        for i in range(nAchieve + 1, len(table)):
            if table[minimum_index][1] > table[i][1]:
                minimum_index = i
        if minimum_index != nAchieve:
            table[nAchieve], table[minimum_index] = table[minimum_index], table[nAchieve]
    return table


def checkStable(stable, comparison):
    if stable == comparison:
        return 'Stable'
    else:
        return 'Not stable'


element = int(input())
table = list(map(str, input().split()))

y = selectionSort(table)
x = bubleSort(table)
print(' '.join(map(str, x)))
print('Stable')
print(' '.join(map(str, y)))
print(checkStable(x, y))

Solution (Python):
class Card:
    def __init__(self, card):
        self.value = int(card[1])
        self.card = card


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

    return A


def bubbleSort(A, N):
    flag = 1
    while flag:
        flag = 0
        for j in range(N-1, 0, -1):
            if A[j].value < A[j-1].value:
                tmp = A[j]
                A[j] = A[j-1]
                A[j-1] = tmp
                flag = 1

    return A


def check_stable(A, cards):
    for num in range(1, 10):
        As = []
        Cs = []
        for a in A:
            if a.value == num:
                As.append(a.card)
        for c in cards:
            if c.value == num:
                Cs.append(c.card)

        if As != Cs:
            print("Not stable")
            return
    else:
        print("Stable")
        return


def main():
    N = int(input())
    cards = [Card(i) for i in input().split()]
    bubble_cards = bubbleSort(cards.copy(), N)
    selection_cards = selectionSort(cards.copy(), N)

    print(*[bc.card for bc in bubble_cards])
    check_stable(bubble_cards, cards)
    print(*[sc.card for sc in selection_cards])
    check_stable(selection_cards, cards)


if __name__ == "__main__":
    main()

Solution (Python):

from sys import stdin


def bubble_sort(A, N):  
  
  flag = True  
  exchange_cnt = 0
  while flag:
    flag = False
    for j in range(N - 1, 0, -1):
      if int(A[j][1]) < int(A[j - 1][1]):
        A[j], A[j - 1] = A[j - 1], A[j]
        flag = True
        exchange_cnt += 1
  return A

def selection_sort(A, N):  
  
  exchange_cnt = 0
  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
    else:
      if i != minj:
        A[i], A[minj] = A[minj], A[i]
        exchange_cnt += 1
  return A

n = int(stdin.readline().rstrip())
A = list(stdin.readline().split())

ans = bubble_sort(list(A), n)
print(' '.join(map(str, ans)))
print('Stable')

ans2 = selection_sort(A, n)
print(' '.join(map(str,ans2)))
print('Stable' if ans2==ans else 'Not stable')

Solution (Python):
N = int(input())
A = list(map(str, input().split()))
l_1 = []
l_2 = []
ans = []

for cha in A:
    l_1.append([cha[:1], int(cha[1:])])
    l_2.append([cha[:1], int(cha[1:])])

def BubbleSort(C, N):
  for i in range(N):
    nums = []
    for j in range(i+1, N):
      nums.append(j)
    nums.sort(reverse=True)
    for num in nums:
      if C[num][1] < C[num-1][1]:
        C[num], C[num-1] = C[num-1], C[num]
    a = []
    for cha in C:
      a.append(''.join(map(str, cha)))
  ans.append(' '.join(map(str, a)))
  print(ans[0])
  print('Stable')
  
BubbleSort(l_1, N)

def SelectionSort(D, N):
  for i in range(N):
    index = i
    for j in range(i, N):
      if D[j][1] < D[index][1]:
        index = j
    D[i], D[index] = D[index], D[i]
  b = []
  for cha in D:
    b.append(''.join(map(str, cha)))
  ans.append(' '.join(map(str, b)))
  if ans[0] == ans[1]:
    print(ans[1])
    print('Stable')
  else:
    print(ans[1])
    print('Not stable')

SelectionSort(l_2, N)

Solution (Python):
from sys import stdin
N = int(input())
A = [{'value': int(x[1]), 'type': x[0]} for x in stdin.readline().split(' ')]
S = 'Stable'
NS = 'Not stable'


def bubble_sort(arr):
    for i in range(N):
        for j in range(N - 1, i, -1):
            if arr[j]['value'] < arr[j - 1]['value']:
                arr[j], arr[j - 1] = (arr[j - 1], arr[j])
    return arr


def selection_sort(arr):
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if arr[j]['value'] < arr[minj]['value']:
                minj = j
        arr[i], arr[minj] = (arr[minj], arr[i])
    return arr


A_bubble = bubble_sort(A.copy())
A_selection = selection_sort(A.copy())


def is_stable(origin, arr):
    for i in range(N):
        for j in range(i+1, N):
            for a in range(0, N):
                for b in range(a+1, N):
                    if (arr[i]['value'] == arr[j]['value']) & \
                            (arr[i] == origin[b]) & (arr[j] == origin[a]):
                        return False

    return True


print(' '.join(map(lambda x: x['type'] + str(x['value']), A_bubble)))
print(S)

print(' '.join(map(lambda x: x['type'] + str(x['value']), A_selection)))
if (is_stable(A_bubble, A_selection)):
    print(S)
else:
    print(NS)

Solution (Python):
n = int(input())
cards = list(map(str, input().split()))


def bubble(a):
    num = [int(i[1]) for i in a]
    char = [i[0] for i in a]
    for i in range(n):
        for j in range(n-1, i, -1):
            if num[j] < num[j-1]:
                num[j], num[j-1] = num[j-1], num[j]
                char[j], char[j-1] = char[j-1], char[j]
    else:
        a_new = [char[i] + str(num[i]) for i in range(n)]
        return a_new


def selection(a):
    num = [int(i[1]) for i in a]
    char = [i[0] for i in a]
    minj = 0
    stay = True
    same_exi = False
    for i in range(n):
        minj = i
        for j in range(i, n):
            if num[minj] > num[j]:
                minj = j
                if same_exi:
                    stay = False
            if num[i] == num[j]:
                same_exi = True
        else:
            num[i], num[minj] = num[minj], num[i]
            char[i], char[minj] = char[minj], char[i]
    else:
        a_new = [char[i] + str(num[i]) for i in range(n)]
        return a_new, stay


def print_space(li):
    for i in range(len(li)-1):
        print(li[i], end=' ')
    else:
        print(li[-1])



cards_bu = bubble(cards)
cards_sl = selection(cards)

sl_list = cards_sl[0]
sl_stay = cards_sl[1]

print_space(cards_bu)
print('Stable')

print_space(sl_list)
if sl_list == cards_bu:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
def bubbleSort(A, N):
    cnt = 0
    flg = True
    while flg:
        flg = False
        for i in range(N - 1):
            if A[i][1] > A[i + 1][1]:
                tmp = A[i]
                A[i] = A[i + 1]
                A[i + 1] = tmp
                flg = True
                cnt += 1
    return A, cnt


def selectionSort(A, N):
    cnt = 0
    for i in range(N):
        minJ = i
        for j in range(i, N):
            if A[minJ][1] > A[j][1]:
                minJ = j
        if A[i][1] != A[minJ][1]:
            tmp = A[i]
            A[i] = A[minJ]
            A[minJ] = tmp
            cnt += 1
    return A, cnt


def resolve():
    import copy
    N = int(input())
    A = [i for i in input().split()]
    B = copy.deepcopy(A)
    ansA, cnt = bubbleSort(A, N)
    print(*ansA)
    print("Stable")
    ansB, cnt = selectionSort(B, N)
    print(*ansB)
    if ansA == ansB:
        print("Stable")
    else:
        print("Not stable")


resolve()

Solution (Python):
from copy import deepcopy

n = int(input())
ls = list(input().split())
C1 = []
for s in ls:
    C1.append((s[0], s[1]))
C2 = deepcopy(C1)



def bubble_sort(ls):
    n = len(ls)
    for _ in range(n):
        for j in range(n-1):
            if ls[j][1] > ls[j+1][1]:
                ls[j], ls[j+1] = ls[j+1], ls[j]
    return ls



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


ans1 = []
ans2 = []
for c in bubble_sort(C1):
    ans1.append(c[0]+c[1])
for c in selection_sort(C2):
    ans2.append(c[0]+c[1])
print(*ans1)
print('Stable')
print(*ans2)
if ans1 == ans2:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
def bubblesort_re(A,N):
    count = 0
    
    
    flag = True
    while flag:
        flag = False
        
        
        
        
        
        for i in range(N-1,0,-1):
            if A[i][1] < A[i-1][1]:
                A[i],A[i-1] = A[i-1],A[i]
                count += 1
                flag = True

    return A,count

def min_index(A):
    index = 0
    m = A[0][1]
    for i in range(1,len(A)):
        if A[i][1] < m:
            m = A[i][1]
            index = i

    return index











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

    return A,count

if __name__ == '__main__':
    import copy

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

    X = A.copy()
    s,t = bubblesort_re(X,N)
    for i in range(N):
        if i != N - 1:
            print(s[i],end = " ")
        else:
            print(s[i])
    print("Stable")

    X = A.copy()
    u,v = selectionsort(X,N)
    for i in range(N):
        if i != N - 1:
            print(u[i],end = " ")
        else:
            print(u[i])
    if s == u:
        print("Stable")
    else:
        print("Not stable")

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

def selection_sort(A,N):
    for i in range(N):
        minj = i
        for j in range(i+1,N):
            if int(A[j][1:])<int(A[minj][1:]):
                minj = j
        if minj != i:
            A[minj],A[i] = A[i],A[minj]
    return A
    
N = int(input())
A = input().split()

A_bubble = bubble_sort(A.copy(), N)
A_select = selection_sort(A.copy(), N)

print(*A_bubble)
print('Stable')
print(*A_select)
if A_select == A_bubble:
    print('Stable')
else:
    print('Not stable')

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

    
    
    
    


if __name__ == "__main__":
    main()