Problem:
Stable Sort Let's arrange a deck of cards. There are totally 36 cards of 4 suits(S, H, C, D) and 9 values (1, 2, ... 9). For example, 'eight of heart' is represented by H8 and 'one of diamonds' is represented by D1 . Your task is to write a program which sorts a given set of cards in ascending order by their values using the Bubble Sort algorithms and the Selection Sort algorithm respectively. These algorithms should be based on the following pseudocode: BubbleSort(C)
1 for i = 0 to C.length-1
2     for j = C.length-1 downto i+1
3         if C[j].value < C[j-1].value
4             swap C[j] and C[j-1] SelectionSort(C)
1 for i = 0 to C.length-1
2     mini = i
3     for j = i to C.length-1
4         if C[j].value < C[mini].value
5             mini = j
6     swap C[i] and C[mini] Note that, indices for array elements are based on 0-origin. Input The first line contains an integer N , the number of cards.  N cards are given in the following line. Each card is represented by two characters. Two consecutive cards are separated by a space character. Output In the first line, print the arranged cards provided by the Bubble Sort algorithm. Two consecutive cards should be separated by a space character. In the second line, print the stability (" Stable " or " Not stable ") of this output. In the third line, print the arranged cards provided by the Selection Sort algorithm. Two consecutive cards should be separated by a space character. In the fourth line, print the stability (" Stable " or " Not stable ") of this output. Constraints 1 ≤ N ≤ 36 Sample Input 1 5
H4 C9 S4 D2 C3 Sample Output 1 D2 C3 H4 S4 C9
Stable
D2 C3 S4 H4 C9
Not stable Sample Input 2 2
S1 H1 Sample Output 2 S1 H1
Stable
S1 H1
Stable

Solution (Python):
def bubble(x):
    x = x + []
    n = len(x)
    for i in range(n):
        for j in range(i+1,n)[::-1]:
            if x[j] % 10 < x[j-1] % 10:
                x[j], x[j-1] = x[j-1], x[j]
    return x

def selection(x):
    x = x + []
    n = len(x)
    for i in range(n):
        mini = i
        for j in range(i, n):
            if x[j] % 10 < x[mini] % 10:
                mini = j
        if i != mini:
            x[i], x[mini] = x[mini], x[i]
    return x
    
def order(x):
    y = []
    for i in range(1,9):
        y.extend([e for e in x if e % 10 == i])
    return y

def output(x):
    for e in x:
        print 'SHDC'[e/10]+str(e % 10),
    print

def check(x, y):
    output(x)
    if y == order(x): 
        print 'Stable'
    else:
        print 'Not stable'
    return

n = input()
x = []
for s in raw_input().split():
    x.append('SHDC'.index(s[0])*10 + int(s[1]))
x0 = order(x)
check(bubble(x), x0)
check(selection(x), x0)

Solution (Python):

from __future__ import division, print_function
from sys import stdin


def bubble(cards):
    for i in range(len(cards)):
        for j in range(len(cards)-1, i, -1):
            if cards[j][1] < cards[j-1][1]:
                cards[j], cards[j-1] = cards[j-1], cards[j]


def selection(cards):
    for i in range(len(cards)):
        mini = i
        for j in range(i, len(cards)):
            if cards[j][1] < cards[mini][1]:
                mini = j
        cards[i], cards[mini] = cards[mini], cards[i]


def stable_test(orders, cards):
    for order in orders:
        n = -1
        for c in order:
            p = n
            n = cards.index(c)
            if p > n:
                return False
    return True


stdin.readline()
data1 = stdin.readline().split()
data2 = data1[:]
orders = [[c for c in data1 if c.endswith(str(i))] for i in range(1, 10)]
orders = [o for o in orders if len(c) > 1]

bubble(data1)
print(*data1)
print('Stable' if stable_test(orders, data1) else 'Not stable')

selection(data2)
print(*data2)
print('Stable' if stable_test(orders, data2) else 'Not stable')

Solution (Python):


