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_Sort(C1, N):
    for i in range(N):
        for j in reversed(range(i+1,N)):
            if C1[j][1] < C1[j-1][1]:
                a = C1[j]
                C1[j] = C1[j-1]
                C1[j-1] = a
    
    return(C1)

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

        a = C2[minj]
        C2[minj] = C2[i]
        C2[i] = a
        
    return(C2)

N = int(input())
A1 = list(map(str,input().split()))
A2 = A1.copy()
B1 = Bubble_Sort(A1,N)
B2 = SelectionSort(A2,N)

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

Solution (Python):
a = int(input())
b = list(map(str, input().split()))









c = b[:] 
d = b[:]





def BubleSort(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 isStable(In, Out):
    for m in range(0,len(Out)):
        for n in range(m+1,len(Out)):
            for x in range(0,len(Out)):
                for y in range(x+1,len(Out)):
                    if int(In[m][1])==int(In[n][1]) and In[m] == Out[y] and In[n] == Out[x]:
                        return print('Not stable')
    return print('Stable')

def SelectSort(d):
    for i in range(len(d)-1):
        mini = i
        for j in range(i+1,len(d)):
            if int(d[mini][1])>int(d[j][1]):
                mini=j
        if int(d[mini][1])!=int(d[i][1]):
            d[i],d[mini]=d[mini],d[i]
    return d


print(*BubleSort(c))
isStable(c,b)


print(*SelectSort(d))
isStable(d,b)

Solution (Python):
import sys

def bubble_sort(size, numbers):
    for i in range(size):
        sorted = True
        for j in range(size - 1, i, -1):
            if numbers[j][1] < numbers[j - 1][1]:
                numbers[j], numbers[j - 1] = numbers[j - 1], numbers[j]
                sorted = False

        if sorted:
            break


def selection_sort(size, numbers):
    for i in range(size):
        minindex = i
        for j in range(i, size):
            if numbers[minindex][1] > numbers[j][1]:
                minindex = j
        if minindex != i:
            numbers[minindex], numbers[i] = numbers[i], numbers[minindex]


def write_result(stdout, sorted_array, original_array):
    stable = True
    for i in range(1, len(sorted_array)):
        if (sorted_array[i - 1][1] != sorted_array[i][1]):
            continue

        index_a = original_array.index(sorted_array[i - 1])
        index_b = original_array.index(sorted_array[i])

        if index_a > index_b:
            stable = False

    stdout.write(" ".join([str(x) for x in sorted_array]) + "\n")
    if stable:
        stdout.write("Stable\n")
    else:
        stdout.write("Not stable\n")


def main(stdin=None, stdout=None):
    if stdin is None:
        stdin = sys.stdin
    if stdout is None:
        stdout = sys.stdout

    size = int(stdin.readline().strip())
    _numbers = stdin.readline().strip().split(" ")

    numbers = _numbers[::]
    swap_count = bubble_sort(size, numbers)
    write_result(stdout, numbers, _numbers)

    numbers = _numbers[::]
    swap_count = selection_sort(size, numbers)
    write_result(stdout, numbers, _numbers)

main()

Solution (Python):
def selection(n, data):
    __count = 0
    for i in range(n):
        min_i = i
        for j in range(i+1, n):
            if data[min_i][1] > data[j][1]:
                min_i = j
        tmp = data[i]
        data[i] = data[min_i]
        data[min_i] = tmp
        if min_i != i:
            __count += 1
    return data, __count

def bubble_sort(n, data):
    __count = 0
    for i in range(n-1):
        for j in range(n-i-1):
            if data[j][1] > data[j+1][1]:
                tmp = data[j+1]
                data[j+1] = data[j]
                data[j] = tmp
                __count += 1
    return data, __count

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

if "__main__" == __name__:
    n = int(input())
    data_b = input().split()
    data_s = data_b.copy()
    sort1, count = bubble_sort(n, data_b)
    show(sort1)
    print("Stable")
    sort2, count = selection(n, data_s)
    show(sort2)
    if sort1 == sort2:
        print("Stable")
    else:
        print("Not stable")

Solution (Python):
import copy

class suit():
    def __init__(self, card):
        self.s = card
    def value(self):
        return int(self.s[1])

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

    return seq

def selectionsort(seq):
    for i in range(len(seq)):
        mini = i
        for j in range(i, len(seq)):
            if seq[j].value() < seq[mini].value():
                mini = j

        seq[i], seq[mini] = seq[mini], seq[i]

    return seq

def is_stable(inp, out):
    for i in range(len(inp)):
        if inp[i] != out[i]:
            return "Not stable"
    return "Stable"

def main():
    cards = list()
    n = int(input())

    for card in input().split():
        cards.append(suit(card))

    seq1 = copy.copy(cards)
    seq2 = copy.copy(cards)

    seq1 = bubblesort(seq1)
    seq2 = selectionsort(seq2)

    print(seq1[0].s, end="")
    for i in range(1, len(seq1)):
        print(" " + seq1[i].s, end = "")
    print("\nStable")

    print(seq2[0].s, end="")
    for i in range(1, len(seq2)):
        print(" " + seq2[i].s, end = "")
    print("\n" + is_stable(seq1, seq2), end="")
    print()

main()

Solution (Python):
n=int(input())
B=list(input().split())
A=[[0 for i in range(n)]for j in range(n)]
C=[[0 for i in range(n)]for j in range(n)]
for i in range(n):
    A[i]=B[i]
    C[i]=B[i]
flag=1
while flag==1:
    flag=0
    for i in range(n-1):
        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=1
for i in range(n-1):
    print(A[i],end=" ")
print(A[n-1])
print("Stable")

for i in range(n):
    min=i
    for j in range(i,n):
        if int(C[j][1])<int(C[min][1]):
            min=j
    if min!=i:
        C[i],C[min]=C[min],C[i]
for i in range(n-1):
    print(C[i],end=" ")
print(C[n-1])
flag=1
for i in range(n):
    if A[i]!=C[i]:
        flag=0
        break
if flag==1:
    print("Stable")
elif flag==0:
    print("Not stable")

Solution (Python):
def checkb():
	for i in range(n-1):
		if nl1[i] == nl1[i+1]:
			
			for j in range(n):
				if nlo[j] == nl1[i]:
					for k in range(j+1,n):
						if nlo[k] == nl1[i]:
							if sl[j] == bsl[i+1] and sl[k]==bsl[i]:
								return False
	return True

def checks():
	for i in range(n-1):
		if nl2[i] == nl2[i+1]:
			for j in range(n):
				if nlo[j] == nl2[i]:
					for k in range(j+1,n):
						if nlo[k] == nl2[i]:
							if sl[j] == ssl[i+1] and sl[k]==ssl[i]:
								return False
	return True

n = int(input())

nlo = [[] for i in range(n)]
nl1 = [[] for i in range(n)]
sl = [[] for i in range(n)]

nl2 = [[] for i in range(n)]
bsl = [[] for i in range(n)]
ssl = [[] for i in range(n)]

a = input().split()
for i in range(n):
	sl[i] = ssl[i] = bsl[i] = a[i][0]
	nlo[i] = nl1[i] = nl2[i] = int(a[i][1])


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


for i in range(n):
	minj = int(i)
	for j in range(i,n):
		if nl2[j] < nl2[minj]:
			minj = j
	nl2[i], nl2[minj] = nl2[minj], nl2[i]
	ssl[i], ssl[minj] = ssl[minj], ssl[i]
"""
print(sl)
print(bsl)
print(ssl)
print(nlo)
print(nl1)
"""
for i in range(n):
	print(str(bsl[i]) + str(nl1[i]),end="")
	if i == n-1:
		break
	print(" ",end="")
print()
if checkb():
	print("Stable")
else:
	print("Not stable")
for i in range(n):
	print(str(ssl[i]) + str(nl2[i]),end="")
	if i == n-1:
		break
	print(" ",end="")
print()
if checks():
	print("Stable")
else:
	print("Not stable")

Solution (Python):
import copy

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

def Selection(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
		tmp = A[i]
		A[i] = A[minj]
		A[minj] = tmp

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

N = int(input())
A = list(input().split())
B = copy.deepcopy(A)
Bubble(A,N)
Selection(B,N)
print(' '.join([str(a) for a in A]))
print('Stable')
print(' '.join([str(a) for a in B]))
print('Stable') if isStable(A,B,N) else print('Not stable')

Solution (Python):
N = int(input())
C = [ x for x in input().split()]
C1 = C.copy()
C2 = C.copy()

def bubble_sort(N, C1):
    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]
    print(' '.join(map(str, C1)))   

def selection_sort(N, C2):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if C2[minj][1] > C2[j][1]:
                minj = j
        C2[i],C2[minj] = C2[minj],C2[i]

    print(' '.join(map(str, C2)))



def bubble(N, C, C1):
    while True:        
        for i in range(N-1):
            for j in range(i+1, N):
                for a in range(N-1):
                    for b in range(a+1, N):
                        if C[i][1] == C[j][1] and C[i] == C1[b] and C[j] == C1[a]:
                            print('Not stable')
                            return False                            
        print('Stable')
        break

def selection(N, C, C2):
    while True:        
        for i in range(N-1):
            for j in range(i+1, N):
                for a in range(N-1):
                    for b in range(a+1, N):
                        if C[i][1] == C[j][1] and C[i] == C2[b] and C[j] == C2[a]:
                            print('Not stable')
                            return False                            
        print('Stable')
        break


bubble_sort(N, C1)
bubble(N, C, C1)
selection_sort(N, C2) 
selection(N, C, C2)

Solution (Python):

def BubbleSort(list, number):
    for i in range(0, number):
        for j in range(number-1, i, -1):
            if int(list[j][-1]) < int(list[j-1][-1]):
                list[j], list[j-1] = list[j-1], list[j]
    return list
    

def SelectionSort(list, number):
    for i in range(0, number):
        min_number = i
        for j in range(i, number):
            if int(list[min_number][-1]) > int(list[j][-1]):
                min_number = j
        list[i], list[min_number] = list[min_number], list[i]
    return list


def StableProcessing(list_A, list_B):
    if list_A == list_B:
        return "Stable"
    else:
        return "Not stable"



input_number = int(input())
input_list_B = list(map(str, input().split()))
input_list_S = list(input_list_B)


input_list_B = BubbleSort(input_list_B, input_number)
print(" ".join(input_list_B))
print("Stable")
input_list_S = SelectionSort(input_list_S, input_number)
print(" ".join(input_list_S))
print(StableProcessing(input_list_B, input_list_S))

Solution (Python):






def BubbleSort(A: list):
    flag = 1
    while flag:
        flag = 0
        for j in range(len(A)-1, 0, -1):
            if A[j][1] < A[j-1][1]:
                A[j], A[j-1] = A[j-1], A[j]
                flag = 1


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

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


def isEqual(a: list, b: list) -> bool:
    if len(a) != len(b):
        return False

    elif a == []:
        return True

    return (a.pop() == b.pop()) and isEqual(a, b)


def main():
    number_of_cards = int(input())
    cards = input().split(" ")

    cards_b = cards.copy()
    BubbleSort(cards_b)
    print(*cards_b, sep=" ")
    print("Stable")
    cards_s = cards.copy()
    SelectionSort(cards_s)
    print(*cards_s, sep=" ")
    if isEqual(cards_b, cards_s):
        print("Stable")
    else:
        print("Not stable")
    pass


if __name__ == "__main__":
    main()

Solution (Python):
from copy import copy


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


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


def to_dict(C):
    dictionary = {n: [] for n in range(1, 36+1)}
    for card in C:
        m, i = tuple(card)
        dictionary[int(i)].append(m)
    return dictionary


N = int(input())
* C, = input().split()
C_dict = to_dict(C)
BC = bubble_sort(copy(C), N)
BC_dict = to_dict(BC)
SC = selection_sort(copy(C), N)
SC_dict = to_dict(SC)

print(*BC)
if C_dict == BC_dict:
    print('Stable')
else:
    print('Not Stable')
print(*SC)
if C_dict == SC_dict:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
n = int(input())
a = list(map(str, input().split()))
b = a.copy()

flag = 1

for _ in range(n-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
print(" ".join(map(str, a)))
print("Stable")

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

Solution (Python):
import copy

def show(C):
    for i in range(len(C)):
        if i :
            print(' ', end = '')
        print(C[i], end = '')
    print()

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]
    show(C)

def SelectionSort(D, N):
    for i in range(N):
        min_j = i
        for j in range(i, N):
            if D[j][1] < D[min_j][1]:
                min_j = j
        D[i], D[min_j] = D[min_j], D[i]
    show(D)

N = int(input())
C = [i for i in input().split()]
D = copy.copy(C)

bubbleSort(C, N)
print('Stable')
SelectionSort(D, N)
if C == D:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
import copy

def printData(data) :
    for i, value in enumerate(data) :
        if i > 0 :
            print(" ", end = "")
        print(value[0] + str(value[1]), end = "")
    print()
    
def isStable(data1, data2) :
    for v1, v2 in zip(data1, data2) :
        if v1[0] != v2[0] :
            return "Not stable"
    return "Stable"

def bubbleSort(data, N) :
    flag = 1
    for i in range(N) :
        if not flag :
            break
        flag = 0
        for j in reversed(range(i + 1, N)) :
            if data[j][1] < data[j - 1][1] :
                buf = data[j]
                data[j] = data[j - 1]
                data[j - 1] = buf
                flag = 1
    printData(data)
    print("Stable")
    
def selectionSort(data, N) :
    for i in range(N) :
        minIdx = i
        for j in range(i + 1, N) :
            if data[j][1] < data[minIdx][1] :
                minIdx = j
        if minIdx != i :
            buf = data[minIdx]
            data[minIdx] = data[i]
            data[i] = buf
    printData(data)


N = int(input())
data = [list(value) for value in input().split()]
for value in data :
    value[1] = int(value[1])
    
copy_data1 = copy.deepcopy(data)
bubbleSort(copy_data1, N)
copy_data2 = copy.deepcopy(data)
selectionSort(copy_data2, N)
print(isStable(copy_data1, copy_data2))

Solution (Python):
import copy


class Card:
    def __init__(self, mark, number):
        self.mark = mark
        self.number = number

    def __repr__(self):
        return self.mark + str(self.number)


def bubble_sort(C, N):
    for i in range(N):
        for j in range(i + 1, N)[::-1]:
            if C[j-1].number > C[j].number:
                C[j-1], C[j] = C[j], C[j-1]


def selection_sort(C, N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if C[j].number < C[minj].number:
                minj = j
        C[i], C[minj] = C[minj], C[i]


if __name__ == "__main__":
    N = int(input())
    C_raw = list(input().split())
    C = []
    for i in range(N):
        c = Card(C_raw[i][0], int(C_raw[i][1]))
        C.append(c)

    C_for_bubble = copy.copy(C)
    bubble_sort(C_for_bubble, N)
    print(' '.join(map(str, C_for_bubble)))
    print('Stable')

    C_for_selection = copy.copy(C)
    selection_sort(C_for_selection, N)
    print(' '.join(map(str, C_for_selection)))
    if C_for_bubble == C_for_selection:
        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

def is_stable(original_list, sorted_list):
    for target in sorted_list:
        for original in original_list:
            
            if target[1] == original[1]:
                if target[0] != original[0]:
                    return "Not stable"
                original_list.remove(original)
                break
    return "Stable"

if __name__ == "__main__":
    import copy
    n = int(input())
    c = input().split()
    bubble_list = bubble_sort(copy.deepcopy(c), n)
    print(*bubble_list)
    print(is_stable(copy.deepcopy(c), bubble_list))
    selection_list = selection_sort(copy.deepcopy(c), n)
    print(*selection_list)
    print(is_stable(copy.deepcopy(c), selection_list))

Solution (Python):
import copy

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


def selection_sort(C, N):
    for i in range(N):
        min_j = i
        for j in range(i, N):
            if C[j]['value'] < C[min_j]['value']:
                min_j = j
        C[i], C[min_j] = C[min_j], C[i]


if __name__ == "__main__":
    N = int(input())
    C = list(map(lambda c: {'suit': c[0:1],'value': int(c[-1])}, input().split()))
    C2 = copy.deepcopy(C)
    bubble_sort(C, N)
    print(' '.join(map(lambda x: x['suit']+str(x['value']), C)))
    print('Stable')  

    selection_sort(C2, N)
    print(' '.join(map(lambda x: x['suit']+str(x['value']), C2)))
    for bc, sc in zip(C, C2):
        if bc['suit'] != sc['suit']:
            print('Not stable')
            exit()
    print('Stable')

Solution (Python):
import copy

class Cards:
    value = 0
    suit = ""

    def __init__(self,su,val):
        self.suit = su
        self.value = val
    
    def __str__(self):
        return f"{self.suit}{self.value}"

    def __eq__(self,other):
        if not isinstance(other, Cards):
            return NotImplemented
        
        return self.value == other.value and self.suit == other.suit


def cards_stablesort(C):
    lst = copy.deepcopy(C)
    n = len(lst)
    for i in range(1,n):
        j = i
        while(j > 0):
            if lst[j-1].value > lst[j].value:
                lst[j-1],lst[j] = lst[j],lst[j-1] 
                j -= 1
            else:
                break

    return lst

def cards_bubblesort(C):
    lst = copy.deepcopy(C)
    n = len(lst)

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

    return lst

def cards_selectionsort(C):
    lst = copy.deepcopy(C)
    n = len(lst)

    for i in range(n):
        minj = i

        for j in range(i,n):

            if lst[j].value < lst[minj].value:
                minj = j
        
        lst[i],lst[minj] = lst[minj],lst[i]

    return lst
    


n = int(input())

l = input().split()

C = []
for cd in l:
    C.append(Cards(cd[:1],int(cd[1:])))

stable_list = cards_stablesort(C)
bubble_list = cards_bubblesort(C)
select_list = cards_selectionsort(C)

print(*bubble_list)

if stable_list == bubble_list:
    print("Stable")
else:
    print("Not stable")

print(*select_list)

if stable_list == select_list:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
def bubble(b,p):
    for i in range(0,p):
        for j in reversed(range(i+1,n)):
            if int(b[j][1]) < int(b[j-1][1]):
                b[j],b[j-1] = b[j-1],b[j]
    return b

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

n = int(input())
a = [s for s in input().split()]
c = a.copy()
print(" ".join(map(str,bubble(a,n))))
print("Stable")
d = selection(c,n)
print(" ".join(map(str,d)))
if a == d:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
import copy

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

def selction(A, N):
    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
        A[i], A[minj] = A[minj], A[i]
    return A
        
n = int(input())
a = list(map(str, input().split()))

b = copy.copy(a)
c = copy.copy(a)
bubble(b, n)
print(*b)
print("Stable")
selction(c, n)
print(*c)
if c == b:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
import copy
N = int(input())
lst1 = list(input().split())
lst2 = copy.copy(lst1)

def bubble_sort(lst):
    for i in range(N):
        for j in range(N-1,i,-1):
            if (int(lst[j][1]) < int(lst[j-1][1])):
                lst[j],lst[j-1] = lst[j-1],lst[j]
    return lst
    
def selection_sort(lst):
    for i in range(N):
        minj = i
        for j in range(i,N):
            if (int(lst[j][1]) < int(lst[minj][1])):
                minj = j
        lst[i],lst[minj] = lst[minj],lst[i]
    return lst

res1 = " ".join(bubble_sort(lst1))
res2 = " ".join(selection_sort(lst2))
print(res1)
print('Stable')
print(res2)
if (res1 == res2):
    print('Stable')
else:
    print('Not stable')

Solution (Python):
N = int(input())
A = list(input().split())
A_ = A.copy()
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]
s = ''
for a in A_:
    s += a + ' '
print(s.rstrip())
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]

