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

Solution (Python):
import copy
n = int(input())
inp = []
inp = input().split()

class card:
    def __init__(self, suitin, numin):
        self.suit = suitin
        self.num = numin

a = []
for i in range(n):
    a.append(card(inp[i][0], inp[i][1]))

bubble = copy.deepcopy(a)

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

print(bubble[0].suit, end="")
print(bubble[0].num, end="")

for i in range(1, len(bubble)):
    print(" ", end="")
    print(bubble[i].suit, end="")
    print(bubble[i].num, end="")
print("\n", end="")
print("Stable")

select = copy.deepcopy(a)

for i in range(n):
    minj = i
    for j in range(i, n):
        if select[j].num < select[minj].num:
            minj = j
   
    select[i], select[minj] = select[minj], select[i]


print(select[0].suit, end="")
print(select[0].num, end="")

for i in range(1, len(select)):
    print(" ", end="")
    print(select[i].suit, end="")
    print(select[i].num, end="")
print("\n", end="")

flag = 1
for i in range(n):
    if bubble[i].suit != select[i].suit:
        flag = 0

if flag == 1:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
import copy
def bubbleSort(B, N):
    stable = True
    flag = 1
    while flag:
        flag = 0
        for j in range(N-1, 0, -1):
            if B[j][1] < B[j-1][1]:
                if B[j][1] == B[j-1][1] and j != j-1:
                    stable = False

                B[j-1], B[j] = B[j], B[j-1]
                flag = 1

    return B

def selectionSort(S, N):
    stable = True
    for i in range(N):
        minj = i
        for j in range(i,N):
            if S[j][1] < S[minj][1]:
                minj = j
        if S[i][1] == S[minj][1] and i != minj:
            stable = False

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

    return S

N = int(input())
A = list(input().split())
B = A.copy()

out_A = selectionSort(A,N)
out_B = bubbleSort(B,N)

print(" ".join(out_B))
print("Stable")

print(" ".join(out_A))
if out_A == out_B:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
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:]):
                c[j],c[j-1] = c[j-1],c[j]
    return c

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

import copy
n = int(input())
c = input().split()
bc = bubble_sort(copy.deepcopy(c), n)
sc = selection_sort(copy.deepcopy(c), n)
print(*bc)
print("Stable")
print(*sc)
print("Stable" if sc == bc else "Not stable")

Solution (Python):
N = int(input())
A = input().split()
A_b = [e for e in A]
A_s = [e for e in A]




flag = True
left = 0

while flag:
    flag = False
    for i in range(N-1, left, -1):
        if int(A_b[i][1]) < int(A_b[i-1][1]):
            A_b[i], A_b[i-1] = A_b[i-1], A_b[i]
            flag = True
    left += 1
print(" ".join(A_b))
print("Stable")




for i in range(N):
    minj = i
    for j in range(i, N):
        if int(A_s[j][1]) < int(A_s[minj][1]):
            minj = j
    if minj != i:
        A_s[i], A_s[minj] = A_s[minj], A_s[i]
print(" ".join(A_s))

is_same = True
for i in range(N):
    if A_s[i] != A_b[i]:
        is_same = False
        break
if is_same:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
n = int(input())
a1 = list(input().split())
a2 = a1[:]
for i in range(0, n):
    for j in range(1, n-i):
        if int(a2[j][1])<int(a2[j-1][1]):
            a2[j], a2[j-1] = a2[j-1], a2[j]
print (*a2)
print ("Stable")

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

Solution (Python):
import copy
def bubble_sort(nums,n):
    flag=1
    while flag:
        flag=0
        for i in range(n-1,0,-1):
            if int(nums[i][1])<int(nums[i-1][1]):
                flag=1
                nums[i],nums[i-1]=nums[i-1],nums[i]

    return nums

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

    return nums

n=int(input())
nums=list(input().split())
nums_2=copy.deepcopy(nums)
b_nums=bubble_sort(nums,n)
s_nums=selection_sort(nums_2,n)

