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 re

def bubbleSort(A, n):
    flag = True
    while flag:
        flag = False
        for j in range (1,n)[::-1]:
            if int(re.sub("\\D", "", A[j])) < int(re.sub("\\D", "", A[j-1])):
                A[j],A[j-1] = A[j-1],A[j]
                flag = True
    return [str(a) for a in A]


def selectionSort(A, n):
    for i in range (n):
        minj = i
        for j in range (i,n):
            if int(re.sub("\\D", "", A[j])) < int(re.sub("\\D", "", A[minj])):
                minj = j
        A[i],A[minj] = A[minj],A[i]
    return [str(a) for a in A]



n = int(input())
A = input().split()
B = [str(a) for a in A]

if bubbleSort(A, n) == selectionSort(B, n):
    print(" ".join(bubbleSort(A, n)))
    print("Stable")
    print(" ".join(selectionSort(A, n)))
    print("Stable")
else:
    print(" ".join(bubbleSort(A, n)))
    print("Stable")
    print(" ".join(selectionSort(B, n)))
    print("Not stable")

Submission status: Accepted

Solution code:
import copy

N = int(input())
A = list(map(str, input().split()))
bub = []
sel = []
bub = copy.copy(A)
sel = copy.copy(A)

# Bubble Sort
for i in range(N - 1, 0, -1):
    for j in range(N - 1, N - i - 1, -1):
        if bub[j][1] < bub[j - 1][1]:
            v = bub[j]
            bub[j] = bub[j - 1]
            bub[j - 1] = v

s_bub = [str(a) for a in bub]
s_bub = " ".join(s_bub)
print(s_bub)
print("Stable")

# Selection Sort
for i in range(N):  # i に、それ以降の最小値を持ってくる
    min_a = sel[i]  # 先頭を最小値として設定
    num = i
    for j in range(i + 1, N):  # 以下for内で、(i, N)における最小値をmin_aに取得
        if min_a[1] > sel[j][1]:
            min_a = sel[j]
            num = j
    if min_a[1] < sel[i][1]:
        sel[num] = sel[i]
        sel[i] = min_a

s_sel = [str(a) for a in sel]
s_sel = " ".join(s_sel)
print(s_sel)

if sel == bub:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
def cardnum(c):
    cc = list(c)
    return int(cc[1])

def cardlabel(c):
    cc = list(c)
    return cc[0]

def bubleSort(c, n):
    for i in range(n):
        for j in range(n-1, i, -1):
            if cardnum(c[j]) < cardnum(c[j-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, n):
            if cardnum(c[j]) < cardnum(c[minj]):
                minj = j
        if minj != i:
            (c[i], c[minj]) = (c[minj], c[i])
    return c

def isStable(c1, c0):
    l0 = []
    l1 = []
    for i in range(1, 10):
        for j in range(len(c0)):
            if (cardnum(c0[j])==i):
                l0.append(cardlabel(c0[j]))
            if (cardnum(c1[j])==i):
                l1.append(cardlabel(c1[j]))
#    print(l0)
#    print(l1)
#    print(l0==l1)
    return l0 == l1
     

n = int(input())
cards = input().split()
c1 = cards.copy()
c1ret = bubleSort(c1, n)
print(' '.join(c1ret))
if (isStable(c1ret, cards)):
    print('Stable')
else:
    print('Not stable')

#print(c1, c1ret, cards)

c2 = cards.copy()
c2ret = selectionSort(c2, n)
print(' '.join(c2ret))
if (isStable(c2ret, cards)):
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
def bubbleSort(A):
  global N
  for i in range(N):
    for j in  range(N-1,i,-1):
      jn = int(A[j][1:])
      jm =  int(A[j-1][1:])
      if jn < jm:
        x = A[j]
        A[j] = A[j-1]
        A[j-1] = x

def selectionSort(A):
  global N
  for i in range(N):
    minj = i
    for j in range(i,N):
      jn = int(A[j][1:])
      jm =  int(A[minj][1:])
      if jn < jm:
        minj = j
    if minj != i :
      x = A[minj]
      A[minj] = A[i]
      A[i] = x

def stableDict(A):
  S = dict()
  for e in A:
    i = e[1:]
    if i in S:
      S[i] = e + S[i]
    else:
      S[i] = e
  return S

def ckStable(org,dst):
  dictOrg = stableDict(org)
  dictDst = stableDict(dst)
  stableFlg = True
  for a in dictOrg.keys():
    if dictOrg[a] != dictDst[a]:
      stableFlg = False
  if stableFlg :
    print("Stable")
  else:
    print("Not stable")

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

A1 = list(A)
A2 = list(A)

bubbleSort(A1)
print(" ".join(A1))
ckStable(A,A1)
  
selectionSort(A2)
print(" ".join(A2))
ckStable(A,A2)

Submission status: Accepted

Solution code:
import copy


def bubbleSort(sort_list, N):

    before = copy.deepcopy(sort_list)

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

    print(' '.join(sort_list))
    print(checkStable(before, sort_list))


def selectionSort(sort_list, N):
    before = copy.deepcopy(sort_list)

    for i in range(0, N):
        minj = i

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

        if minj != i:
            tmp = sort_list[i]
            sort_list[i] = sort_list[minj]
            sort_list[minj] = tmp

    print(' '.join([str(i) for i in sort_list]))
    print(checkStable(before, sort_list))


def checkStable(before_list, sorted_list):

    for val in sorted_list:
        same_list = [
            i for i in sorted_list if (int(val[1]) == int(i[1])) and val != i
        ]
        if len(same_list) == 0:
            continue

        for data in same_list:
            bef = before_list.index(val) - before_list.index(data)
            aft = sorted_list.index(val) - sorted_list.index(data)

            if (bef > 0 and aft < 0) or (bef < 0 and aft > 0):
                return 'Not stable'

    return 'Stable'


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

    sort_list2 = copy.deepcopy(sort_list)
    bubbleSort(sort_list, N)
    selectionSort(sort_list2, N)

Submission status: Accepted

Solution code:
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
   # if i != minj:
    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")

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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


# bubble sort

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


# selsection sort

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# Problem - 安定なソート

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

# input
N = int(input())
cards = input().split()
check_dic = {}
check_dic_2 = {}
cards_1 = ['']*N
cards_2 = ['']*N
for i in range(N):
    # dictionaly create
    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]

# bubble sort
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")

# selection sort
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")

Submission status: Accepted

Solution code:
# Stable Sort

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):
	# bubble sort is always stable
	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')

Submission status: Accepted

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

# Bubble Sort
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')

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)))#pythonの場合は一回関数入れるとlは更新されてしまうのでlをコピーかなんかでもう一個作っとく必要がある
    print('Stable')#バブルソートは同じ数の順番入れ替わらないんすよね
    print(' '.join(selectionSort(l2,n)))
    if l != l2:
        print('Not stable')
    else:
        print('Stable')

Submission status: Accepted

Solution code:
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=入れ替える数のindex
    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')

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding:utf8 -*-

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

Submission status: Accepted

Solution code:
# 安定なソート
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")

Submission status: Accepted

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

Submission status: Accepted

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

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

#bubble sort
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


#select sort
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")

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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):
    # Stable なら True
    flag = True
    
    # C2 を並び替え後とする
    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)

Submission status: Accepted

Solution code:

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