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 

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



Sample input:
5
H4 C9 S4 D2 C3


Sample output:
D2 C3 H4 S4 C9
Stable
D2 C3 S4 H4 C9
Not stable

Submission status: Accepted

Solution code:
import copy

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

def selectionSort(A, N):
    count = 0
    for i in range(N):
        min = i
        for j in range(i, N):
            if A[j][1] < A[min][1]:
                min = j
        if min != i:
            A[i], A[min] = A[min], A[i]
            count += 1

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

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

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

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

Submission status: Accepted

Solution code:
N = int(input()) 
C = list(input().split())
C1 = C[:]
C2 = C[:]

def func(C):
    nums = []
    for i in range(N-1):
        for j in range(i+1,N):
            if C[i][1] in nums:
                continue
            elif C[i][1] == C[j][1]:
                nums.append(C[i][1])
    nums.sort()

    test = []
    for i in range(len(nums)):
        A = []
        for j in range(N):
            if C[j][1] == nums[i]:
                A.append(C[j])
        test.append(A)
    return test

def isStable(A,B):
    if func(A) == func(B):
        print("Stable")
    else:
        print("Not stable")

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

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

Submission status: Accepted

Solution code:
import copy

class card:
    def __init__(self, s):
        self.value = int(s[1:])
        self.mark = s[0]
        self.s = s
    
    def __repr__(self):
        return self.s
        
def isstable(Cin, Cout, 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 Cin[i].value==Cin[j].value and Cout[a].s==Cin[j].s and Cout[b].s == Cin[i].s:
                        return False
    return True
    
def BubbleSort(C, N):
    Cin = copy.copy(C)
    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]
    print(*C)

    if isstable(Cin, C, N):
        print('Stable')
    else:
        print('Not stable')

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

    print(*C)
    if isstable(Cin, C, N):
        print('Stable')
    else:
        print('Not stable')

N = int(input())
C = list(map(card, input().split()))

#N = 5
#C = list(map(card, ['H4', 'C9', 'S4', 'D2', 'C3']))
BubbleSort(copy.copy(C), N)
SelectionSort(copy.copy(C), N)

Submission status: Accepted

Solution code:
import copy
N = int(input())
A = [[i for i in item] for item in input().split()]

B = copy.deepcopy(A)

def bubbleSort(A, N):
    for i in range(N):
        for i in reversed(range(i, N-1)):
            if A[i][1] > A[i+1][1]:
                A[i], A[i+1] = A[i+1], A[i]

    res = []
    for item in A:
        temp_res = ''
        for i in item:
            temp_res += i
        res.append(temp_res)
    return res



def selectionSort(A, N):
    cnt = 0
    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]
    
    res = []
    for item in A:
        temp_res = ''
        for i in item:
            temp_res += i
        res.append(temp_res)
    return res

A_res = bubbleSort(A, N)
B_res = selectionSort(B, N)

print(*A_res)
print('Stable')
print(*B_res)
if A_res == B_res:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
n = int(input())
l = input().split(" ")
L = l[:]
for k in range(n - 1):
    for j in range(n - 1, 0, -1):
        if L[j][1:] < L[j - 1][1:]:
            L[j], L[j - 1] = L[j - 1], L[j]
    m = l[k:].index(min(l[k:], key=lambda x: x[1]))
    if m != 0:
        l[k], l[m + k] = l[m + k], l[k]
print(*L)
print("Stable")
print(*l)
print(['Not s', 'S'][l == L] + 'table')

Submission status: Accepted

Solution code:
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]
        

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

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

B_A = O_A[:]
S_A = O_A[:]

bubble_sort(B_A, N)
selection_sort(S_A, N)
print(*B_A)
print('Stable')
print(*S_A)
for i in range(N):
    if B_A[i] != S_A[i]:
        print('Not stable')
        break
else:
    print('Stable')

Submission status: Accepted

Solution code:
def bubble_sort(A, N):
    A = list(A)
    for i in range(1, N):
        for j in range(0, N-i):
            if A[j][1] > A[j+1][1]:
                A[j], A[j+1] = A[j+1], A[j]
    tmp = []
    for x, y in A:
        tmp.append(x+str(y))
    return tmp


