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:
class Selection_sort:
    def __init__(self):
        self.swap_num=0
    
    def sort(self,data):
        for i in range(len(data)):
            mini=i
            for j in range(i+1,len(data)):
                if(data[j][1] < data[mini][1]):
                    mini=j
            if(mini!=i):
                data[i],data[mini]=data[mini],data[i]
                self.swap_num+=1


class Bubble_sort:
    def __init__(self):
        self.swap_num=0
    
    def sort(self,list):
        for i in range(len(list)):
            for j in range(i+1,len(list))[::-1]:
                if(list[j][1] < list[j-1][1]):
                    list[j],list[j-1]=list[j-1],list[j]
                    self.swap_num+=1


def stability_judge(sorted,original):
    n=len(sorted)
    j=-1
    x=sorted[0][1]
    for i in range(n):
        if(x!=sorted[i][1]):
            x=sorted[i][1]
            j=-1
        
        while(1):
            j+=1
            if(x==original[j][1]):
                if(sorted[i][0]!=original[j][0]):
                    return 0
                else:
                    break
    return 1


def cards_print(cards):
    newcards=[]
    for card in cards:
        card[1]=str(card[1])
    newcards=["".join(card) for card in cards]    
    print(" ".join(newcards))




n=int(input())
cards=[list(str) for str in input().split()]
for card in cards:
    card[1]=int(card[1])

b_cards=[i for i in cards]
s_cards=[i for i in cards]


bubble_sort=Bubble_sort()
bubble_sort.sort(b_cards)
#x=stability_judge(b_cards,cards)
cards_print(b_cards)

if(stability_judge(b_cards,cards)):
    print("Stable")
else:
    print("Not stable")



selection_sort=Selection_sort()
selection_sort.sort(s_cards)
cards_print(s_cards)
if(stability_judge(s_cards,cards)):
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
def bubbleSort(list_a, n):
    flag = 1
    i = 0
    while flag:
        flag = 0
        for j in list(range(i+1,n))[::-1]:
            if list_a[j][1] < list_a[j-1][1]:
                (list_a[j], list_a[j-1]) = (list_a[j-1], list_a[j])
                flag = 1
    return list_a

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


n = int(input())
list_a_origin = list(map(str, input().split()))
list_a = list_a_origin.copy()
bubbleSort(list_a, n)
list_a_pre = list_a.copy()
print(" ".join(list_a))
bubbleSort(list_a, n)
if list_a_pre == list_a:
    print("Stable")
else:
    print("Not stable")

list_a2 = list_a_origin.copy()
selectionSort(list_a2, n)
list_a_pre2 = list_a2.copy()
print(" ".join(list_a2))
selectionSort(list_a2, n)
if list_a_pre2 == list_a:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

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

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

def ChkIfStable(c1, c2):
    for v in range(1,10):
        a1=[]
        for k1 in c1:
            if k1.value == v: a1.append(k1.suit)
        a2=[]
        for k2 in c2:
            if k2.value == v: a2.append(k2.suit)
        if a1!=a2:
            print('Not stable')
            return
    print('Stable')

def BubbleSort(C):
    for i in range(0, len(C)):
        for j in range(len(C)-1,i,-1):
            if C[j].value < C[j-1].value:
                 C[j], C[j-1] = C[j-1], C[j]
    return C

def SelectionSort(C):
    for i in range(len(C)):
        mini = i
        for j in range(i, len(C)):
            if C[j].value < C[mini].value:
                mini = j
        C[i], C[mini] = C[mini], C[i]
    return C

cc = []
input()
for c in input().split():
    cc.append(Card(c[0], int(c[1])))

bs=BubbleSort(cc[:])
print(' '.join(map(str,bs)))
ChkIfStable(cc, bs)
ss=SelectionSort(cc[:])
print(' '.join(map(str,ss)))
ChkIfStable(cc, ss)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def bubble(a):
    card = a[:]
    size = len(card)
    for i in range(size):
        for j in range(size - 1, i, -1):
            if card[j][1] < card[j - 1][1]:
                card[j], card[j - 1] = card[j - 1], card[j]
    return card


