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):
import re
import copy
n = int(input())
str = input()
Origin = list(str.split())


A = copy.deepcopy(Origin)   
B = []*n

for i in range(n):
    B.append(int(re.sub("\\D","",A[i])))
flag = 1
i = 0
while flag:
    flag = 0
    for j in range(n-1,i,-1):
        if B[j] < B[j-1]:
            buf1 = B[j-1]
            buf2 = A[j-1]
            B[j-1] = B[j]
            A[j-1] = A[j]
            B[j] = buf1
            A[j] = buf2
            flag = 1
    i += 1


C = copy.deepcopy(Origin)
D = []*n
for i in range(n):
    D.append(int(re.sub("\\D","",C[i])))
for k in range(n):
    min_k = k
    for l in range(k,n):
        if D[l] < D[min_k]:
            min_k = l
    if min_k != k:
        buf1 = D[k]
        buf2 = C[k]
        D[k] = D[min_k]
        C[k] = C[min_k]
        D[min_k] = buf1
        C[min_k] = buf2

for i in range(n):
    if i != n-1:print(A[i],"",end="")
    else: print(A[i])
print("Stable")
for i in range(n):
    if i != n-1:print(C[i],"",end="")
    else: print(C[i])

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

Solution (Python):
import copy


class Card:
    def __init__(self, pair):
        self.suit = pair[0]
        self.value = int(pair[1])

    def __str__(self):
        return self.suit + str(self.value)


def bubble_sort(a, n):
    for i in range(0, n):
        for j in range(n-1, i, -1):
            if a[j].value < a[j-1].value:
                a[j], a[j-1] = a[j-1], a[j]


def selection_sort(a, n):
    for i in range(0, n):
        min_j = i
        for j in range(i, n):
            if a[j].value < a[min_j].value:
                min_j = j
        a[i], a[min_j] = a[min_j], a[i]


def equals(cards1, cards2):
    for card1, card2 in zip(cards1, cards2):
        if card1.suit != card2.suit:
            return False
    return True


def main():
    
    n = int(input())
    cards1 = list(map(Card, input().split(' ')))
    cards2 = copy.deepcopy(cards1)

    
    bubble_sort(cards1, n)
    selection_sort(cards2, n)

    
    print(' '.join(map(str, cards1)))
    print('Stable')
    print(' '.join(map(str, cards2)))
    if equals(cards1, cards2):
        print('Stable')
    else:
        print('Not stable')


if __name__ == "__main__":
    main()

Solution (Python):
n=int(input())
a=list(map(str,input().split()))
import copy
b=copy.copy(a)
k=copy.copy(a)
for i in range(n):
	for j in range(n-1,i,-1):
		if int(a[j][1])<int(a[j-1][1]):
			a[j],a[j-1]=a[j-1],a[j]
for i in range(n):
	mini=i
	for j in range(i,n):
		if int(b[j][1])<int(b[mini][1]):
			mini=j
	b[i],b[mini]=b[mini],b[i]
print(*a)
print("Stable")
print(*b)
r=True
for i in range(n):
	if not r:
		break
	for j in range(i+1,n):
		for aa in range(n):
			for bb in range(aa+1,n):
				if k[i][0]==k[j][0] and k[i]==b[bb] and k[j]==a[aa]:
					r=False
					break
if r==False:
	print("Not stable")
else:
	print("Stable")

Solution (Python):
from copy import copy
N, *A = open(0).read().split()
N = int(N)
S = ['S', 'H', 'D', 'C']
T = [0 for _ in range(N)]
for id, s in enumerate(A):
    T[id] = S.index(s[0]) * 9 + int(s[1]) - 1
B, C = copy(T), copy(T)
for i in range(N):
    for j in range(N-1, i, -1):
        if B[j] % 9 < B[j-1] % 9:
            B[j], B[j-1] = B[j-1], B[j]
