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(x):
    x = x + []
    n = len(x)
    for i in range(n):
        for j in range(i+1,n)[::-1]:
            if x[j] % 10 < x[j-1] % 10:
                x[j], x[j-1] = x[j-1], x[j]
    return x

def selection(x):
    x = x + []
    n = len(x)
    for i in range(n):
        mini = i
        for j in range(i, n):
            if x[j] % 10 < x[mini] % 10:
                mini = j
        if i != mini:
            x[i], x[mini] = x[mini], x[i]
    return x
    
def order(x):
    y = []
    for i in range(1,9):
        y.extend([e for e in x if e % 10 == i])
    return y

def output(x):
    for e in x:
        print 'SHDC'[e/10]+str(e % 10),
    print

def check(x, y):
    output(x)
    if y == order(x): 
        print 'Stable'
    else:
        print 'Not stable'
    return

n = input()
x = []
for s in raw_input().split():
    x.append('SHDC'.index(s[0])*10 + int(s[1]))
x0 = order(x)
check(bubble(x), x0)
check(selection(x), x0)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def bubble(cards):
    for i in range(len(cards)):
        for j in range(len(cards)-1, i, -1):
            if cards[j][1] < cards[j-1][1]:
                cards[j], cards[j-1] = cards[j-1], cards[j]


def selection(cards):
    for i in range(len(cards)):
        mini = i
        for j in range(i, len(cards)):
            if cards[j][1] < cards[mini][1]:
                mini = j
        cards[i], cards[mini] = cards[mini], cards[i]


def stable_test(orders, cards):
    for order in orders:
        n = -1
        for c in order:
            p = n
            n = cards.index(c)
            if p > n:
                return False
    return True


stdin.readline()
data1 = stdin.readline().split()
data2 = data1[:]
orders = [[c for c in data1 if c.endswith(str(i))] for i in range(1, 10)]
orders = [o for o in orders if len(c) > 1]

bubble(data1)
print(*data1)
print('Stable' if stable_test(orders, data1) else 'Not stable')

selection(data2)
print(*data2)
print('Stable' if stable_test(orders, data2) else 'Not stable')

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding:utf-8 -*-
from __future__ import print_function
import time
import sys
import io
import re
import math
start = time.clock()

def bubble(cards):
    for i in range(len(cards)):
        for j in range(len(cards)-1, i, -1):
            if cards[j][1]<cards[j-1][1]:
                cards[j],cards[j-1]=cards[j-1],cards[j]

def selection(cards):
    for i in range(len(cards)):
        mini=i
        for j in range(i,len(cards)):
            if cards[j][1]<cards[mini][1]:
                mini=j
        cards[i],cards[mini]=cards[mini],cards[i]

def stable_test(orders,cards):
    for order in orders:
        n=-1
        for c in order:
            p=n
            n=cards.index(c)
            if p>n:
                return False
    return True

sys.stdin.readline()
data1=sys.stdin.readline().split()
data2=data1[:]
orders=[[c for c in data1 if c.endswith(str(i))] for i in range(1,10)]
orders=[o for o in orders if len(c)>1]

bubble(data1)
print(*data1)
print('Stable' if stable_test(orders, data1) else 'Not stable')

selection(data2)
print(*data2)
print('Stable' if stable_test(orders, data2) else 'Not stable')

Submission status: Accepted

Solution code:
def buble(C):
	for i in range(len(C)):
		for j in range(len(C)-1,i,-1):
			if int(C[j][-1]) < int(C[j-1][-1]):
				C[j],C[j-1] = C[j-1],C[j]
	return C
	
def selection(C):
	for i in range(len(C)):
		mini = i
		for j in range(i,len(C)):
			if int(C[j][-1]) < int(C[mini][-1]):
				mini = j
		C[i],C[mini] = C[mini],C[i]
	return C

n = int(raw_input())
card = map(str, raw_input().split())
card1 = card[:]
buble(card);selection(card1)
print " ".join(map(str, card))
print "Stable"
print " ".join(map(str, card1))
print "Stable" if card == card1 else "Not stable"