def selection(a):
    card = a[:]
    size = len(card)
    for i in range(size):
        minj = i
        for j in range(i, size):
            if card[j][1] < card[minj][1]:
                minj = j
        if minj != i:
            card[i], card[minj] = card[minj], card[i]
    return card


def is_stable(a, b):
    size = len(a)
    for i in range(size):
        if a[i][0] != b[i][0]:
            return False
    return True


def main():
    n = int(input())
    cards = input().split()
    a = bubble(cards)
    b = selection(cards)

    print(*a)
    print("Stable")
    print(*b)
    print("Stable" if is_stable(a, b) else "Not stable")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy
n = int(input())
A = input().split()
B = copy.deepcopy(A)
C = A[:]
for i in range(n):
    for j in range(n-1, i, -1):
        if int(B[j-1][1]) > int(B[j][1]):
            B[j-1], B[j] = B[j], B[j-1]
print(" ".join(B))
print("Stable")

_min = 0
for i in range(n):
    _min = i
    for j in range(i, n):
        if int(C[j][1]) < int(C[_min][1]):
            _min = j
    C[_min], C[i] = C[i], C[_min]
print(" ".join(C))
if B == C:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


def li_input():
    return [int(_) for _ in input().split()]

def BubbleSort(N, A):

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

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]
            
    return A

def is_stable(A, A_):
    for i in range(len(A_) - 1):
        if A_[i][1] == A_[i + 1][1]:
            j = A.index(A_[i])
            k = A.index(A_[i + 1])
            
            if j > k:
                return "Not stable"
    
    return "Stable"

def main():
    N = int(input())
    A = input().split()

    BA = BubbleSort(N, A[:])
    SA = SelectionSort(N, A[:])

    print(" ".join(list(map(str, BA))))
    print(is_stable(A, BA))
    print(" ".join(list(map(str, SA))))
    print(is_stable(A, SA))


main()

Submission status: Accepted

Solution code:
#70
#ALDS1_2_C
n=int(input())
*temp,=input().split()
a=temp[:]
b=temp[:]
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]

for i in range(n):
    m=i
    for j in range(i,n):
        if b[m][1]>b[j][1]:
            m=j
    if i!=m:
         b[m],b[i]=b[i],b[m]

print(*a)
print('Stable')
print(*b)
if a==b:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
def bubble_sort(a, n):
  for i in range(n-1, 0, -1):
    j = i
    while (j < n) and (a[j][1] < a[j-1][1]):
      tmp = a[j-1]
      a[j-1] =  a[j]
      a[j] = tmp
      j += 1
  return a

