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:
def bubble_sort(cards, n):
#2   for i = 0 to N-1
#3     for j = N-1 downto i+1
#4       if C[j].value < C[j-1].value
#5         C[j] と C[j-1] を交換
    for i in range(0, n):
        for j in range(n-1, i, -1):
            if int(cards[j][1]) <  int(cards[j-1][1]):
                cards[j], cards[j-1] = cards[j-1], cards[j]
    
    return cards

def selection_sort(cards, n):

#8   for i = 0 to N-1
#9     minj = i
#10    for j = i to N-1
#11      if C[j].value < C[minj].value
#12        minj = j
#13    C[i] と C[minj] を交換
    for i in range(0, n-1):
        minj = i
        for j in range(i, n):
            if int(cards[j][1]) <  int(cards[minj][1]):
                minj = j
        cards[i], cards[minj] = cards[minj], cards[i]
    
    return cards


n = int(input())
cards = input().split()
list_buble = bubble_sort(cards[:], n)
list_selection = selection_sort(cards[:], n)
print(*list_buble)
print("Stable")
print(*list_selection)
print("Stable" if list_buble == list_selection else "Not stable")

Submission status: Accepted

Solution code:
def is_stable(bubble, selection, _N):
    for i in range(N):
        if bubble[i][0] != selection[i][0]:
            return False
    return True


def bubble(N_input, A_input):
    count = 0
    flag = 1
    _A = list(A_input)

    while flag:
        flag = 0
        for i in range(N_input-1, 0, -1):
            _A_i = int(_A[i][1])
            _A_i_1 = int(_A[i-1][1])

            if _A_i < _A_i_1:
                _A[i], _A[i-1] = _A[i-1], _A[i]

                flag = 1
                count += 1

    return _A


def selection(inN, inA):
    _A = list(inA)

    for i in range(0, inN-1, 1):
        minj = i
        for j in range(i+1, inN, 1):
            if int(_A[j][1]) < int(_A[minj][1]):
                minj = j
        _A[i], _A[minj] = _A[minj], _A[i]

    return _A


N = int(input())
# A = list(map(int, input().split()))
A = input().split()
# print(N, A)

A_bubble = bubble(N, A)
A_bubble_str = map(str, A_bubble)
print(' '.join(A_bubble_str))
print('Stable')

A_selection = selection(N, A)
A_selection_str = map(str, A_selection)
print(' '.join(A_selection_str))
if is_stable(A_bubble, A_selection, N):
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
class Card:
    def __init__(self):
        self.suit = ""
        self.value = ""

def bubbleSort(C, N):
    flag = 1
    while flag:
        flag = False
        for j in reversed(range(1,N)):
            if C[j][1] < C[j-1][1]:
                C[j],C[j-1] = C[j-1],C[j]
                flag = True

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 check(L1,L2):
    if L1 == L2:
        return 'Stable'
    else:
        return 'Not stable'

N = int(input())
C = list(input().split())
from copy import deepcopy
L1 = deepcopy(C)
L2 = deepcopy(C)

bubbleSort(L1,N)
selectionSort(L2,N)

print(*L1)
print('Stable')
print(*L2)
print(check(L1,L2))

Submission status: Accepted

Solution code:
n = int(input())
A = list(input().split())

BS = A[::]
SS = A[::]

#BS
for i in range(0, n):
  for j in range(n-1, i, -1):
    if int(BS[j][1]) < int(BS[j-1][1]):
      BS[j], BS[j-1] = BS[j-1], BS[j]
print(*BS, sep=" ")
print("Stable")

#SS
for i in range(0, n):
  minj = i
  for j in range(i, n):
    if int(SS[j][1]) < int(SS[minj][1]):
      minj = j
  SS[i], SS[minj] = SS[minj], SS[i]
print(*SS, sep=" ")
if SS == BS:
  print("Stable")
else:
  print("Not stable")

Submission status: Accepted

Solution code:
import copy

# 入力
N=int(input())
C=list(input().split())
C_value=list(int(C[n][1:])for n in range(N))

# 安定性の判定を行う関数
def isStable(In,Out,In_value):
    flag=1
    for i in range(N):
        for j in range(i+1,N):
            for a in range(N):
                for b in range(a+1,N):
                    if In_value[i]==In_value[j] and In[i]==Out[b] and In[j]==Out[a]:
                        flag=0
    if flag==1:
        return 'Stable'
    else:
        return 'Not stable'

