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 makedic(array):
    dic = {str(i): '' for i in range(10)}
    for v in array:
        dic[v[1]] += v[0]
    return dic


def main():
    n = int(input())
    origin = [v for v in input().split()]
    dic_origin = makedic(origin)

    a = origin[:]
    for i in range(n - 1):
        last = n - i - 1
        for j in range(last):
            if int(a[j][1]) > int(a[j + 1][1]):
                a[j], a[j + 1] = a[j + 1], a[j]

    print(' '.join(a))
    print('Stable' if makedic(a) == dic_origin else 'Not Stable')

    b = origin[:]
    for i in range(n):
        m = i
        for j in range(i + 1, n):
            if int(b[j][1]) < int(b[m][1]):
                m = j

        if not m == i:
            b[m], b[i] = b[i], b[m]

    print(' '.join(b))
    print('Stable' if makedic(b) == dic_origin else 'Not stable')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy


def bubbleSort(a, n):
    for i in range(0, 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 selectionSort(a, n):
    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]


n = int(input())
a = list(input().split())
b = copy.deepcopy(a)

bubbleSort(a, n)
print(*a)
print('Stable')

selectionSort(b, n)
print(*b)
print('Stable') if a == b else print('Not stable')

Submission status: Accepted

Solution code:
import copy
def bubble(box,n):
    for i in range(n):
        p=n-1
        while p!=i:
            if box[p][1]<box[p-1][1]:
                box[p],box[p-1]=box[p-1],box[p]
            p -=1
    return box

def selection(box,n):
    for i in range(n):
        mini=i
        for j in range(i,n):
            if box[j][1]<box[mini][1]:
                mini=j
        if box[i][1]>box[mini][1]:
            box[i],box[mini]=box[mini],box[i]
    return box

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

bubble=bubble(A,n)
print(*A)
print("Stable")
selection=selection(B,n)
print(*B)
print("Stable" if A==B else "Not stable")

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(str, input().split()))

import copy
A1 = copy.copy(A)
A2 = copy.copy(A)
# バブルソート
flag = 1
while flag:
    flag = 0
    for j in range(N-1, 0, -1):
        if int(A1[j][1]) < int(A1[j-1][1]):
            # A1[j]とA1[j-1]を交換する
            A1[j], A1[j-1] = A1[j-1], A1[j]
            flag = 1    # このフラグは、逆の隣接要素があるかどうかのフラグ
                        # 一回操作したあとはもう一回全体を走査して、逆の隣接要素があるかを確かめる

# セレクションソート
for i in range(0, N):
    minj = i
    for j in range(i, N): # minjを探す
        if int(A2[j][1]) < int(A2[minj][1]): 
            minj = j
    A2[i], A2[minj] = A2[minj], A2[i]

print(*A1)
print('Stable')
print(*A2)

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

Submission status: Accepted

Solution code:
def main(n):
	a = list(input().split())
	b = list(a)
	c = list(a)
	achk = [[] for _ in range(10)]
	bchk = [[] for _ in range(10)]
	cchk = [[] for _ in range(10)]
	for i in range(n):
		for j in range(n-1, i, -1):
			if int(b[j][1]) < int(b[j-1][1]):
				b[j], b[j-1] = b[j-1], b[j]
	print(" ".join(b))
	print("Stable")
	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]
	print(" ".join(c))
	if c == b:
		print("Stable")
	else:
		print("Not stable")

main(int(input()))

Submission status: Accepted

Solution code:
#! /usr/bin/python
# -*- coding: utf-8 -*-
# ALDS1_2_C: Stable Sort

import copy

def BubbleSort(A, N):
    minj = 0
    tmp = 0
    flag = 1

    for i in range(1, N):
        for j in reversed(range(i, N)):
            if A[j][1] < A[j-1][1]:
                tmp = A[j]
                A[j] = A[j-1]
                A[j-1] = tmp
    # while flag:
    #     flag = 0    #数値の転倒があることを表すflagを定義
    #     for i in range(1, N):
    #         j = N - i   #末尾から見ていくための変数jを定義
    #         if A[j][1] < A[j-1][1]:   #転倒があるとき
    #             tmp = A[j]  #この行から下の2行目までで、転倒のある部分を入れ替える
    #             A[j] = A[j-1]
    #             A[j-1] = tmp
    #             flag = 1    #転倒があったことを表すflagを立てる。1度入れ替えたところで他にも入れ替えの必要がある要素がある可能性はあるので、そのためのフラグ。
    return A