s_ = ''
for a in A:
    s_ += a + ' '
print(s_.rstrip())
if A == A_:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
def bubble_sort_index(n, number_from_cards):
    flag = True
    index_lists = list(range(n))
    while flag:
        flag = False
        for i in range(n - 1, 0, -1):
            if number_from_cards[i] < number_from_cards[i - 1]:
                number_from_cards[i], number_from_cards[i - 1] = number_from_cards[i - 1], number_from_cards[i]
                index_lists[i], index_lists[i - 1] = index_lists[i - 1], index_lists[i]
                flag = True
    return index_lists


def selection_sort_index(n, number_from_cards):
    index_list = list(range(n))
    for i in range(n):
        min_j = i
        for j in range(i, n):
            if number_from_cards[min_j] > number_from_cards[j]:
                min_j = j
        if min_j == i:
            continue
        number_from_cards[i], number_from_cards[min_j] = number_from_cards[min_j], number_from_cards[i]
        index_list[i], index_list[min_j] = index_list[min_j], index_list[i]
    return index_list


def main():
    N = int(input())
    true_cards = input().split(' ')
    number_from_cards = [int(c[-1]) for c in true_cards]
    sorted_index_lists_for_bubble = bubble_sort_index(N, number_from_cards.copy())
    sorted_bubble = [true_cards[index] for index in sorted_index_lists_for_bubble]

    sorted_index_lists_for_selection = selection_sort_index(N, number_from_cards.copy())
    sorted_selection = [true_cards[index] for index in sorted_index_lists_for_selection]

    print(' '.join(sorted_bubble))
    print('Stable')
    print(' '.join(sorted_selection))
    if sorted_bubble == sorted_selection:
        print('Stable')
    else:
        print('Not stable')