# バブルソート用のリスト作成
Cb=copy.copy(C)
Cb_value=list(int(Cb[n][1:])for n in range(N))

# バブルソート
for i in range(N):
    for j in range(N-1,i,-1):
        if Cb_value[j]<Cb_value[j-1]:
            Cb_value[j],Cb_value[j-1]=Cb_value[j-1],Cb_value[j]
            Cb[j],Cb[j-1]=Cb[j-1],Cb[j]

# 出力
print(' '.join(Cb))
print(isStable(C,Cb,C_value))


# 選択ソート用のリスト作成
Cs=copy.copy(C)
Cs_value=list(int(Cs[n][1:])for n in range(N))

# 選択ソート
for i in range(N):
    minj=i
    for j in range(i,N):
        if Cs_value[j]<Cs_value[minj]:
            minj=j
    Cs_value[i],Cs_value[minj]=Cs_value[minj],Cs_value[i]
    Cs[i],Cs[minj]=Cs[minj],Cs[i]

# 出力
print(' '.join(Cs))
print(isStable(C,Cs,C_value))

Submission status: Accepted

Solution code:
import copy

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

bubble = copy.copy(a)
for i in range(n):
    for j in reversed(range(i+1,n)):
        if bubble[j][1] < bubble[j-1][1]:
            bubble[j],bubble[j-1] = bubble[j-1],bubble[j]

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

print(' '.join(bubble))
print('Stable')
print(' '.join(insertion))
if tuple(bubble) != tuple(insertion):
    print('Not stable')
else:
    print('Stable')

Submission status: Accepted

Solution code:
n = int(input())
*ls_a, = input().split()
ls_b = ls_a[:]
for i in range(n):
    for j in range(n-1, i, -1):
        if ls_a[j][1:] < ls_a[j-1][1:]:
            ls_a[j], ls_a[j-1] = ls_a[j-1], ls_a[j]

print(*ls_a)
print("Stable")

for i in range(n):
    minj = i
    for j in range(i, n):
        if ls_b[j][1:] < ls_b[minj][1:]:
            minj = j
    ls_b[i], ls_b[minj] = ls_b[minj], ls_b[i]
print(*ls_b)
if ls_a == ls_b:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
class Card:
    def __init__(self, suit: str, value: int):
        self.suit = suit
        self.value = value

    def __str__(self):
        return self.suit + self.value


N = int(input())
cards1 = [Card(card[0], card[1]) for card in list(map(str, input().split()))]
cards2 = [*cards1]


def bubbleSort(cards: list, n: int):
    for i in range(n):
        for j in reversed(range(i+1, n)):
            if cards[j-1].value > cards[j].value:
                cards[j-1], cards[j] = cards[j], cards[j-1]
    return cards


def selectionSort(cards: list, n: int):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if cards[minj].value > cards[j].value:
                minj = j
        cards[i], cards[minj] = cards[minj], cards[i]
    return cards


def isStable(cards1: list, cards2: list, n: int):
    for i in range(n):
        if cards1[i].suit != cards2[i].suit:
            return False
    return True


bubbleSort(cards1, N)
selectionSort(cards2, N)
print(*cards1)
print('Stable')
print(*cards2)
print('Stable' if isStable(cards1, cards2, N) else 'Not stable')

Submission status: Accepted

Solution code:
n=int(input())
c=input().split()
d=c[:]

for i in range(n):
    for j in range(n-1,i,-1):
        if d[j][1]<d[j-1][1]:
            d[j],d[j-1]=d[j-1],d[j]
print(*d)
print("Stable")

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]

print(*c)
if c==d:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import copy

class trump:
    def __init__(self, s):
        self.name = s
        s = list(s)
        self.value = int(s[1])

N=int(input())
C = list(map(trump, input().split()))
C_copy = C.copy()

def BubbleSort(A,N):
    for i in range(N):
        for j in reversed(range(i+1,N)):
            if A[j].value < A[j-1].value:
                A[j],A[j-1]=A[j-1],A[j]
    for i in range(N):
        if i==N-1:
            print(A[i].name)
        else:
            print(A[i].name,end=" ")
    print("Stable")