def SelectionSort(A, N):
    minj = 0
    tmp = 0
    flag = 1
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if A[j][1] < A[minj][1]:  #一番小さい要素よりも小さいものを記憶する
                minj = j
        tmp = A[i]  #一番小さい要素とi番目の要素を入れ替え
        A[i] = A[minj]
        A[minj] = tmp
        
    return A

def isStable(list1, list2, N):
    for i in range(0, N):
        if list1[i][0] != list2[i][0]:
            print("Not stable")
            return 0
    print("Stable")
    return 0

if __name__ == "__main__":
    N=int(input()) # 数列の長さ
    A=list(input().split()) # 空白を区切文字として配列に格納
    L1 = copy.deepcopy(A)
    L2 = copy.deepcopy(A)
    # print(id(L1), id(L2))
    A1 = BubbleSort(L1, N)
    A2 = SelectionSort(L2, N)
    print(*A1)
    print("Stable")
    print(*A2)
    isStable(A1, A2, N)

Submission status: Accepted

Solution code:
import copy

def show(C):
    N=len(C)
    for i in range(N):
        if i<N-1:
            print(C[i][0]+str(C[i][1]),end=' ')
        else:
            print(C[i][0]+str(C[i][1]))
    
def BubbleSort(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],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[minj][1])>int(C[j][1]):
                minj=j
        C[i],C[minj]=C[minj],C[i]
    return C

def compare(C1,C2):
    for i in range(1,10):
        l1=[]
        for c in C1:
            if int(c[1])==i:
                l1.append(c)
        l2=[]
        for c in C2:
            if int(c[1])==i:
                l2.append(c)
        for j in range(min(len(l1),len(l2))):
            if l1[j][0]!=l2[j][0]:
                return False
    return True
   
N=int(input())
l=list(input().split())
deck=[]
for c in l:
    deck.append((c[0],c[1]))

deck1=copy.copy(deck)
deck2=copy.copy(deck)

deck1=BubbleSort(deck1,N)
deck2=SelectionSort(deck2,N)

show(deck1)
compare(deck,deck1)
print('Stable' if compare(deck,deck1) else 'Not stable')
show(deck2)
print('Stable' if compare(deck,deck2) else 'Not stable')

Submission status: Accepted

Solution code:
# coding: utf-8

def returnInt(x):
    return int(x[-1])

def bubbleSort(A, N):
    flag = 1
    while flag:
        flag = 0
        for i in range(N - 1, 0, -1):
            if returnInt(A[i]) < returnInt(A[i - 1]):
                A[i], A[i - 1] = A[i - 1], A[i]
                flag = 1
    print(' '.join(A))
    return A