def selection_sort(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:
      a[minj], a[i] = a[i], a[minj]
  return a

n = int(input())
input1 = input().split()
a = list(input1)
b = a[:]
a = bubble_sort(a, n)
b = selection_sort(b, n)


#*をつけることでタプル（の中に入れた型）として実行が可能になる　タプルはオブジェクトの変更ができない
print(*a)
print("Stable")
print(*b)

if a == b:
  print("Stable")
else:
  print("Not stable")


#a = b[:]とは何か：リストのindexとobjectをまんまコピー
#print(*aとは) タプルとして出力

Submission status: Accepted

Solution code:
N = int(input())
Numbers = list(input().split())
A = Numbers[::]
for i in range(N):
    for j in range(N - 1, i, -1):
        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')
B = Numbers[::]
for i in range(N):
    minj = i
    for j in range(i, N):
        if int(B[j][1]) < int(B[minj][1]):
            minj = j
    B[i], B[minj] = B[minj], B[i]
print(' '.join(B))
if A == B:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
import copy
n = int(input())
a = input().split()
a_sr = []
a_sr_l = []
for i in range(n-1):
    if a[i][1] not in a_sr_l:
        for j in range(i+1, n):
            if a[i][1] == a[j][1]:
                if a[i][1] not in a_sr_l:
                    a_sr_l.append(a[i][1])
                if len(a_sr) == 0:
                    a_sr.append(a[i][0])
                a_sr.append(a[j][0])
a_b = copy.deepcopy(a)
a_s = copy.deepcopy(a)
# print(a)
# print(a1)
# print(a2)

# Bubble Sort
neighbor = True
while neighbor:
    neighbor = False
    for i in range(n-1, 0, -1):
        if a_b[i][1] < a_b[i-1][1]:
            a_tmp = a_b[i]
            a_b[i] = a_b[i-1]
            a_b[i-1] = a_tmp
            neighbor = True
for i in range(n-1):
    print(a_b[i], end=" ")
print(a_b[n-1])
a_b_s = []
a_b_s_l = []
for _ in a_sr_l:
    for i in range(n):
        if a_b[i][1] == _ and _ not in a_b_s_l:
            for j in range(i+1, n):
                if a_b[i][1] == a_b[j][1]:
                    if a_b[i][1] not in a_b_s_l:
                        a_b_s_l.append(a_b[i][1])
                    if len(a_b_s) == 0:
                        a_b_s.append(a_b[i][0])
                    a_b_s.append(a_b[j][0])

if a_b_s != a_sr:
    print("Not stable")
else:
    print("Stable")
# Selection Sort
# print(a_s)
for i in range(n-1):
    tmp_index = i
    for j in range(i+1, n):
        # 最小の値探索
        # print("# temp", tmp_index, "j", j)
        if a_s[j][1] < a_s[tmp_index][1]:
            tmp_index = j
    if tmp_index != i:
        # 最小と左端入れ替え
        a_tmp = a_s[i]
        a_s[i] = a_s[tmp_index]
        a_s[tmp_index] = a_tmp
for i in range(n-1):
    print(a_s[i], end=" ")
print(a_s[n-1])
a_s_s = []
a_s_s_l = []
for _ in a_sr_l:
    for i in range(n):
        if a_s[i][1] == _ and _ not in a_s_s_l:
            for j in range(i+1, n):
                if a_s[i][1] == a_s[j][1]:
                    if a_s[i][1] not in a_s_s_l:
                        a_s_s_l.append(a_s[i][1])
                    if len(a_s_s) == 0:
                        a_s_s.append(a_s[i][0])
                    a_s_s.append(a_s[j][0])
# print("a_s_s", a_s_s)
# print("a_sr", a_sr)
if a_s_s != a_sr:
    print("Not stable")
else:
    print("Stable")

Submission status: Accepted

Solution code:
def bubble_sort(sequence):
    for i in range(len(sequence)):
        for j in range(len(sequence)-1, i, -1):
            if int(sequence[j-1][1]) > int(sequence[j][1]):
                sequence[j], sequence[j-1] \
                    = sequence[j-1], sequence[j]
    return sequence


def selection_sort(sequence):
    for i in range(len(sequence)):
        mini = i
        for j in range(i, len(sequence)):
            if int(sequence[j][1]) < int(sequence[mini][1]):
                mini = j
        sequence[i], sequence[mini] = sequence[mini], sequence[i]
    return sequence   


def main():
    input()
    cards = input().split()
    bubble = bubble_sort(cards[:])
    selection = selection_sort(cards[:])
    stable = sorted(cards, key=lambda card: int(card[1]))
    print(' '.join(bubble))
    print('Stable' if bubble == stable else 'Not stable')
    print(' '.join(selection))
    print('Stable' if selection == stable else 'Not stable')


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def val(card):
    return int(card[1])

def bubble_sort(A, N):
    x = A.copy()
    for i in range(N):
        for j in range(N-1, i, -1):
            if val(x[j]) < val(x[j-1]):
                x[j], x[j-1] = x[j-1], x[j]
    return x

def selection_sort(A, N):
    x = A.copy()
    for i in range(N):
        mini = i
        for j in range(i, N):
            if val(x[j]) < val(x[mini]):
                mini = j
        x[i], x[mini] = x[mini], x[i]
    return x
    
A_bubble = bubble_sort(A, N)
A_selection = selection_sort(A, N)

print(' '.join(map(str, A_bubble)))
print("Stable")
print(' '.join(map(str, A_selection)))
if A_bubble == A_selection:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
def SelectionSort(A):
    n = len(A)
    for i in range(n-1):
        mini = i
        for j in range(i+1, n):
            if int(A[j][1]) < int(A[mini][1]):
                mini = j
        if i != mini:
            A[i], A[mini] = A[mini], A[i]
    print(' '.join(A))
    return A

def BubbleSort(A):
    n = len(A)
    for i in range(n):
        for j in range(n-1, i, -1):
            if int(A[j][1]) < int(A[j-1][1]):
                A[j], A[j-1] = A[j-1], A[j]
    print(' '.join(A))
    return A

_ = input()
lines = input().split()
a = BubbleSort(lines.copy())
print('Stable')
b = SelectionSort(lines.copy())
ans = 'Stable' if a == b else 'Not stable'
print(ans)

Submission status: Accepted

Solution code:
def b_sort(alist):
    for i in range(len(alist)):
        for j in range(len(alist)-1, i, -1):
            if alist[j][1] < alist[j-1][1]:
                alist[j], alist[j-1] = alist[j-1], alist[j]
        alist[i] = alist[i][0] + alist[i][1]
    return ' '.join(alist)


def s_sort(alist):
    for x in range(len(alist)):
        currentmin = x
        for y in range(x+1, len(alist)):
            if alist[y][1] < alist[currentmin][1]:
                currentmin = y
        if x != currentmin:
            alist[x], alist[currentmin] = alist[currentmin], alist[x]
        alist[x] = alist[x][0] + alist[x][1]
    return ' '.join(alist)


if __name__ == '__main__':
    N = int(input())
    alist = [list(x) for x in list(input().split())]
    clist = alist.copy()
    ans_b = b_sort(alist)
    ans_s = s_sort(clist)
    print(ans_b)
    print('Stable')
    print(ans_s)
    print('Stable' if ans_b == ans_s else "Not stable")

Submission status: Accepted

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

    return cards

def selection_sort(cards, n):
    for i in range(n):
        minj = i

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

        if i != minj:
            cards[i], cards[minj] = cards[minj], cards[i]

    return cards

def is_stable(cards, sorted_cards):
    hashed = {}

    for m, v in cards:
        if v not in hashed:
            hashed[v] = []

        hashed[v].append((m, v))

    for sm, sv in sorted_cards:
        if hashed[sv][0] != (sm, sv):
            return False

        hashed[sv] = hashed[sv][1:]

    return True

def print_cards(cards, sorted_cards):
    print(' '.join([card[0]+str(card[1]) for card in sorted_cards]))

    if is_stable(cards, sorted_cards):
        print('Stable')
    else:
        print('Not stable')

def main():
    n = int(input())
    cards = [(card[0], int(card[1])) for card in input().split()]

    sorted_cards = bubble_sort(cards[:], n)
    print_cards(cards, sorted_cards)

    sorted_cards = selection_sort(cards[:], n)
    print_cards(cards, sorted_cards)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy
def BubbleSort(A):
    C = copy.deepcopy(A)
    N = len(A)
    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(A):
    C = copy.deepcopy(A)
    N = len(A)
    for i in range(N):
        min_temp = i
        for j in range(i, N, 1):
            if int(C[j][1]) < int(C[min_temp][1]):
                min_temp = j
        C[min_temp], C[i] = C[i], C[min_temp]
    return C

def isStable(A, B):
    N = len(A)
    M = len(B)
    for i in range(N):
        for j in range(i+1, N, 1):
            for x in range(M):
                for y in range(x+1, M, 1):
                    if A[i][1] == A[j][1] and A[i] == B[y] and A[j] == B[x]:
                        return 'Not stable'
    else:
        return 'Stable'

N = int(input())
cards = input().split()
result1 = ' '.join(BubbleSort(cards))
result2 = ' '.join(SelectionSort(cards))
print(result1)
print(isStable(cards, BubbleSort(cards)))
print(result2)
print(isStable(cards, SelectionSort(cards)))

Submission status: Accepted

Solution code:
import copy
N = int(input())
Cards1 = list(map(str, input().split()))
# リストのコピー
# copyをインポートしてcopy.deepcopy()関数を使う。
Cards2 = copy.deepcopy(Cards1)


# バブルソート: Cards1
for i in range(0, N):
    for j in reversed(range(i+1, N)):
        if int(Cards1[j][1:]) < int(Cards1[j-1][1:]):
            Cards1[j], Cards1[j-1] = Cards1[j-1], Cards1[j]

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

print(*Cards1)
print('Stable')
print(*Cards2)
if Cards1 != Cards2:
    print('Not stable')
else:
    print('Stable')

# バブルソートは安定ソート
# 選択ソートは安定ソートではない

Submission status: Accepted

Solution code:
def bubble_sort(lis, l):
    flag = 1
    while flag:
        flag = 0
        for i in range(l - 1, 0, -1):
            if int(lis[i][1:]) < int(lis[i - 1][1:]):
                ele = lis[i]
                lis[i] = lis[i - 1]
                lis[i - 1] = ele
                flag = 1
    return 'Stable'


def selection_sort(lis, l):
    for i in range(0, l - 1):
        minj = i
        for j in range(i, l):
            if int(lis[j][1:]) < int(lis[minj][1:]):
                minj = j
        ele = lis[i]
        lis[i] = lis[minj]
        lis[minj] = ele

inputs = []
while True:
    try:
        inputs.append(input())
    except(EOFError):
        break

ln = int(inputs[0])
li_1 = list(inputs[1].split())
li_2 = li_1.copy()

stab_1 = bubble_sort(li_1, ln)
stab_2 = selection_sort(li_2, ln)

sortComp = 'Stable' if (li_1 == li_2) else 'Not stable'

print(*li_1)
print(stab_1)
print(*li_2)
print(sortComp)

Submission status: Accepted

Solution code:
def bubble_sort(c, n):
    is_swapped = True
    i = 0
    while is_swapped:
        is_swapped = False
        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
                is_swapped = True
        i += 1


def selection_sort(c, n):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if c[j][1] < c[minj][1]:
                minj = j
        if i != minj:
            tmp = c[i]
            c[i] = c[minj]
            c[minj] = tmp


def make_dict(l):
    result = {}
    for v in l:
        num = v[1]
        if num in result:
            result[num].append(v)
        else:
            result[num] = [v]
    result = {k: v for k, v in result.items() if len(v) >= 2}

    return result


def print_is_stable(before, after):
    is_stable = True
    before_dict = make_dict(before)
    after_dict = make_dict(after)
    for k in before_dict:
        if before_dict[k] != after_dict[k]:
            is_stable = False
            break

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


n = int(input())
a = [i for i in input().split()]
c = a[:]

bubble_sort(c, n)
print(' '.join([str(i) for i in c]))
print_is_stable(a, c)

c = a[:]
selection_sort(c, n)
print(' '.join([str(i) for i in c]))
print_is_stable(a, c)

Submission status: Accepted

Solution code:
n = int(input())
c = list(input().split())
c1, c2 = c[:], c[:]

def bubbleSort():
  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]