def SelectionSort(A,N):
    for i in range(N):
        minj=i
        for j in range(i,N):
            if A[j].value<A[minj].value:
                minj=j
        A[i],A[minj]=A[minj],A[i]
    for i in range(N):
        if i==N-1:
            print(A[i].name)
        else:
            print(A[i].name,end=" ")
    if C==C_copy:
        print("Stable")
    else:
        print("Not stable")
        
BubbleSort(C,N)
SelectionSort(C_copy,N)

Submission status: Accepted

Solution code:
def bs(a,n):
    ans=0
    flag=True
    while flag:
        flag=False
        for i in range(n-1,0,-1):
            if int(a[i][1])<int(a[i-1][1]):
                a[i],a[i-1]=a[i-1],a[i]
                flag=True
                ans+=1
    return a

def ss(a,n):
    ans=0
    for i in range(n):
        m=i
        for j in range(i,n):
            if int(a[j][1])<int(a[m][1]):
                m=j
        if m!=i:
            a[i],a[m]=a[m],a[i]
            ans+=1
    return a
N=int(input())
A=list(input().split())
B=A[:]
ans1,ans2=bs(A,N),ss(B,N)
print(*ans1)
print("Stable")
print(*ans2)
print("Stable" if ans1==ans2 else "Not stable")

Submission status: Accepted

Solution code:
def bubble(n, A):
    flag = True
    i = 0
    while (flag):
        flag = False
        for j in reversed(range(i+1, n)):
            if (A[j-1][1] > A[j][1]):
                A[j-1], A[j] = A[j], A[j-1]
                flag = True
        i += 1
    return A

def selection(n, A):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if (A[minj][1] > A[j][1]):
                minj = j
        A[minj], A[i] = A[i], A[minj]
    return A

def judge(A, B):
    for i in range(n):
        if (bubble(n, A)[i] != selection(n, B)[i]):
            return "Not stable"
    return "Stable"

n = int(input())
A = input().split(" ")
B = A.copy()
print (" ".join(bubble(n, A)))
print ("Stable")
print (" ".join(selection(n, B)))
print (judge(bubble(n, A), selection(n, B)))

Submission status: Accepted

Solution code:
#安定なソート判定
def print_output(_list):
    for index in range(len(_list)):
        if index == len(_list) - 1:
            print(_list[index])
        else:
            print(_list[index],end=' ')

def bubble(_target_list):
    target_list = _target_list.copy()
    for index in range(1, len(target_list)):
        for compare_index in reversed(range(index)):
            if target_list[compare_index + 1][1] < target_list[compare_index][1]:
                target_list[compare_index + 1] ,target_list[compare_index] = target_list[compare_index] ,target_list[compare_index + 1]
            else:            
                break
    return target_list

def selection(_target_list):
    target_list = _target_list.copy()
    for i in range(len(target_list)):
        minj = i
        for j in range(i, len(target_list)):
            if target_list[j][1] < target_list[minj][1]:
                minj = j
        if i != minj:
            target_list[i], target_list[minj] = target_list[minj], target_list[i]
    return target_list

target_length = int(input())
target_list = [x for x in input().split()]

bubble_list = bubble(target_list)
print_output(bubble_list)
print("Stable")
selection_list = selection(target_list)
print_output(selection_list)
if bubble_list == selection_list:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
from typing import List


class Trump:
	def __init__(self, value, suit):
		self.value = value
		self.suit = suit

	def __repr__(self):
		return self.suit + str(self.value)


def bubble(C: List[Trump], N: int) -> None:
	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)


def selection(C: List[Trump], N: int) -> None:
	for i in range(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]
	print(*C)


if __name__ == "__main__":
	N = int(input())
	C1 = []
	for c in input().split():
		C1.append(Trump(int(c[1]), c[0]))
	C2 = C1.copy()

	bubble(C1, N)
	print("Stable")
	selection(C2, N)
	if C1 == C2:
		print("Stable")
	else:
		print("Not stable")

Submission status: Accepted

Solution code:
def BubbleSort(A,B,N):
    for i in range(N):
        for j in range(N-1,i,-1):
            if B[j] < B[j-1]:
                A[j],A[j-1]=A[j-1],A[j]
                B[j],B[j-1]=B[j-1],B[j]

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