def selectionSort(A, N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if returnInt(A[j]) < returnInt(A[minj]):
                minj = j
        A[i], A[minj] = A[minj], A[i]
    print(' '.join(A))
    return A

if __name__ == "__main__":
    N = int(input())
    A = input().split()
    B = [i for i in A]

    A_bubble = bubbleSort(A, N)
    print('Stable')
    A_selection = selectionSort(B, N)
    if A_bubble == A_selection:
        print('Stable')
    else:
        print('Not stable')

Submission status: Accepted

Solution code:
import copy

class Card:
    def __init__(self, str):
        self.mark = str[0]
        self.number = int(str[1:])
        
    def __str__(self):
        return self.mark + str(self.number)
        
n = int(input())
card_list = [Card(c) for c in input().split()]

# Bubble Sort
def bubble_sort(a):
    a = copy.copy(a)
    n = len(a)
    for i in range(n):
        for j in range(0, n-i-1):
            if a[j].number > a[j+1].number:
                a[j], a[j+1] = a[j+1], a[j]
    return a

sorted_card_list1 = bubble_sort(card_list)
print(" ".join([str(c) for c in sorted_card_list1]))
print("Stable")

# Selection Sort
def selection_sort(a):
    a = copy.copy(a)
    n = len(a)
    for i in range(n):
        min_index = i
        for j in range(i+1, n):
            if a[j].number < a[min_index].number:
                min_index = j
        if i != min_index:
            a[i], a[min_index] = a[min_index], a[i]
    return a

sorted_card_list2 = selection_sort(card_list)
is_stable = sorted_card_list1 == sorted_card_list2
print(" ".join([str(c) for c in sorted_card_list2]))
print("Stable" if is_stable else "Not stable")

Submission status: Accepted

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

BC = [0] * N
SC = [0] * N

#boubblesort
for i in range(N):
    BC[i] = C[i]
    SC[i] = C[i]
for i in range(N):
    for j in range(N-1, i, -1):
        if int(BC[j][1]) < int(BC[j-1][1]):
            BC[j], BC[j-1] = BC[j-1], BC[j]

print(' '.join(list(map(str, BC))))
print("Stable")

#Selectionsort

for i in range(N):
    minj = i
    for j in range(i, N):
        if int(SC[j][1]) < int(SC[minj][1]):
            minj = j
    SC[minj], SC[i] = SC[i], SC[minj]
    
print(' '.join(list(map(str, SC))))
if SC == BC:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
def BubbleSort(N, A):
    for i in range(N):
        flag = True
        while flag:
            flag = False
            for j in range(1, N):
                if int(A[j][1]) < int(A[j - 1][1]):
                    A[j], A[j - 1] = A[j - 1], A[j]
                    flag = True


def SelectionSort(N, A):
    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]


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


N = int(input())
A = [str(i) for i in input().split()]


A1 = A.copy()

BubbleSort(N, A)
trace(A)
print('Stable')

SelectionSort(N, A1)
trace(A1)

same = True
for i in range(N):
    if A[i] != A1[i]:
        same = False
if same:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
import copy
def isStable(n,n_old):
  for i in range(len(n)-1):
    for j in range(i+1,len(n),+1):
      for a in range(len(n)-1):
        for b in range(a+1,len(n),+1):
          if n[i][1]==n[j][1]:
            if n[i]==n_old[b] and n[j]==n_old[a]:
              return 'Not stable'
  return 'Stable'
  
m=int(input())
n=list(map(str,input().split()))
n_old=copy.deepcopy(n)

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

print(' '.join(map(str, n)))
print(isStable(n,n_old))

n=copy.deepcopy(n_old)

for i in range(len(n)-1):
  minj=i
  cnt=0
  for j in range(i+1,len(n)):
    if n[j][1]<n[minj][1]:
      minj=j
      cnt=1
  if cnt==1:
    n[i],n[minj]=n[minj],n[i]

print(' '.join(map(str, n)))
print(isStable(n,n_old))

Submission status: Accepted

Solution code:
# ALDS1_2_C - Stable Sort
def main():
    N, *A = open(0).read().split()
    N = int(N)
    B = A.copy()
    # bubble sort
    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]
    print(*A)
    print("Stable")

    # selection sort
    for i in range(N):
        mi = i
        for j in range(i, N):
            if B[j][1] < B[mi][1]:
                mi = j
        B[i], B[mi] = B[mi], B[i]
    print(*B)
    flg = B == A
    print("Stable" if flg else "Not stable")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def bubble(A0):
    A = A0.copy()
    N = len(A)
    flag = True
    while(flag):
        flag = False
        for i in range(N-1):
            if A[i][1] > A[i+1][1]:
                A[i], A[i+1] = A[i+1], A[i]
                flag = True
    return A

def select(A0):
    A = A0.copy()
    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
        if i != minj:
            A[i], A[minj] = A[minj], A[i]
    return A

