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


"""
??????????????????
?????????????????????????????´?????????????????????
????????§?????????????????????(S, H, C, D)??¨???????????°???(1, 2, ..., 9)??????
?§??????????????¨? 36 ????????????????????¨????????????
????????°??????????????? 8 ???"H8"??????????????? 1 ???"D1"??¨??¨????????????

????????????????????????????????????????????¢?????´??????????????¨?????????
??????????????? N ????????????????????????????????°???????????????
???????????´?????????????????°????????????????????????????????????
??¢?????´??????????????????????????\????????????????????????????????????????????¨????????????
??°??????????´???? 0 ??????????????§?¨???°?????????????????????

1 BubbleSort(C, N)
2   for i = 0 to N-1
3     for j = N-1 downto i+1
4       if C[j].value < C[j-1].value
5         C[j] ??¨ C[j-1] ?????????
6
7 SelectionSort(C, N)
8   for i = 0 to N-1
9     minj = i
10    for j = i to N-1
11      if C[j].value < C[minj].value
12        minj = j
13    C[i] ??¨ C[minj] ?????????

??????????????¢?????´?????????????????????????????????????????\??????????????????????????????????????£??????????????±????????????????????????

"""
import math

def swap(A, x, y):
    """ ??????A???x????????¨y?????????????´??????\???????????? """
    t = A[x]
    A[x] = A[y]
    A[y] = t

def value(c):
    """ ??????????????°?????¨???????????? """
    return int(c[1:])

def suits(A):
    """ ????????????????????????????????¨???????????????????????? """
    s = ""
    for c in A:
        s = s + c[0]
    return s

def bSort(A, N):
    """ ?????????????????? """
    for i in range(0, N-1):
        for j in range(N-1, i, -1):
            if value(A[j]) < value(A[j-1]):
                swap(A,j,j-1)

def sSort(A, N):
    """ ?????????????????? """
    for i in range(0, N-1):
        minj = i
        for j in range(i,N):
            if value(A[j]) < value(A[minj]):
                minj = j
        if minj != i:
            swap(A,i,minj)


N = int(input().strip())
A = input().strip().split()
bA = A[:]
bSort(bA,N)
b1 = suits(bA)
print(" ".join(map(str,bA)))
print("Stable")

sA = A[:]
sSort(sA,N)
s1 = suits(sA)
print(" ".join(map(str,sA)))
if s1 == b1:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
import re


def bubble_sort(C, N):
    for i in range(N):
        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]
    return C


def selection_sort(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 is_stable(C, sorted):
    
    c_container = []
    s_container = []
    for i in range(len(C)):
        
        for j in range(len(C)):
            
            if C[i][1] == C[j][1]:
                
                c_container.append(C[j][0])
        
        if len(c_container) >= 2:
            
            for k in range(len(sorted)):
                
                if sorted[k][1] == C[i][1]:
                    s_container.append(sorted[k][0])
            
            if c_container != s_container:
                
                return False
        
        c_container = []
        s_container = []

    return True


if __name__ == '__main__':
    N = int(input())
    
    cards = input().split()
    C = [[] for i in range(N)]
    for i in range(N):
        
        symbol_and_num = re.findall(r'(\d+|\D+)', cards[i])
        C[i] = [symbol_and_num[0], int(symbol_and_num[1])]

    
    bubble_sorted = bubble_sort(C.copy(), N)
    
    bubble_sorted_cards = [val[0] + str(val[1]) for val in bubble_sorted]
    
    print(' '.join(bubble_sorted_cards))
    
    print('Stable' if is_stable(C, bubble_sorted) else 'Not stable')

    
    selection_sorted = selection_sort(C.copy(), N)
    
    selection_sorted_cards = [val[0] + str(val[1]) for val in selection_sorted]
    
    print(' '.join(selection_sorted_cards))
    
    print('Stable' if is_stable(C, selection_sorted) else 'Not stable')

Solution (Python):
def main():
    N = int(input())
    CARD = tuple(input().split())

    sort_ = []
    for i in range(1, 10):
        for s in CARD:
            if str(i) in s:
                sort_.append(s)

    sort_ = tuple(sort_)
    bsort = tuple(bubbleSort(list(CARD), N))
    ssort = tuple(selectionSort(list(CARD), N))

    for s in (bsort, ssort):
        print(*s, sep=' ')
        if s == sort_:
            print('Stable')
        else:
            print('Not stable')

def bubbleSort(c, n):
    flag = 1
    while flag:
        flag = 0
        for i in range(1, n):
            if c[i][1] < 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):
        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