N = int(input())
A = list(input().split())
A_BubbleSort = A[:]
A_SelectionSort = A[:]
B=[0 for i in range(N)]
for i in range(N):
    B[i] = int(A[i][1])
B_BubbleSort = B[:]
B_SelectionSort = B[:]
BubbleSort(A_BubbleSort,B_BubbleSort,N)
SelectionSort(A_SelectionSort,B_SelectionSort,N)
print(*A_BubbleSort)
print("Stable")
print(*A_SelectionSort)
if A_BubbleSort == A_SelectionSort:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
import copy

n = int(input())
cards = list(map(str, input().split()))

def BubbleSort(NUM_LIST):
    for i in range(1, len(NUM_LIST)):
        for j in range(len(NUM_LIST)-1, i-1, -1):
            if NUM_LIST[j-1][1] >NUM_LIST[j][1]:
                NUM_LIST[j], NUM_LIST[j-1] = NUM_LIST[j-1], NUM_LIST[j]

def SelectionSort(NUM_LIST):
    for i in range(len(NUM_LIST)):
        minj = i
        for j in range(i, len(NUM_LIST)):
            if NUM_LIST[minj][1] > NUM_LIST[j][1]:
                minj = j
        NUM_LIST[minj], NUM_LIST[i] = NUM_LIST[i], NUM_LIST[minj]

bubble_cards = copy.copy(cards)
selection_cards = copy.copy(cards)

BubbleSort(bubble_cards)
SelectionSort(selection_cards)


print(" ".join(bubble_cards))
print("Stable")

print(" ".join(selection_cards))
if bubble_cards == selection_cards:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
class Bubblesort():
    def __init__(self,x,n):
        self.C = x
        self.n = n
    def sorting(self):
        for i in range(self.n):
            for j in range(self.n - 1 , i , -1):
                if int(self.C[j][1]) < int(self.C[j - 1][1]):
                    self.C[j], self.C[j - 1] = self.C[j - 1], self.C[j]
        return self.C
    
    def check(self, xx):
        return CheckStable(self.C, xx)

class Selectionsort():
    def __init__(self, x, n):
        self.C = x
        self.n = n
    def sorting(self):
        for i in range(0, self.n):
            minj = i
            for j in range(i+1, self.n):
                if int(self.C[j][1])  < int(self.C[minj][1]):
                    minj = j
            self.C[i], self.C[minj] = self.C[minj], self.C[i]
        return self.C
    
    def check(self, xx):
        return CheckStable(self.C, xx)
    
def CheckStable(x1, xx2):
    ch1 = []
    for i in range(n - 1):
        if x1[i][1] == x1[i + 1][1]:
            ch1.append(x1[i])
            if i + 1 == n - 1:
                ch1.append(x1[i + 1])
        elif x1[i - 1][1] == x1[i][1]:
            ch1.append(x1[i])
    
    ch2 = []
    x2 = xx2
    for i in ch1:
        for j in range(len(x2)):
            if i[1] == x2[j][1]:
                ch2.append(x2[j])
                x2.pop(j)
                break

    if ch1 == ch2:
        return ('Stable')
    else:
        return ('Not stable')

n = int(input())
x = input().split()
xx =x[:]
y =x[:]
yy =x[:]

a = Bubblesort(x, n)
b = Selectionsort(y, n)
print(' '.join(a.sorting()))
print(a.check(xx))
print(' '.join(b.sorting()))
print(b.check(yy))

Submission status: Accepted

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

B = [int(x[1]) for x in A]
C = [x[0] for x in A]
D = [int(x[1]) for x in A]
E = [x[0] for x in A]
F = [int(x[1]) for x in A]
G = [x[0] for x in A]

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

def selectionSort(A, B, N):
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if A[j] < A[minj]: minj = j
        A[i], A[minj] = A[minj], A[i]
        B[i], B[minj] = B[minj], B[i]
    return 0

def showArray(A, B, N):
    for _ in range(N):
        if _ == N-1:
            print(A[_], sep='', end='')
            print(B[_], sep='', end='')
        else:
            print(A[_], sep='', end='')
            print(B[_], sep='', end=' ')
    print()
    return 0

def isStable(A, B, C, D, N):
    for _ in range(1, 10):
        if A.count(_) > 1:
            if [B[i] for i, x in enumerate(A) if x == _] == [D[i] for i, x in enumerate(C) if x == _]:
                continue
            else:
                return 'Not stable'
    return 'Stable'