def selectionSort():
  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]

bubbleSort()
selectionSort()
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:
# Stable sort
class Card:
    def __init__(self, c):
        self.suit = c[0]
        self.value = int(c[1])
def toi(c):
    return c.value
def toStr(c):
    return c.suit + str(c.value)
def bubble_sort(C,N):
    for i in range(0, N):
        for j in range(N-1,i,-1):
            if C[j].value < C[j-1].value:
                tmp = C[j]
                C[j] = C[j-1]
                C[j-1] = tmp
    return (C,True)
def selection_sort(C,N):
    st = True
    for i in range(0,N):
        minj = i
        for j in range(i,N):
            # ????????§??????????´??????????????????°??????????????§?????????????????????????????????
            if C[j].value < C[minj].value:
                minj = j
        if not i == minj:
            if (list(map(toi, C[i:]))).count(C[i].value) > 1: st = False
            tmp = C[i]
            C[i] = C[minj]
            C[minj] = tmp
    return (C, st)
N = int(input())
C = [Card(i) for i in input().split(' ')]
C1, isstable1 = bubble_sort(C[:],N)
print(' '.join(list(map(toStr, C1))))
if isstable1: print('Stable')
else: print('Not stable')
C2, isstable2 = selection_sort(C[:],N)
print(' '.join(list(map(toStr, C2))))
if isstable2: print('Stable')
else: print('Not stable')

