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):
from copy import deepcopy


def printer(A):
    ret = str(A[0][1]) + str(A[0][0])
    for i in range(1, len(A)):
        ret += " " + str(A[i][1]) + str(A[i][0])
    print(ret)
    return True


def devide(card):
    ret = []
    for c in card:
        num = int(c[1])
        pic = c[0]
        ret.append((num, pic))
    return ret


def bubblesort(A):
    ret = 0
    flag = True
    num = len(A)
    while flag is True:
        flag = False
        for i in reversed(range(1, num)):
            if A[i - 1][0] > A[i][0]:
                tmp = A[i - 1]
                A[i - 1] = A[i]
                A[i] = tmp
                flag = True
                ret += 1
                
        
    return ret


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


def isStable(card, sorted_card):
    if len(card) != len(sorted_card):
        return False
    for i in range(len(card)):
        c = card[i]
        s = sorted_card[i]
        if c[0] != s[0] or c[1] != s[1]:
            return False
    return True


n = int(input())
card = list(map(str, input().split()))

card = devide(card)
card_bubble = deepcopy(card)
card_selection = deepcopy(card)

bubblesort(card_bubble)
selection_sort(card_selection)


printer(card_bubble)
print("Stable")

printer(card_selection)
if isStable(card_bubble, card_selection) is True:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
import sys
from collections import namedtuple


class Card(namedtuple('Card', ('suit', 'value'))):
    __slots__ = ()

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


def bubble_sort(cards):
    n = len(cards)
    for i in range(n):
        for j in range(n - 1, i, -1):
            if cards[j - 1].value > cards[j].value:
                cards[j - 1], cards[j] = cards[j], cards[j - 1]


def selection_sort(cards):
    n = len(cards)
    for i in range(n):
        minj = min(range(i, n), key=lambda j: cards[j].value)
        if i != minj:
            cards[i], cards[minj] = cards[minj], cards[i]


cards = [Card(suit, value) for suit, value in sys.stdin.readlines()[1].strip().split()]

bubbled = cards[:]
bubble_sort(bubbled)
print(' '.join([str(c) for c in bubbled]))
print('Stable')

selected = cards[:]
selection_sort(selected)
print(' '.join([str(c) for c in selected]))
print('Stable' if selected == bubbled else 'Not stable')

Solution (Python):

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:
			tmp = A[i]
			A[i] = A[minj]
			A[minj] = tmp

	return A

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:]:
				tmp = A[j]
				A[j] = A[j - 1]
				A[j - 1] = tmp

	return A

if __name__ == '__main__':
	n = int(input())
	R = list(map(str, input().split()))
	C = R[:]
	SR = selectionSort(R, n)
	BR = bubbleSort(C, n)

	fStable = SR == BR

	print(" ".join(map(str, BR)))
	print("Stable")
	print(" ".join(map(str, SR)))
	if (fStable == True):
		print("Stable")
	else:
		print("Not stable")

Solution (Python):
import copy
n = int(input())
b = list(map(str, input().split()))
a = copy.copy(b)
c = copy.copy(b)
k = 'Stable'

flag = 1
i = 0
while flag:
    flag = 0
    for j in range(n - 1, i, -1):
        if b[j][1] < b[j - 1][1]:
            t = b[j]
            b[j] = b[j - 1]
            b[j - 1] = t
            flag = 1
    i += 1

for i in range(0, n - 1):
    print(b[i], end=' ')
print(b[n - 1])
print(k)

for i in range(0, n):
    minj = i
    for j in range(i + 1, n):
        if a[j][1] < a[minj][1]:
            minj = j
    t = a[i]
    a[i] = a[minj]
    a[minj] = t

fl = 0
for i in range(0, n):
    for j in range(i+1, n):
        if a[i][1] == a[j][1]:
            for q in range(0, n):
                if c[q][1] == a[i][1]:
                    if c[q][0] == a[i][0]:
                        break
                    else:
                        fl = 1