Submission status: Accepted

Solution code:
n = int(input())
a = input().strip().split()

# bubble sort
b = a[:]
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]

print(' '.join(b))
print('Stable')

# selection sort
for i in range(n):
    mini = i
    for j in range(i, n):
        if a[j][1] < a[mini][1]:
            mini = j
    a[i], a[mini] = a[mini], a[i]
print(' '.join(a))
print('Stable' if a == b else 'Not stable')

Submission status: Accepted

Solution code:
def BubbleSort(n, lst):
    for i in range(n):
        for j in range(n-1, i, -1):
            if lst[j][1] < lst[j-1][1]:
                lst[j-1], lst[j] = lst[j], lst[j-1]
    return lst

def SelectionSort(n, lst):
    for i in range(n):
        minj = i
        for j in range(i+1, n):
            if lst[j][1] < lst[minj][1]:
                minj = j
        if minj != i:
            lst[i], lst[minj] = lst[minj], lst[i]
    return lst

#バブルソートは必ず安定なので１つめのソート結果と比較することで
#O(N)で２つ目のソートの安定性を判定できる
def check(lst1, lst2):
    if lst1 == lst2:
        print("Stable")
    else:
        print("Not stable")

"""
def check(n, lst_o, lst):
    keeper = [[]]*10
    keeper2 = [[]]*10
    for i in range(n):
        keeper[int(lst_o[i][1])] = keeper[int(lst_o[i][1])] + [lst_o[i][0]]
        keeper2[int(lst[i][1])] = keeper2[int(lst[i][1])] + [lst[i][0]]
    if keeper == keeper2:
        print("Stable")
    else:
        print("Not stable")
"""

n = int(input())
lst = input().split()
lst1 = BubbleSort(n, lst.copy())
print(*lst1)
#check(n, lst.copy(), lst1)
print("Stable")
lst2 = SelectionSort(n, lst.copy())
print(*lst2)
check(lst1, lst2)
#check(n, lst.copy(), lst2)

Submission status: Accepted

Solution code:
import copy as cp

n = int(input())
A = [str(x) for x in input().split()]
AS = cp.copy(A)


def bubble(X):
    for i in range(n):
        X[i] = list(X[i])
        X[i][1] = int(X[i][1])

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

    for i in range(n):
        X[i][1] = str(X[i][1])
        X[i] = "".join(X[i])
    return(X)


BA = bubble(A)



def minsort():

    for i in range(n):
        AS[i] = list(AS[i])
        AS[i][1] = int(AS[i][1])

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

        if (minj != i):
            AS[i],AS[minj] = AS[minj],AS[i]

    for i in range(n):
        AS[i][1] = str(AS[i][1])
        AS[i] = "".join(AS[i])

    return(AS)

MA = minsort()


for k in range(n-1):
    print(str(BA[k])+" ",end = "")
print(str(BA[n-1]))
print("Stable")

for k in range(n-1):
    print(str(MA[k])+" ",end = "")
print(str(MA[n-1]))
if (BA == MA):
    print("Stable")
else :
    print("Not stable")

Submission status: Accepted