Submission status: Runtime Error

Solution code:
import copy

def print_list(A):
    print(*A, sep=" ")

def swap(a, b):
    return b, a

def val(str):
    return int(str[1])

def is_stable(_in, _out, n):
    for i in range(0, n):
        for j in range(i+1, n):
            for a in range(0, n):
                for b in range(a+1, n):
                    if val(_in[i]) == val(_in[j]) and _in[i] == _out[b] and _in[j] == _out[a]:
                        return False
    return True

def print_stable(_in, _out, n):
    if is_stable(_in, _out, n):
        print("Stable")
    else:
        print("Not Stable")    

def find_minj(A, i, n):
    minj = i
    for j in range(i, n):
        if val(A[j]) < val(A[minj]):
            minj = j
    return minj        

def bubble_sort(A, n):
    A0 = copy.copy(A)
    flg = 1 #逆の隣接要素が存在する
    i = 0
    while flg:
        flg = 0
        for j in range(n-1, i, -1):
            if val(A[j-1]) > val(A[j]):
                A[j-1], A[j] = swap(A[j-1], A[j])
                flg = 1
        i += 1
    print_list(A)
    print_stable(A0, A, n)

def selection_sort(A, n):
    A0 = copy.copy(A)
    for i in range(0, n):
        minj = find_minj(A, i, n)
        if val(A[i]) > val(A[minj]):
            A[i], A[minj] = swap(A[i], A[minj])
    print_list(A)
    print_stable(A0, A, n)

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