if fl == 1:
    k = 'Not stable'


for i in range(0, n - 1):
    print(a[i], end=' ')
print(a[n - 1])
print(k)

Solution (Python):
import re

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

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

if __name__ == '__main__':
    
    N = int(input())
    A = input()
    C = list(map(int,re.sub(r'\D', ' ', A).split()))
    CC = list(re.sub(r'[^A-Z]', ' ', A).split())
    A = A.split()

    BSA = BubbleSort(C[:],N,A[:])
    print(' '.join(BSA))
    print('Stable')
    SSA = SelectionSort(C[:],N,A[:])
    print(' '.join(SSA))
    print('Stable' if (BSA == SSA) else 'Not stable')

Solution (Python):
import copy
def bubbleSort(A, N):
    cnt = 0
    flag = 1
    while flag:
        flag = 0
        for j in range(N - 1, 0, -1):
            if A[j][1] < A[j - 1][1]:
                A[j], A[j - 1] = A[j - 1], A[j]
                flag = 1
                cnt = cnt + 1
    return cnt


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

def prArr(A, N):
    for i in range(N):
        if i != 0:
            print(" ", end = "")
        print(A[i], end = "")
    print()

    
N = int(input())
A = [i for i in input().split()]
B = copy.deepcopy(A)

bubbleSort(A, N)
selectionSort(B, N)

prArr(A, N)
print("Stable")

prArr(B, N)
print("Stable" if A == B else "Not stable")

Solution (Python):
import copy

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

def bubblesort(n,a):
    flag = 1
    while flag:
        flag = False
        for i in reversed(range(1,n)):
            if a[i-1].value > a[i].value:
                a[i], a[i-1] = a[i-1], a[i]
                flag = True
    return a

def selectionsort(n,a):
    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]
    return a

def is_stable(before, after):
    n = 9
    lb = [[] for _ in range(n)]
    la = [[] for _ in range(n)]
    for i in range(len(before)):
        lb[before[i].value-1].append(before[i].suit)
        la[after[i].value-1].append(after[i].suit)
    if la == lb:
        print('Stable')
    else:
        print('Not stable')


if __name__ == '__main__':
    n = int(input())
    cards = [Card(x[0], int(x[1])) for x in input().split()]

    bubble_cards = bubblesort(n, copy.deepcopy(cards))
    selection_cards = selectionsort(n, copy.deepcopy(cards))

    print(' '.join(map(lambda x: x.suit+str(x.value), bubble_cards)))
    is_stable(cards, bubble_cards)

    print(' '.join(map(lambda x: x.suit+str(x.value), selection_cards)))
    is_stable(cards, selection_cards)

Solution (Python):
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:
			tmp = A[i]
			A[i] = A[minj]
			A[minj] = tmp

	return A

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:]:
				tmp = A[j]
				A[j] = A[j - 1]
				A[j - 1] = tmp

	return A

if __name__ == '__main__':
	n = int(input())
	R = list(map(str, input().split()))
	C = R[:]
	SR = selectionSort(R, n)
	BR = bubbleSort(C, n)

	fStable = SR == BR

	print(" ".join(map(str, BR)))
	print("Stable")
	print(" ".join(map(str, SR)))
	if (fStable == True):
		print("Stable")
	else:
		print("Not stable")

Solution (Python):


from copy import deepcopy

"""
stable sort
"""
N = int(input())
cN = list(map(str, input().split()))
cN2 = deepcopy(cN)


for i in range(N):
    for j in range(N-1, i, -1):
        if int(cN[j][1]) < int(cN[j-1][1]):
            tmp = cN[j]
            cN[j] = cN[j-1]
            cN[j-1] = tmp
print(' '.join(cN))
print('Stable')