Solution code:
def BubbleSort(C, N):
    for i in range(N-1):
        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):
        min_j = i
        for j in range(i+1, 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

def isStable(in_list, out_list):
    N = len(in_list)
    for i_in in range(N):
        for j_in in range(i_in+1, N):
            for i_out in range(N):
                for j_out in range(i_out+1, N):
                    if (in_list[i_in][1] == in_list[j_in][1]) and\
                       (in_list[i_in] == out_list[j_out]) and\
                       (in_list[j_in] == out_list[i_out]):
                        return False
    return True

if __name__ == "__main__":
    N = int(input())
    C = list(map(str, input().split()))
    C1 = C.copy()
    C2 = C.copy()
    Bubble_C = BubbleSort(C1, N)
    Selection_C = SelectionSort(C2, N)

    print(*Bubble_C)
    print('Stable')
    print(*Selection_C)
    if Bubble_C == Selection_C:
        print('Stable')
    else:
        print('Not stable')

Submission status: Accepted

Solution code:
n = int(input())
card1 = list(input().split())
card2 = [i for i in card1]
def bubbleSort(c1:list, n:int):
    for i in range(n):
        for j in range(n-1, i, -1):
            if c1[j][1] < c1[j-1][1]:
                c1[j], c1[j-1] = c1[j-1], c1[j]
    return c1

def selectionSort(c2:list, n:int):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if c2[j][1] < c2[minj][1]:
                minj = j
        c2[i], c2[minj] = c2[minj], c2[i]
    return c2

bubblesort = bubbleSort(card1, n)
selectionsort = selectionSort(card2, n)

flag = 0
for i in range(n):
    if bubblesort[i] != selectionsort[i]:
        flag = 1

print(" ".join(bubblesort))
print("Stable")
print(" ".join(selectionsort))
if flag:
    print("Not stable")
else:
    print("Stable")

Submission status: Accepted

Solution code:
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
		if i != minj:
			tmp = A[i]
			A[i] = A[minj]
			A[minj] = tmp

	return A

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

	return A

if __name__ == '__main__':
	n = int(input())
	R = list(map(str, input().split()))
	C = R[:]
	SR = selectionSort(R, n)
	BR = bubbleSort(C, n)

	fStable = SR == BR

	print(" ".join(map(str, BR)))
	print("Stable")
	print(" ".join(map(str, SR)))
	if (fStable == True):
		print("Stable")
	else:
		print("Not stable")

Submission status: Accepted

Solution code:
N = int(input())
SI = list(input().split())
SB = SI.copy()

# bubble sort
for i in range(N):
	for j in range(N - 1, i, -1):
		if SB[j - 1][1] > SB[j][1]:
			x = SB[j - 1]
			SB[j - 1] = SB[j]
			SB[j] = x

# insertion sort
for i in range(N):
	ptr = i
	for j in range(i + 1, N):
		if SI[ptr][1] > SI[j][1]:
			ptr = j
	x = SI[i]
	SI[i] = SI[ptr]
	SI[ptr] = x

# print the answer!
for i in range(N):
	print(SB[i] + " " if i != N - 1 else str(SB[i]) + "\n", end='')
print("Stable")
for i in range(N):
	print(SI[i] + " " if i != N - 1 else str(SI[i]) + "\n", end='')
print("Stable" if SI == SB else "Not stable")

Submission status: Accepted

Solution code:
#愚直な判定
def JudgeStable(inC, outC, N):
    for i in range(N):
        for j in range(i+1, N):
            for a in range(N):
                for b in range(a+1, N):
                    if inC[i][1] == inC[j][1] and inC[i] == outC[b] and inC[j] == outC[a]:
                        return False
    return True

def PrintJudge(judge):
    if judge:
        print('Stable')
    else:
        print('Not stable')
        
def BubbleSort(C, N):
    for i in range(N):
        for j in reversed(range(i+1, N)):
            if C[j-1][1] > C[j][1]:
                C[j-1], C[j] = C[j], C[j-1]
                
def SelectionSort(C, N):
    for i in range(N):
        minj = i
        for j in range(i+1, N):
            if C[minj][1] > C[j][1]:
                minj = j
        C[minj], C[i] = C[i], C[minj]
                
def PrintC(C):
    print(' '.join([''.join([c[0], str(c[1])]) for c in C]))

N = int(input())
C = [[c[0], int(c[1])] for c in input().split()]
C1 = C.copy()
C2 = C.copy()

BubbleSort(C1, N)
SelectionSort(C2, N)

PrintC(C1)
PrintJudge(JudgeStable(C, C1, N))

PrintC(C2)
PrintJudge(JudgeStable(C, C2, N))

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
A = LS()
A_Bub = []
A_Sel = []
for i in range(N):
    A_Bub.append([A[i][0], int(A[i][1]), i])
    A_Sel.append([A[i][0], int(A[i][1]), i])

#BubleSort(C, N)
def BubleSort(C, N):
    for i in range(N):
        for j in range(N - 1, i, -1):
            if C[j][1] < C[j - 1][1]:
                a = C[j]
                b = C[j - 1]
                C[j] = b
                C[j - 1] = a

#SelectionSort(C, N)
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
        a = C[i]
        b = C[minj]
        C[i] = b
        C[minj] = a

def Check(C, N):
    for i in range(1, N):
        if C[i][1] == C[i - 1][1]:
            if C[i][2] < C[i - 1][2]:
                return 'Not stable'
    return 'Stable'
BubleSort(A_Bub, N)
ans_Bub = []
for i in range(N):
    b = [A_Bub[i][0], A_Bub[i][1]]
    ans_Bub.append(''.join(map(str, b)))
print(' '.join(map(str, ans_Bub)))
print(Check(A_Bub, N))


SelectionSort(A_Sel, N)
ans_Sel = []
for i in range(N):
    s = [A_Sel[i][0], A_Sel[i][1]]
    ans_Sel.append(''.join(map(str, s)))
print(' '.join(map(str, ans_Sel)))
print(Check(A_Sel, N))

Submission status: Accepted

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

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

def J(C, C_):
    for i in range(1,len(C_)):
        if int(C_[i-1][1]) == int(C_[i][1]):
            p = C.index(C_[i-1])
            q = C.index(C_[i])
            if q<p:
                return 'Not stable'
    return 'Stable'

N = int(input())
C = list(input().split())
C_B = C.copy()
C_S = C.copy()
CB = BubbleSort(C_B, N)
CS = SelectionSort(C_S, N)

for i in range(len(CB)):
    if i==len(CB)-1:
        print(CB[i])
    else:
        print(CB[i],end=' ')
print(J(C, CB))
for i in range(len(CS)):
    if i==len(CS)-1:
        print(CS[i])
    else:
        print(CS[i],end=' ')
print(J(C, CS))

Submission status: Accepted

Solution code:
import copy

def bubbleSort(A):
    flag = 1
    while flag:
        flag = 0
        for j in range(len(A)-1,0,-1):#こういう書き方なんや……逆順処理
            if int(A[j][1]) < int(A[j-1][1]):
                A[j],A[j-1] = A[j-1],A[j]
                flag += 1
    return A

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

N = int(input())
lst1 = list(input().split())
lst2 =  copy.copy(lst1)
print(" ".join(bubbleSort(lst1)))
print("Stable")
print(" ".join(selectionSort(lst2)))
if lst1 == lst2:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
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
        temp = c[i]
        c[i] = c[minj]
        c[minj] = temp
    return c


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]):
                temp = c[j]
                c[j] = c[j-1]
                c[j-1] = temp
    return c


