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 isStable(inlist, outlist):
	flag = True
	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 int(inlist[i][1:]) == int(inlist[j][1:]) and inlist[i] == outlist[b] and inlist[j] == outlist[a]:
						flag = False
						break
				else:
					continue
				break
			else:
				continue
			break
		else:
			continue
		break

	return(flag)
N = int(input())
A = input().split()
B = A[:]
C = A[:]

flag = 1
counter = 0
while flag:
    flag = 0
    for i in reversed(range(1,N)):
        if int(C[i][1:]) < int(C[i-1][1:]):
            C[i], C[i-1] = C[i-1], C[i]
            counter += 1
            flag = 1
print(" ".join(map(str, C)))

if(isStable(A, C)):
	print("Stable")
else:
	print("Not stable")

counter=0
for i in range(N):
	Br = B[i:]
	Brr = [int(Br[j][1:]) for j in range(N-i)]
	num = Brr.index(min(Brr)) 
	if num != 0:
		B[i], B[(i+num)] = B[(i+num)], B[i]
		counter += 1
print(" ".join(map(str,B)))
if(isStable(A, B)):
	print("Stable")
else:
	print("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
        
            
        A[i], A[minj] = A[minj], A[i]
        
    return A

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

    return A

N= int(input())
A = [str(x) for x in input().split()]
B = [0 for i in range(N)]
for i in range(N):
    B[i] = A[i]
bubble = BubbleSort(A, N)
selection = SelectionSort(B, N)


print(*bubble)
print('Stable')
print(*selection)
if bubble == selection:
    print('Stable')
else:
    print('Not stable')

Solution (Python):


A = int(input())
N = tuple(input().split())
bs=[]
ss=[]
def isStable(a,b):
    leng = int(len(a))
    for i in range(leng):
        for j in range(i+1,leng):
            for x in range(leng):
                for y in range(x+1,leng):
                    if a[i][1]==a[j][1] and a[i]==b[y] and a[j]==b[x]:
                        return "Not stable"
    return "Stable"
    
def bSort(n,a):
    n = list(n)
    for i in range(a):
        for j in range(a-1,i,-1):
            if int(n[j][1]) < int(n[j-1][1]):
                n[j],n[j-1]=n[j-1],n[j]
    return n
    

    
def seleSort(n,a):
    n = list(n)
    for i in range(a):
        minj = i
        for j in range(i+1,a):
            if n[j][1]<n[minj][1]:
                minj = j
                
        n[i],n[minj]=n[minj],n[i]
    return n
    

bs = bSort(N,A)
ss = seleSort(N,A)
print(" ".join(bs))
print(isStable(bs,bs))
print(" ".join(ss))
print(isStable(bs,ss))

Solution (Python):
N = int(input())
A = [ x for x in input().split(" ")]
orig_A = A[:]


for i in range(0, 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(*A)
print("Stable")



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


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

Solution (Python):
N, C = int(input()), [temp for temp in input().split()]
D    = list(C)

for i in range(N) :
    for j in range(i + 1, N)[ : : -1] :
        if int(C[j][1 :]) < int(C[j - 1][1 :]) :
            C[j], C[j - 1] = C[j - 1], C[j]
print(*C)
print('Stable')

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

cou = 0
for che in range(N) :
    if C[che] != D[che] :
        cou = 1
if cou == 0 : print('Stable')
else        : print('Not stable')

Solution (Python):
N = input()
A = map(str,raw_input().split())
Ab = A[:]
As = A[:]

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

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

def Output(A):
    for i in range(N-1):
        print A[i],
    print A[-1]

def Stable(AA):
    n = []
    for i in range(N-1):
        if AA[i][1] == AA[i+1][1] and AA[i][1] not in n:
            n.append(AA[i][1])
    l = []
    m = []
    for item in n:
        for i in range(N):
            if AA[i][1] == item:
                l.append(AA[i])
            if A[i][1] == item:
                m.append(A[i])
    if l == m:
        msg = "Stable"
    else:
        msg = "Not stable"
    print msg

SelectionSort(As,N)
BubbleSort(Ab,N)

Output(Ab)
Stable(Ab)
Output(As)
Stable(As)

Solution (Python):

import copy

def bubble_sort(card, N):
    for i in range(0, N):
        for j in range(N-1, i, -1):
            if value(card[j]) < value(card[j-1]):
                card[j], card[j-1] = card[j-1], card[j]
    return " ".join(map(str, card))


def selection_sort(card, N):
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if value(card[j]) < value(card[minj]):
                minj = j
        card[i], card[minj] = card[minj], card[i]
    return " ".join(map(str, card))




def insertion_sort(card, N):
    for i in range(1, N):
        v = card[i]
        j = i - 1
        while j >= 0 and value(card[j]) > value(v):
            card[j+1] = card[j]
            j -= 1
        card[j+1] = v
    return " ".join(map(str, card))


def value(elem):
    return elem[1]


def main():
    size = int(input())
    line = input().split()
    gold_standard = insertion_sort(copy.deepcopy(line), copy.deepcopy(size))

    bubble_ans = bubble_sort(copy.deepcopy(line), copy.deepcopy(size))
    print(bubble_ans)
    if bubble_ans == gold_standard:
        print('Stable')
    else:
        print('Not stable')

    selection_ans = selection_sort(copy.deepcopy(line), copy.deepcopy(size))
    print(selection_ans)
    if selection_ans == gold_standard:
        print('Stable')
    else:
        print('Not stable')


if __name__ == '__main__':
    main()

Solution (Python):
class Card:
    def __init__(self, suit, value):
        self.suit = suit
        self.value = value
    
def selection(ls):
    for i in range(len(ls)):
        minj = i
        
        for j in range(i, len(ls)):
            if ls[j].value < ls[minj].value:
                minj = j
        ls[i], ls[minj] = ls[minj], ls[i]

def bubblesort(ls):
    for i in range(1, len(ls)):
        for j in reversed(range(i, len(ls))):
            if ls[j].value < ls[j-1].value:
                ls[j], ls[j-1] = ls[j-1], ls[j]

def isStable(ls1, ls2):
    if ls1 == ls2:
        print("Stable")
    else:
        print("Not stable")

def printcards(cards):
    for x in range(len(cards)):
        if x == len(cards) - 1:
            print(cards[x].suit + cards[x].value)
        else:
            print(cards[x].suit + cards[x].value, ' ', sep='', end='')

def main():
    N = int(input().rstrip())

    cards = []
    for card in list(input().split(' ')):
        cards.append(Card(card[0], card[1]))

    a = [x for x in cards]
    b = [x for x in cards]
    

    bubblesort(a)
    selection(b)
    
    printcards(a)
    print("Stable")

    printcards(b)
    isStable(a,b)
    
if __name__ == '__main__':
    main()

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

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

def isStable(list_x, list_y):
    leng = int(len(list_x))
    for i in range(leng-1):
        for j in range(i+1, leng):
            for x in range(leng-1):
                for y in range(x+1, leng):
                    if list_x[i][1]==list_x[j][1] and list_x[i]==list_y[y] and list_x[j] == list_y[x]:
                        return "Not stable"
    return "Stable"


qnt = int(input())
num_list = input().split()

bs = bubble_sort(num_list)
ss = selection_sort(num_list)
print(" ".join(bs))
print(isStable(num_list,bs))
print(" ".join(ss))
print(isStable(num_list,ss))

Solution (Python):
def bubble_sort(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]):
				A[j], A[j-1] = A[j-1], A[j]
				flag = 1

		i += 1
	
	return A

def selection_sort(A, n):
	for i in range(n-1):
		minj = i
		for j in range(i, n):
			if int(A[j][1]) < int(A[minj][1]):
				minj = j

		if i != minj:
			A[i], A[minj] = A[minj], A[i]

	return A

def is_stable(A, B, 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 int(A[i][1]) == int(A[j][1]) and A[i] == B[b] and A[j] == B[a]:
						return False

	return True

def print_stable(flag):
	if flag:
		print('Stable')
	else:
		print('Not stable')

if __name__ == '__main__':
	n = int(input())
	A = list(input().split())
	A2 = A[:]

	B = bubble_sort(A, n)
	print(' '.join(B))
	print_stable(is_stable(A, B, n))

	B = selection_sort(A2, n)
	print(' '.join(B))
	print_stable(is_stable(A, B, n))

Solution (Python):
def bubble_sort(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]

	print(' '.join(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[i], A[minj] = A[minj], A[i]

	print(' '.join(A))

if __name__ == '__main__':
	n = int(input())
	A = list(input().split())
	B = A[:]

	bubble_sort(A, n)
	print('Stable')

	selection_sort(B, n)
	print('Stable' if A == B else 'Not stable')

Solution (Python):
def bubble_sort(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]

	print(' '.join(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

		A[i], A[minj] = A[minj], A[i]

	print(' '.join(A))

if __name__ == '__main__':
	n = int(input())
	A = list(input().split())
	B = A[:]

	bubble_sort(A, n)
	print('Stable')

	selection_sort(B, n)
	print('Stable' if A == B else 'Not stable')

Solution (Python):
def bubble_sort(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]

	print(' '.join(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

		A[i], A[minj] = A[minj], A[i]

	print(' '.join(A))

if __name__ == '__main__':
	n = int(input())
	A = list(input().split())
	B = A[:]

	bubble_sort(A, n)
	print('Stable')

	selection_sort(B, n)
	print('Stable' if A == B else 'Not stable')

Solution (Python):
def bubble_sort(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]

	print(' '.join(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

		A[i], A[minj] = A[minj], A[i]

	print(' '.join(A))

if __name__ == '__main__':
	n = int(input())
	A = list(input().split())
	B = A[:]

	bubble_sort(A, n)
	print('Stable')

	selection_sort(B, n)
	print('Stable' if A == B else 'Not stable')

Solution (Python):

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

def bubbleSort(A,N):
    c=0
    flag=1
    while flag:
        flag=0
        j=N-1
        while j>0:
            if(int(A[j][1])<int(A[j-1][1])):
                c+=1
                A[j],A[j-1]=A[j-1],A[j]
                flag=1
            j-=1
    return c

N=int(input())
A=input().split()
checkA=[""]*9
for i in range(N):
    checkA[int(A[i][1])-1]+=A[i][0]

B=[]+A
C=[]+A

bubbleSort(B,N)
checkB=[""]*9
for i in range(N):
    checkB[int(B[i][1])-1]+=B[i][0]
S=""
for i in range(N-1):
    S+=B[i]+" "
S+=str(B[-1])
print(S)
if(checkB==checkA):
    print("Stable")
else:
    print("Not stable")
    
selectionSort(C,N)
checkC=[""]*9
for i in range(N):
    checkC[int(C[i][1])-1]+=C[i][0]
S=""
for i in range(N-1):
    S+=C[i]+" "
S+=str(C[-1])
print(S)
if(checkC==checkA):
    print("Stable")
else:
    print("Not stable")

Solution (Python):
N = int(input())
A1 = list(map(str,input().split()))
A2 = A1[:]

def bubbleSort(A, N):
 flag = 0
 i = 0
 while flag == 0:
  flag = 1
  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]
    flag = 0
  i += 1
 return A

def selectSort(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 A[i][1] != A[minj][1]:
   A[i], A[minj] = A[minj], A[i]
 return A

def stable(Ab, As, N):
 for i in range(N):
  if Ab[i] != As[i]:
   return False
 return True

bubbleSort(A1, N)
selectSort(A2, N)
print(" ".join(map(str, A1)))
print("Stable")
print(" ".join(map(str, A2)))
if stable(A1, A2, N):
 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 print_list(X):
    first_flag = True
    for val in X:
        if first_flag:
            print_line = str(val)
            first_flag = False
        else:
            print_line = print_line + ' ' + str(val)
    print(print_line)

def combine_list(A_suit, A_rank, N):
    A_after = []
    for i in range(N):
        A_after.append(A_suit[i] + str(A_rank[i]))
    return A_after


def bubble_sort(A, index_list, N):
    
    
    flag = True
    i = 0
    while flag:
        flag = False
        for j in range(N-1, i, -1):
            if A[j] < A[j-1]:
                A[j-1], A[j] = A[j], A[j-1]
                index_list[j-1], index_list[j] = index_list[j], index_list[j-1]
                flag = True
        i += 1
    return A, index_list

def selection_sort(A, index_list, N):
    for i in range(N):
        min_j = i
        for j in range(i, N):
            if A[j] < A[min_j]:
                min_j = j
        if i != min_j:
            A[i], A[min_j] = A[min_j], A[i]
            index_list[i], index_list[min_j] = index_list[min_j], index_list[i]
    return A, index_list

def main():
    N = int(input())
    A = list(input().split())
    A_suit = []
    A_rank = []
    index_list = [x for x in range(N)]
    A_after_bubble = []
    A_after_selection = []

    for element in A:
        val = list(element)
        val_suit = val[0]
        val_rank = int(val[1])
        A_suit.append(val_suit)
        A_rank.append(val_rank)
    A_suit_after_bubble = [0 for x in range(N)]
    A_suit_after_selection = [0 for x in range(N)]

    A_rank_after_bubble, index_list_after_bubble = bubble_sort(A_rank.copy(), index_list.copy(), N)
    A_rank_after_selection, index_list_after_selection = selection_sort(A_rank.copy(), index_list.copy(), N)

    for index_before, index_after in enumerate(index_list_after_bubble):
        A_suit_after_bubble[index_before] = A_suit[index_after]

    for index_before, index_after in enumerate(index_list_after_selection):
        A_suit_after_selection[index_before] = A_suit[index_after]

    A_after_bubble = combine_list(A_suit_after_bubble, A_rank_after_bubble, N)
    A_after_selection = combine_list(A_suit_after_selection, A_rank_after_selection, N)

    print_list(A_after_bubble)
    print("Stable")
    print_list(A_after_selection)
    if A_after_selection == A_after_bubble:
        print("Stable")
    else:
        print("Not stable")



if __name__ == '__main__':
    main()

Solution (Python):
from operator import lt

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

    Ab = bubbleSort(A[:], N, lambda a, b: int(a[1]) < int(b[1]))
    As = selectionSort(A[:], N, lambda a, b: int(a[1]) < int(b[1]))

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

    print(' '.join([str(a) for a in As]))
    print('Stable' if Ab == As else 'Not stable')

def bubbleSort(A, N, comp=lt):
    flag = True

    while flag:
        flag = False

        for j in range(N-1, 0, -1):
            if comp(A[j], A[j-1]):
                A[j], A[j-1] = A[j-1], A[j]
                flag = True

    return A

def selectionSort(A, N, comp=lt):
    for i in range(0, N-1):
        minj = i

        for j in range(i, N):
            if comp(A[j], A[minj]):
                minj = j

        if i != minj:
            A[i], A[minj] = A[minj], A[i]

    return A

if __name__ == '__main__':
    main()

Solution (Python):
def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def rls(): return list(map(str, input().split()))
def pl(a): print(" ".join(list(map(str, a))))


N = ri()
a = rls()
bubble = a[:]

flag = True
while(flag):
    flag = False
    for i in range(1, N):
        if(bubble[-i][1] < bubble[-i-1][1]):
            hold = bubble[-i]
            bubble[-i] = bubble[-i-1]
            bubble[-i-1] = hold
            flag = True
pl(bubble)
print("Stable")  

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

pl(selection)
print("Stable" if bubble == selection else "Not stable")

Solution (Python):
def buble(lst):

    src_list = list(lst)
    flag=True
    while flag:
        flag = False
        for idx in range(len(lst)-1, 0, -1):
            if int(lst[idx][1]) < int(lst[idx-1][1]):
                tmp=lst[idx]
                lst[idx]=lst[idx-1]
                lst[idx-1]=tmp
                flag=True

    flag_stable = True
    for num in range(0, 9):
        tmp1 = []
        tmp2 = []
        for i in range(0, len(lst)):
            if int(lst[i][1]) == num:
                tmp1.append(lst[i])
            if int(src_list[i][1]) == num:
                tmp2.append(src_list[i])

        if tmp1 != tmp2:
           flag_stable = False
           break
    print " ".join(lst)

    if flag_stable:
        print "Stable"
    else:
        print "Not stable"

def selection(lst):

    src_list = list(lst)
    for i in range(len(lst)):
        m = i
        for j in range(i,len(lst)):
            if int(lst[m][1]) > int(lst[j][1]):
                m=j
        tmp=lst[i]
        lst[i]=lst[m]
        lst[m]=tmp

    flag_stable = True
    for num in range(0, 9):
        tmp1 = []
        tmp2 = []
        for i in range(0, len(lst)):
            if int(lst[i][1]) == num:
                tmp1.append(lst[i])
            if int(src_list[i][1]) == num:
                tmp2.append(src_list[i])

        if tmp1 != tmp2:
           flag_stable = False
           break

    print " ".join(lst)
    if flag_stable:
        print "Stable"
    else:
        print "Not stable"


n=raw_input()
lst1 = raw_input().split()
lst2 = list(lst1)

buble(lst1)
selection(lst2)

Solution (Python):
class Cards:
    def __init__(self,shape,value):
        self.shape = shape
        self.value = value

n = int(input())
s = input().split(" ")
cards1 = []
for i in range(n):
    cards1.append(Cards(s[i][0],int(s[i][1])))
cards2 = list(cards1)
for i in range(n):
    for j in range(n-1,i,-1):
        if cards1[j].value < cards1[j-1].value:
            w = cards1[j]
            cards1[j] = cards1[j-1]
            cards1[j-1] = w
for i in range(n):
    if i == n-1:
        print("{0}{1}".format(cards1[i].shape,cards1[i].value))
    else:
        print("{0}{1}".format(cards1[i].shape,cards1[i].value),end=" ")
print("Stable")

for i in range(n):
    minj = i
    for j in range(i+1,n):
        if cards2[j].value < cards2[minj].value:
            minj = j
    w = cards2[i]
    cards2[i] = cards2[minj]
    cards2[minj] = w
for i in range(n):
    if i == n-1:
        print("{0}{1}".format(cards2[i].shape,cards2[i].value))
    else:
        print("{0}{1}".format(cards2[i].shape,cards2[i].value),end=" ")
for i in range(n):
    if cards1[i].shape != cards2[i].shape:
        print("Not stable")
        break
    if i == n-1:
        print("Stable")

Solution (Python):

"""
Created on Sun Jun 18 10:01:05 2017

@author: syaga
"""

if __name__ == "__main__":
    N = int(input())
    C = list(input().split())
    D = C[:]

    
    for i in range(0, 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
    print(" ".join(C))
    print("Stable")

    
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if int(D[j][1]) < int(D[minj][1]):
                minj = j
        temp = D[i]
        D[i] = D[minj]
        D[minj] = temp
    print(" ".join(D))
    flag = 0
    for (i, j) in zip(C, D):
        if i != j:
            flag = 1
            break
    if flag == 1:
        print("Not stable")
    else:
        print("Stable")

Solution (Python):
N = int(input())
a = [(s[0], int(s[1])) for s in input().split()]

def bubble(a):
    n = len(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]
    return a

def selection(a):
    n = len(a)
    for i in range(n):
        minj = i
        for j in range(i+1, n):
            if a[j][1] < a[minj][1]:
                minj = j
        a[i], a[minj] = a[minj], a[i]

    return a

b_a = bubble(a[:])
s_a = selection(a[:])

print(" ".join([p[0]+str(p[1]) for p in b_a]))
print("Stable")
print(" ".join([p[0]+str(p[1]) for p in s_a]))
print("Stable" if b_a==s_a else "Not stable")

Solution (Python):
import copy

n = int(input())
a = input().split()
b = copy.deepcopy(a)

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

ra = " ".join(a)

print(ra)
print("Stable")

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

rb = " ".join(b)
print(rb)

if ra == rb:
    print("Stable")
else:
    print("Not stable")

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

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

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

    A_bubble = bubble(A[:], N)
    print (*A_bubble)
    print ("Stable")

    A_selection = selection(A[:], N)
    print (*A_selection)
    if A_bubble == A_selection:
        print ("Stable")
    else:
        print ("Not stable")

Solution (Python):

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

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

def CompareSuit(L1, L2):
    suit1, suit2 = "", ""
    for i in range(len(L1)):
        suit1 = suit1 + L1[i]
        suit2 = suit2 + L2[i]
    if suit1 == suit2:
        return "Stable"
    else:
        return "Not stable"

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

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

print(" ".join(C1))
print(CompareSuit(C1, C1))
print(" ".join(C2))
print(CompareSuit(C1, C2))

Solution (Python):
N=int(input())
A=input().split()

B=A[:]
S=A[:]

def BubbleSort(A, N):
    count = 0
    flag = True
    while flag:
        flag = False
        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]
                count += 1
                flag = True
                
    return A

def SelectionSort(A, N):
    count = 0
    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] 
        count += 1
    return A

b = BubbleSort(B, N)
s = SelectionSort(S, N)
print(*b)
print("Stable")
print(*s)

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

Solution (Python):
import sys

class Card:
    def __init__(self, kind, num):
        self.kind = kind
        self.num = num
    def __eq__(self, other):
        return (self.kind == other.kind) and (self.num == other.num)
    def __ne__(self, other):
        return not ((self.kind == other.kind) and (self.num == other.num))
    def __str__(self):
        return self.kind + self.num

def list_to_string(array):
    s = ""
    for n in array:
        s += str(n) + " "
    return s.strip()
    
def swap(array, i, j):
    tmp = array[i]
    array[i] = array[j]
    array[j] = tmp

def is_stable(array1, array2):
    if reduce(lambda x, y: x and y, map(lambda x: x[0] == x[1], zip(array1, array2))):
        return "Stable"
    else:
        return "Not stable"

def bubble_sort(array):
    for i in range(0, len(array)):
        for j in reversed(range(i+1, len(array))):
            if array[j].num < array[j-1].num:
                swap(array, j, j-1)
    return array
        
def selection_sort(array):
    for i in range(0, len(array)):
        min_index = i
        for j in range(i, len(array)):
            if array[min_index].num > array[j].num:
                min_index = j
        swap(array, i, min_index)
    return array

def main():
    num = int(sys.stdin.readline().strip())
    array = map(lambda x: Card(x[0], x[1]), sys.stdin.readline().strip().split(" "))

    a = list(array)
    b = list(array)

    print list_to_string(bubble_sort(a))
    print "Stable"
    print list_to_string(selection_sort(b))
    print is_stable(a, b)

if __name__ == "__main__":
    main()

Solution (Python):
def print_list(array, N):
    for i in range(N):
        if i == N-1:
            print(array[i])
        else:
            print(array[i], end=" ")
            
def stable_sort(array_a, array, N):
    for i in range(N-1):
        stable = "yes"
        if array[i][1] == array[i+1][1]:
            index_1 = array.index(array[i])
            index_2 = array.index(array[i+1])
            index_a1 = array_a.index(array[i])
            index_a2 = array_a.index(array[i+1])
            
            if not(index_1 < index_2\
            and index_a1 < index_a2):
                stable = "no"
                break
    if stable == "yes":
        print("Stable")
    else:
        print("Not stable")
            
N = int(input())
a = input().split()
b = [s for s in a]
for i in range(N-1):
    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
print_list(b, N)
stable_sort(a, b, N)

c = [s for s in a]
for i in range(N-1):
    min_i = c[i][1]
    change = "no"
    for j in range(i+1, N):
        if min_i > c[j][1]:
            min_i = c[j][1]
            index = c.index(c[j])
            change = "ok"
    if change == "ok":
        t = c[i]
        c[i] = c[index]
        c[index] = t
print_list(c, N)
stable_sort(a, c, N)