for i in range(N):
    minj = i
    for j in range(i, N):
        if int(cN2[j][1]) < int(cN2[minj][1]):
            minj = j
    tmp = cN2[i]
    cN2[i] = cN2[minj]
    cN2[minj] = tmp
print(' '.join(cN2))

for i in range(N):
    if cN[i] != cN2[i]:
        print('Not stable')
        exit()
print('Stable')

Solution (Python):
import copy

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

a = [(x[0], int(x[1])) for x in a]
b = copy.deepcopy(a)


flag = True
i = 0
while flag:
    flag = False

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

    i += 1


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


for i in range(len(a)):
    if i!=len(a)-1:
        print(a[i][0], end="")
        print(a[i][1], end=" ")
    else:
        print(a[i][0], end="")
        print(a[i][1], end="")
print()
print("Stable")

for i in range(len(b)):
    if i!=len(b)-1:
        print(b[i][0], end="")
        print(b[i][1], end=" ")
    else:
        print(b[i][0], end="")
        print(b[i][1], end="")

print()

for i in range(len(b)):
    if a[i][0] != b[i][0]:
        print("Not stable")
        check = False
        break
if check:
    print("Stable")

Solution (Python):
n=int(input())
l1=list(input().split())
l2=l1.copy()
 
def bubble(L,N):
    c=0
    for i in range(N):
        j=N-1
        while j>0:
            if int(L[j][1])<int(L[j-1][1]):
                L[j],L[j-1]=L[j-1],L[j]
            j-=1
    print(" ".join(L))

bubble(l1,n)
print("Stable")

def select(L,N):
    for i in range(N):
        L2=[int(L[k][1]) for k in range(N)]
        j = L2[i:].index(min(L2[i:])) + i
        L[i], L[j] = L[j], L[i]
    print(" ".join(map(str,L)))

select(l2,n)
if l1==l2:
    print("Stable")
else:
    print("Not stable")

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 solve():
    n = int(input())
    l = input().split()
    m = l.copy()

    l = BubbleSort(l, n)
    m = SelectionSort(m, n)

    print(' '.join(l))
    print('Stable')
    print(' '.join(m))
    if l == m:
        print('Stable')
    else:
        print('Not stable')


if __name__ == '__main__':
    solve()

Solution (Python):
n=int(input())
lst=list(input().split())
lst1=[""]*n
lst2=[""]*n
for i in range(n):
    lst1[i]=lst[i]
    lst2[i]=lst[i]

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

for i in range(n-1):
    minlst=min([int(lst2[_][1]) for _ in range(i,n)])
    if minlst==int(lst2[i][1]):continue
    for j in range(i+1,n):
        if minlst==int(lst2[j][1]):
            lst2[i],lst2[j]=lst2[j],lst2[i]
            break