if __name__ == '__main__':
    N = int(input())
    A = list(map(str, input().split()))
    A_sort = bubble(A)
    print(*A_sort)
    
    flag = True
    for i in range(N-1):
        if A_sort[i][1] == A_sort[i+1][1]:
            if A.index(A_sort[i]) > A.index(A_sort[i+1]):
                flag = False
                break
    if flag:
        print('Stable')
    else:
        print('Not stable')
    
    A_sort = select(A)
    print(*A_sort)
    flag = True
    for i in range(N-1):
        if A_sort[i][1] == A_sort[i+1][1]:
            if A.index(A_sort[i]) > A.index(A_sort[i+1]):
                flag = False
                break

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

Submission status: Accepted

Solution code:
N = int(input())
cards = list(input().split())
cards_list = [list(i) for i in cards]

for i in range(N):
	for j in reversed(range(i+1,N)):
		if j<N:
			if int(cards_list[j][1])<int(cards_list[j-1][1]):
				cards_list[j],cards_list[j-1]=cards_list[j-1],cards_list[j]
cards_t =[0 for i in range(N)]
for i in range(N):
	cards_t[i] = "".join(cards_list[i])			
print(" ".join(cards_t))
print("Stable")

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

cards_t =[0 for i in range(N)]
for i in range(N):
	cards_t[i] = "".join(cards_list_1[i])			
print(" ".join(cards_t))
if cards_list == cards_list_1:
	print("Stable")
else:
	print("Not stable")

Submission status: Accepted

Solution code:
import copy
num =int(input())

l = input().split()

def ccompare( p, q):
    return ord(p[1]) - ord(q[1])


def bsort(l):
    a = copy.copy(l)
    for i in range(len(a)):
        for j in reversed(range(i+1,len(a))):
            if ccompare(a[j],a[j-1]) < 0:
                tmp = a[j-1]
                a[j-1] = a[j]
                a[j] = tmp
    return a
def ssort(l):
    b = copy.copy(l)
    for i in range(len(b)):
        minj = i
        for j in range(i,len(b)):
            if ccompare(b[j], b[minj]) < 0:
                minj = j
        tmp = b[minj]
        b[minj] = b[i]
        b[i] = tmp
    return b
    
def show(lst):
    for i in range(len(lst)):
        print(lst[i], end="")
        if i < len(lst)-1:
            print(" ", end="")
        else:
            print()

def complist(s,t):
    for i in range(len(s)):
        if s[i] != t[i]:
            return False
    return True

bres = bsort(l)
sres = ssort(l)
show(bres)
print("Stable")
show(sres)
if complist(bres, sres):
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

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


def bubble_sort():
    for i in range(n):
        for j in reversed(range(i+1, n)):
            num = int(a[j][1])
            num_ = int(a[j-1][1])
            if num < num_:
                a[j], a[j-1] = a[j-1], a[j]
    return a


def selection_sort():
    for i in range(n):
        minv = int(b[i][1])
        mink = i
        for j in range(i, n):
            if int(b[j][1]) < minv:
                minv = int(b[j][1])
                mink = j
        if int(b[i][1]) != minv:
            b[i], b[mink] = b[mink], b[i]
    return b


bubble = bubble_sort()
selection = selection_sort()


def check_stable():
    if selection == bubble:
        return 'Stable'
    else:
        return 'Not stable'


check_selection = check_stable()


print(*bubble)
print('Stable')
print(*selection)
print(check_selection)

Submission status: Accepted

Solution code:
import copy

def Bubble_Sort(n,cards):

	for i in range(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]

def Selection_Sort(n,cards):

	for i in range(n):
		mini = i
		for j in range(i,n):
			if int(cards[j][1]) < int(cards[mini][1]):
				mini = j
		cards[i],cards[mini] = cards[mini],cards[i]

def Print_cards(n,cards):

	for i in range(n-1):
		print(f"{cards[i][0]}{cards[i][1]} ",end='')
	print(f"{cards[n-1][0]}{cards[n-1][1]}")


def isStable(n,original,sorted):

	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 int(original[i][1]) == int(original[j][1]) and original[i] == sorted[b] and original[j] == sorted[a]:
						return False

	return True