def selection_sort(A, N):
    A = list(A)
    for i in range(0, N-1):
        pivot = i
        for j in range(i+1, N):
            if A[pivot][1] > A[j][1]:
                pivot = j
        if pivot != i:
            A[pivot], A[i] = A[i], A[pivot]
    tmp = []
    for x, y in A:
        tmp.append(x+str(y))
    return tmp


N = int(input())
X = list(map(str, input().split()))
A = []
for x in X:
    A.append((x[0], int(x[1])))
A = tuple(A)
a = bubble_sort(A, N)
print(*a)
print('Stable')
b = selection_sort(A, N)
print(*b)
if a == b:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
from copy import copy
from collections import defaultdict


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


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

def soot_order(C):
    ret = defaultdict(list)
    for c in C:
        soot = c[0]
        number = c[1]
        ret[number].append(soot)
    return ret


def judge_stable(C, N, order):
    
    cursor = 0
    stable = True
    while cursor < N:
        number = C[cursor][1]
        soots = order[number]
        for soot in soots:
            if C[cursor][0] != soot:
                print("Not stable")
                stable = False
                cursor += N
                break
            else:
                cursor += 1
    if stable:
        print("Stable")
        

def main():
    N = int(input())
    C = [c for c in input().split()]    
    
    order = soot_order(C)
    
    _C = copy(C)
    C_order = bubblesort(_C, N)
    print(' '.join(C_order))
    
    judge_stable(C_order, N, order)
    
    C_order = selectionsort(C, N)
    print(' '.join(C_order))
    
    judge_stable(C_order, N, order)
    
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
def bubbleSort(a,n):
    for i in range(n):
        for j in range(n-1, i, -1):
            if a[j-1][1] > a[j][1]: #Sort by card number
                a[j-1], a[j] = a[j], a[j-1]
    print(' '.join(a))

def selectionSort(a,n):
    for i in range(n):
        minj = i
        for j in range(i,n):
            if a[j][1] < a[minj][1]: #Sort by card number
                minj = j
        if minj != i:
            a[i],a[minj] = a[minj],a[i]
    a = [str(s) for s in a]
    print(' '.join(a))

def isStable(a, a2):
    """
    :param a: Stable-sorted list (Bubble sort)
    :param a2: List to check if isStable
    :return: Boolean
    """
    if a == a2:
        return True
    else:
        return False

n = int(input())
a = list(input().split())
a2 = a[::]

bubbleSort(a,n)
print('Stable')
selectionSort(a2,n)
print('Stable' if isStable(a, a2) else 'Not stable')

Submission status: Accepted

Solution code:
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
        #print(C)
    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")

Submission status: Accepted

Solution code:
a = int(input())
b = list(map(str, input().split()))
# print(b)

# print(b[1][1])
# print(type(int(b[1][1])))

# for k in range(len(b)):
#     c.append(b[k][1])
# print(c)

c = b[:] #リストで参照渡しをせずに、値のみを渡す方法。
d = b[:]

# print(id(b))
# print(id(c))
# print(id(d))

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(d)
# print(b)
print(*SelectSort(d))
isStable(d,b)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
def checkb():
	for i in range(n-1):
		if nl1[i] == nl1[i+1]:
			#print("Same number")
			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)]#Origin number
nl1 = [[] for i in range(n)]#number Bubble
sl = [[] for i in range(n)]

nl2 = [[] for i in range(n)]#number Selection
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])

#Bubble Sort
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]

#Selection Sort
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")

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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]: #2個目のカッコで文字数を指定(0スタート)
                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)

Submission status: Accepted

Solution code:
#アルゴリズム：バブルソート
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"


#初期data
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))

Submission status: Accepted

Solution code:
# Algorithms and Data Structures 1
# Stable Sort
# Name: Ryuya Asada
# ID: s1260064


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()

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
#stable sort Taka
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:
            #print(target, original)
            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))

Submission status: Accepted

Solution code:
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')  # bubblesort is definitely Stable sort

    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')