from __future__ import print_function
import time
import sys
import io
import re
import math
start = time.clock()

def bubble(cards):
    for i in range(len(cards)):
        for j in range(len(cards)-1, i, -1):
            if cards[j][1]<cards[j-1][1]:
                cards[j],cards[j-1]=cards[j-1],cards[j]

def selection(cards):
    for i in range(len(cards)):
        mini=i
        for j in range(i,len(cards)):
            if cards[j][1]<cards[mini][1]:
                mini=j
        cards[i],cards[mini]=cards[mini],cards[i]

def stable_test(orders,cards):
    for order in orders:
        n=-1
        for c in order:
            p=n
            n=cards.index(c)
            if p>n:
                return False
    return True

sys.stdin.readline()
data1=sys.stdin.readline().split()
data2=data1[:]
orders=[[c for c in data1 if c.endswith(str(i))] for i in range(1,10)]
orders=[o for o in orders if len(c)>1]

bubble(data1)
print(*data1)
print('Stable' if stable_test(orders, data1) else 'Not stable')

selection(data2)
print(*data2)
print('Stable' if stable_test(orders, data2) else 'Not stable')

Solution (Python):
def buble(C):
	for i in range(len(C)):
		for j in range(len(C)-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 selection(C):
	for i in range(len(C)):
		mini = i
		for j in range(i,len(C)):
			if int(C[j][-1]) < int(C[mini][-1]):
				mini = j
		C[i],C[mini] = C[mini],C[i]
	return C

n = int(raw_input())
card = map(str, raw_input().split())
card1 = card[:]
buble(card);selection(card1)
print " ".join(map(str, card))
print "Stable"
print " ".join(map(str, card1))
print "Stable" if card == card1 else "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):
    mini = i
    for j in range(i, n):
        if a[j][1] < a[mini][1]:
            mini = j
    a[i], a[mini] = a[mini], a[i]
print(' '.join(a))
print('Stable' if a == b else 'Not stable')

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

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



def check(lst1, lst2):
    if lst1 == lst2:
        print("Stable")
    else:
        print("Not stable")

"""
def check(n, lst_o, lst):
    keeper = [[]]*10
    keeper2 = [[]]*10
    for i in range(n):
        keeper[int(lst_o[i][1])] = keeper[int(lst_o[i][1])] + [lst_o[i][0]]
        keeper2[int(lst[i][1])] = keeper2[int(lst[i][1])] + [lst[i][0]]
    if keeper == keeper2:
        print("Stable")
    else:
        print("Not stable")
"""

n = int(input())
lst = input().split()
lst1 = BubbleSort(n, lst.copy())
print(*lst1)

print("Stable")
lst2 = SelectionSort(n, lst.copy())
print(*lst2)
check(lst1, lst2)

Solution (Python):
import copy as cp

n = int(input())
A = [str(x) for x in input().split()]
AS = cp.copy(A)


def bubble(X):
    for i in range(n):
        X[i] = list(X[i])
        X[i][1] = int(X[i][1])

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

    for i in range(n):
        X[i][1] = str(X[i][1])
        X[i] = "".join(X[i])
    return(X)


BA = bubble(A)



def minsort():

    for i in range(n):
        AS[i] = list(AS[i])
        AS[i][1] = int(AS[i][1])

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

        if (minj != i):
            AS[i],AS[minj] = AS[minj],AS[i]

    for i in range(n):
        AS[i][1] = str(AS[i][1])
        AS[i] = "".join(AS[i])

    return(AS)

MA = minsort()


for k in range(n-1):
    print(str(BA[k])+" ",end = "")
print(str(BA[n-1]))
print("Stable")

for k in range(n-1):
    print(str(MA[k])+" ",end = "")
print(str(MA[n-1]))
if (BA == MA):
    print("Stable")
else :
    print("Not stable")

Solution (Python):
def BubbleSort(C, N):
    for i in range(N-1):
        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):
        min_j = i
        for j in range(i+1, N):
            if int(C[j][1]) < int(C[min_j][1]):
                min_j = j
        C[i], C[min_j] = C[min_j], C[i] 
    return C

