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):
class Card:
    def __init__(self, suit, value, order):
        self.suit = suit
        self.value = value
        self.order = order
    def __str__(self):
        return self.suit + str(self.value)

n = int(input())
a = list(input().split())
cards = []
for i in range(n):
    c = Card(a[i][0], int(a[i][1]), i)
    cards.append(c)

c = cards + [] 


for i in range(n):
    for j in range(n-1, i, -1):
        if c[j].value < c[j-1].value:
            c[j], c[j-1] = c[j-1], c[j]
print(' '.join([str(c1) for c1 in c]))
for i in range(n-1):
    if c[i].value == c[i+1].value and c[i].order >= c[i+1].order:
        print('Not stable')
        break
else:
    print('Stable')

c = cards + [] 


for i in range(n):
    minj = i
    for j in range(i, n):
        if c[j].value < c[minj].value:
            minj = j
    c[i], c[minj] = c[minj], c[i]
print(' '.join([str(c1) for c1 in c]))
for i in range(n-1):
    if c[i].value == c[i+1].value and c[i].order >= c[i+1].order:
        print('Not stable')
        break
else:
    print('Stable')

Solution (Python):
import copy
def BubbleSort(N, A):
    A = copy.deepcopy(A)
    for i in range(N-1):
        for j in range(N-1,i,-1):
            if int(A[j-1][1]) > int(A[j][1]):
                A[j-1], A[j] = A[j], A[j-1]
    return A

def SelectSort(N, A):
    A = copy.deepcopy(A)
    for i in range(N-1):
        minidx = i
        for j in range(i+1,N):
            if int(A[j][1]) < int(A[minidx][1]):
                minidx = j
        if minidx != i:
            A[i], A[minidx] = A[minidx], A[i]
    return A

def main():
    n = int(input());  L = input().split()
    B = BubbleSort(n, L)
    S = SelectSort(n, L)
    print(*B); print('Stable')
    print(*S); print('Not stable') if B != S else print('Stable')
main()

Solution (Python):
import sys, copy
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    C_tmp = LSS()
    C = [{'suit':'', 'value':0} for _ in range(N)]
    for i in range(N):
        C[i]['suit'] = C_tmp[i][0]
        C[i]['value'] = int(C_tmp[i][1:])

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

    def SelectionSort(C, N):
        for i in range(N):
            minj = i
            for j in range(i, N):
                if C[j]['value']<C[minj]['value']:
                    minj = j
            if i!=minj:
                C[i], C[minj] = C[minj], C[i]
        return C

    def isStable(C, C_s):
        isStable = True
        for i in range(1, 10):
            if [j['suit'] for j in C if j['value']==i]!=[j['suit'] for j in C_s if j['value']==i]:
                isStable = False
        ret = 'Stable' if isStable else 'Not stable'
        return ret

    C_bs = BubbleSort(copy.deepcopy(C), N)
    print(*[i['suit']+str(i['value']) for i in C_bs])
    print(isStable(C, C_bs))

    C_ss = SelectionSort(copy.deepcopy(C), N)
    print(*[i['suit']+str(i['value']) for i in C_ss])
    print(isStable(C, C_ss))

if __name__ == '__main__':
    resolve()

Solution (Python):
import copy
def BubbleSort(C, N) :
    for i in range(N-1) :
        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 Stable(A, B, N) :
    for i in range(N) :
        for j in range(i+1, N) :
            for a in range(N) :
                for b in range(a+1, N) :
                    if A[i][1] == A[j][1] and A[i] == B[b] and A[j] == B[a] :
                        return "false"
    return "true"

N = int(input())
OrgC = list(map(str, input().split()))
BubC = copy.copy(OrgC)
SelC = copy.copy(OrgC)
print(" ".join(BubbleSort(BubC, N)))
if Stable(OrgC, BubC, N) == "false" :
    print("Not stable")
else :
    print("Stable")

print(" ".join(SelectionSort(SelC, N)))
if Stable(OrgC, SelC, N) == "false" :
    print("Not stable")
else :
    print("Stable")