def test():

	n = int(input())
	cards_original = input().split()
	cards_for_Bubble = copy.deepcopy(cards_original)
	cards_for_Selection = copy.deepcopy(cards_original)

	Bubble_Sort(n,cards_for_Bubble)
	Print_cards(n,cards_for_Bubble)
	if isStable(n,cards_original,cards_for_Bubble) == True:
		print("Stable")
	else:
		print("Not stable")

	Selection_Sort(n,cards_for_Selection)
	Print_cards(n,cards_for_Selection)
	if isStable(n,cards_original,cards_for_Selection) == True:
		print("Stable")
	else:
		print("Not stable")

if __name__ == "__main__":
	test()

Submission status: Accepted

Solution code:
#安定なソート
N = int(input())
*A, = input().split()

def stableSort(N,A):
    cnum1 = [(a[0], int(a[1:])) for a in A]
    
    #バブルソート
    flag = 1
    i = 0
    while i < N-1:
        for j in range(N-1, i, -1):
            if cnum1[j][1] < cnum1[j-1][1]:
                tmp = cnum1[j]
                cnum1[j] = cnum1[j-1]
                cnum1[j-1] = tmp
        i += 1
    print(' '.join([''.join([cn[0], str(cn[1])]) for cn in cnum1]))
    print('Stable')
    
    #選択ソート
    cnum2 = [(a[0], int(a[1:])) for a in A]
    count = 0
    for i in range(N):
        minj = i
        for j in range(i+1, N):
            if cnum2[j][1] < cnum2[minj][1]:
                minj = j
        if not minj == i:
            tmp = cnum2[i]
            cnum2[i] = cnum2[minj]
            cnum2[minj] = tmp
            count += 1
    print(' '.join([''.join([cn[0], str(cn[1])]) for cn in cnum2]))
    print('Not stable' if cnum1 != cnum2 else 'Stable' )

stableSort(N,A)

Submission status: Accepted

Solution code:
def bubble(A,n):
	A = A.copy()
	for i in range(n):
		for j in range(n-1,i,-1):
			if A[j][1]<A[j-1][1]:
				A[j],A[j-1]=A[j-1],A[j]
	return A

def selection(A,n):	
	A=A.copy()
	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()

C1,C2=bubble(A,n),selection(A,n)

print(' '.join(C1))
print('Stable')
print(' '.join(C2))
flag = 1
for i in range(n):
	if C1[i]!=C2[i]:
		flag=0
if flag:
	print('Stable')
else:
	print('Not stable')

Submission status: Accepted

Solution code:
import copy


# global
cards_origin = []


# function
def BubbleSort(count, cards):
    for i in range(count):
        for j in range(count-1, i, -1):
            if cards[j][1] < cards[j-1][1]:
                cards[j], cards[j-1] = cards[j-1], cards[j]


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

def SuitOrder(cards, numbers):
    for i in range(len(cards)):
        numbers[cards[i][1]].append(cards[i][0])


def IsStable(numbers1, numbers2):
    for i in range(len(numbers1)):
        if numbers1[i] != numbers2[i]:
            return "Not stable"

    return "Stable"



if __name__ == "__main__":

    # 入力
    in_count = int(input())
    in_cards = input().split(" ")

    # 入力されたカードの値を独自の配列に格納 ["suit", number]
    for i in range(in_count):
        cards_origin.append([in_cards[i][0], int(in_cards[i][1])])

    # リストをコピーしておく
    cards_bubble = copy.deepcopy(cards_origin)
    cards_selection = copy.deepcopy(cards_origin)

    # 関数呼び出し
    BubbleSort(in_count, cards_bubble)
    SelectionSort(in_count, cards_selection)

    # 1から9までの数字に対し、絵柄がどの順番で出現するか求め、0-9のリストに格納
    # _originとbubble, _originとselectionでそれぞれ比較する
    order_origin = []
    order_bubble = []
    order_selection = []
    for i in range(10):
        order_origin.append([])
        order_bubble.append([])
        order_selection.append([])

    
    SuitOrder(cards_origin, order_origin)
    SuitOrder(cards_bubble, order_bubble)
    SuitOrder(cards_selection, order_selection)
    

    bubble_is_stable = IsStable(order_origin, order_bubble)
    selection_is_stable = IsStable(order_origin, order_selection)

    # 表示
    for i in range(len(cards_bubble)):
        print("%s%d" % (cards_bubble[i][0], cards_bubble[i][1]), end="")
        if i != len(cards_bubble)-1:
            print(" ", end="")
    print()
    print(bubble_is_stable)


    for i in range(len(cards_selection)):
        print("%s%d" % (cards_selection[i][0], cards_selection[i][1]), end="")
        if i != len(cards_selection)-1:
            print(" ", end="")
    print()
    print(selection_is_stable)