def isStable(in_list, out_list):
    N = len(in_list)
    for i_in in range(N):
        for j_in in range(i_in+1, N):
            for i_out in range(N):
                for j_out in range(i_out+1, N):
                    if (in_list[i_in][1] == in_list[j_in][1]) and\
                       (in_list[i_in] == out_list[j_out]) and\
                       (in_list[j_in] == out_list[i_out]):
                        return False
    return True

if __name__ == "__main__":
    N = int(input())
    C = list(map(str, input().split()))
    C1 = C.copy()
    C2 = C.copy()
    Bubble_C = BubbleSort(C1, N)
    Selection_C = SelectionSort(C2, N)

    print(*Bubble_C)
    print('Stable')
    print(*Selection_C)
    if Bubble_C == Selection_C:
        print('Stable')
    else:
        print('Not stable')

Solution (Python):
n = int(input())
card1 = list(input().split())
card2 = [i for i in card1]
def bubbleSort(c1:list, n:int):
    for i in range(n):
        for j in range(n-1, i, -1):
            if c1[j][1] < c1[j-1][1]:
                c1[j], c1[j-1] = c1[j-1], c1[j]
    return c1

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

bubblesort = bubbleSort(card1, n)
selectionsort = selectionSort(card2, n)

flag = 0
for i in range(n):
    if bubblesort[i] != selectionsort[i]:
        flag = 1

print(" ".join(bubblesort))
print("Stable")
print(" ".join(selectionsort))
if flag:
    print("Not stable")