print(*lst2)
print("Stable" if lst1==lst2 else "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):
def bubble_sort(num_list):
    flag = 1
    while flag:
        flag = 0
        for i in range(len(num_list)-1,0,-1):
            if int(num_list[i][1:]) < int(num_list[i-1][1:]):
                num_list[i],num_list[i-1] = num_list[i-1],num_list[i]
                flag = 1

def selectin_sort(num_list):
    for i in range(len(num_list)):
        min_idx = i
        for j in range(i,len(num_list)):
            if int(num_list[j][1:]) < int(num_list[min_idx][1:]):
                min_idx = j
        num_list[i],num_list[min_idx] = num_list[min_idx],num_list[i]

n = input()
card_list_1 = [i for i in input().split()]
card_list_2 = [i for i in card_list_1]
bubble_sort  (card_list_1)
selectin_sort(card_list_2)

print(' '.join(card_list_1))
print('Stable')
print(' '.join(card_list_2))
if card_list_1 == card_list_2:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
def bubble_sort(card, n):
    flag = 1
    while flag:
        flag = 0
        for i in range(n-1, 0, -1):
            if card[i][1] < card[i-1][1]:
                card[i], card[i-1] = card[i-1], card[i]
                flag = 1
    print(' '.join(map(str, card)))
    return card

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

    print(' '.join(map(str, card)))
    return card

def isStable(stable_sorted, target):
    for i in range(len(stable_sorted)):
        if stable_sorted[i] != target[i]:
            return "Not stable"
    return "Stable"

def main():
    n = int(input())
    card = input().split()

    bubble_sorted_card = bubble_sort(card.copy(), n)
    print(isStable(bubble_sorted_card, bubble_sorted_card))

    selection_sorted_card = selection_sort(card.copy(), n)
    print(isStable(bubble_sorted_card, selection_sorted_card))

if __name__ == "__main__":
    main()

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

def SelectionSort(C):
    A=C
    
    for i in range(len(A)):
        mini=i
        for j in range(i,len(A)):
            if A[j].value<A[mini].value:
                mini=j
        if mini!=i:
            tmp=A[i]
            A[i]=A[mini]
            A[mini]=tmp
    return A

def BubbleSort(C):
    A=C
    for i in range(len(A)):
        for j in reversed(range(i+1,len(A))):
            if A[j].value < A[j-1].value:
                tmp=A[j]
                A[j]=A[j-1]
                A[j-1]=tmp
    return A

def getCardString(A):
    maplist=[]
    for a in A:
        maplist.append(a.getCard())
    return ' '.join(maplist)

n=int(input())
cardsA=[]
cardsB=[]
for data in input().split():
    charList=list(data)
    cardsA.append(Card(charList[0],int(charList[1])))
    cardsB.append(Card(charList[0],int(charList[1])))
bubble=getCardString(BubbleSort(cardsA))
select=getCardString(SelectionSort(cardsB))
print(bubble)
print('Stable')
print(select)
print('Stable' if select==bubble else 'Not stable')

Solution (Python):
import copy

n = int(input())

blist = list(map(str, input().split()))
slist = copy.deepcopy(blist)

cnt = 0

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


for i in range(n):
    minj = i
    for j in range(i, n):
        if slist[j][1] < slist[minj][1]:
            minj = j
    if i != minj:
        cnt += 1
        slist[i], slist[minj] = slist[minj], slist[i]

for i in range(n):
    if i == n-1:
        print(blist[i])
    else:
        print(blist[i] + " ", end="")

print("Stable")

for i in range(n):
    if i == n-1:
        print(slist[i])
    else:
        print(slist[i] + " ", end="")

for b, s, in zip(blist, slist):
    if b != s:
        print("Not stable")
        exit()

print("Stable")

Solution (Python):
def bubblesort(A, N):
    for i in range(N):
        for j in range(N-1,i,-1):
            if A[j-1][1] > A[j][1]:
                A[j-1], A[j] = A[j], A[j-1]
    print(*A)
    return A
    
def selectionsort(A, N):
    for i in range(N):
        minj = i
        for j in range(i+1,N):
            if A[minj][1] > A[j][1]:
                minj = j
        A[minj], A[i] = A[i], A[minj]
    print(*A)
    return A
def judge(A,B,N):
    stable = True
    for m in range(N):
        for n in range(m+1, N):
            for x in range(N):
                for y in range(x+1,N):
                    if A[m][1]==A[n][1] and A[m]==B[y] and A[n]==B[x]:
                        stable = False
    if stable:
        return "Stable"
    else:
        return "Not stable"

N = int(input())
A = list(map(str, input().split(" ")))
B = A.copy()
Bubble = bubblesort(B,N)
print(judge(A,Bubble, N))
B = A.copy()
Selection = selectionsort(B,N)
print(judge(A,Selection, N))

Solution (Python):

def showList(A, N):
    for i in range(N-1):
        print(A[i],end=' ')
    print(A[N-1])

def get_intlist(A):
    list_int = [int(x[1:]) for x in A]
    return list_int 

def bubbleSort(A, N):
    """
    バブルソート
    O(n^2)のアルゴリズム
    """
    B = get_intlist(A)
    flag = 1
    count = 0
    while flag:
        flag = 0
        for i in range(N-1, 0, -1):
            if B[i] < B[i-1]:
                v = A[i]
                A[i] = A[i-1]
                A[i-1] = v

                v = B[i]
                B[i] = B[i-1]
                B[i-1] = v
                flag = 1
    return A

def selectionSort(A, N):
    """
    選択ソート
    O(n^2)のアルゴリズム
    """
    B = get_intlist(A)
    for i in range(N):
        minj = i
        for j in range(i,N):
            if B[j] < B[minj]:
                minj = j
        if minj != i:
            t = B[minj]
            B[minj] = B[i]
            B[i] = t

            t = A[minj]
            A[minj] = A[i]
            A[i] = t
    return A

N = int(input())
A = [x for x in input().split(' ')]
A_ss = A.copy()
bub = bubbleSort(A,N)
showList(bub,N)
print('Stable')
sel = selectionSort(A_ss,N)
showList(sel,N)
if sel == bub:
    print('Stable')
else:
    print('Not stable')

Solution (Python):








number = int(input())
array = input().split(' ')
bubble_array = array.copy()
select_array = array.copy()


def bubbleSort(array, number):
    flag = 1
    i = 0
    while flag ==1:
        flag = 0
        for j in range(number-1, i, -1):
            if array[j][1] < array[j-1][1]:
                tmp = array[j]
                array[j] = array[j-1]
                array[j-1] = tmp
                flag = 1
    map_list = map(str, array)
    a = ' '.join(map_list)
    print(a)
    return array


def selectionSort(array, number):
    
    for i in range(number-1):
        mini_j = i
        for j in range(i + 1, number):
            if int(array[mini_j][1]) > int(array[j][1]):
                mini_j = j

        
        v = array[i]
        array[i] = array[mini_j]
        array[mini_j] = v
            

    map_list = map(str, array)
    a = ' '.join(map_list)
    print(a)
    return array


def isStable(input, output):
    for i in range(0, number):
        for j in range(i+1, number):
            for a in range(0, number):
                for b in range(a+1, number):
                    if input[i][1] == input[j][1] and input[i] == output[b] and input[j] == output[a]:
                        return 'Not stable'
    return 'Stable'

input = array
output_bubble = bubbleSort(bubble_array, number)

print(isStable(input, output_bubble))

output_select = selectionSort(select_array, number)

print(isStable(input, output_select))

Solution (Python):
import 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]
                
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
        if i != minj:
            c[i], c[minj] = c[minj], c[i]
            
            