if __name__ == '__main__':
    bubbleSort(B, C, N)
    selectionSort(D, E, N)
    
    showArray(C, B, N)
    print(isStable(B, C, F, G, N))
    showArray(E, D, N)
    print(isStable(D, E, F, G, N))

Submission status: Accepted

Solution code:
import copy

class Card:
    def __init__(self, mark_num):
        self.mark_num = mark_num
        self.mark = mark_num[0]
        self.num = int(mark_num[1:])

def bubble_sort(cards, n):
    flag = True
    while flag:
        flag = False
        for i in reversed(range(1, n)):
            if cards[i].num < cards[i-1].num:
                tmp = cards[i]
                cards[i] = cards[i-1]
                cards[i-1] = tmp
                flag = True
    
    # for c in cards:
    #     print(c.mark_num + " ", end="")

    mark_nums = []
    for c in cards:
        mark_nums.append(c.mark_num)

    print(" ".join(mark_nums))
    print("Stable")

    return cards

    # nums_str = map(str, nums)
    # print(" ".join(cards))
    # print(cards)

def selection_sort(cards, n):
    for i in range(n):
        minj = i
        flag = False
        for j in range(i, n-1):
            if cards[minj].num > cards[j+1].num:
                minj = j+1
                flag = True
        
        if flag:
            tmp = cards[i]
            cards[i] = cards[minj]
            cards[minj] = tmp

    mark_nums = []
    for c in cards:
        mark_nums.append(c.mark_num)

    print(" ".join(mark_nums))

    return cards

def is_stable(cards1, cards2, n):
    is_stable = True
    for i in range(n):
        if cards1[i].mark_num != cards2[i].mark_num:
            is_stable = False
            break

    if is_stable:
        print("Stable")
    else:
        print("Not stable")
    
#     nums_str = map(str, nums)
#     print(" ".join(nums_str))
#     print(count)

if __name__=="__main__":
    n = int(input())
    input_cards = list(input().split())
    card_list = []
    for input_card in input_cards:
        card = Card(input_card)
        card_list.append(card)

    cards_1 = bubble_sort(copy.deepcopy(card_list), n)
    cards_2 = selection_sort(copy.deepcopy(card_list), n)

    is_stable(cards_1, cards_2, n)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(str, input().split()))
unsorted_A = A[:]
bub_A = A[:]
sel_A = A[:]

def BubbleSort(bub_A):
    for i in range(N):
        for j in range(1, N):
            if bub_A[j][1] < bub_A[j-1][1]:
                swp = bub_A[j]
                bub_A[j], bub_A[j-1] = bub_A[j-1], swp

    print(' '.join(bub_A))
    print('Stable')

def SelectionSort(sel_A):
    for i in range(N):
        min = i
        for j in range(i, N):
            if sel_A[j][1] < sel_A[min][1]:
                min = j
        if sel_A[i][1] > sel_A[min][1]:
            sel_A[i], sel_A[min] = sel_A[min], sel_A[i]

    print(' '.join(sel_A))
    if bub_A == sel_A:
        print('Stable')
    else:
        print('Not stable')

BubbleSort(bub_A)
SelectionSort(sel_A)

Submission status: Accepted

Solution code:
n=int(input())
A=input().split()
B=A[::]

flag=1
while flag:
  flag=0
  for i in range(n-1,0,-1):
    if int(A[i-1][1])>int(A[i][1]):
      A[i-1],A[i]=A[i],A[i-1]
      flag=1
print(*A)
print("Stable")

for i in range(n-1):
  minj=i
  for j in range(i,n):
    if int(B[minj][1])>int(B[j][1]):
      minj=j
  if minj!=i:
    B[i],B[minj]=B[minj],B[i]
print(*B)
if A==B:
  print("Stable")
else:
  print("Not stable")

Submission status: Accepted

Solution code:
import sys
import copy
input = sys.stdin.readline


def main():
    N = int(input())
    P = list(input().split())
    bubbleSortted = bubbleSort(N, copy.copy(P))
    print(' '.join(map(str, bubbleSortted)))
    print("Stable")
    selectionSorted = selectionSort(N, copy.copy(P))
    print(' '.join(map(str, selectionSorted)))
    print(isStable(bubbleSortted, selectionSorted))