else:
    print("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):
N = int(input())
SI = list(input().split())
SB = SI.copy()


for i in range(N):
	for j in range(N - 1, i, -1):
		if SB[j - 1][1] > SB[j][1]:
			x = SB[j - 1]
			SB[j - 1] = SB[j]
			SB[j] = x


for i in range(N):
	ptr = i
	for j in range(i + 1, N):
		if SI[ptr][1] > SI[j][1]:
			ptr = j
	x = SI[i]
	SI[i] = SI[ptr]
	SI[ptr] = x


for i in range(N):
	print(SB[i] + " " if i != N - 1 else str(SB[i]) + "\n", end='')
print("Stable")
for i in range(N):
	print(SI[i] + " " if i != N - 1 else str(SI[i]) + "\n", end='')
print("Stable" if SI == SB else "Not stable")

Solution (Python):

def JudgeStable(inC, outC, N):
    for i in range(N):
        for j in range(i+1, N):
            for a in range(N):
                for b in range(a+1, N):
                    if inC[i][1] == inC[j][1] and inC[i] == outC[b] and inC[j] == outC[a]:
                        return False
    return True

def PrintJudge(judge):
    if judge:
        print('Stable')
    else:
        print('Not stable')
        
def BubbleSort(C, N):
    for i in range(N):
        for j in reversed(range(i+1, N)):
            if C[j-1][1] > C[j][1]:
                C[j-1], C[j] = C[j], C[j-1]
                
def SelectionSort(C, N):
    for i in range(N):
        minj = i
        for j in range(i+1, N):
            if C[minj][1] > C[j][1]:
                minj = j
        C[minj], C[i] = C[i], C[minj]
                
def PrintC(C):
    print(' '.join([''.join([c[0], str(c[1])]) for c in C]))

N = int(input())
C = [[c[0], int(c[1])] for c in input().split()]
C1 = C.copy()
C2 = C.copy()

BubbleSort(C1, N)
SelectionSort(C2, N)

PrintC(C1)
PrintJudge(JudgeStable(C, C1, N))

PrintC(C2)
PrintJudge(JudgeStable(C, C2, N))

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
A = LS()
A_Bub = []
A_Sel = []
for i in range(N):
    A_Bub.append([A[i][0], int(A[i][1]), i])
    A_Sel.append([A[i][0], int(A[i][1]), i])


def BubleSort(C, N):
    for i in range(N):
        for j in range(N - 1, i, -1):
            if C[j][1] < C[j - 1][1]:
                a = C[j]
                b = C[j - 1]
                C[j] = b
                C[j - 1] = a


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

def Check(C, N):
    for i in range(1, N):
        if C[i][1] == C[i - 1][1]:
            if C[i][2] < C[i - 1][2]:
                return 'Not stable'
    return 'Stable'
BubleSort(A_Bub, N)
ans_Bub = []
for i in range(N):
    b = [A_Bub[i][0], A_Bub[i][1]]
    ans_Bub.append(''.join(map(str, b)))
print(' '.join(map(str, ans_Bub)))
print(Check(A_Bub, N))


SelectionSort(A_Sel, N)
ans_Sel = []
for i in range(N):
    s = [A_Sel[i][0], A_Sel[i][1]]
    ans_Sel.append(''.join(map(str, s)))
print(' '.join(map(str, ans_Sel)))
print(Check(A_Sel, N))

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

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

def J(C, C_):
    for i in range(1,len(C_)):
        if int(C_[i-1][1]) == int(C_[i][1]):
            p = C.index(C_[i-1])
            q = C.index(C_[i])
            if q<p:
                return 'Not stable'
    return 'Stable'

N = int(input())
C = list(input().split())
C_B = C.copy()
C_S = C.copy()
CB = BubbleSort(C_B, N)
CS = SelectionSort(C_S, N)

for i in range(len(CB)):
    if i==len(CB)-1:
        print(CB[i])
    else:
        print(CB[i],end=' ')
print(J(C, CB))
for i in range(len(CS)):
    if i==len(CS)-1:
        print(CS[i])
    else:
        print(CS[i],end=' ')
print(J(C, CS))

Solution (Python):
import copy

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

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

N = int(input())
lst1 = list(input().split())
lst2 =  copy.copy(lst1)
print(" ".join(bubbleSort(lst1)))
print("Stable")
print(" ".join(selectionSort(lst2)))
if lst1 == lst2:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
def selection_sort(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
        temp = c[i]
        c[i] = c[minj]
        c[minj] = temp
    return c


def bubble_sort(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]):
                temp = c[j]
                c[j] = c[j-1]
                c[j-1] = temp
    return c


def is_stable(a, b):
    for i in range(len(a)):
        if a[i] != b[i]:
            print('Not stable')
            return
    print('Stable')


def main():
    n = int(input())
    nums = input().split(' ')
    bubble_nums = [i for i in nums]
    select_nums = [i for i in nums]
    bubble_nums = bubble_sort(bubble_nums, n)
    select_nums = selection_sort(select_nums, n)

    print(' '.join(bubble_nums))
    print('Stable')
    print(' '.join(select_nums))
    is_stable(bubble_nums, select_nums)


if __name__ == "__main__":
    main()

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

def bubble_sort(N, A):
  flag = 1
  sorted_index = 0
  while flag:
    flag = 0
    for i in range(N-1, sorted_index, -1):  
      if A[i][1] < A[i-1][1]:
        temp = A[i]
        A[i] = A[i-1]
        A[i-1] = temp
        flag = 1
    sorted_index += 1

def selection_sort(N, A):
  for i in range(0, N-1):
    minj = i
    for j in range(i+1, N):
      if A[j][1] < A[minj][1]:
        minj = j
    if i is not minj:
      temp = A[i]
      A[i] = A[minj]
      A[minj] = temp

bubble_sort(N, A)
selection_sort(N,A_copy)
print(' '.join(map(str, A)))
print('Stable')
print(' '.join(map(str, A_copy)))
if A == A_copy:
  print('Stable')
else:
  print('Not stable')

Solution (Python):
def sep(Nf, Mf):
    mm = [[] for _ in range(9)]
    for m in range(len(Nf)):
        for i in range(9):
            if Nf[m] == i+1:
                mm[i].append(Mf[m])
    return mm


def ssort(L, N, M):
    for i in range(len(N)-1):
        x = N[i+1:].index(min(N[i+1:])) + i + 1
        if N[i] > N[x]:
            L[i], L[x] = L[x], L[i]
            N[i], N[x] = N[x], N[i]
            M[i], M[x] = M[x], M[i]


def bsort(L, N, M):
    for i in range(len(N)-1):
        for j in range(len(N)-1-i):
            if N[j] > N[j+1]:
                L[j], L[j+1] = L[j+1], L[j]
                N[j], N[j+1] = N[j+1], N[j]
                M[j], M[j+1] = M[j+1], M[j]


n = int(input())
L = list(input().split())
N = [int(i[1]) for i in L]
M = [i[0] for i in L]
marks = ['S', 'H', 'C' ,'D']
Lb, Nb, Mb = L[:], N[:], M[:]
bsort(Lb, Nb, Mb)
print(' '.join(Lb))
if sep(N, M) == sep(Nb, Mb):
    print('Stable')
else:
    print('Not stable')

Ls, Ns, Ms = L[:], N[:], M[:]
ssort(Ls, Ns, Ms)
print(' '.join(Ls))
if sep(N, M) == sep(Ns, Ms):
    print('Stable')
else:
    print('Not stable')

Solution (Python):
def BSort(A,n):
    flag=1
    while flag:
        flag=0
        for i in range(n-1,0,-1):
            if A[i][1]<A[i-1][1]:
                A[i],A[i-1]=A[i-1],A[i]
                flag=1

def SSort(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]

n = int(input())

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

BSort(A,n)
print(' '.join(A))
print('Stable')
SSort(B,n)
print(' '.join(B))

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

Solution (Python):
def is_stable(A, B, n):
    for i in range(n):
        for j in range(i+1, n):
            if A[i]['value'] == A[j]['value']:
                for a in range(n):
                    for b in range(a+1, n):
                        if A[i] == B[b] and A[j] == B[a]:
                            return False
    return True


def show(Card, n):
    for i in range(n):
        if i != n-1:
            print(Card[i]['suit'] + str(Card[i]['value']), end=' ')
        else:
            print(Card[i]['suit'] + str(Card[i]['value']))


def bubble_sort(A, n):
    Card = A.copy()
    flag = 1
    while flag:
        flag = 0
        for i in range(n-1):
            if Card[i]['value'] > Card[i+1]['value']:
                Card[i], Card[i+1] = Card[i+1], Card[i]
                flag = 1
    show(Card, n)
    return Card


def selection_sort(A, n):
    Card = A.copy()
    for i in range(n-1):
        min_j = i
        for j in range(i+1, n):
            if Card[min_j]['value'] > Card[j]['value']:
                min_j = j
        if min_j != i:
            Card[i], Card[min_j] = Card[min_j], Card[i]
    show(Card, n)
    return Card


def main():
    n = int(input())
    A = list(input().split())
    Card = [
        {'value': int(a[1]), 'suit': a[0]}
        for a in A
    ]
    Card_bubble = bubble_sort(Card, n)
    if is_stable(Card, Card_bubble, n):
        print('Stable')
    else:
        print('Not stable')
    Card_selection = selection_sort(Card, n)
    if is_stable(Card, Card_selection, n):
        print('Stable')
    else:
        print('Not stable')


if __name__ == "__main__":
    main()

Solution (Python):
'''
5
H4 C9 S4 D2 C3
'''
N = int(input())
C1 = list(map(str, input().split()))
C2 = [None] * N

for i in range(N):
  C2[i] = C1[i]

def bubble(C, N):
  
  for i in range(0, N-1, 1):
    for j in range(N-1, i, -1):
      
      if (int(C[j-1][1]) > int(C[j][1])):
        C[j-1], C[j] = C[j], C[j-1]
        
        

  print(str(C).replace('[', '').replace(']', '').replace(',', '').replace('\'', ''))
  print("Stable") 

def selection(C, N):
  for i in range(N):
    minj = i
    for j in range(i+1, N):
      if (int(C[minj][1]) > int(C[j][1])):
        minj = j
    C[minj], C[i] = C[i], C[minj]

  print(str(C).replace('[', '').replace(']', '').replace(',', '').replace('\'', ''))

def main():
  bubble(C1, N)
  selection(C2, N)

  if (C1 == C2):
    print("Stable")
  else:
    print("Not stable")

main()

Solution (Python):
import sys
import copy

def print_data(data):
    last_index = len(data) - 1
    
    for idx, item in enumerate(data):
        print(item, end='')
        if idx != last_index:
            print(' ', end='')

    print('')

def bubbleSort(data, N):
    for i in range(N):
        j = N -1
        while j >= i+1:
            if data[j][1] < data[j-1][1]:
                hoge = data[j]
                data[j] = data[j-1]
                data[j-1] = hoge
            j -= 1
    return data

def selectSort(data, N):
    for i in range(N):
        mini = i
        for j in range(i, N):
            if data[j][1] < data[mini][1]:
                mini = j
        if i == mini:
            pass
        else:
            hoge = data[mini]
            data[mini] = data[i]
            data[i] = hoge
    
    return data

def isStable(inData, outData, N):
    for i in range(N):
        for j in range(i+1, N):
            if inData[i][1] == inData[j][1]:
                a = outData.index(inData[i])
                b = outData.index(inData[j])
                if a > b :
                    return False
    return True




def main():
    N = int(input())
    data0 = list(input().split())
    data1 = copy.deepcopy(data0)
    data2 = copy.deepcopy(data0)
    
    bubbleData = bubbleSort(data1, N)
    selectData = selectSort(data2, N)
    
    
                  
        
    print_data(bubbleData)
    if isStable(data0, bubbleData, N):
        print('Stable')
    else:
        print('Not stable')
    
        
    print_data(selectData)
    if isStable(data0, selectData, N):
        print('Stable')
    else:
        print('Not stable')

            
if __name__ == '__main__':
    main()

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

def SelectionSort(A):
    for i in range(len(A)):
        mini = i
        for j in range(i,len(A)):
            if A[j][1] < A[mini][1]:
                mini = j
        A[i],A[mini] = A[mini],A[i]
    return A


N = int(input())

array = [i for i in input().split()]
array_cp = list(array)

result_bs = BubbleSort(array)
print(*result_bs)
print('Stable') 

result_ss = SelectionSort(array_cp)
print(*result_ss)
if result_ss == result_bs:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
from copy import deepcopy
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
        C[i], C[minj] = C[minj], C[i]

N = int(input())
C = list(map(str, input().split()))
C1 = deepcopy(C)
C2 = deepcopy(C)
bubbleSort(C1, N)
selectionSort(C2, N)
O = [[] for _ in range(9)]
for i in range(N):
    j = int(C[i][1]) - 1
    O[j].append(C[i][0])
O1 = [[] for _ in range(9)]
for i in range(N):
    j = int(C1[i][1]) - 1
    O1[j].append(C1[i][0])
O2 = [[] for _ in range(9)]
for i in range(N):
    j = int(C2[i][1]) - 1
    O2[j].append(C2[i][0])
for i in range(N):
    if i == N - 1:
        print(C1[i])
    else:
        print(C1[i], end=' ')
if O == O1:
    print('Stable')
else:
    print('Not stable')
for i in range(N):
    if i == N - 1:
        print(C2[i])
    else:
        print(C2[i], end=' ')
if O == O2:
    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):
        if a[j][1]>a[j+1][1]:
            a[j],a[j+1] = a[j+1],a[j]
    minj = i
    for j in range(i,n):
        if b[minj][1]>b[j][1]:
            minj = j
    b[minj],b[i] = b[i],b[minj]        