n = int(input())
a = input().split()
b = copy.copy(a)

bubblesort(a,n)
for i in range(n-1):
    print(a[i], end=' ')
print(a[-1])
print('Stable')
selectionsort(b,n)
for i in range(n-1):
    print(b[i], end=' ')
print(b[-1])
if a == b:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
N = int(input())
A = []
for card in input().split():
    A.append([card[0], int(card[1])])
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]
A = " ".join([i + str(j) for i, j in A])
print(A)   
print("Stable")
for i in range(N-1):
    minj = i
    for j in range(i, N):
        if B[minj][1] > B[j][1]:
            minj = j
    B[i], B[minj] = B[minj], B[i]
B = " ".join([i + str(j) for i, j in B])
print(B)

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

Solution (Python):
import copy
n = int(input())
a = input().split()
a_bubble = a
a_selection = copy.deepcopy(a)
flag = 1
k = 0
while flag == 1:
    flag = 0
    for i in range(n-1,k,-1):
        if int(a_bubble[i-1][1]) > int(a_bubble[i][1]):
            a_bubble[i],a_bubble[i-1] = a_bubble[i-1],a_bubble[i]
            flag = 1
    k += 1
print(" ".join(a_bubble))
print("Stable")
for i in range(n):
    minj = i
    for j in range(i,n):
        if int(a_selection[j][1]) < int(a_selection[minj][1]):
            minj = j
    a_selection[i],a_selection[minj] = a_selection[minj],a_selection[i]