if __name__ == '__main__':
    main()

Solution (Python):
import copy

def bubble_sort(a, n):
    a = copy.deepcopy(a)
    count = 0
    flag = 1
    
    while flag:
        flag = 0
        
        for j in range(n-1, 0, -1):
            if int(a[j][1]) < int(a[j-1][1]):
                a[j-1], a[j] = a[j], a[j-1]
                flag = 1
                count += 1
                
    return a, count

def selection_sort(a, n):
    a = copy.deepcopy(a)
    
    count = 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 minj != i:
          count += 1
          a[minj], a[i] = a[i], a[minj]
        
    return a, count

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

bubble_sorted, _ = bubble_sort(a=cards, n=n)
selection_sorted, _ = selection_sort(a=cards, n=n)


print(" ".join(bubble_sorted))
print("Stable")
print(" ".join(selection_sorted))

stable_flag = True
for i in range(n):
    if bubble_sorted[i] != selection_sorted[i]:
      stable_flag = False
      

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

Solution (Python):
def bubble_sort(C, N):
    flag = 1
    while flag:
        flag = 0
        for j in range(1, N):
            if list(C[j])[1] < list(C[j-1])[1]:
                C[j], C[j-1] = C[j-1], C[j]
                flag = 1
        N -= 1
    return C

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

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