print(*a)
print('Stable')
print(*b)
print(['Not s','S'][a==b] + 'table')

Solution (Python):
def bblsrt(cards):
    cards1 = cards.copy()
    for i in range(len(cards1)):
        for j in range(len(cards1) - 1, i, -1):
            if cards1[j][1] < cards1[j - 1][1]:
                cards1[j], cards1[j - 1] = cards1[j - 1], cards1[j]
    return cards1


def slcsrt(cards):
    cards2 = cards.copy()
    for i in range(len(cards2)):
        minj = i
        for j in range(i, len(cards2)):
            if cards2[j][1] < cards2[minj][1]:
                minj = j
        cards2[i], cards2[minj] = cards2[minj], cards2[i]
    return cards2


n = int(input())
C = list(input().split())
print(' '.join(bblsrt(C)))
print('Stable')
print(' '.join(slcsrt(C)))
print('Stable' if slcsrt(C) == bblsrt(C) else 'Not stable')

Solution (Python):
def val(a):
    return int(a[1:])


def bubble(lst,n):
    for i in range(n):
        for j in range(n-1,i,-1):
            if val(lst[j])<val(lst[j-1]):
                lst[j],lst[j-1]=lst[j-1],lst[j]
    return lst

def selection(lst,n):
    for i in range(n):
        minj=i
        for j in range(i,n):
            if val(lst[j])<val(lst[minj]):
                minj=j
        if i!=minj:
            lst[minj],lst[i]=lst[i],lst[minj]
    return lst