main()

Solution (Python):
def BubbleSort(C,n):
	for i in range(n):
		for j in range(i+1,n)[::-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(C):
	new = []
	for i in range(1,10):
		Ci = [cc for cc in C if cc[1]==str(i)]
		new += Ci
	return new

n = int(input())
C = input().split()
x,y,z = C[:],C[:],C[:]
bubble = BubbleSort(x,n)
selection = SelectionSort(y,n)
sta = stable(z)

print(' '.join(bubble))
print({True:'Stable',False:'Not stable'}[sta==bubble])
print(' '.join(selection))
print({True:'Stable',False:'Not stable'}[sta==selection])

Solution (Python):

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


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

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

b=bubbleSort(cards, n)
s=selectionSort(cards,n)
print(*b)
print("Stable")
print(*s)
if bubbleSort(cards, n) == selectionSort(cards, n):
    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], 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):


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

def bubble_sort(cards_b,n):
    for i in range(n):
        for j in range(-1,-n,-1):
            a=int(cards_b[j][1])
            b=int(cards_b[j-1][1])
            if a<b:
                cards_b[j],cards_b[j-1]=cards_b[j-1],cards_b[j]
    return cards_b

def selection_sort(cards_s,n):
    for i in range(n):
        minv=i
        for j in range(i,n):
            a=int(cards_s[minv][1])
            b=int(cards_s[j][1])
            if a>b:
                minv=j
        cards_s[minv],cards_s[i]=cards_s[i],cards_s[minv]
    return cards_s


dummy=cards.copy()
ans_1=bubble_sort(cards,n)

ans_2=selection_sort(dummy,n)

print(*ans_1)
print("Stable")
print(*ans_2)
if ans_1!=ans_2:
    print("Not stable")
else:
    print("Stable")

Solution (Python):
import copy

def stable(origin, new):
    for i in range(n-1):
        if int(new[i][1]) == int(new[i+1][1]):
            if origin.index(new[i]) > origin.index(new[i+1]):
                return False
    return True

n = int(raw_input())
a_origin = raw_input().split()

a = copy.copy(a_origin)
b = copy.copy(a_origin)


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

for i in range(n):
    if i == n-1:
        print a[i]
    else:
        print a[i], 

if stable(a_origin, a):
    print 'Stable'
else:
    print 'Not stable'


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

for i in range(n):
    if i == n-1:
        print b[i]
    else:
        print b[i],

if stable(a_origin, b):
    print 'Stable'
else:
    print 'Not stable'

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

for i in range(N):
    for j in range(N-1, i, -1):
        if B[j][1] < B[j-1][1]:
            B[j], B[j-1] = B[j-1], B[j]
    
    m = i
    for j in range(i, N):
        if S[m][1] > S[j][1]:
            m = j
    S[m], S[i] = S[i], S[m]

print(*B)
print('Stable')
print(*S)
print(['Not s', 'S'][B==S] + 'table')

Solution (Python):

N=int(input())
Ci=[i for i in input().split()]
C=[]
for i in range(N):
   
    C.append([])
    C[i].append(Ci[i][0])
  
    C[i].append(int(Ci[i][1]))
Cb=C
fl=1

while fl==1:
    fl=0
    for j in range(N-1):
   
        if Cb[N-1-j][1]<Cb[N-2-j][1]:
       
            t=Cb[N-1-j]
            Cb[N-1-j]=Cb[N-2-j]
            Cb[N-2-j]=t
            fl=1
        
for i in range(N):
    Cb[i][1]=str(Cb[i][1])
 
    Cb[i]="".join(Cb[i])
print(" ".join(Cb))
p="Stable"
print(p)
C=[]
for i in range(N):
 
    C.append([])
    C[i].append(Ci[i][0])
  
    C[i].append(int(Ci[i][1]))
Co=[]
for i in range(N):
    Co.append([])
  
    Co[i].append(Ci[i][0])
    Co[i].append(int(Ci[i][1]))
for i in range(N-1):
    minj=i
    for j in range(i,N):
    
        if C[j][1]<C[minj][1]:
            minj=j
        elif C[j][1]==C[minj][1]:
            k=0
            while k<N and C[minj][1]!=Co[k][1]:
                k+=1
    
            if k<N and C[minj][0]!=Co[k][0]:
                p="Not stable"
    if i!=minj:
        t=C[i]
        C[i]=C[minj]
        C[minj]=t
   