def is_stable(a, b):
    for i in range(len(a)):
        if a[i] != b[i]:
            print('Not stable')
            return
    print('Stable')


def main():
    n = int(input())
    nums = input().split(' ')
    bubble_nums = [i for i in nums]
    select_nums = [i for i in nums]
    bubble_nums = bubble_sort(bubble_nums, n)
    select_nums = selection_sort(select_nums, n)

    print(' '.join(bubble_nums))
    print('Stable')
    print(' '.join(select_nums))
    is_stable(bubble_nums, select_nums)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(input().split())
A_copy = A[:]

def bubble_sort(N, A):
  flag = 1
  sorted_index = 0
  while flag:
    flag = 0
    for i in range(N-1, sorted_index, -1):  # N-1からソート済みのインデックス番号まで降順
      if A[i][1] < A[i-1][1]:
        temp = A[i]
        A[i] = A[i-1]
        A[i-1] = temp
        flag = 1
    sorted_index += 1

def selection_sort(N, A):
  for i in range(0, N-1):
    minj = i
    for j in range(i+1, N):
      if A[j][1] < A[minj][1]:
        minj = j
    if i is not minj:
      temp = A[i]
      A[i] = A[minj]
      A[minj] = temp

bubble_sort(N, A)
selection_sort(N,A_copy)
print(' '.join(map(str, A)))
print('Stable')
print(' '.join(map(str, A_copy)))
if A == A_copy:
  print('Stable')