n=int(input())
lst=input().split()
lstc=lst[:]
blst=bubble(lstc,n)
lstc=lst[:]
slst=selection(lstc,n)


print(" ".join(blst))
print("Stable") 
print(" ".join(slst))
if slst==blst : print("Stable")
else : print("Not stable")

Solution (Python):
input()
C = [[x[0], x[1]] for x in list(input().split())]
D = C.copy()
N = len(C)


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


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


length = len(C)
for i in range(length):
    if i == length - 1:
        print("".join(C[i]), end="")
    else:
        print("".join(C[i]), end=" ")

print("")
print("Stable")


for i in range(length):
    if i == length - 1:
        print("".join(D[i]), end="")
    else:
        print("".join(D[i]), end=" ")

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

Solution (Python):
import copy

n = int(input())
A = list (map(str, input().split()))
B = copy.copy(A) 

def BubbleSort_dict(A, n):
    flag = 1    
    while flag:
        flag = 0
        for i in reversed(range(n-1)):
            if int(A[i][1]) > int(A[i+1][1]):
                a = A[i]
                A[i] = A[i+1]
                A[i+1] = a
                flag = 1
    return A
    
def SelectionSort_dict(A, n):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if int(A[j][1]) < int(A[minj][1]):
                minj = j
        if i != minj:
            a = A[i]
            A[i] = A[minj]
            A[minj] = a
    return A