B = list(map(lambda n: S[n // 9] + str(n % 9 + 1), B))
print(' '.join(B))
print('Stable')
for i in range(N):
    minj = i
    for j in range(i, N):
        if C[j] % 9 < C[minj] % 9:
            minj = j
    if i != minj:
        C[i], C[minj] = C[minj], C[i]
C = list(map(lambda n: S[n // 9] + str(n % 9 + 1), C))
print(' '.join(C))
print('Stable' if B == C else 'Not stable')

Solution (Python):



class Card:
    def __init__(self, suit, value):
        self.suit = suit
        self.value = value
        

def bubbleSort(A, N):
    flag = 1
    while flag:
        flag = 0;
        for i in reversed(range(1, N)):
            if A[i-1].value > A[i].value:
                A[i-1], A[i] = A[i] , A[i-1]
                flag = 1;
    showResult(A)
    return A

def selectionSort(A, N):
    for i in range(0, N):
        minj = i
        mink = i
        for j in range(i, N):
            if A[mink].value > A[j].value:
                mink = j
        if minj != mink:
            A[minj], A[mink] = A[mink], A[minj]
    showResult(A)
    return A



def showResult(B):
    for i in range(N-1):
        print(B[i].suit+str(B[i].value), end = " ")
    print(B[N-1].suit+str(B[N-1].value))

def isStable(rawA, sortedA):
    rawDic = listToDic(rawA)
    sortedDic = listToDic(sortedA)
    flag = 1
    for key in rawDic:
        if len(rawDic[key]) >= 2:
            for i in range(len(rawDic[key])-1):
                if rawDic[key][i] != sortedDic[key][i]:
                    
                    flag = 0
    if flag:
        print("Stable")
    else:
        print("Not stable")

def listToDic(raw):
    rawDic = {}
    for i in range(len(raw)):
        if rawDic.get(raw[i].value) != None:
            rawDic[raw[i].value].append(raw[i].suit)
        else:
            rawDic[raw[i].value] = [raw[i].suit]
    return rawDic

N = int(input())
A = list(input().split()) 
B = []
for i in range(0, N):
    B.append(Card(A[i][:1], A[i][1:]))
C = tuple(B)
"""
C = []
for i in range(0, N):
    C.append(Card(A[i][:1], A[i][1:]))
D = []
for i in range(0, N):
    D.append(Card(A[i][:1], A[i][1:]))
E = []
for i in range(0, N):
    E.append(Card(A[i][:1], A[i][1:]))

F = tuple(B)
print(B)
"""

bubbleA = bubbleSort(B.copy(), N)
isStable(B.copy(), bubbleA)
selectionA = selectionSort(B.copy(), N)
isStable(B.copy(), selectionA)

Solution (Python):
N = int(input())

card1 = input()
card2 = card1.split()
card3 = card1.split()

for i in range(N-1):
  for j in range(N-1):
    if card2[N-1-j][1] < card2[N-2-j][1]:
      a = card2[N-1-j]
      b = card2[N-2-j]
      card2[N-2-j] = a
      card2[N-1-j] = b

print(" ".join(map(str,card2)))
print("Stable")

for i in range(N):
  minj = i
  for j in range(i,N):
    if card3[j][1] < card3[minj][1]:
      minj = j
  if not card3[i][1] == card3[minj][1]:
    a = card3[i]
    b = card3[minj]
    card3[i] = b
    card3[minj] = a

print(" ".join(map(str,card3)))


if card2 == card3:
  print("Stable")
else:
  print("Not stable")

Solution (Python):
def bubbleSort(C, N):
    for i in range(0, N):
        for j in range(i+1, N):
            if int(C[N-j+i][1]) < int(C[N-j+i-1][1]):
                (C[N-j+i], C[N-j+i-1]) = (C[N-j+i-1], C[N-j+i])
    print(" ".join(C))

def selectionSort(C, N):
    count = 0
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if int(C[j][1])<int(C[minj][1]):
                minj = j
        if minj != i:
            (C[i], C[minj]) = (C[minj], C[i])
            count += 1
    print(" ".join(C))

def isStable(C1, C2, N):
    for i in range(N):
        if C1[i] != C2[i]:
            return "Not stable"
    return "Stable"

n = int(input())
card = list(input().split())
card2 = card[:]

bubbleSort(card, n)
print("Stable")
selectionSort(card2, n)
print(isStable(card, card2, n))

Solution (Python):
import copy

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


A1 = copy.deepcopy(A)
for i in range(N-1):
    for j in reversed(range(i+1, N)):
        if A1[j][1] < A1[j-1][1]:
            A1[j], A1[j-1] = A1[j-1], A1[j]
print(*A1)
print('Stable')

A2 = copy.deepcopy(A)
for i in range(N-1):
    minj = i
    for j in range(i+1, N):
        if A2[j][1] < A2[minj][1]:
            minj = j
    A2[i], A2[minj] = A2[minj], A2[i]
print(*A2)

if A1 == A2:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def SelectionSort(aa,n):
    for i in range(n):
        min_j=i
        for j in range(i+1,n):
            if int(aa[j][1])<int(aa[min_j][1]):min_j=j
        if min_j!=i:
            aa[i],aa[min_j]=aa[min_j],aa[i]
    return aa

def BubbleSort(aa,n):
    for i in range(n):
        for j in range(i,0,-1):
            if int(aa[j-1][1])<=int(aa[j][1]):break
            aa[j-1],aa[j]=aa[j],aa[j-1]
    return aa

def main():
    n = int(input())
    
    aa=input().split()
    atoi={}
    for i,a in enumerate(aa):
        atoi[a]=i

    sorted_aa=BubbleSort(aa[:],n)
    stable=True
    for a0,a1 in zip(sorted_aa,sorted_aa[1:]):
        if a0[1]==a1[1] and atoi[a0]>atoi[a1]:
            stable=False
    print(*sorted_aa)
    print("Stable") if stable else print("Not stable")

    sorted_aa=SelectionSort(aa[:],n)
    stable=True
    for a0,a1 in zip(sorted_aa,sorted_aa[1:]):
        if a0[1]==a1[1] and atoi[a0]>atoi[a1]:
            stable=False
    print(*sorted_aa)
    print("Stable") if stable else print("Not stable")

main()

Solution (Python):
import copy
N = int(input())
A = list(input().split())
C = []
C = copy.deepcopy(A)

for i in range(N):
    for j in range(N-1,i,-1):
        if int(C[j][1:]) < int(C[j-1][1:]):
                temp = C[j]
                C[j] = C[j-1]
                C[j-1] = temp

for i in range(N-1):
    minj = i
    for j in range(i+1,N):
        if int(A[j][1:]) < int(A[minj][1:]):
            minj = j
    temp = A[i]
    A[i] = A[minj]
    A[minj] = temp


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

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

def bubbleSort(A, N):
    flag = 1
    
    while flag:
        flag = 0
        for i in range(N-1, 0, -1):
            if A[i][1] < A[i-1][1]:
                temp = A[i]
                A[i] = A[i-1]
                A[i-1] = temp
                flag = 1
    return " ".join(map(str, A))
    
bubbleSort(A, N)
print(bubbleSort(A, N))
print("Stable")

def selectionSort(A, N):
    for j in range(N):
        C = []
        for i in range(N):
            C.append((A[i][1]))
            
        idx = C[j:].index(min(C[j:])) + j
        
        if A[idx][1] < A[j][1]:
            temp = A[j]
            A[j] = A[idx]
            A[idx] = temp

    return " ".join(map(str, A))

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

Solution (Python):
N = int(input())
A = list(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, sep=' ')
print('Stable')

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

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

Solution (Python):
def bubble_sort(arr, n):
    for i in range(n):
        for j in reversed(range(i + 1, n)):
            if arr[j - 1].value > arr[j].value:
                arr[j - 1], arr[j] = arr[j], arr[j - 1]
    return arr


def selection_sort(arr, n):
    for i in range(n):
        min_idx = i
        for j in range(i, n):
            if arr[j].value < arr[min_idx].value:
                min_idx = j
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr


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


def is_stable(stable_arr, target_arr):
    for s, t in zip(stable_arr, target_arr):
        if s.str != t.str:
            return False
    return True


def main():
    n = int(input())
    
    cards = input().split()
    arr = [Card(card_str) for card_str in cards]
    
    b_arr = bubble_sort(arr, n)
    print(" ".join([b.str for b in b_arr]))
    print("Stable")
    arr = [Card(card_str) for card_str in cards]
    s_arr = selection_sort(arr, n)
    print(" ".join([s.str for s in s_arr]))
    if is_stable(b_arr, s_arr):
        print("Stable")
    else:
        print("Not stable")


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import copy
sys.setrecursionlimit(10 ** 7)

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

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

N = int(input())
C1 = list(input().split())
C2 = copy.deepcopy(C1)
bC = bubbleSort(C1)
sC = selectionSort(C2)

print(*bC)
s = "Stable" 
print(s)

print(*sC)
s = "Stable"
for i in range(len(sC)-1):
    if sC[i][1] == bC[i][1] and sC[i][0] != bC[i][0]:
        s = "Not stable"
        break
print(s)

Solution (Python):
import copy
N=int(input())
c1=list(input().split())
c2=copy.deepcopy(c1)
c3=copy.deepcopy(c1)
def bubble(card):
    for i in range(N):
        for j in [N-x for x in range(1,N-i)]:
            if int(card[j][1]) < int(card[j-1][1]):
                s= card[j]
                card[j]=card[j-1]
                card[j-1]=s
    return card
def selection(card):
    for i in range(N):
        minj = i
        for j in range(i,N):
            if int(card[j][1]) < int(card[minj][1]):
                minj = j
        s = card[i]
        card[i]=card[minj]
        card[minj]=s
    return card
def stable(card):
    j=0
    for i in range(N-1):
        if int(card[i][1]) == int(card[i+1][1]):
            if c3.index(card[i]) > c3.index(card[i+1]):
                j=1
                break
    if j == 0:
        return 'Stable'
    else:
        return 'Not stable' 
print(*bubble(c1))
print(stable(bubble(c1)))
print(*selection(c2))
print(stable(selection(c2)))

Solution (Python):
import copy
N = int(input())
A = list(input().split())
B = []
for i in A:
    temp = list(i)
    B.append(temp)
C = copy.copy(B)

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

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

ans = []
for k in bubble_sort(B):
    ans.append(k[0]+k[1])
print(*ans)
print("Stable")

ans_2 = []
for k in selection_sort(C):
    ans_2.append(k[0]+k[1])

print(*ans_2)

if ans == ans_2:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
def bubbleSort(numlist):
    n = len(numlist)
    flag = True
    for i in range(n):
        if flag is False:
            break
        flag = False
        for j in range(n - 1, i, -1):
            if numlist[j][1] < numlist[j - 1][1]:
                numlist[j], numlist[j - 1] = numlist[j - 1], numlist[j]
                flag = True

def selectionSort(numlist):
    n = len(numlist)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if numlist[min_index][1] > numlist[j][1]:
                min_index = j
        
        if min_index != i:
            numlist[min_index], numlist[i] = numlist[i], numlist[min_index]

def print_numlist(numlist):
    if len(numlist) == 1:
        print(numlist[0])
    else:
        n = len(numlist)
        for i in range(n - 1):
            print(numlist[i], end=' ')
        print(numlist[-1])

if __name__ == '__main__':
    n = int(input())
    numlist = [num for num in input().replace('\n', '').split(' ')]
    numlist2 = numlist.copy()
    bubbleSort(numlist)
    print_numlist(numlist)
    print('Stable')
    selectionSort(numlist2)
    print_numlist(numlist2)
    flag = True
    for i in range(len(numlist)):
        if numlist[i] != numlist2[i]:
            flag = False
            break
    if flag:
        print('Stable')
    else:
        print('Not stable')

Solution (Python):
def to_int(A):
    return int(A[1])

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

def selection_sort(N, A):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if to_int(A[j]) < to_int(A[minj]):
                minj = j
        a = A[i]
        A[i] = A[minj]
        A[minj] = a
    return A

def is_stable(bubble, selection):
    if bubble == selection:
        return "Stable"
    else:
        return "Not stable"

if __name__ == "__main__":
    N = int(input())
    A = input().split(" ")
    bubble = bubble_sort(N, A[:])
    selection = selection_sort(N, A[:])
    print(" ".join(bubble))
    print("Stable")
    print(" ".join(selection))
    print(is_stable(bubble, selection))

Solution (Python):
n = int(input())
trump = input().split()

def bubbleSort(trump, n):
    c = trump[::]
    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))
    print('Stable')
    return c

def selectionSort(trump, n):
    c = trump[::]
    for i in range(n):
        minj = i
        for j in range(i+1, n):
            if int(c[j][1]) < int(c[minj][1]):
                minj = j
        c[i], c[minj] = c[minj], c[i]
    print(' '.join(c))
    return c

if bubbleSort(trump, n) == selectionSort(trump, n):
    print('Stable')
else:
    print('Not stable')

Solution (Python):
def bubble_sort(cards, n):




    for i in range(0, 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 selection_sort(cards, n):







    for i in range(0, n-1):
        minj = i
        for j in range(i, n):
            if int(cards[j][1]) <  int(cards[minj][1]):
                minj = j
        cards[i], cards[minj] = cards[minj], cards[i]
    
    return cards


n = int(input())
cards = input().split()
list_buble = bubble_sort(cards[:], n)
list_selection = selection_sort(cards[:], n)
print(*list_buble)
print("Stable")
print(*list_selection)
print("Stable" if list_buble == list_selection else "Not stable")

Solution (Python):
def is_stable(bubble, selection, _N):
    for i in range(N):
        if bubble[i][0] != selection[i][0]:
            return False
    return True


def bubble(N_input, A_input):
    count = 0
    flag = 1
    _A = list(A_input)

    while flag:
        flag = 0
        for i in range(N_input-1, 0, -1):
            _A_i = int(_A[i][1])
            _A_i_1 = int(_A[i-1][1])

            if _A_i < _A_i_1:
                _A[i], _A[i-1] = _A[i-1], _A[i]

                flag = 1
                count += 1

    return _A


def selection(inN, inA):
    _A = list(inA)

    for i in range(0, inN-1, 1):
        minj = i
        for j in range(i+1, inN, 1):
            if int(_A[j][1]) < int(_A[minj][1]):
                minj = j
        _A[i], _A[minj] = _A[minj], _A[i]

    return _A


N = int(input())

A = input().split()


A_bubble = bubble(N, A)
A_bubble_str = map(str, A_bubble)
print(' '.join(A_bubble_str))
print('Stable')

A_selection = selection(N, A)
A_selection_str = map(str, A_selection)
print(' '.join(A_selection_str))
if is_stable(A_bubble, A_selection, N):
    print('Stable')
else:
    print('Not stable')

Solution (Python):
class Card:
    def __init__(self):
        self.suit = ""
        self.value = ""

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

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]

def check(L1,L2):
    if L1 == L2:
        return 'Stable'
    else:
        return 'Not stable'

N = int(input())
C = list(input().split())
from copy import deepcopy
L1 = deepcopy(C)
L2 = deepcopy(C)

bubbleSort(L1,N)
selectionSort(L2,N)

print(*L1)
print('Stable')
print(*L2)
print(check(L1,L2))

Solution (Python):
n = int(input())
A = list(input().split())

BS = A[::]
SS = A[::]


for i in range(0, n):
  for j in range(n-1, i, -1):
    if int(BS[j][1]) < int(BS[j-1][1]):
      BS[j], BS[j-1] = BS[j-1], BS[j]
print(*BS, sep=" ")
print("Stable")


for i in range(0, n):
  minj = i
  for j in range(i, n):
    if int(SS[j][1]) < int(SS[minj][1]):
      minj = j
  SS[i], SS[minj] = SS[minj], SS[i]
print(*SS, sep=" ")
if SS == BS:
  print("Stable")
else:
  print("Not stable")

Solution (Python):
import copy


N=int(input())
C=list(input().split())
C_value=list(int(C[n][1:])for n in range(N))


def isStable(In,Out,In_value):
    flag=1
    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 In_value[i]==In_value[j] and In[i]==Out[b] and In[j]==Out[a]:
                        flag=0
    if flag==1:
        return 'Stable'
    else:
        return 'Not stable'


Cb=copy.copy(C)
Cb_value=list(int(Cb[n][1:])for n in range(N))


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


print(' '.join(Cb))
print(isStable(C,Cb,C_value))



Cs=copy.copy(C)
Cs_value=list(int(Cs[n][1:])for n in range(N))


for i in range(N):
    minj=i
    for j in range(i,N):
        if Cs_value[j]<Cs_value[minj]:
            minj=j
    Cs_value[i],Cs_value[minj]=Cs_value[minj],Cs_value[i]
    Cs[i],Cs[minj]=Cs[minj],Cs[i]


print(' '.join(Cs))
print(isStable(C,Cs,C_value))

Solution (Python):
import copy

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

bubble = copy.copy(a)
for i in range(n):
    for j in reversed(range(i+1,n)):
        if bubble[j][1] < bubble[j-1][1]:
            bubble[j],bubble[j-1] = bubble[j-1],bubble[j]

insertion = copy.copy(a)
for i in range(n):
    minj = i
    for j in range(i,n):
        if insertion[j][1] < insertion[minj][1]:
            minj = j
    insertion[i],insertion[minj] = insertion[minj],insertion[i]

print(' '.join(bubble))
print('Stable')
print(' '.join(insertion))
if tuple(bubble) != tuple(insertion):
    print('Not stable')
else:
    print('Stable')

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

print(*ls_a)
print("Stable")

for i in range(n):
    minj = i
    for j in range(i, n):
        if ls_b[j][1:] < ls_b[minj][1:]:
            minj = j
    ls_b[i], ls_b[minj] = ls_b[minj], ls_b[i]
print(*ls_b)
if ls_a == ls_b:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
class Card:
    def __init__(self, suit: str, value: int):
        self.suit = suit
        self.value = value

    def __str__(self):
        return self.suit + self.value


N = int(input())
cards1 = [Card(card[0], card[1]) for card in list(map(str, input().split()))]
cards2 = [*cards1]


def bubbleSort(cards: list, n: int):
    for i in range(n):
        for j in reversed(range(i+1, n)):
            if cards[j-1].value > cards[j].value:
                cards[j-1], cards[j] = cards[j], cards[j-1]
    return cards


def selectionSort(cards: list, n: int):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if cards[minj].value > cards[j].value:
                minj = j
        cards[i], cards[minj] = cards[minj], cards[i]
    return cards


def isStable(cards1: list, cards2: list, n: int):
    for i in range(n):
        if cards1[i].suit != cards2[i].suit:
            return False
    return True


bubbleSort(cards1, N)
selectionSort(cards2, N)
print(*cards1)
print('Stable')
print(*cards2)
print('Stable' if isStable(cards1, cards2, N) else 'Not stable')

Solution (Python):
n=int(input())
c=input().split()
d=c[:]

for i in range(n):
    for j in range(n-1,i,-1):
        if d[j][1]<d[j-1][1]:
            d[j],d[j-1]=d[j-1],d[j]
print(*d)
print("Stable")

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]

print(*c)
if c==d:
    print("Stable")
else:
    print("Not stable")

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

class trump:
    def __init__(self, s):
        self.name = s
        s = list(s)
        self.value = int(s[1])

N=int(input())
C = list(map(trump, input().split()))
C_copy = C.copy()

def BubbleSort(A,N):
    for i in range(N):
        for j in reversed(range(i+1,N)):
            if A[j].value < A[j-1].value:
                A[j],A[j-1]=A[j-1],A[j]
    for i in range(N):
        if i==N-1:
            print(A[i].name)
        else:
            print(A[i].name,end=" ")
    print("Stable")

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
        A[i],A[minj]=A[minj],A[i]
    for i in range(N):
        if i==N-1:
            print(A[i].name)
        else:
            print(A[i].name,end=" ")
    if C==C_copy:
        print("Stable")
    else:
        print("Not stable")
        
BubbleSort(C,N)
SelectionSort(C_copy,N)

Solution (Python):
def bs(a,n):
    ans=0
    flag=True
    while flag:
        flag=False
        for i in range(n-1,0,-1):
            if int(a[i][1])<int(a[i-1][1]):
                a[i],a[i-1]=a[i-1],a[i]
                flag=True
                ans+=1
    return a

def ss(a,n):
    ans=0
    for i in range(n):
        m=i
        for j in range(i,n):
            if int(a[j][1])<int(a[m][1]):
                m=j
        if m!=i:
            a[i],a[m]=a[m],a[i]
            ans+=1
    return a
N=int(input())
A=list(input().split())
B=A[:]
ans1,ans2=bs(A,N),ss(B,N)
print(*ans1)
print("Stable")
print(*ans2)
print("Stable" if ans1==ans2 else "Not stable")

Solution (Python):
def bubble(n, A):
    flag = True
    i = 0
    while (flag):
        flag = False
        for j in reversed(range(i+1, n)):
            if (A[j-1][1] > A[j][1]):
                A[j-1], A[j] = A[j], A[j-1]
                flag = True
        i += 1
    return A

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

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

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

Solution (Python):

def print_output(_list):
    for index in range(len(_list)):
        if index == len(_list) - 1:
            print(_list[index])
        else:
            print(_list[index],end=' ')

def bubble(_target_list):
    target_list = _target_list.copy()
    for index in range(1, len(target_list)):
        for compare_index in reversed(range(index)):
            if target_list[compare_index + 1][1] < target_list[compare_index][1]:
                target_list[compare_index + 1] ,target_list[compare_index] = target_list[compare_index] ,target_list[compare_index + 1]
            else:            
                break
    return target_list

def selection(_target_list):
    target_list = _target_list.copy()
    for i in range(len(target_list)):
        minj = i
        for j in range(i, len(target_list)):
            if target_list[j][1] < target_list[minj][1]:
                minj = j
        if i != minj:
            target_list[i], target_list[minj] = target_list[minj], target_list[i]
    return target_list

target_length = int(input())
target_list = [x for x in input().split()]

bubble_list = bubble(target_list)
print_output(bubble_list)
print("Stable")
selection_list = selection(target_list)
print_output(selection_list)
if bubble_list == selection_list:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
from typing import List


class Trump:
	def __init__(self, value, suit):
		self.value = value
		self.suit = suit

	def __repr__(self):
		return self.suit + str(self.value)


def bubble(C: List[Trump], N: int) -> None:
	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(*C)


def selection(C: List[Trump], N: int) -> None:
	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(*C)


if __name__ == "__main__":
	N = int(input())
	C1 = []
	for c in input().split():
		C1.append(Trump(int(c[1]), c[0]))
	C2 = C1.copy()

	bubble(C1, N)
	print("Stable")
	selection(C2, N)
	if C1 == C2:
		print("Stable")
	else:
		print("Not stable")

Solution (Python):
def BubbleSort(A,B,N):
    for i in range(N):
        for j in range(N-1,i,-1):
            if B[j] < B[j-1]:
                A[j],A[j-1]=A[j-1],A[j]
                B[j],B[j-1]=B[j-1],B[j]

def SelectionSort(A,B,N):
    for i in range(N):
        minj = i
        for j in range(i,N):
            if B[j] < B[minj]:
                minj = j
        A[i],A[minj]=A[minj],A[i]
        B[i],B[minj]=B[minj],B[i]

N = int(input())
A = list(input().split())
A_BubbleSort = A[:]
A_SelectionSort = A[:]
B=[0 for i in range(N)]
for i in range(N):
    B[i] = int(A[i][1])
B_BubbleSort = B[:]
B_SelectionSort = B[:]
BubbleSort(A_BubbleSort,B_BubbleSort,N)
SelectionSort(A_SelectionSort,B_SelectionSort,N)
print(*A_BubbleSort)
print("Stable")
print(*A_SelectionSort)
if A_BubbleSort == A_SelectionSort:
    print("Stable")
else:
    print("Not stable")