def show(nums):
    for i in range(len(nums)):
        if i!=len(nums)-1:
            print(nums[i],end=' ')

        else:
            print(nums[i])

show(b_nums)
print("Stable")
show(s_nums)
if b_nums==s_nums:
    print("Stable")

else:
    print("Not stable")

Solution (Python):


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

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

def stable_check(check_dic, ans_list):
    is_ok = True
    for a in ans_list:
        v = a[0]
        k = a[1]
        if check_dic[k][0]==v:
            check_dic[k].pop(0)
        else:
            is_ok = False
    return is_ok


N = int(input())
cards = input().split()
check_dic = {}
check_dic_2 = {}
cards_1 = ['']*N
cards_2 = ['']*N
for i in range(N):
    
    c_list = list(cards[i])
    if not c_list[1] in check_dic:
        check_dic[c_list[1]] = [c_list[0]]
        check_dic_2[c_list[1]] = [c_list[0]]
    else:
        check_dic[c_list[1]].append(c_list[0])
        check_dic_2[c_list[1]].append(c_list[0])
    cards_1[i] = cards[i]
    cards_2[i] = cards[i]


ans = bubble_sort(cards_1, N)
is_stable = stable_check(check_dic, ans)
print(" ".join(list(map(str, ans))))
if is_stable:
    print("Stable")
else:
    print("Not stable")


ans = selection_sort(cards_2, N)
is_stable = stable_check(check_dic_2, ans)
print(" ".join(list(map(str, ans))))
if is_stable:
    print("Stable")
else:
    print("Not stable")

Solution (Python):


n = int(input())
C = list(input().split(' '))

C1, C2 = [], []
for v in C:
	tmp = v[0]
	num = int(v[1])
	C1.append([tmp, num])
	C2.append([tmp, num])

def bubble(A):
	n = len(A)
	for i in range(n):
		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]
	return 0

def selection(A):
	n = len(A)
	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 0

def is_Stable(C1, C2):
	
	n = len(C1)
	for i in range(n):
		if C1[i][0] != C2[i][0]:
			return False
	return True

def pprint(A):
	res = []
	for v in A:
		tmp1 = v[0]
		tmp2 = str(v[1])
		res.append(tmp1 + tmp2)
	print(*res)
	return
	
bubble(C1)
selection(C2)

pprint(C1)
print('Stable')
pprint(C2)
print('Stable') if is_Stable(C1, C2) else print('Not stable')

Solution (Python):
N = int(input())
A = input().split()
A1 = [a for a in A]
A2 = [a for a in A]


flag = True
i = 0
while flag:
    flag = False
    for j in range(1, N - i):
        if int(A1[j][1]) < int(A1[j - 1][1]):
            A1[j - 1], A1[j] = A1[j], A1[j  -1]
            flag = True
    i += 1

print(*A1)
print('Stable')


for i in range(N - 1):
    mni = i
    for j in range(i + 1, N):
        if int(A2[j][1]) < int(A2[mni][1]):
            mni = j
    if mni != i:
        A2[i], A2[mni] = A2[mni], A2[i]

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

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

def selectSort(arr):
    for i in range(len(arr)):
        Min = i
        for j in range(i, len(arr)):
            if arr[j][1] < arr[Min][1]:
                Min = j
        if i != Min:
            arr[i], arr[Min] = arr[Min], arr[i]

n = int(input())
arr = list(map(str, input().split()))
arr1 = arr[:]
bubbeSort(arr)
selectSort(arr1)
print(*arr)
print("Stable")
print(*arr1)
print(["Not stable", "Stable"][arr == arr1])

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

def selection_sort(A):
    N=len(A)
    for i in range(N-1):
        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

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

bub=bubble_sort(A[:])
sel=selection_sort(A)
msg="Stable"

for i in range(N):
    if bub[i]!=sel[i]:
        msg="Not stable"

print(*bub)
print("Stable")
print(*sel)
print(msg)

Solution (Python):
import copy
def BubbleSort(d,N):
    for i in range(0,N):
        for j in range(i+1,N)[::-1]:
            if d[j][1] < d[j-1][1]:
                t=d[j]
                d[j]=d[j-1]
                d[j-1]=t 
    return d