print(" ".join(a_selection))
if a_selection == a_bubble:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
class Selection_sort:
    def __init__(self):
        self.swap_num=0
    
    def sort(self,data):
        for i in range(len(data)):
            mini=i
            for j in range(i+1,len(data)):
                if(data[j][1] < data[mini][1]):
                    mini=j
            if(mini!=i):
                data[i],data[mini]=data[mini],data[i]
                self.swap_num+=1


class Bubble_sort:
    def __init__(self):
        self.swap_num=0
    
    def sort(self,list):
        for i in range(len(list)):
            for j in range(i+1,len(list))[::-1]:
                if(list[j][1] < list[j-1][1]):
                    list[j],list[j-1]=list[j-1],list[j]
                    self.swap_num+=1


def stability_judge(sorted,original):
    n=len(sorted)
    j=-1
    x=sorted[0][1]
    for i in range(n):
        if(x!=sorted[i][1]):
            x=sorted[i][1]
            j=-1
        
        while(1):
            j+=1
            if(x==original[j][1]):
                if(sorted[i][0]!=original[j][0]):
                    return 0
                else:
                    break
    return 1


def cards_print(cards):
    newcards=[]
    for card in cards:
        card[1]=str(card[1])
    newcards=["".join(card) for card in cards]    
    print(" ".join(newcards))




n=int(input())
cards=[list(str) for str in input().split()]
for card in cards:
    card[1]=int(card[1])

b_cards=[i for i in cards]
s_cards=[i for i in cards]


bubble_sort=Bubble_sort()
bubble_sort.sort(b_cards)

cards_print(b_cards)

if(stability_judge(b_cards,cards)):
    print("Stable")
else:
    print("Not stable")



selection_sort=Selection_sort()
selection_sort.sort(s_cards)
cards_print(s_cards)
if(stability_judge(s_cards,cards)):
    print("Stable")
else:
    print("Not stable")

Solution (Python):
def bubbleSort(list_a, n):
    flag = 1
    i = 0
    while flag:
        flag = 0
        for j in list(range(i+1,n))[::-1]:
            if list_a[j][1] < list_a[j-1][1]:
                (list_a[j], list_a[j-1]) = (list_a[j-1], list_a[j])
                flag = 1
    return list_a

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


n = int(input())
list_a_origin = list(map(str, input().split()))
list_a = list_a_origin.copy()
bubbleSort(list_a, n)
list_a_pre = list_a.copy()
print(" ".join(list_a))
bubbleSort(list_a, n)
if list_a_pre == list_a:
    print("Stable")
else:
    print("Not stable")

list_a2 = list_a_origin.copy()
selectionSort(list_a2, n)
list_a_pre2 = list_a2.copy()
print(" ".join(list_a2))
selectionSort(list_a2, n)
if list_a_pre2 == list_a:
    print("Stable")
else:
    print("Not stable")

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

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

def ChkIfStable(c1, c2):
    for v in range(1,10):
        a1=[]
        for k1 in c1:
            if k1.value == v: a1.append(k1.suit)
        a2=[]
        for k2 in c2:
            if k2.value == v: a2.append(k2.suit)
        if a1!=a2:
            print('Not stable')
            return
    print('Stable')

def BubbleSort(C):
    for i in range(0, len(C)):
        for j in range(len(C)-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):
    for i in range(len(C)):
        mini = i
        for j in range(i, len(C)):
            if C[j].value < C[mini].value:
                mini = j
        C[i], C[mini] = C[mini], C[i]
    return C

cc = []
input()
for c in input().split():
    cc.append(Card(c[0], int(c[1])))