st = [''] * 9
bubble_st = [''] * 9
selection_st = [''] * 9
bubble_c = bubble_sort(C[:], N)
selection_c = selction_sort(C[:], N)
for i in range(N):
    st[int(list(C[i])[1])-1] += list(C[i])[0]
    bubble_st[int(list(bubble_c[i])[1])-1] += list(bubble_c[i])[0]
    selection_st[int(list(selection_c[i])[1])-1] += list(selection_c[i])[0]
print(' '.join(bubble_c))
if st == bubble_st:
    print('Stable')
else:
    print('Not stable')
print(' '.join(selection_c))
if st == selection_st:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
class Card():
    def __init__(self, suit, value):
        self.suit = suit
        self.value = value
    
    def __eq__(self, ins):
        if not isinstance(ins, Card):
            return NotImplemented
        return self.suit == ins.suit and self.value == ins.value

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

def selectionSort(C, N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if C[minj].value > C[j].value:
                minj = j
        C[i], C[minj] = C[minj], C[i]

def printCard(C, N):
    c = [C[i].suit + C[i].value for i in range(N)]
    print(' '.join(c))

def isStable(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].value == inc[j].value and inc[i] == outc[b] and inc[j] == outc[a]:
                        return False
    return True


n = int(input())
input_cards = [Card(*c) for c in input().split()]
output_cards = input_cards.copy()
bubbleSort(output_cards, n)
printCard(output_cards, n)
if isStable(input_cards, output_cards, n):
    print('Stable')
else:
    print('Not stable')
output_cards = input_cards.copy()
selectionSort(output_cards, n)
printCard(output_cards, n)
if isStable(input_cards, output_cards, n):
    print('Stable')
else:
    print('Not stable')

Solution (Python):
import copy

n = int(input())
arr1 = [(int(x[-1]), x) for x in list(input().split())]
arr2 = copy.copy(arr1)

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

def select_sort(arr, n):
  for i in range(n):
    minj = i
    for j in range(i, n):
      if arr[j][0] < arr[minj][0]:
        minj = j
    arr[i],arr[minj] = arr[minj],arr[i]

def check_stable(input, output):
  return 'Stable' if input == output else 'Not stable'

def arr_to_map(input):
  return ' '.join([x[1] for x in input])

bubble_sort(arr1, n)
select_sort(arr2, n)

print (arr_to_map(arr1))
print ('Stable')
print (arr_to_map(arr2))
print (check_stable(arr1, arr2))