bubble_sort(A, n)
selection_sort(B, n)

Submission status: Runtime Error

Solution code:
import copy

def print_list(A):
    print(*A, sep=" ")

def swap(a, b):
    return b, a

def val(str):
    return int(str[1])

def is_stable(_in, _out, n):
    for i in range(0, n):
        for j in range(i+1, n):
            for a in range(0, n):
                for b in range(a+1, n):
                    if val(_in[i]) == val(_in[j]) and _in[i] == _out[b] and _in[j] == _out[a]:
                        return False
    return True

def print_stable(_in, _out, n):
    if is_stable(_in, _out, n):
        print("Stable")
    else:
        print("Not stable")    

def find_minj(A, i, n):
    minj = i
    for j in range(i, n):
        if val(A[j]) < val(A[minj]):
            minj = j
    return minj        

def bubble_sort(A, n):
    A0 = copy.copy(A)
    flg = 1 #逆の隣接要素が存在する
    i = 0
    while flg:
        flg = 0
        for j in range(n-1, i, -1):
            if val(A[j-1]) > val(A[j]):
                A[j-1], A[j] = swap(A[j-1], A[j])
                flg = 1
        i += 1
    print_list(A)
    print_stable(A0, A, n)

def selection_sort(A, n):
    A0 = copy.copy(A)
    for i in range(0, n):
        minj = find_minj(A, i, n)
        if val(A[i]) > val(A[minj]):
            A[i], A[minj] = swap(A[i], A[minj])
    print_list(A)
    print_stable(A0, A, n)

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

bubble_sort(A, n)
selection_sort(B, n)

Submission status: Runtime Error

Solution code:
_ = int(input())
l2 = list(map(int, input().split()))


class Card():
    def __init__(self, card):
        self.card = card
        self.mark = card[0]
        self.number = card[1]
        
    def __lt__(self, other):
        if not isinstance(other, Card):
            return NotImplemented
        return self.number < other.number
    
    def __eq__(self, other):
        if not isinstance(other, Card):
            return NotImplemented
        return self.mark == other.mark and self.number == other.number
        
    def __repr__(self):
        return '{}{}'.format(self.mark, self.number)

    def ls_sort(self):
        return


def BubbleSort(target):
    ls = target.copy()
    flag = 1
    while flag:
        flag = 0
        for i in range(len(ls)-1, 0, -1):
            if ls[i] < ls[i-1]:
                ls[i], ls[i-1] = ls[i-1], ls[i]
                flag = 1
    print(' '.join(map(str, ls)))
    return sorted(ls)


def SelectSort(target):
    ls = target.copy()
    for i in range(len(ls)):
        minj = i
        for j in range(i+1, len(ls)):
            if ls[j] < ls[minj]:
                minj = j
        if ls[i] != ls[minj]:
            ls[i], ls[minj] = ls[minj], ls[i]
    
    print(' '.join(map(str, ls)))
    return sorted(ls)

l2 =  [Card(i) for i in l2]
l2_sort = sorted(l2)
print(l2_sort)