for i in range(N):
    C[i][1]=str(C[i][1])
    C[i]="".join(C[i])
print(" ".join(C))
print(p)

Solution (Python):


import sys, math, os


PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input2.txt", "rt")


def printA(A):
    print(' '.join([str(a) for a in A]))


def bubble_sort(A):
    for i in range(len(A) - 1):
        for j in range(len(A) - 1, i, -1):
            if A[j][1] < 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)):
        mini = i
        for j in range(i, len(A)):
            if A[j][1] < A[mini][1]:
                mini = j
        if mini != i:
            A[i], A[mini] = A[mini], A[i]
    return A

def is_stable(A, B):
    for val in range(1, 10):
        v = str(val)
        if [a[0] for a in A if a[1] == v] != [b[0] for b in B if b[1] == v]:
            return False
    return True
        
N = int(input())
A = list(input().split())
A_bubble = bubble_sort(A[:])
printA(A_bubble)
print("Stable" if is_stable(A, A_bubble) else "Not stable")
A_select = selection_sort(A[:])
printA(A_select)
print("Stable" if is_stable(A, A_select) else "Not stable")

Solution (Python):
def BubbleSort(C, N):
    for i in range(N):
        for j in range(N-1, i, -1):
            if C[j][1] < C[j-1][1]:
                C[j], C[j-1] = C[j-1], C[j]
    print " ".join(map(str, C))
    print "Stable"

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]
    print " ".join(map(str, C))


N = int(raw_input())
L = raw_input().split()

t1 = list(L)
BubbleSort(t1, N)

t2 = list(L)
SelectionSort(t2, N)

if  t1 == t2:
    print "Stable"
else:
    print "Not stable"

Solution (Python):
def compare_cards(a, b):
    return a[1] < b[1]

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

def selection_sort(A):
    for i in range(len(A)):
        mini = i
        for j in range(i, len(A)):
            if compare_cards(A[j], A[mini]):
                mini = j
        A[i], A[mini] = A[mini], A[i]

def check_stable(originA, sortedA):
    for i in range(len(originA)-1):
        if not compare_cards(sortedA[i], sortedA[i+1]):
            if originA.index(sortedA[i]) > originA.index(sortedA[i+1]):
                return "Not stable"
    return "Stable"

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

bubbleA = list(A)
selectionA = list(A)

bubble_sort(bubbleA)
selection_sort(selectionA)

print(*bubbleA)
print(check_stable(A, bubbleA))

print(*selectionA)
print(check_stable(A, selectionA))

Solution (Python):
def compare_cards(a, b):
    return a[1] < b[1]

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

def selection_sort(A):
    for i in range(len(A)):
        mini = i
        for j in range(i, len(A)):
            if compare_cards(A[j], A[mini]):
                mini = j
        A[i], A[mini] = A[mini], A[i]

def check_stable(originA, sortedA):
    for i in range(len(originA)-1):
        if not compare_cards(sortedA[i], sortedA[i+1]):
            if originA.index(sortedA[i]) > originA.index(sortedA[i+1]):
                return "Not stable"
    return "Stable"

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

bubbleA = list(A)
selectionA = list(A)

bubble_sort(bubbleA)
selection_sort(selectionA)

print(*bubbleA)
print(check_stable(A, bubbleA))

print(*selectionA)
print(check_stable(A, selectionA))

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

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

def isStable(B, S, N):
    for i in range(N):
        if B[i] != S[i]:
            return False
    return True

N = int(input())
B = input().split()
S = B[:]
B = BubbleSort(B, N)
S = SelectionSort(S, N)
mes = "Stable" if isStable(B, S, N) else "Not stable"
print(" ".join(B))
print("Stable")
print(" ".join(S))
print(mes)

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

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

if __name__ == '__main__':
    N = (int)(input())
    A1 = [[x[0],(int)(x[1])] for x in [list(x) for x in input().split()] ]
    A2 = A1.copy()

    resultA1 = bubbleSort(A1,N)
    resultA2 = selectionSort(A2,N)

    outputA1 = ' '.join( [x[0]+(str)(x[1]) for x in resultA1])
    outputA2 = ' '.join( [x[0]+(str)(x[1]) for x in resultA2])

    print(outputA1)
    print("Stable")
    print(outputA2)
    if outputA1 == outputA2 :
        print("Stable")
    else:
        print("Not stable")