Submission status: Accepted

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

def BubbleSort(C):
    N = len(C)
    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]
    return C

def SelectionSort(C):
    N = len(C)
    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]
    return C

D1 = C[:]
#注：D1 = Cだと参照渡しになる. つまり, D1を変更するとCも変更される
#C[:]を代入すると値渡しになる.
D1 = BubbleSort(D1)
for i in range(N-1):
    print(D1[i], end=" ")
print(D1[N-1])
print("Stable")

D2 = C[:]
D2 = SelectionSort(D2)
for i in range(N-1):
    print(D2[i], end=" ")
print(D2[N-1])
if D1 ==D2:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
import copy
def convert(list):
    res=" ".join(map(str, list))
    return res

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

b=a[:]
s=copy.deepcopy(a)

for i in range(n-1):
    for j in reversed(range(i+1,n)):
        if b[j][1]<b[j-1][1]:
            bj=b[j]
            b[j]=b[j-1]
            b[j-1]=bj
bub=convert(b)
print(bub)
print("Stable")

for k in range(n):
    minl=k
    for l in range(k,n):
        if s[minl][1]>s[l][1]:
            minl=l

    if minl!=k:
        sk=s[k]
        s[k]=s[minl]
        s[minl]=sk

se=convert(s)
print(se)
if s==b:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
#judge stable or not stbale

def printout(array, n):
    output = ""
    for i in range(n - 1):
        output += str(array[i]) + " "
    output += str(array[N - 1])
    print(output)


def bubble_sort(array):
    for i in range(N):
        for j in reversed(range(i+1,N)):
            if (int(array[j-1][1]) > int(array[j][1])):
                #swap
                tmp = array[j]
                array[j] = array[j-1]
                array[j-1] = tmp
    return array


def linearsearch(subarray):
    # return index of minimum array element
    min = int(subarray[0][1])
    min_index = 0;
    for i in range(1,len(subarray)):
        if min > int(subarray[i][1]):
            min = int(subarray[i][1])
            min_index = i
    return min_index


def selection_sort(array):
    index,tmp = 0,0
    for i in range(N):
        index = linearsearch(array[i:]) + i

        if index != i:
            #swap
            tmp = array[index]
            array[index] = array[i]
            array[i] = tmp
    return array


N = int(input())
array = [i for i in input().split()]
array1 = bubble_sort(array[:])
array2 = selection_sort(array[:])
original_array = array[:]

printout(array1,N)
print("Stable")
printout(array2,N)
if array1 == array2:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
def getInput():
    n = int(input())
    a = [i for i in input().split(" ")]
    return n, a

def getNum(s):
    return int(s[1])

def swap(x, y):
    v = x
    x = y
    y = v
    return x, y

def bubbleSort(n, a):
    cnt = 0
    for j in range(n):
        init = True
        for i in range(n-1, -1, -1):
            if init:
                init = False
                continue
            if getNum(a[i]) > getNum(a[i+1]):
                a[i], a[i+1] = swap(a[i], a[i+1])
                cnt += 1
    print(" ".join([str(i) for i in a]))
    return a

def selectionSort(n, a):
    cnt = 0
    for i in range(n):
        id_min = i
        for j in range(i+1, n):
            if getNum(a[j]) < getNum(a[id_min]):
                id_min = j
        if id_min != i:
            a[i], a[id_min] = swap(a[i], a[id_min])
            cnt += 1
    print(" ".join([str(i) for i in a]))
    return a