Solution (Python):
def BubbleSort(C,N):
    for i in range(N):
        for j in reversed(range(i+1,N)):
            if C[j][1] < C[j-1][1]:
                sw = C[j]
                C[j] = C[j-1]
                C[j-1] = sw
    print(" ".join(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
        sw = C[i]
        C[i] = C[minj]
        C[minj] = sw
    print(" ".join(C))

n = int(input())
cardlistB = [x for x in input().split()]
cardlistS = []

for c in cardlistB:
    cardlistS.append(c)

BubbleSort(cardlistB,n)

print("Stable")

SelectionSort(cardlistS,n)

if cardlistB == cardlistS:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
n = int(input())
R = [x for x in input().split()]
R2=R.copy()

def selected_sort(a,n):
    for i in range(0,n-1):
        minj=i
        for j in range(i,n):
            if a[j][1]<a[minj][1]:
                minj=j
                judge=True
        a[i],a[minj]=a[minj],a[i]
    print(*a)

def bubble_sort(r,n):
    flag=True
    i=0
    count=0
    while flag:
        flag=False
        for i in range(n-1,i,-1):
            if r[i][1]<r[i-1][1]:
                r[i],r[i-1]=r[i-1],r[i]
                count+=1
                flag=True
    print(*r)

def isStable(a,b):
    if R==R2:
        print("Stable")
    else:
        print("Not stable")


bubble_sort(R,n)
print("Stable")

selected_sort(R2,n)
isStable(R,R2)

Solution (Python):
n = int(input())
C = list(map(str,input().split()))
data = [[] for i in range(9)]
for i in C:
    data[int(i[1])-1].append(i[0])
D = [s for s in C]

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]
print(" ".join(C))
flag = True
for i in range(9):
    if len(data[i]) >= 2:
        for j in range(len(data[i])-1):
            if C.index(data[i][j]+"{}".format(i+1)) > C.index(data[i][j+1]+"{}".format(i+1)):
                print("Not stable")
                flag = False
                break
        if not flag:
            break
else:
    print("Stable")
for i in range(n):
    minj = i
    for j in range(i,n):
        if int(D[j][1]) < int(D[minj][1]):
            minj = j
    else:
        D[i],D[minj] = D[minj],D[i]
print(" ".join(D))
flag = True
for i in range(9):
    if len(data[i]) >= 2:
        for j in range(len(data[i])-1):
            if D.index(data[i][j]+"{}".format(i+1)) > D.index(data[i][j+1]+"{}".format(i+1)):
                print("Not stable")
                flag = False
                break
        if not flag:
            break
else:
    print("Stable")

Solution (Python):
import copy
def SelectionSort(a):
    for i in range(len(a)):
        mini = i
        for j in range(i,len(a)):
            if a[j][1]<a[mini][1]:
                mini = j
        if i != mini:
            tmp = a[i]
            a[i] = a[mini]
            a[mini] = tmp
def BubbleSort(a):
    for i in range(len(a)):
        for j in range(len(a)-1,i,-1):
            if a[j][1]< a[j-1][1]:
                tmp = a[j]
                a[j] = a[j-1]
                a[j-1] = tmp

n = int(input())
a = list(input().split())
item = []
for i in a:
    item.append([i[0],int(i[1])])
a1 = copy.copy(item)
BubbleSort(a1)
ans1 = []
for i in a1:
    s = i[0] + str(i[1])
    ans1.append(s)
print(*ans1)
print("Stable")
a2 = copy.copy(item)
SelectionSort(a2)
ans2 = []
for i in a2:
    s = i[0] + str(i[1])
    ans2.append(s)
print(*ans2)
if ans1 == ans2:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
n = int(input())
A = [x for x in input().split()]
B = A.copy()
for i in range(n):
    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]

print(*A)
print("Stable")

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)

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

Solution (Python):
import copy

def BubbleSort(card):
    card_b = []
    card_b = copy.deepcopy(card)
    for i in range(len(card_b)-1):
        j = len(card_b)-1
        while i+1 <= j:
            if list(card_b[j])[1] < list(card_b[j-1])[1]:
                w = card_b[j]
                card_b[j] = card_b[j-1]
                card_b[j-1] = w
            j -= 1
    return card_b

def SelectionSort(card):
    card_s = []
    card_s = copy.deepcopy(card)
    for i in range(len(card_s)-1):
        mini = i
        j = i
        while len(card_s)-1 >= j:
            if list(card_s[j])[1] < list(card_s[mini])[1]:
                mini = j
            j += 1
        w = card_s[i]
        card_s[i] = card_s[mini]
        card_s[mini] = w
    return card_s

def CardPrint(card):
    i = 0
    for c in card:
        if i != n-1:
            print("{} ".format(c), end="")
        elif i == n-1:
            print(c)
        i += 1


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