Solution (Python):
import copy
def bs(array):
    for i in range(len(array)-1):
        for c in range(len(array)-1, i,-1):
            if array[c][1] < array[c-1][1]:
                swap = array[c]
                array[c] = array[c-1]
                array[c-1] = swap
    return array
def ss(array):
    for i in range(len(array)):
        minj = i
        for c in range(i+1,len(array)):
            if array[minj][1] > array[c][1]:
                minj = c
        swap = array[i]
        array[i] = array[minj]
        array[minj] = swap
    return array
def isStable(ar1,ar2):
    flag = 0
    for (x,y) in zip(ar1,ar2):
        if x != y:
            flag = 1
            break
    if flag == 0:
        print('Stable')
    else:
        print('Not stable')


n = input()
arr = [[i[0],int(i[1])] for i in input().split()]
arr1 = copy.deepcopy(arr)
arr2 = copy.deepcopy(arr)

bsarr = bs(arr2)
ssarr = ss(arr1)
print(' '.join([''.join([ x[0], str(x[1]) ]) for x in bsarr]))
print('Stable')
print(' '.join([''.join([ x[0], str(x[1]) ]) for x in ssarr]))
isStable(bsarr,ssarr)

Solution (Python):
n = int(input())
a = input().split()
b = a[:]
flag = 1
while flag:
    flag = 0
    for i in range(n-1):
        if a[i][1] > a[i+1][1]:
            a[i], a[i+1] = a[i+1], a[i]
            flag = 1
print(*a)
print("Stable")

for i in range(n-1):
    min_j = i
    for j in range(i,n):
        if b[j][1] < b[min_j][1]:
            min_j = j
    b[i], b[min_j] = b[min_j], b[i]
print(*b)
if a == b:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
n = int(input())
a = input().split()
b = a[:]
flag = 1
while flag:
    flag = 0
    for i in range(n-1):
        if a[i][1] > a[i+1][1]:
            a[i], a[i+1] = a[i+1], a[i]
            flag = 1
print(*a)
print("Stable")

for i in range(n-1):
    min_j = i
    for j in range(i,n):
        if b[j][1] < b[min_j][1]:
            min_j = j
    b[i], b[min_j] = b[min_j], b[i]
print(*b)
if a == b:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
import copy
def inputInline():
    N = int(input())
    cards = input().split(" ")
    return cards

def selectionSort(list):
    cards=copy.deepcopy(list)
    n = len(cards)
    count = 0
    for i in range(n):
        min_j = i
        for j in range(i + 1, n):
            if int(cards[j][1]) < int(cards[min_j][1]):
                min_j = j
        if min_j != i:
            temp = cards[i]
            cards[i] = cards[min_j]
            cards[min_j] = temp
            count += 1
    return (" ".join(cards), count)

def bubbleSort(list):
    cards=copy.deepcopy(list)
    N = len(cards)
    count = 0
    flag = True
    while flag:
        flag = False
        for i in range(N - 1):
            if int(cards[i][1]) > int(cards[i + 1][1]):
                temp = cards[i]
                cards[i] = cards[i + 1]
                cards[i + 1] = temp
                flag = True
                count += 1
    return (" ".join(cards), count)
cards=inputInline()
sortedbubble=bubbleSort(cards)[0]
sortedselection=selectionSort(cards)[0]
print(sortedbubble)
print("Stable")
print(sortedselection)
if sortedbubble==sortedselection:
    print("Stable")
else:
    print("Not stable")

Solution (Python):

def bubblesort(c, n):
	for i in range(n):
		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]

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 output(c):
	for i in range(len(c)):
		if i != 0: print(" ", end="")
		print("{}{}".format(c[i][0], c[i][1]), end="")
	print()

def main():
	n = int(input())
	data = input().split()
	cards = []

	for c in data:
		cards.append((c[0],int(c[1])))
	cards1 = cards[:]
	cards2 = cards[:]

	bubblesort(cards1, n)
	output(cards1)
	print("Stable")

	selectionsort(cards2, n)
	output(cards2)
	if (cards1 == cards2):
		print("Stable")
	else:
		print("Not stable")

if __name__ == "__main__":
	main()

Solution (Python):
from collections import namedtuple


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]


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


Card = namedtuple('Card', 'mark value')
n = int(input())
a = [Card(i[0], int(i[1])) for i in input().split()]
b = a[:]