def selectionSort(d,N):
    c1 = 0
    for i in range(0,N):
        minj = i    
        for j in range(i,N):
            if d[j][1] < d[minj][1]:
                minj = j
        if(i!=minj):
            t = d[i]
            d[i] = d[minj]
            d[minj] = t
            c1+=1     
    return d           

if __name__=="__main__":
    n = int(input())
    l = [i for i in input().split()]
    l2=copy.deepcopy(l)
    print(' '.join(BubbleSort(l,n)))
    print('Stable')
    print(' '.join(selectionSort(l2,n)))
    if l != l2:
        print('Not stable')
    else:
        print('Stable')

Solution (Python):
n = int(input())
cards = list(input().split())
cardb = cards.copy()
cards = cards.copy()

for i in range(n-1):
    for j in range(n-1,i,-1):
        if int(cardb[j].strip('S''H''C''D')) < int(cardb[j-1].strip('S''H''C''D')):
            cardb[j],cardb[j-1] = cardb[j-1],cardb[j]
for i in range(n):
    if i != n-1:
        print(cardb[i], end=' ')
    else:
        print(cardb[i])
print('Stable')

for i in range(n-1):
    
    minj = i
    for j in range(i+1,n):
        if int(cards[j].strip('S''H''C''D')) < int(cards[minj].strip('S''H''C''D')):
            minj = j
    if i != minj:
        cards[i],cards[minj] = cards[minj],cards[i]
for i in range(n):
    if i != n-1:
        print(cards[i], end=' ')
    else:
        print(cards[i])

judge = True
for i in range(n):
    if cardb[i] != cards[i]:
        judge = False
if judge == True:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
import copy

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

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

n = int(input())
c = input().split()
c2 = copy.copy(c)

bubble(c,n)
selection(c2,n)
print(" ".join(c))
print("Stable")
print(" ".join(c2))
if c==c2:
    print("Stable")
else:
    print("Not stable")

Solution (Python):

import sys
import math
import bisect
import copy
sys.setrecursionlimit(1000000)
from collections import deque

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

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

def main():
    n = int(input())
    a = list(input().split())
    b = copy.copy(a)
    bubble(a,n)
    selection(b,n)
    print (' '.join(a))
    print ('Stable')
    print (' '.join(b))
    if a==b:print ('Stable')
    else   :print ('Not stable')



if __name__ == '__main__':
    main()

Solution (Python):
def bubble_sort(c, n):
    for i in range(n):
        for j in reversed(range(i+1, n)):
            if c[j][1] < c[j-1][1]:
                c[j], c[j-1] = c[j-1], c[j]
    print(' '.join(map(str, c)))


def selection_sort(c, n):
    for i in range(n):
        m = i
        for j in range(i, n):
            if c[j][1] < c[m][1]:
                m = j
        c[i], c[m] = c[m], c[i]
    print(' '.join(map(str, c)))


n = int(input())
c = list(input().split())
b = list(c)
bubble_sort(c, n)
print('Stable')
selection_sort(b, n)
if c == b:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
import copy


def group(arr):
    r = {}
    for a in arr:
        if r.get(a[1]):
            r[a[1]] += a[0]
        else:
            r[a[1]] = a[0]

    return r


n = int(input())
A = list(input().split(' '))
_A = copy.deepcopy(A)

for _ in range(n - 1):
    for i in range(1, n)[::-1]:
        if A[i - 1][1] > A[i][1]:
            A[i - 1], A[i] = A[i], A[i - 1]
print(*A)
print('Stable')

A = copy.deepcopy(_A)

for i in range(n - 1):
    minv_idx = i
    for k in range(i + 1, n):
        if A[minv_idx][1] > A[k][1]:
            minv_idx = k
    if i != minv_idx:
        A[i], A[minv_idx] = A[minv_idx], A[i]

print(*A)
if group(A) == group(_A):
    print('Stable')
else:
    print('Not stable')