bubble = BubbleSort(l2)
if bubble == l2_sort:
    print('a')
else:
    print('b')

select = SelectSort(l2)
if select == l2_sort:
    print('a')
else:
    print('b')

Submission status: Runtime Error

Solution code:
def bubble(A):
    flag=True;
    n=len(A)
    i=0
    while flag:
        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]
                flag=True
        i+=1

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


n=int(input())
ss=[x for x in input().split()]
ss2=ss.copy()

bubble(ss)
for i in range(len(ss)-1):
    print(ss[i],end=' ')
print(ss[-1])
print('Stable')

selection(ss2)
for i in range(len(ss2)-1):
    print(ss2[i],end=' ')
print(ss2[-1])
if ss=ss2:
    print('Stable')
else:
    print('Not stable')

Submission status: Runtime Error

Solution code:
<?php
fscanf(STDIN, '%d', $N);
$line = trim(fgets(STDIN));
$arr = explode(' ', $line);

$bubbleArr = BubbleSort($arr,$N);
echo(implode(' ',$bubbleArr).PHP_EOL."Stable".PHP_EOL);
$selectionArr = SelectionSort($arr,$N);
echo implode(" ",$selectionArr) . PHP_EOL;
isStable($bubbleArr, $selectionArr);

function BubbleSort($arr,$N)
{
    for ($i = 0; $i<$N; ++$i) {
        for ($j = $N-1; $j>$i; --$j) {
            if ($arr[$j][1] < $arr[$j-1][1]) {
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j - 1];
                $arr[$j - 1] = $tmp;
            }
        }
    }

    return $arr;
}

function SelectionSort($arr, $N){
    for ($i=0; $i<$N; ++$i){
        $mini = $i;
        for ($j=$i; $j<$N; ++$j){
            if ($arr[$j][1] < $arr[$mini][1]){
                $mini = $j;
            }
        }
        if($mini!=$i){
            $tmp = $arr[$i];
            $arr[$i] = $arr[$mini];
            $arr[$mini] = $tmp;
        }
    }
    return $arr;
}

function isStable($bubbleArr, $selectionArr){
    $result = array_diff_assoc($bubbleArr, $selectionArr);
    if(count($result)==0){
        echo("Stable".PHP_EOL);
    } else {
        echo("Not stable".PHP_EOL);
    }
}

Submission status: Runtime Error

Solution code:
class Sort():
	def __init__(self,n,cards):
		self.cards = cards
		self.n = n

	def bubble_sort(self):
		# bubble sort
		flag = 1
		while flag != 0:
			flag = 0
			rev = list(range(1,self.n))
			rev.reverse()
			for j in rev:
				if int(self.cards[j][1]) < int(self.cards[j-1][1]):
					self.cards[j],self.cards[j-1] = self.cards[j-1],self.cards[j]
					flag = 1

	def select_sort(self):
		for i in range(self.n):
			mini = i
			for j in range(i,self.n):
				if int(self.cards[j][1]) < int(self.cards[mini][1]):
					mini = j
			if i != mini:
				self.cards[i],self.cards[mini] = self.cards[mini],self.cards[i]

	def check_stable(self,origin):
		check_org = [["" for i in range(self.n)] for k in range(9)]
		check_sort = [["" for i in range(self.n)] for k in range(9)]
		for i in range(self.n):
			check_org[int(origin[i][1])-1][i] = origin[i][0]
			check_sort[int(self.cards[i][1])-1][i] = self.cards[i][0]
		flag = 0
		for i in range(self.n):
			if "".join(check_org[i]) != "".join(check_sort[i]):
				flag = 1
				break

		if flag == 0:
			print("Stable")
		else:
			print("Not stable")

	def print_card(self):
		for i in range(self.n):
			if i != self.n-1:
				print("%s" % (self.cards[i]),end=" ")
			else:
				print("%s" % (self.cards[i]))

if __name__ == '__main__':
	n = int(input())
	card = input().split()
	card2 = card.copy()
	card_origin = card.copy()
	
	bubble = Sort(n,card)
	bubble.bubble_sort()
	bubble.print_card()
	bubble.check_stable(card_origin)
	
	select = Sort(n,card2)
	select.select_sort()
	select.print_card()
	select.check_stable(card_origin)