r1 = []
r1 = BubbleSort(card)
CardPrint(r1)
print("Stable")

r2 = []
r2 = SelectionSort(card)
CardPrint(r2)
if r1 == r2:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
import copy
N = int(input())
C = input().split()
D = copy.copy(C)
for i in range(N):
    for j in range(i+1,N):
        k = N-j+i
        if int(C[k][1]) < int(C[k-1][1]):
            dummy = C[k]
            C[k] = C[k-1]
            C[k-1] = dummy

for i in range(N-1):
    print(f"{C[i]}",end =" ")
print(f"{C[N-1]}\nStable")
for i in range(N):
    minj = i
    for j in range(i,N):
        if int(D[j][1]) < int(D[minj][1]):
            minj = j
    dummy = D[i]
    D[i] = D[minj]
    D[minj] = dummy
for i in range(N-1):
    print(f"{D[i]}",end =" ")
flag = 0
for i in range(N):
    if C[i] != D[i]:
        flag = 1
        print(f"{D[N-1]}\nNot stable")
        break
if flag == 0:
    print(f"{D[N-1]}\nStable")

Solution (Python):
def BubbleSort(C,N):
    for a in range(0,N-1):
        for b in range(N-1,a,-1):
            if int(C[b][1]) < int(C[b-1][1]):
                C[b],C[b-1] = C[b-1],C[b]

def SelectionSort(C,N):
    for a in range(0,N-1):
        index_min = [x[1] for x in C[(a+1):]].index(min([x[1] for x in C[(a+1):]]))+a+1
        
        if C[a][1] > C[index_min][1]:
            C[a],C[index_min] = C[index_min],C[a]


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

BubbleSort(A,N)
print(*A)
print('Stable')

SelectionSort(B,N)
print(*B)
if A == B:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
n = int(input())
a = input().split()
b=a[:]
for i in range(n):
    for j in range(n-1,i,-1):
        if a[j][1]<a[j-1][1]:
            a[j-1],a[j]=a[j],a[j-1]

print(*a)
print('Stable')

for i in range(n):
    min=i
    for j in range(i,n):
        if b[min][1]>b[j][1]:
            min=j
    b[i],b[min]=b[min],b[i]
print(*b)
if a==b:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
def swap(a, i, j):
    k = a[j]
    a[j] = a[i]
    a[i] = k


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


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
        swap(A, i, minj)


N = int(input())
A = list(input().split())
B = A[:]

bubbleSort(A, N)
print(*A)
print("Stable")
selectionSort(B, N)
print(*B)
if A == B:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
import math
import itertools

def getNum(card: str) -> int:
  return int(card[1])

def checkStable(origin: list, sorted: list) -> str: 
  N_origin = [[] for _ in range(9)]
  for item in origin:
    num = getNum(item)
    N_origin[num-1].append(item)

  for item in sorted:
    num = getNum(item)    

    if N_origin[num-1][0] != item:
      return False
    else:
      N_origin[num-1].pop(0)

  return True

def main():
  n = int(input())
  A = list(input().split())
  len_A = len(A)  
  B = list(A)
  C = list(A)

  
  for i in range(len_A): 
    for j in reversed(range(i+1, len_A)):
      if getNum(B[j]) < getNum(B[j-1]):
        tmp = B[j]
        B[j] = B[j-1]
        B[j-1] = tmp

  
  for i in range(len_A):
    min = i
    for j in range(i, len_A):
      if getNum(C[j]) < getNum(C[min]):
        min = j
    
    if min != i:
      tmp = C[min]
      C[min] = C[i]
      C[i] = tmp

  print(*B) 
  if checkStable(A, B):
    print('Stable')
  else:
    print('Not stable')
  print(*C) 
  if checkStable(A, C):
    print('Stable')
  else:
    print('Not stable')

if __name__ == '__main__':
  main()

Solution (Python):
def card_encoder(a):
  result = []
  for i in a:
    s = list(map(str,i))
    c_attr = s[0]
    s.pop(0)
    c_num = int(''.join(s))
    result.append([c_attr,c_num])
  return result

def card_encoder2(a):
  result = []
  for i in a:
    s = list(map(str,i))
    s.pop(0)
    c_num = int(''.join(s))
    result.append(c_num)
  return result

def card_decoder(a):
  result = []
  for t in a:
    result.append(t[0] + str(t[1]))
  return result