bs=BubbleSort(cc[:])
print(' '.join(map(str,bs)))
ChkIfStable(cc, bs)
ss=SelectionSort(cc[:])
print(' '.join(map(str,ss)))
ChkIfStable(cc, ss)

Solution (Python):

def bubble(a):
    card = a[:]
    size = len(card)
    for i in range(size):
        for j in range(size - 1, i, -1):
            if card[j][1] < card[j - 1][1]:
                card[j], card[j - 1] = card[j - 1], card[j]
    return card


def selection(a):
    card = a[:]
    size = len(card)
    for i in range(size):
        minj = i
        for j in range(i, size):
            if card[j][1] < card[minj][1]:
                minj = j
        if minj != i:
            card[i], card[minj] = card[minj], card[i]
    return card


def is_stable(a, b):
    size = len(a)
    for i in range(size):
        if a[i][0] != b[i][0]:
            return False
    return True


def main():
    n = int(input())
    cards = input().split()
    a = bubble(cards)
    b = selection(cards)

    print(*a)
    print("Stable")
    print(*b)
    print("Stable" if is_stable(a, b) else "Not stable")


if __name__ == '__main__':
    main()

Solution (Python):
import copy
n = int(input())
A = input().split()
B = copy.deepcopy(A)
C = A[:]
for i in range(n):
    for j in range(n-1, i, -1):
        if int(B[j-1][1]) > int(B[j][1]):
            B[j-1], B[j] = B[j], B[j-1]
print(" ".join(B))
print("Stable")

_min = 0
for i in range(n):
    _min = i
    for j in range(i, n):
        if int(C[j][1]) < int(C[_min][1]):
            _min = j
    C[_min], C[i] = C[i], C[_min]
print(" ".join(C))
if B == C:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
import sys
import math
import collections
import itertools
import array
import inspect


sys.setrecursionlimit(1000000)


def li_input():
    return [int(_) for _ in input().split()]

def BubbleSort(N, 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]
    
    return A

def SelectionSort(N, A):

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

def is_stable(A, A_):
    for i in range(len(A_) - 1):
        if A_[i][1] == A_[i + 1][1]:
            j = A.index(A_[i])
            k = A.index(A_[i + 1])
            
            if j > k:
                return "Not stable"
    
    return "Stable"

def main():
    N = int(input())
    A = input().split()

    BA = BubbleSort(N, A[:])
    SA = SelectionSort(N, A[:])

    print(" ".join(list(map(str, BA))))
    print(is_stable(A, BA))
    print(" ".join(list(map(str, SA))))
    print(is_stable(A, SA))


main()

Solution (Python):


n=int(input())
*temp,=input().split()
a=temp[:]
b=temp[:]
for i in range(n):
    for j in range(n-1):
        if a[j][1]>a[j+1][1]:
            a[j],a[j+1]=a[j+1],a[j]

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

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

Solution (Python):
def bubble_sort(a, n):
  for i in range(n-1, 0, -1):
    j = i
    while (j < n) and (a[j][1] < a[j-1][1]):
      tmp = a[j-1]
      a[j-1] =  a[j]
      a[j] = tmp
      j += 1
  return a

def selection_sort(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:
      a[minj], a[i] = a[i], a[minj]
  return a

n = int(input())
input1 = input().split()
a = list(input1)
b = a[:]
a = bubble_sort(a, n)
b = selection_sort(b, n)



print(*a)
print("Stable")
print(*b)

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

Solution (Python):
N = int(input())
Numbers = list(input().split())
A = Numbers[::]
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] 
print(' '.join(A))
print('Stable')
B = Numbers[::]
for i in range(N):
    minj = i
    for j in range(i, N):
        if int(B[j][1]) < int(B[minj][1]):
            minj = j
    B[i], B[minj] = B[minj], B[i]
print(' '.join(B))
if A == B:
    print('Stable')
else:
    print('Not stable')