def selectionSort(N, P):
    change_count = 0
    for i in range(0, N):
        minj = i

        # print(P[i:N])
        # print(min(P[i:N]))

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

        if i != minj:
            tmp = P[i]
            P[i] = P[minj]
            P[minj] = tmp
            change_count += 1

        # print(' '.join(map(str, P)))

    return P


def bubbleSort(N, P):
    change_count = 0
    i = 0
    while True:
        for j in range(N - 1, i, -1):
            if P[j][1] < P[j - 1][1]:
                tmp = P[j]
                P[j] = P[j - 1]
                P[j - 1] = tmp
                change_count += 1
        i += 1
        # print("i:{}".format(i))
        if i == N:
            break

    return P


def isStable(P1, P2):
    for i in range(len(P1)):
        # print("P1:{0},P2:{1}".format(P1[i], P2[i]))
        if P1[i] != P2[i]:
            return "Not stable"
    return "Stable"


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from copy import copy
from collections import defaultdict  

def bubble_sort(collection):
    collection = copy(collection)
    for i in range(len(collection)):
        for j in range(len(collection)-1, i, -1):
            if collection[j] < collection[j-1]:
                collection[j], collection[j-1] = collection[j-1], collection[j]
    return collection
    
def selection_sort(collection):
    collection = copy(collection)
    for i in range(len(collection)):
        mini = i
        for j in range(i, len(collection)):
            if collection[j] < collection[mini]:
                mini = j
        collection[i], collection[mini] = collection[mini], collection[i]
        
    return collection
    
def print_cards(cards):
    for card in cards[:-1]:
        print(card, end=' ')
    print(cards[-1])

def find_card_order(cards):
    duplicate_numbers = defaultdict(list)
    for card in cards:
        duplicate_numbers[card.number].append(card.suit)
    duplicate_numbers = {k: v for k, v in duplicate_numbers.items() if len(v) >= 2}
    return duplicate_numbers



class Card:
    def __init__(self, card):
        self._suit = card[0]
        self._number = int(card[1])
    
    def __str__(self):
        return self.card
    
    def __lt__(self, other):
        return self._number < other._number
        
    @property
    def card(self):
        return self._suit + str(self._number)
    
    @property
    def number(self):
        return self._number
    @property
    def suit(self):
        return self._suit
        
nums_card = int(input())
cards = list(map(Card, input().split()))
duplicate_cards =  find_card_order(cards)
bubble_sorted = bubble_sort(cards)
selection_sorted = selection_sort(cards)


print_cards(bubble_sorted)

stable = 'Stable'
for k, v in duplicate_cards.items():
    sorted_order = [card.suit for card in bubble_sorted if card.number == k]
    if duplicate_cards[k] != sorted_order:
        stable = 'Not stable'
print(stable)

print_cards(selection_sorted)
stable = 'Stable'
for k, v in duplicate_cards.items():
    sorted_order = [card.suit for card in selection_sorted if card.number == k]
    if duplicate_cards[k] != sorted_order:
        stable = 'Not stable'
print(stable)

Submission status: Accepted

Solution code:
from collections import namedtuple


Card = namedtuple('Card', 'suit value')
Card.__str__ = lambda self: self.suit + str(self.value)


def printcards(cards):
    print(' '.join([str(c) for c in cards]))


def bubblesort(it, key):
    it = list(it)
    for start_ind in range(len(it)):
        for target_ind in range(len(it)-1, start_ind, -1):
            target_val = key(it[target_ind])
            compare_val = key(it[target_ind-1])
            if target_val < compare_val:
                it[target_ind], it[target_ind-1] = it[target_ind-1], it[target_ind],
    return it


def selectsort(it, key):
    it = list(it)
    for start_ind in range(len(it)):
        min_ind = start_ind
        for target_ind in range(start_ind, len(it)):
            target_val = key(it[target_ind])
            min_val = key(it[min_ind])
            if target_val < min_val:
                min_ind = target_ind
        it[start_ind], it[min_ind] = it[min_ind], it[start_ind]
    return it