BubbleSort(a, n)
SelectionSort(b, n)

print(" ".join([i.mark + str(i.value) for i in a]))
print("Stable")
print(" ".join([i.mark + str(i.value) for i in b]))
print("Stable" if a == b else "Not stable")

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

def selectionSort(N, A):
    C = [] + A
    for i in range(N):
        minj = i
        for j in range(i,N):
            if int(C[j][1]) < int(C[minj][1]):
                minj = j
        C[i], C[minj] = C[minj], C[i]
    return C

N, A= int(input()), input().split()
Ab = bubblesort(N, A)
print(*Ab)
print('Stable')
As = selectionSort(N, A)
print(*As)
if Ab != As:
    print('Not stable')
else:
    print('Stable')

Solution (Python):
class Card(object):
    def __init__(self, card):
        self._suit = card[0]
        self._value = int(card[1])

    def __eq__(self, other):
        if other is None:
            return False
        return self.__dict__ == other.__dict__

    def getValue(self):
        return self._value

    def toString(self):
        return self._suit + str(self._value)


def card_bubbleSort(lst, n):
    for i in range(0, n):
        for j in range(n-1, i, -1):
            if lst[j].getValue() < lst[j-1].getValue():
                tmp = lst[j]
                lst[j] = lst[j-1]
                lst[j-1] = tmp

    return lst


def card_selectionSort(lst, n):
    for i in range(0, n):
        minj = i
        for j in range(i, n):
            if lst[j].getValue() < lst[minj].getValue():
                minj = j

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

    return lst


def isStable(in_lst, out_lst, n):
    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 in_lst[i].getValue() == in_lst[j].getValue() \
                            and in_lst[i] == out_lst[b] \
                            and in_lst[j] == out_lst[a]:
                                return False
    return True


if __name__ == "__main__":
    n = int(input())
    lst = input().split()
    func_table = [card_bubbleSort, card_selectionSort]
    for func in func_table:
        cards = [Card(item) for item in lst]
        result = func(cards, n)
        cards = [Card(item) for item in lst]
        print(" ".join([card.toString() for card in result]))
        if isStable(cards, result, n):
            print("Stable")
        else:
            print("Not stable")

Solution (Python):
def bubbleSort(A,N):
    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]
    return A

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

N =int(input())
cards = input().split()
bub , sel =cards[:] , cards[:]
X = bubbleSort(bub , N)
print(*X)
print("Stable")
Y = selectionSort(sel,N)
print(*Y)
print("Stable" if X == Y else "Not stable")

Solution (Python):
import copy

n = int(raw_input())
cards = raw_input().split()
cards1 = copy.deepcopy(cards)
cards2 = copy.deepcopy(cards)

def isbig(card1, card2):
	if int(card1[1]) > int(card2[1]):
		return 2
	elif int(card1[1]) == int(card2[1]):
		return 1
	else:
		return 0

def BubbleSort(c, n):
	temp = 0
	for i in range(n):
		for j in reversed(range(i+1,n)):
			if isbig(c[j], c[j-1]) == 0:
				temp = c[j]
				c[j] = c[j-1]
				c[j-1] = temp
	return c

def SelectionSort(c, n):
	temp = 0
	for i in range(n):
		minj = i
		for j in range(i,n):
			if isbig(c[j], c[minj]) == 0:
				minj = j
		temp = c[i]
		c[i] = c[minj]
		c[minj] = temp
		
	return c

def isstable(unsort, sort):
	for i in range(n):
		for j in range(i+1,n):
			for k in range(n):
				for l in range(k+1,n):
					if isbig(unsort[i], unsort[j]) == 1 and unsort[i] == sort[l] and unsort[j] == sort[k]:
						return 0
	return 1

for i in range(n):
	if i != n-1:
		print BubbleSort(cards1, n)[i],
	else:
		print BubbleSort(cards1, n)[i]

if isstable(cards, BubbleSort(cards1, n)) == 1:
	print("Stable")
else:
	print("Not stable")

for i in range(n):
	if i != n-1:
		print SelectionSort(cards2, n)[i],
	else:
		print SelectionSort(cards2, n)[i]

if isstable(cards, SelectionSort(cards2, n)) == 1:
	print("Stable")
else:
	print("Not stable")

Solution (Python):
N = int(input())
C = input().split()
_C = C.copy()

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]
print(*C)
print("Stable")