else:
  print('Not stable')

Submission status: Accepted

Solution code:
def sep(Nf, Mf):
    mm = [[] for _ in range(9)]
    for m in range(len(Nf)):
        for i in range(9):
            if Nf[m] == i+1:
                mm[i].append(Mf[m])
    return mm


def ssort(L, N, M):
    for i in range(len(N)-1):
        x = N[i+1:].index(min(N[i+1:])) + i + 1
        if N[i] > N[x]:
            L[i], L[x] = L[x], L[i]
            N[i], N[x] = N[x], N[i]
            M[i], M[x] = M[x], M[i]


def bsort(L, N, M):
    for i in range(len(N)-1):
        for j in range(len(N)-1-i):
            if N[j] > N[j+1]:
                L[j], L[j+1] = L[j+1], L[j]
                N[j], N[j+1] = N[j+1], N[j]
                M[j], M[j+1] = M[j+1], M[j]


n = int(input())
L = list(input().split())
N = [int(i[1]) for i in L]
M = [i[0] for i in L]
marks = ['S', 'H', 'C' ,'D']
Lb, Nb, Mb = L[:], N[:], M[:]
bsort(Lb, Nb, Mb)
print(' '.join(Lb))
if sep(N, M) == sep(Nb, Mb):
    print('Stable')
else:
    print('Not stable')

Ls, Ns, Ms = L[:], N[:], M[:]
ssort(Ls, Ns, Ms)
print(' '.join(Ls))
if sep(N, M) == sep(Ns, Ms):
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
def BSort(A,n):
    flag=1
    while flag:
        flag=0
        for i in range(n-1,0,-1):
            if A[i][1]<A[i-1][1]:
                A[i],A[i-1]=A[i-1],A[i]
                flag=1