def bubble_sort(a,n):
  a = card_encoder(a)
  flag = 1
  while flag:
    flag = 0
    for i in range(1,n)[::-1]:
      if a[i][1] < a[i-1][1]:
        temp = a[i]
        a[i] = a[i-1]
        a[i-1] = temp
        flag = 1
  a = card_decoder(a)
  return a
  
def selection_sort(a,n):
  a = card_encoder(a)
  for i in range(0,n):
    minv = i
    for j in range(i,n):
      if a[j][1] < a[minv][1]:
        minv = j
    if a[i][1] != a[minv][1]:
      temp = a[i]
      a[i] = a[minv]
      a[minv] = temp
  a = card_decoder(a)
  return a

def main():
  num = int(input())
  s = list(input().split())
  bubble1 = bubble_sort(s,num)
  select1 = selection_sort(s,num)
  print(' '.join(bubble1))
  print(is_stable(s,bubble1))
  print(' '.join(select1))
  print(is_stable(s,select1))

def is_stable(a_in, a_out):
  v_in = card_encoder2(a_in)
  n = len(a_in)
  for i in range(0,n):
    for j in range(i + 1,n):
      for a in range(0,n):
        for b in range(a + 1,n):
          if v_in[i] == v_in[j] and a_in[i] == a_out[b] and a_in[j] == a_out[a]:
            return 'Not stable'
  return 'Stable'

main()

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

for i in range(n):
    mj = i
    for j in range(i, n):
        if B[j][1] < B[mj][1]:
            mj = j
    B[i], B[mj] = B[mj], B[i]
print(*B)
if A == B:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
import re

def selectionSort(A, N):
    for i in range(N):
        minj = i
        for j in range(i,N):
            if A[j][1] < A[minj][1]:
                minj = j
        if i != minj:        
            ho = A[i]
            A[i] = A[minj]
            A[minj] = ho
    return A
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]:
                ho = A[j]
                A[j] = A[j-1]
                A[j-1] = ho
                flag = 1
    return A

n = int(input())
a = [i for i in input().split()]
c = a.copy()
e = a.copy()
b = bubblesort(a,n)
for i in range(len(b)):
    if i == len(b)-1:
        print(b[i])
    else:
        print(b[i],end=' ')            
f = sorted(e, key=lambda x:int((re.search(r"[0-9]+", x)).group(0)))
D = 0
for i in range(len(b)):
    if f[i] != b[i]:
        print('Not stable')
        D = 1
        break
if D == 0:
    print('Stable')
d = selectionSort(c,n)
for i in range(len(d)):
    if i == len(d)-1:
        print(d[i])
    else:
        print(d[i],end=' ')            
D = 0
for i in range(len(d)):
    if f[i] != d[i]:
        print('Not stable')
        D = 1
        break
if D == 0:
    print('Stable')

Solution (Python):
def chk_stable(re):
    for i in range(N-1):
        re_chk = list()
        re_chk.append(re[i])
        for j in range(i+1, N):
            if int(re[i][1]) == int(re[j][1]):
                re_chk.append(re[j])
        if len(re_chk) >= 2:
            for j in range(1, len(re_chk)):
                if A.index(re_chk[j]) < A.index(re_chk[j-1]):
                    return 'Not stable'
    return 'Stable'


def bubble():
    b_list = [i for i in A]
    flag = True
    while flag:
        flag = False
        for i in reversed(range(1, N)):
            if int(b_list[i][1]) < int(b_list[i-1][1]):
                tmp = b_list[i]
                b_list[i] = b_list[i-1]
                b_list[i-1] = tmp
                flag = True
    print(' '.join(b_list))
    return chk_stable(b_list)


def selection():
    s_list = [i for i in A]
    for i in range(N):
        min_i = i
        for j in range(i, N):
            if int(s_list[min_i][1]) > int(s_list[j][1]):
                min_i = j
        tmp = s_list[i]
        s_list[i] = s_list[min_i]
        s_list[min_i] = tmp
    print(' '.join(s_list))
    return chk_stable(s_list)


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

print(bubble())
print(selection())

Solution (Python):
N = int(input())
buble_A = list(map(str,input().split()))
selection_A=list(buble_A)
number=str(''.join(buble_A))
number=list(number[1::2])
number=[int(x) for x in number]
num_B=list(number)
num_S=list(number)


flg=1
while flg:
    flg=0
    for i in range(N-1,0,-1):
        if num_B[i]<num_B[i-1]:
            num_B[i],num_B[i-1]=num_B[i-1],num_B[i]
            buble_A[i],buble_A[i-1]=buble_A[i-1],buble_A[i]
            flg=1