for i in range(N):
    m = i
    for j in range(i, N):
        if (_C[j][1] < _C[m][1]):
            m = j
    _C[i], _C[m] = _C[m], _C[i]
print(*_C)
if(C ==_C):
    print("Stable")
else:
    print("Not stable")

Solution (Python):
N = int(input())
C = list(input().split())
_C = C.copy()

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]
print(*C)
print("Stable")

for i in range(N):
    m = i
    for j in range(i, N):
        if (_C[j][1] < _C[m][1]):
            m = j
    _C[i], _C[m] = _C[m], _C[i]
print(*_C)
if(C ==_C):
    print("Stable")
else:
    print("Not stable")

Solution (Python):
n = int(input())
a = input().split()
b = a[:]
frag = 1
while frag:
  frag = 0
  for i in range(n - 1):
    if a[i][1] > a[i + 1][1]:
      a[i], a[i + 1] = a[i + 1], a[i]
      frag = 1
print(*a)
print("Stable")

for i in range(n - 1):
  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)
if a == b:
  print("Stable")
else:
  print("Not stable")

Solution (Python):
n=int(input())
a=[i for i in input().split(" ")]
b=a.copy()
flg=1

while flg:
    flg=0
    for j in range(n-1,0,-1):
        if a[j][1] < a[j-1][1]:
           a[j-1],a[j]=a[j],a[j-1]
           flg=1  

for i in range(n):
    mi=i
    for j in range(i,n):
        if b[j][1] < b[mi][1]:
            mi = j
    if i != mi:
        b[i],b[mi]=b[mi],b[i]

print(" ".join([str(i) for i in a]))
print("Stable")
print(" ".join([str(i) for i in b]))
if a==b:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
n = int(input())
a = input().strip().split()

b = a[:]
for i in range(n):
    for j in range(n-1,i,-1):
        if b[j][1] < b[j-1][1]:
            b[j],b[j-1] = b[j-1],b[j]
print(' '.join(b))
print('Stable')

for i in range(n):
    minj = i
    for j in range(i,n):
        if a[j][1] < a[minj][1]:
            minj = j
    a[i],a[minj] = a[minj],a[i]
print(' '.join(a))
print('Stable' if b == a else 'Not stable')

Solution (Python):
def bubbleSort(A,N):
    flag = 1 
    i = 0

    while flag:
        flag = 0
        for j in range(N-1,i,-1):
            if int(A[j][1]) < int(A[j-1][1]):
                tmp = A[j]
                A[j] = A[j-1]
                A[j-1] = tmp
                flag = 1
        i += 1
    return A


def selectionSort(A,N):
    for i in range(0,N-1):
        minj = i
        j=i+1
        for j in range(j,N):
            if int(A[j][1]) < int(A[minj][1]):
                minj = j
        tmp = A[minj]
        A[minj] = A[i]
        A[i] = tmp
    return A

def isStable(ori,sorted):
    for i in range(len(ori)-1):
        for j in range(i+1, len(ori)-1):
            for a in range(len(ori)):
                for b in range(a+1, len(ori)):
                    if ori[i][1] == ori[j][1] and ori[i] == sorted[b] and ori[j] == sorted[a]:
                        return 'Not stable'
    return 'Stable'

def output(A):
    for i in range(len(A)):  
        if i == len(A) - 1:
            print(A[i])
        else:
            print(A[i], end=' ')

if __name__ == '__main__':

    N = int(input())

    numbers = input().split(' ')
    n1 = numbers.copy()
    n2 = numbers.copy()

    A = bubbleSort(n1,N)

    output(A)
    print(isStable(numbers,A))

    B = selectionSort(n2,N)

    output(B)
    print(isStable(numbers, B))

Solution (Python):
import copy

def bubbleSort(cards):
    C = copy.copy(cards)
    for i in range(0, len(C)):
        for j in range(len(C) - 1, i, -1):
            if C[j][1] < C[j-1][1]:
                C[j-1], C[j] = C[j], C[j-1]
    return C

def selectionSort(cards):
    C = copy.copy(cards)
    for i in range(0, len(C)):
        min = i
        for j in range(i, len(C)):
            if C[j][1] < C[min][1]:
                min = j
        C[i], C[min] = C[min], C[i]
    return C


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

CB = bubbleSort(cards)
CS = selectionSort(cards)
print(' '.join(CB))
print('Stable')
print(' '.join(CS))
if CB == CS:
    print('Stable')
else:
    print('Not stable')