if __name__ == '__main__':
    n = int(input())
    cards = [Card(*suit_val) for suit_val in input().split()]
    cards_bub = bubblesort(cards, key=lambda x: x.value)
    cards_slc = selectsort(cards, key=lambda x: x.value)
    printcards(cards_bub)
    print('Stable')
    printcards(cards_slc)
    print('Stable') if cards_bub == cards_slc else print('Not stable')

Submission status: Accepted

Solution code:
import copy

def is_stable(ax,bx):
    num=[]
    for ix in ax:
        if ix[1] not in num:
            num.append(ix[1])
    for ix in num:
        cx=[]
        for jx in ax:
            if jx[1]==ix:
                cx.append(jx)
        dx=[]
        for jx in bx:
            if jx[1]==ix:
                dx.append(jx)
        if cx!=dx:
            return "Not stable"
    else:
        return "Stable"

def array_print(ar):
    s=""
    for i in range(len(ar)):
        s+=(ar[i][0]+str(ar[i][1]))
        if i!=n-1:
            s+=" "
    return s

n=int(input())
a=[[i[0],int(i[1])]for i in input().split()]
b1=copy.deepcopy(a)
b2=copy.deepcopy(a)

#バブルソート
f=1
while f:
    f=0
    for i in range(n-1):
        if b1[n-i-1][1]<b1[n-i-2][1]:
            b1[n-i-1],b1[n-i-2]=b1[n-i-2],b1[n-i-1]
            f=1
print(array_print(b1))
print(is_stable(a,b1))

#選択ソート
for i in range(n):
    min=i
    for j in range(i+1,n):
        if b2[min][1]>b2[j][1]:
            min=j
    b2[min],b2[i]=b2[i],b2[min]
print(array_print(b2))
print(is_stable(a,b2))

Submission status: Accepted

Solution code:
#coding: utf-8

def printCards(C, N):
    for i in range(N):
        if i > 0:
            print(' ', end = '')
        print(C[i][0], end = '')
    print('')
    return True

n = int(input())
cards0 = map(str, input().split())
cards1 = list()
for i in cards0:
    cards1.append((i, int(i[1])))
cards2 = cards1[:]
del cards0

# BubbleSort
for i in range(n):
    for j in range(n-1, i, -1):
        if cards1[j][1] < cards1[j-1][1]:
            temp = cards1[j]
            cards1[j] = cards1[j-1]
            cards1[j-1] = temp
printCards(cards1, n)
print('Stable')

# SelectionSort
for i in range(n-1):
    minj = i
    for j in range(i+1, n):
        if cards2[j][1] < cards2[minj][1]:
            minj = j
    temp = cards2[i]
    cards2[i] = cards2[minj]
    cards2[minj] = temp
printCards(cards2, n)

for i in range(n):
    if cards1[i] != cards2[i]:
        print('Not stable')
        exit()
print('Stable')

Submission status: Accepted

Solution code:

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

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, N):
            if int(C[j][1]) < int(C[minj][1]):
                minj = j
        C[i], C[minj] = C[minj], C[i]
    return C

C1 = BubbleSort(A[:], N)
C2 = SelectionSort(A[:], N)
print(' '.join(map(str,C1)))
print('Stable')
print(' '.join(map(str,C2)))
if C1 == C2:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
def Bubble_Sort(l,n):
    count = 0
    dec = 0
    
    is_reverse = True
    while is_reverse:
        is_reverse = False
        
        for i in range(n-1-dec):
            if l[i][1] > l[i+1][1]:
                l[i] , l[i+1] = l[i+1], l[i]
                is_reverse = True
                count += 1
        
        dec += 1

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

n = int(input())
A = input().split()
B = A.copy()
Bubble_Sort(B,n)
print(' '.join(B))
print('Stable')

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

Submission status: Accepted

Solution code:
# input
n = int(input())
c_ori = input().split()

# bubble sort
c1 = c_ori[:]
for i in range(n):
    for j in range(n-1, i, -1):
        if c1[j][1] < c1[j-1][1]:
            c1[j-1], c1[j] = c1[j], c1[j-1]
print(*c1)
print('Stable')

# selection sort
c2 = c_ori[:]
for i in range(n):
    minj = i
    for j in range(i, n):
        if c2[j][1] < c2[minj][1]:
            minj = j
    c2[minj], c2[i] = c2[i], c2[minj]
print(*c2)

if c1 == c2:
    print('Stable')
else:
    print('Not stable')