for i in range(N-1):
    minj=i
    for j in range(i,N):
        if num_S[j]<num_S[minj]:
            minj=j
    if minj != i:
        num_S[i],num_S[minj]=num_S[minj],num_S[i]
        selection_A[i],selection_A[minj]=selection_A[minj],selection_A[i]

[print(buble_A[x],end=' ') for x in range(N-1)];print(buble_A[N-1]);print('Stable')

[print(selection_A[x],end=' ') for x in range(N-1)];print(selection_A[N-1]); print('Stable') if buble_A == selection_A else print('Not stable')

Solution (Python):
n = int(input())
c = input().split()
c = [(int(s[1]), s[0]) for s in c]
d = c.copy()


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

ans1 = " ".join([c[i][1] + str(c[i][0]) for i in range(n)])
print(ans1)
print("Stable")


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

ans2 = " ".join([d[i][1] + str(d[i][0]) for i in range(n)])
print(ans2)
if ans2 == ans1:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
def selectionSort(arr):
	icnt = 0
	for i in range(0, len(arr)):
		imin = i
		for j in range(i + 1, len(arr)):
			if arr[j][1] < arr[imin][1]:
				
				imin = j
		if imin != i:
			arr[i], arr[imin] = arr[imin], arr[i]
			icnt = icnt + 1


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

def combine(arr):
	result = ''
	for i in arr:
		result = result + i[0] + str(i[1]) + ' '
	return result.rstrip(' ')

n = int(input())
a = list(input().split())  

b = []  
for i in range(0, len(a)):
	b.append([a[i][0], int(a[i][1])])
c = b.copy()


bubbleSort(b)
result_b = combine(b)

selectionSort(c)
result_s = combine(c)

print(result_b)
print('Stable')

print(result_s)
if result_s == result_b:
	print('Stable')
else:
	print('Not stable')

Solution (Python):
import copy
num = int(input())
base_list = list(input().split())
a = copy.copy(base_list)
b = copy.copy(base_list)

for i in range(num):
    for j in reversed(range(i+1,num)):
        if a[j][1] < a[j-1][1]:
            a[j],a[j-1] = a[j-1],a[j]

print(" ".join([str(i) for i in a]))
print('Stable')

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

print(" ".join([str(i) for i in b]))
flg = False
for bubble,sele in zip(a,b):
    if bubble != sele:
        flg = True
        break

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

Solution (Python):
from typing import Any,Sequence
import  copy


def selectionSort(A:Sequence, N:int) -> None:

    for i in range(0, N - 1):
        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]



def bubble_sort(A:Sequence, N:int) -> None:

    for i in range(N):
        for j in range(N - 1, i, -1):
            if A[j][1] < A[j -1][1]:

                A[j], A[j - 1] = A[j - 1], A[j]


def bool_isStable(C1:Sequence, C2:Sequence, N:int) -> bool:
    for i in range(N):
        if C1[i] != C2[i]:
            return False
    return  True


n = int(input())
B = list(map(str, input().split()))
C1 = n * []
C2 = n * []

C1 = copy.copy(B)
C2 = copy.copy(B)


bubble_sort(C1, n)
selectionSort(C2, n)


print(' '.join(map(str, C1)))
print('Stable')


print(' '.join(map(str, C2)))
if bool_isStable(C1, C2, n) == True:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
import copy

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


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

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

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

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

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

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

Solution (Python):
n=int(input())
ss=[x for x in input().split()]     
ss2=ss.copy()

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[minj], C[i] = C[i], C[minj]
    return C

ss = BubbleSort(ss, len(ss))
ss2 = SelectionSort(ss2, len(ss2))
output = [[str(t) for t in row ] for row in ss]
print(" ".join([ "".join(row) for row in output]))
print('Stable')
output = [[str(t) for t in row ] for row in ss2]
print(" ".join([ "".join(row) for row in output]))
if(ss == ss2):
    print('Stable')
else:
    print('Not stable')

Solution (Python):
import re

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


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



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

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

Solution (Python):
import copy

N = int(input())
A = list(map(str, input().split()))
bub = []
sel = []
bub = copy.copy(A)
sel = copy.copy(A)


for i in range(N - 1, 0, -1):
    for j in range(N - 1, N - i - 1, -1):
        if bub[j][1] < bub[j - 1][1]:
            v = bub[j]
            bub[j] = bub[j - 1]
            bub[j - 1] = v