def SSort(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=A[:]

BSort(A,n)
print(' '.join(A))
print('Stable')
SSort(B,n)
print(' '.join(B))

if A==B:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
def is_stable(A, B, n):
    for i in range(n):
        for j in range(i+1, n):
            if A[i]['value'] == A[j]['value']:
                for a in range(n):
                    for b in range(a+1, n):
                        if A[i] == B[b] and A[j] == B[a]:
                            return False
    return True


def show(Card, n):
    for i in range(n):
        if i != n-1:
            print(Card[i]['suit'] + str(Card[i]['value']), end=' ')
        else:
            print(Card[i]['suit'] + str(Card[i]['value']))


def bubble_sort(A, n):
    Card = A.copy()
    flag = 1
    while flag:
        flag = 0
        for i in range(n-1):
            if Card[i]['value'] > Card[i+1]['value']:
                Card[i], Card[i+1] = Card[i+1], Card[i]
                flag = 1
    show(Card, n)
    return Card


def selection_sort(A, n):
    Card = A.copy()
    for i in range(n-1):
        min_j = i
        for j in range(i+1, n):
            if Card[min_j]['value'] > Card[j]['value']:
                min_j = j
        if min_j != i:
            Card[i], Card[min_j] = Card[min_j], Card[i]
    show(Card, n)
    return Card


def main():
    n = int(input())
    A = list(input().split())
    Card = [
        {'value': int(a[1]), 'suit': a[0]}
        for a in A
    ]
    Card_bubble = bubble_sort(Card, n)
    if is_stable(Card, Card_bubble, n):
        print('Stable')
    else:
        print('Not stable')
    Card_selection = selection_sort(Card, n)
    if is_stable(Card, Card_selection, n):
        print('Stable')
    else:
        print('Not stable')


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
'''
5
H4 C9 S4 D2 C3
'''
N = int(input())
C1 = list(map(str, input().split()))
C2 = [None] * N

for i in range(N):
  C2[i] = C1[i]

def bubble(C, N):
  #count = 0
  for i in range(0, N-1, 1):
    for j in range(N-1, i, -1):
      #print("j:{} C[j-1]:{} C[j]:{}".format(j, C[j-1], C[j]))
      if (int(C[j-1][1]) > int(C[j][1])):
        C[j-1], C[j] = C[j], C[j-1]
        #count += 1
        #print("Swapped. C:{}".format(C))

  print(str(C).replace('[', '').replace(']', '').replace(',', '').replace('\'', ''))
  print("Stable") # because buddle sort is stable sort

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

  print(str(C).replace('[', '').replace(']', '').replace(',', '').replace('\'', ''))

def main():
  bubble(C1, N)
  selection(C2, N)

  if (C1 == C2):
    print("Stable")
  else:
    print("Not stable")

main()

Submission status: Accepted

Solution code:
import sys
import copy

def print_data(data):
    last_index = len(data) - 1
    
    for idx, item in enumerate(data):
        print(item, end='')
        if idx != last_index:
            print(' ', end='')

    print('')

def bubbleSort(data, N):
    for i in range(N):
        j = N -1
        while j >= i+1:
            if data[j][1] < data[j-1][1]:
                hoge = data[j]
                data[j] = data[j-1]
                data[j-1] = hoge
            j -= 1
    return data

def selectSort(data, N):
    for i in range(N):
        mini = i
        for j in range(i, N):
            if data[j][1] < data[mini][1]:
                mini = j
        if i == mini:
            pass
        else:
            hoge = data[mini]
            data[mini] = data[i]
            data[i] = hoge
    
    return data

def isStable(inData, outData, N):
    for i in range(N):
        for j in range(i+1, N):
            if inData[i][1] == inData[j][1]:
                a = outData.index(inData[i])
                b = outData.index(inData[j])
                if a > b :
                    return False
    return True




def main():
    N = int(input())
    data0 = list(input().split())
    data1 = copy.deepcopy(data0)
    data2 = copy.deepcopy(data0)
    
    bubbleData = bubbleSort(data1, N)
    selectData = selectSort(data2, N)
    
    
                  
        
    print_data(bubbleData)
    if isStable(data0, bubbleData, N):
        print('Stable')
    else:
        print('Not stable')
    
        
    print_data(selectData)
    if isStable(data0, selectData, N):
        print('Stable')
    else:
        print('Not stable')

            
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def BubbleSort(A):
    for i in range(len(A)):
        for j in range(len(A)-1,i,-1):  
            
            if A[j][1] < A[j-1][1]:
                # リストの要素の文字列は2次元配列として記憶される
                A[j],A[j-1] = A[j-1],A[j]
    return A

def SelectionSort(A):
    for i in range(len(A)):
        mini = i
        for j in range(i,len(A)):
            if A[j][1] < A[mini][1]:
                mini = j
        A[i],A[mini] = A[mini],A[i]
    return A


N = int(input())
# example for input to array : H4 C9 S4 D2 C3 (from cards)
array = [i for i in input().split()]
array_cp = list(array)

result_bs = BubbleSort(array)
print(*result_bs)
print('Stable') # Bubble sort is stable

result_ss = SelectionSort(array_cp)
print(*result_ss)
if result_ss == result_bs:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
from copy import deepcopy
def bubbleSort(C, N):
    for i in range(N):
        for j in range(N - 1, i, - 1):
            if C[j][1] < C[j - 1][1]:
                C[j], C[j - 1] = C[j - 1], C[j]

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]

N = int(input())
C = list(map(str, input().split()))
C1 = deepcopy(C)
C2 = deepcopy(C)
bubbleSort(C1, N)
selectionSort(C2, N)
O = [[] for _ in range(9)]
for i in range(N):
    j = int(C[i][1]) - 1
    O[j].append(C[i][0])
O1 = [[] for _ in range(9)]
for i in range(N):
    j = int(C1[i][1]) - 1
    O1[j].append(C1[i][0])
O2 = [[] for _ in range(9)]
for i in range(N):
    j = int(C2[i][1]) - 1
    O2[j].append(C2[i][0])
for i in range(N):
    if i == N - 1:
        print(C1[i])
    else:
        print(C1[i], end=' ')