A1 = BubbleSort_dict(A, n)
A2 = SelectionSort_dict(B, n)

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

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue

from decimal import Decimal
from collections import defaultdict, deque
import copy

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


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


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


def is_stable(bubble, selection):
    for b, s in zip(bubble, selection):
        if b != s:
            return False
    else:
        return True


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = sl()
    bubble_list = copy.copy(A)
    selection_list = copy.copy(A)

    bubble_sort(bubble_list, N)
    selection_sort(selection_list, N)
    print(*bubble_list)
    print('Stable')
    print(*selection_list)
    print('Stable' if is_stable(bubble_list, selection_list) else 'Not stable')


if __name__ == '__main__':
    main()

Solution (Python):
def bubbleSort(cards):
    for i, _ in enumerate(cards):
        for j in range(len(cards) -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 selectionSort(cards):
    for i in range(len(cards)):
        min_j = i
        for j in range(i, len(cards)):
            if int(cards[j][1]) < int(cards[min_j][1]):
                min_j = j
        cards[i], cards[min_j] = cards[min_j], cards[i]
    return cards
    
N = int(input())
A = input().split()

temp = A.copy()
bs = bubbleSort(temp)

temp = A.copy()
ss = selectionSort(temp)

print(' '.join(bs))
print('Stable')
print(' '.join(ss))
if [a[:1] for a in bs] == [a[:1] for a in ss]:
    print('Stable')
else:
    print('Not stable')