def checkStability(n, a_sample, a):
    for i in range(n-1):
        flag1 = False
        flag2 = False
        if getNum(a_sample[i]) == getNum(a_sample[i+1]):
            for j in range(n):
                if a[j] == a_sample[i+1]:
                    flag1 = True
                if a[j] == a_sample[i]:
                    flag2 = True
                if (flag1==True)&(flag2==False):
                    print("Not stable")
                    return
    print("Stable")
    return


from copy import deepcopy
N, A = getInput()
a_bs = bubbleSort(deepcopy(N), deepcopy(A))
checkStability(deepcopy(N), deepcopy(a_bs), deepcopy(A))
a_ss = selectionSort(deepcopy(N), deepcopy(A))
checkStability(deepcopy(N), deepcopy(a_ss), deepcopy(A))

Submission status: Accepted

Solution code:
import copy

class Card:
    def __init__(self):
        self.suit = ''
        self.value = 0

def bubbleSort(C, N):
    for i in reversed(range(N)):
        for j in range(i):
            if C[j].value > C[j+1].value:
                C[j], C[j+1] = C[j+1], C[j]

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

def isSame(C1, C2, N):
    for i in range(N):
        if C1[i].suit != C2[i].suit:
            return False
    return True

def main():
    N = int(input())
    list = input().split(" ")
    
    cards1 = []
    for i in range(N):
        card = Card()
        card.suit = list[i][0]
        card.value = int(list[i][1:])
        cards1.append(card)
    cards2 = copy.deepcopy(cards1)

    bubbleSort(cards1, N)
    selectionSort(cards2, N)

    for c in cards1:
        if c == cards1[len(cards1)-1]:
            print(c.suit + str(c.value))
            print("Stable")
        else:
            print(c.suit + str(c.value), end=" ")

    for c in cards2:
        if c == cards2[len(cards2)-1]:
            print(c.suit + str(c.value))
            if isSame(cards1,cards2,N):
                print("Stable")
            else:
                print("Not stable")
        else:
            print(c.suit + str(c.value), end=" ")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
num_inputs = int(input())
l_origin = input().split(' ')

flag = True
l_bubble = l_origin[:]
while flag:
    flag = False
    for i in reversed(range(1, num_inputs)):
        if int(l_bubble[i][-1:]) < int(l_bubble[i - 1][-1:]):
            buf = l_bubble[i]
            l_bubble[i] = l_bubble[i - 1]
            l_bubble[i - 1] = buf
            flag = True
print(' '.join(l_bubble))
print('Stable')

l_selection = l_origin[:]
for j in range(num_inputs):
    mink = j
    for k in range(j, num_inputs):
        if int(l_selection[k][-1:]) < int(l_selection[mink][-1:]):
            mink = k
    if mink != j:
        buf = l_selection[j]
        l_selection[j] = l_selection[mink]
        l_selection[mink] = buf
print(' '.join(l_selection))

is_stable = True

for l in range(num_inputs):
    if l_bubble[l] == l_selection[l]:
        pass
    else:
        is_stable = False
        break

if is_stable:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
import sys
  
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]:
                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 C[j][1] < C[minj][1]:
                minj = j
  
        C[i], C[minj] = C[minj], C[i]
      
    return C
fin = sys.stdin
  
N = int(fin.readline())
A = fin.readline().split()
B = A[:]
  
A = bubble_sort(A, N)
B = selection_sort(B, N)
  
print(" ".join(A))
print("Stable")
  
print(" ".join(B))
if A == B:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
import copy
def bubbleSort(A, N):
    cnt = 0
    flag = 1
    while flag:
        flag = 0
        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]
                flag = 1
                cnt = cnt + 1
    return cnt
 
 
def selectionSort(A, N):
    cnt = 0
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if A[j][1] < A[minj][1]:
                minj = j
        cnt = cnt + int(i != minj)
        A[i], A[minj] = A[minj], A[i]
    return cnt
 
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")