Solution (Python):
def bubblesort(c, n):
    for i in range(0, 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(0, n):
        min_j = i
        for j in range(i, 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


n = int(input())
c_to_bubble = list(map(str, input().split()))
c_to_selection = c_to_bubble.copy()

bubblesorted = bubblesort(c_to_bubble, n)
selectionsorted = selectionsort(c_to_selection, n)

print(' '.join(bubblesorted))
print('Stable')
print(' '.join(selectionsorted))
if bubblesorted == selectionsorted:
    print('Stable')
else:
    print('Not stable')

Solution (Python):


import copy

n = int(input())
l1 = list(map(str, input().split()))
l2 = copy.deepcopy(l1)

flag = 1
while flag:
    flag = 0
    for i in reversed(range(1, n)):
        if l1[i][-1] < l1[i - 1][-1]:
            l1[i], l1[i - 1] = l1[i - 1], l1[i]
            flag = 1
print(' '.join(map(str, l1)))
print('Stable')

for i in range(n):
    minj = i + l2[i:].index(min(l2[i:], key = lambda x : x[-1]))
    if minj != i:
        l2[i], l2[minj] = l2[minj], l2[i]
print(' '.join(map(str, l2)))
print('Stable' if l1 == l2 else 'Not stable')

Solution (Python):

import copy


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


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


class Card:
    value = 0
    x = ""

    def __init__(self, x):
        self.x = x
        self.value = int(x[1])


N = int(input())
C = list(map(lambda x: Card(x), input().split(" ")))

c1 = copy.copy(C)
c2 = copy.copy(C)

BubbleSort(c1, N)
SelectionSort(c2, N)
print(" ".join([x.x for x in c1]))
print("Stable")
print(" ".join([x.x for x in c2]))
isStable = True
for i in range(0, N):
    if c1[i] != c2[i]:
        isStable = False
        break
if isStable:
    print("Stable")
else:
    print("Not stable")

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

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

B = deepcopy(A)
S = deepcopy(A)


def p(N):
    for i in range(len(N)):
        if i == len(N) - 1:
            print(N[i])
        else:
            print(N[i], end=" ")


def bubblesort(n):
    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]

    p(B)
    print("Stable")


def sellectionsort(n):
    for i in range(N):
        m = i
        for j in range(i + 1, N):
            if S[j][1] < S[m][1]:
                m = j
        S[m], S[i] = S[i], S[m]

    p(S)

    flag = True
    for i in range(N):
        if B[i] != S[i]:
            flag = False

    if flag:
        print("Stable")
    else:
        print("Not stable")


bubblesort(N)
sellectionsort(N)

Solution (Python):
N = int(input())
card = list(input().split())

card_buble = card.copy()
card_select = card.copy()


flag = 1
i = 0
count = 0
while flag==1:
    flag = 0
    for j in range(i+1,len(card_buble))[::-1]:
        if int(card_buble[j][-1]) < int(card_buble[j-1][-1]):
            temp  = card_buble[j]
            card_buble[j] = card_buble[j-1]
            card_buble[j-1] = temp
            flag = 1
    i += 1



for i in range(0,len(card_select)):
    mini = i
    for j in range(i,len(card_select)):
        if int(card_select[j][-1]) < int(card_select[mini][-1]):
            mini = j
    temp = card_select[i]
    card_select[i] = card_select[mini]
    card_select[mini] = temp

print(" ".join(card_buble))
print("Stable")

print(" ".join(card_select))
if card_select == card_buble: print("Stable")
else: print("Not stable")

Solution (Python):
N = int(input())
lst = list(input().split())
lst2 = []
for i in lst:
    lst2.append(i)

def bubble_sort(lst):

    flag = 1
    while flag:
        flag = 0
        for i in reversed(list(range(1,len(lst)))):
            if int(lst[i-1][1])>int(lst[i][1]):
                lst[i-1],lst[i] = lst[i],lst[i-1]
                flag = 1

    return lst

def selection_sort(lst):


    for i in range(len(lst)):
        min_i = i
        for j in range(i+1,len(lst)):
            if int(lst[j][1]) < int(lst[min_i][1]):
                min_i = j
        lst[i],lst[min_i] = lst[min_i],lst[i]

    return lst

list1 = bubble_sort(lst)
list2 = selection_sort(lst2)

print(' '.join(map(str,list1)))
print("Stable")
print(' '.join(map(str,list2)))
if list1 == list2:
    print("Stable")
else:
    print("Not stable")

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


def print_stable(original_list, sorted_list):
    for n in range(1, 10):
        original_list_n = filter(lambda card: int(card[1]) == n, original_list)
        sorted_list_n = filter(lambda card: int(card[1]) == n, sorted_list)
        is_same = all(map(lambda c: c[0] == c[1], zip(original_list_n, sorted_list_n)))
        if not is_same:
            print('Not stable')
            return
    print('Stable')


def print_list(l):
    print(' '.join(map(str, l)))


def bubble_sort(l):
    swapped = True
    while swapped:
        swapped = False
        for i in range(n - 1, 0, -1):
            if l[i][1] < l[i - 1][1]:
                l[i], l[i - 1] = l[i - 1], l[i]
                swapped = True
    return l


def selection_sort(l):
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if l[j][1] < l[min_index][1]:
                min_index = j
        l[i], l[min_index] = l[min_index], l[i]
    return l


bubble_list = bubble_sort(cards[:])
print_list(bubble_list)
print_stable(cards, bubble_list)

selection_list = selection_sort(cards[:])
print_list(selection_list)
print_stable(cards, selection_list)

Solution (Python):
N=int(input())
tmp = input().split()
A=[0]*N
ind=[0]*N
for i in range(N):
    card=tmp[i]
    A[i]=int(card[1])
    ind[i]=i

def BubbleSort(A,N):
    A_bubble=A[:]
    ind_bubble=ind[:]
    flag=1
    while flag:
        flag=0
        j=0
        for i in range(N-1-j):
            if A_bubble[i] > A_bubble[i+1]:
                a=A_bubble[i]
                A_bubble[i]=A_bubble[i+1]
                A_bubble[i+1]=a
                flag=1
                a=ind_bubble[i]
                ind_bubble[i]=ind_bubble[i+1]
                ind_bubble[i+1]=a
    return ind_bubble


def SelectionSort(A,N):
    A_selection=A[:]
    ind_selection=ind[:]
    for i in range(N):
        mini=i
        for j in range(i+1,N):
            if A_selection[j] < A_selection[mini]:
                mini=j
        if mini != i:
            a=A_selection[i]
            A_selection[i]=A_selection[mini]
            A_selection[mini]=a
            a=ind_selection[i]
            ind_selection[i]=ind_selection[mini]
            ind_selection[mini]=a
    return ind_selection


i_b=BubbleSort(A,N)
i_s=SelectionSort(A,N)
ans_b=[]
ans_s=[]
for i in range(N):
    ans_b.append("".join([tmp[i_b[i]][0],tmp[i_b[i]][1]]))
    ans_s.append("".join([tmp[i_s[i]][0],tmp[i_s[i]][1]]))

print(*ans_b)
print("Stable")
print(*ans_s)
if ans_b != ans_s:
    print("Not stable")
else:
    print("Stable")

Solution (Python):
def BobbleSort(C, N):
    flag = True
    while flag:
        flag = False
        for i in range(N-1,0,-1):
            if C[i-1][1] > C[i][1]:
                C[i-1], C[i] = C[i], C[i-1]
                flag = True
    return C

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

def Stable(C1, C2, N):
    
    flag = True
    
    
    for i in range(1, N):
        if C2[i-1][1] == C2[i][1]:
            a = C1.index(C2[i-1])
            b = C1.index(C2[i])
            if a > b:
                flag = False
                break
    
    if flag:
        print("Stable")
    else:
        print("Not stable")
    
N = int(input())
orgC = [x for x in input().split()]
C = orgC.copy()

BobbleSort(C,N)
print(" ".join(C))
Stable(orgC, C, N)

C = orgC.copy()
SelectionSort(C,N)
print(" ".join(C))
Stable(orgC, C, N)

Solution (Python):

from copy import deepcopy

def bubblesort(C,N):
    A = deepcopy(C)
    for i in range(N):
        for j in reversed(range(i+1,N)):
            if int(A[j][1]) < int(A[j-1][1]):
                A[j],A[j-1] = A[j-1],A[j]
    return A

def selectionsort(C,N):
    A = deepcopy(C)
    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 main():
    N = int(input())
    C = list(input().split())
    bs = bubblesort(C,N)
    print(*bs)
    print("Stable")
    ss = selectionsort(C,N)
    print(*ss)
    if bs == ss:
        print("Stable")
    else:
        print("Not stable")

if __name__ == "__main__":
    main()

Solution (Python):
import copy 
n = int(input())


*L, = input().split()

A1 = copy.copy(L)
A2 = copy.copy(L)

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

"""
for i in range(N):
	for j in reversed(range(i+1,N)):
		if int(A[j][1]) < int(A[j-1][1]):
			key = A
			A[j] = A[j][0] + A[j-1][1]
			A[j-1] = key[j-1][0] + key[j][1]
			print(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 A[i][1] > A[minj][1]:
			key = A[i]
			A[i] = A[minj]
			A[minj] = key
			

"""
def isStable(input,output):
	for i in range(len(inp)):
		if inp[i][1] == oup[i][1] and inp[i][0] != oup[i][0]:
			
			return False
		else:
			True
"""



"""
if inp[i][1] == oup[i][1] and inp[i][0] != oup[i][0]:
	print("False")

print(inp[i][1])
print(oup[i][1])
print(inp[i][0])
print(oup[i][0])
"""

bubble_sort(A1,n)
selection_sort(A2,n)

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

Solution (Python):
def bubbleSort(matrix, N):
  for i in range(N):
    for j in reversed(range(i+1, N)):
      if matrix[j][1] < matrix[j-1][1]:
        matrix[j], matrix[j-1] = matrix[j-1], matrix[j]

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

def printList(matrix, N):
  matrix_cards = []
  for i in range(N):
    matrix_cards.append(matrix[i][0])
  print(" ".join(map(str, matrix_cards)))

n = int(input())
A = list(input().split())
B = [[] for i in range(n)]
C = [[] for i in range(n)]

for i in range(n):
  A[i] = [A[i], int(A[i][1:])]
  B[i] = A[i]
  C[i] = A[i]

bubbleSort(B, n)
selectionSort(C, n)

printList(B,n)
print("Stable")

printList(C,n)
if B == C:
  print("Stable")
else:
  print("Not stable")

Solution (Python):
def isStable(in_lst,out_lst):
    for i in range(n):
        for j in range(i+1,n):
            for a in range(n):
                for b in range(a+1,n):
                    if in_lst[i][1] == in_lst[j][1] and in_lst[i] == out_lst[b] and in_lst[j] == out_lst[a]:
                        return False
    return True

def isStable1(in_lst,out_lst):
    tmp = isStable(in_lst,out_lst)
    if tmp == True:
        print('Stable')
    else:
        print('Not stable')

n = int(input())
lst = list(map(str,input().split()))
ans_lst = lst.copy()
for i in range(0,n):
    for j in range(n-1,i,-1):
        if lst[j][1] < lst[j-1][1]:
            lst[j],lst[j-1] = lst[j-1],lst[j]

print(' '.join(lst))
isStable1(ans_lst,lst)

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

print(' '.join(lst))
isStable1(ans_lst,lst)

Solution (Python):

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







def insertionSort(A, N):
    
    for i in range(1, N):
        v = A[i]
        j = i - 1
        while j >= 0 and int(A[j][1]) > int(v[1]):
            A[j+1] = A[j]
            j = j - 1
        A[j+1] = v
    
    return " ".join(map(str, A))
    
stablesort = insertionSort(A.copy(), N)

def bubbleSort(A, N):
    flag = True
    i = 0
    while(flag):
        flag = False
        for j in reversed(range(1, N)):
            if int(A[j][1]) < int(A[j-1][1]):                
                A[j], A[j-1] = A[j-1], A[j]
                flag = True
                i += 1
                
    print(" ".join(map(str, A)))
    
    return " ".join(map(str, A))
    
bubble = bubbleSort(A.copy(), N)
if bubble == stablesort:
    print("Stable")
else:
    print("Not stable")

def selectionSort(A, N):
    e = 0
    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[i], A[minj] = A[minj], A[i]
            e += 1
            
    print(" ".join(map(str, A)))
    
    return " ".join(map(str, A))
    
selection = selectionSort(A.copy(), N)
if selection == stablesort:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
def check(orijinal,A):
    A2 = [int(x[1]) for x in A]
    orijinal2 = [int(x[1]) for x in orijinal]
    B=[x for x in set(A2) if  A2.count(x)>1]
    flag=True
    if len(B)!=0:
        count=0
        soeji=[]
        for fig in B:
            a=[i for i, x in enumerate(orijinal2) if x == fig]
            b=[i for i, x in enumerate(A2) if x == fig]
            orijinal3=[orijinal[k] for k  in a]
            A3 = [A[k] for k in b]
            if orijinal3!=A3:
                flag=False
                break
    if flag:
        print("Stable")
    else:
        print("Not stable")
def selectSort(N,A):
    count=0
    orijinal=A[:]
    B=[ int(x[1]) for x in A]
    C=list(range(N))
    for i in range(N):
        min=i
        for j in range(i,N):
            if B[j] < B[min]:
                min=j
        if i<=min:
            count+=1
            
            A[i],A[min]=A[min],A[i]
            B[i], B[min] = B[min], B[i]

    for k in range(N):print(A[k],end=' \n'[k+1==N])
    check(orijinal,A)



def bubbleSort(N,A):
    i=0
    flag=True
    count=0
    orijinal = A[:]
    B = [int(x[1]) for x in A]
    while flag:
        flag=False
        for j in range(N-1,i,-1):
            if B[j]<B[j-1]:
                A[j],A[j-1]=A[j-1],A[j]
                B[j], B[j - 1] = B[j-1], B[j]
                count+=1
                flag=True


        i += 1
    for i in range(N):print(A[i],end=' \n'[i+1==N])
    check(orijinal, A)

N=int(input())
A=[(x) for x in input().split()]
B=A[:]
bubbleSort(N,A)
selectSort(N,B)

Solution (Python):
class Card:
    def __init__(self, info):
        self.suit = info[0]
        self.number = info[1]
    
    def getSuit(self):
        return self.suit
    
    def getNumber(self):
        return self.number
    
    def __repr__(self):
        return self.suit + str(self.number)
    
def isSameCard(card1, card2):
    return card1.getNumber() == card2.getNumber() and card1.getSuit() == card2.getSuit()

def bubbleSort(Ain, N):
    for i in range(0,N):
        for j in range(N-1, i, -1):
            if Ain[j].getNumber() < Ain[j-1].getNumber():
                temp = Ain[j]
                Ain[j] = Ain[j-1]
                Ain[j-1] = temp

def selectionSort(Ain, N):
    for i in range(0,N):    
        minj = i
        for j in range(i+1,N):   
            if Ain[j].getNumber() < Ain[minj].getNumber():
                minj = j
        temp = Ain[i]
        Ain[i] = Ain[minj]
        Ain[minj] = temp

def printCards(Ain, N):
    for i in range(N-1):
        print(str(Ain[i]) + " ", end="")
    print(str(Ain[N-1]))

N = int(input())
Ain = [Card(info) for info in input().split()]
Ab = [i for i in Ain]
As = [i for i in Ain]
bubbleSort(Ab, N)
selectionSort(As, N)
printCards(Ab, N)
print("Stable")
printCards(As, N)
for i in range(0,N):
    if not isSameCard(Ab[i], As[i]):
        print("Not stable")
        break
    elif i != N-1:
        continue
    print("Stable")