if O == O1:
    print('Stable')
else:
    print('Not stable')
for i in range(N):
    if i == N - 1:
        print(C2[i])
    else:
        print(C2[i], end=' ')
if O == O2:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
n = int(input())
a = list(input().split())
b = a[:]
for i in range(n):
    for j in range(n-1):
        if a[j][1]>a[j+1][1]:
            a[j],a[j+1] = a[j+1],a[j]
    minj = i
    for j in range(i,n):
        if b[minj][1]>b[j][1]:
            minj = j
    b[minj],b[i] = b[i],b[minj]        
print(*a)
print('Stable')
print(*b)
print(['Not s','S'][a==b] + 'table')

Submission status: Accepted

Solution code:
def bblsrt(cards):
    cards1 = cards.copy()
    for i in range(len(cards1)):
        for j in range(len(cards1) - 1, i, -1):
            if cards1[j][1] < cards1[j - 1][1]:
                cards1[j], cards1[j - 1] = cards1[j - 1], cards1[j]
    return cards1


def slcsrt(cards):
    cards2 = cards.copy()
    for i in range(len(cards2)):
        minj = i
        for j in range(i, len(cards2)):
            if cards2[j][1] < cards2[minj][1]:
                minj = j
        cards2[i], cards2[minj] = cards2[minj], cards2[i]
    return cards2


n = int(input())
C = list(input().split())
print(' '.join(bblsrt(C)))
print('Stable')
print(' '.join(slcsrt(C)))
print('Stable' if slcsrt(C) == bblsrt(C) else 'Not stable')

Submission status: Accepted

Solution code:
def val(a):
    return int(a[1:])


def bubble(lst,n):
    for i in range(n):
        for j in range(n-1,i,-1):
            if val(lst[j])<val(lst[j-1]):
                lst[j],lst[j-1]=lst[j-1],lst[j]
    return lst

def selection(lst,n):
    for i in range(n):
        minj=i
        for j in range(i,n):
            if val(lst[j])<val(lst[minj]):
                minj=j
        if i!=minj:
            lst[minj],lst[i]=lst[i],lst[minj]
    return lst

n=int(input())
lst=input().split()
lstc=lst[:]
blst=bubble(lstc,n)
lstc=lst[:]
slst=selection(lstc,n)


print(" ".join(blst))
print("Stable") #バブルソートは安定ソート
print(" ".join(slst))
if slst==blst : print("Stable")
else : print("Not stable")

Submission status: Accepted

Solution code:
input()
C = [[x[0], x[1]] for x in list(input().split())]
D = C.copy()
N = len(C)

# バブルソート
for i in range(0, N-1, 1):
    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

# 選択ソート
for i in range(0, N-1, 1):
    minj = i
    for j in range(i, N, 1):
        if D[j][1] < D[minj][1]:
            minj = j
    tmp = D[i]
    D[i] = D[minj]
    D[minj] = tmp

# バブルソートの結果出力
length = len(C)
for i in range(length):
    if i == length - 1:
        print("".join(C[i]), end="")
    else:
        print("".join(C[i]), end=" ")

print("")
print("Stable")

# 選択ソートの結果出力
for i in range(length):
    if i == length - 1:
        print("".join(D[i]), end="")
    else:
        print("".join(D[i]), end=" ")

print("")
if C == D:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
import copy

n = int(input())
A = list (map(str, input().split()))
B = copy.copy(A) 

def BubbleSort_dict(A, n):
    flag = 1    
    while flag:
        flag = 0
        for i in reversed(range(n-1)):
            if int(A[i][1]) > int(A[i+1][1]):
                a = A[i]
                A[i] = A[i+1]
                A[i+1] = a
                flag = 1
    return A
    
def SelectionSort_dict(A, n):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if int(A[j][1]) < int(A[minj][1]):
                minj = j
        if i != minj:
            a = A[i]
            A[i] = A[minj]
            A[minj] = a
    return A

A1 = BubbleSort_dict(A, n)
A2 = SelectionSort_dict(B, n)

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