s_bub = [str(a) for a in bub]
s_bub = " ".join(s_bub)
print(s_bub)
print("Stable")


for i in range(N):  
    min_a = sel[i]  
    num = i
    for j in range(i + 1, N):  
        if min_a[1] > sel[j][1]:
            min_a = sel[j]
            num = j
    if min_a[1] < sel[i][1]:
        sel[num] = sel[i]
        sel[i] = min_a

s_sel = [str(a) for a in sel]
s_sel = " ".join(s_sel)
print(s_sel)

if sel == bub:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
def cardnum(c):
    cc = list(c)
    return int(cc[1])

def cardlabel(c):
    cc = list(c)
    return cc[0]

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

def isStable(c1, c0):
    l0 = []
    l1 = []
    for i in range(1, 10):
        for j in range(len(c0)):
            if (cardnum(c0[j])==i):
                l0.append(cardlabel(c0[j]))
            if (cardnum(c1[j])==i):
                l1.append(cardlabel(c1[j]))



    return l0 == l1
     

n = int(input())
cards = input().split()
c1 = cards.copy()
c1ret = bubleSort(c1, n)
print(' '.join(c1ret))
if (isStable(c1ret, cards)):
    print('Stable')
else:
    print('Not stable')



c2 = cards.copy()
c2ret = selectionSort(c2, n)
print(' '.join(c2ret))
if (isStable(c2ret, cards)):
    print('Stable')
else:
    print('Not stable')

Solution (Python):
def bubbleSort(A):
  global N
  for i in range(N):
    for j in  range(N-1,i,-1):
      jn = int(A[j][1:])
      jm =  int(A[j-1][1:])
      if jn < jm:
        x = A[j]
        A[j] = A[j-1]
        A[j-1] = x

def selectionSort(A):
  global N
  for i in range(N):
    minj = i
    for j in range(i,N):
      jn = int(A[j][1:])
      jm =  int(A[minj][1:])
      if jn < jm:
        minj = j
    if minj != i :
      x = A[minj]
      A[minj] = A[i]
      A[i] = x

def stableDict(A):
  S = dict()
  for e in A:
    i = e[1:]
    if i in S:
      S[i] = e + S[i]
    else:
      S[i] = e
  return S

def ckStable(org,dst):
  dictOrg = stableDict(org)
  dictDst = stableDict(dst)
  stableFlg = True
  for a in dictOrg.keys():
    if dictOrg[a] != dictDst[a]:
      stableFlg = False
  if stableFlg :
    print("Stable")
  else:
    print("Not stable")

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

A1 = list(A)
A2 = list(A)

bubbleSort(A1)
print(" ".join(A1))
ckStable(A,A1)
  
selectionSort(A2)
print(" ".join(A2))
ckStable(A,A2)

Solution (Python):
import copy


def bubbleSort(sort_list, N):

    before = copy.deepcopy(sort_list)

    for i in range(0, N):
        for j in range(N - 1, i, -1):
            if int(sort_list[j][1]) < int(sort_list[j - 1][1]):
                tmp = sort_list[j]
                sort_list[j] = sort_list[j - 1]
                sort_list[j - 1] = tmp

    print(' '.join(sort_list))
    print(checkStable(before, sort_list))


def selectionSort(sort_list, N):
    before = copy.deepcopy(sort_list)

    for i in range(0, N):
        minj = i

        for j in range(i, N):
            if int(sort_list[j][1]) < int(sort_list[minj][1]):
                minj = j

        if minj != i:
            tmp = sort_list[i]
            sort_list[i] = sort_list[minj]
            sort_list[minj] = tmp

    print(' '.join([str(i) for i in sort_list]))
    print(checkStable(before, sort_list))


def checkStable(before_list, sorted_list):

    for val in sorted_list:
        same_list = [
            i for i in sorted_list if (int(val[1]) == int(i[1])) and val != i
        ]
        if len(same_list) == 0:
            continue

        for data in same_list:
            bef = before_list.index(val) - before_list.index(data)
            aft = sorted_list.index(val) - sorted_list.index(data)

            if (bef > 0 and aft < 0) or (bef < 0 and aft > 0):
                return 'Not stable'

    return 'Stable'


if __name__ == "__main__":
    N = int(input())
    sort_list = input().split()

    sort_list2 = copy.deepcopy(sort_list)
    bubbleSort(sort_list, N)
    selectionSort(sort_list2, N)