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:
from copy import deepcopy

n = int(input())
ls = list(input().split())
C1 = []
for s in ls:
    C1.append((s[0], s[1]))
C2 = deepcopy(C1)


# bubble_sort: 2d
def bubble_sort(ls):
    n = len(ls)
    for _ in range(n):
        for j in range(n-1):
            if ls[j][1] > ls[j+1][1]:
                ls[j], ls[j+1] = ls[j+1], ls[j]
    return ls


# selection_sort: 2d
def selection_sort(ls):
    n = len(ls)
    for i in range(n):
        minj = i
        for j in range(i, n):
            if ls[j][1] < ls[minj][1]:
                minj = j
        if minj != i:
            ls[i], ls[minj] = ls[minj], ls[i]
    return ls


ans1 = []
ans2 = []
for c in bubble_sort(C1):
    ans1.append(c[0]+c[1])
for c in selection_sort(C2):
    ans2.append(c[0]+c[1])
print(*ans1)
print('Stable')
print(*ans2)
if ans1 == ans2:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
def bubblesort_re(A,N):
    count = 0
    #A[i] > A[i+1]の状態がある→交換する必要がある：flag = True
    #交換する必要が無いとbreak→値の無駄な比較をしない
    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]
        #         count += 1
        #         flag = True
        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]
                count += 1
                flag = True

    return A,count

def min_index(A):
    index = 0
    m = A[0][1]
    for i in range(1,len(A)):
        if A[i][1] < m:
            m = A[i][1]
            index = i

    return index

# def selectionsort(A,N):
#     count = 0
#     for i in range(N-1):
#         j = min_index(A[i+1:])
#         if int(A[i][1]) > int(A[i+j+1][1]):
#             A[i],A[i+j+1] = A[i+j+1],A[i]
#             count += 1
#
#     return A,count

def selectionsort(A,N):
    count = 0
    for i in range(N):
        minj = i
        #最小値を見つけるfor文：O(n)
        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,count

if __name__ == '__main__':
    import copy

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

    X = A.copy()
    s,t = bubblesort_re(X,N)
    for i in range(N):
        if i != N - 1:
            print(s[i],end = " ")
        else:
            print(s[i])
    print("Stable")

    X = A.copy()
    u,v = selectionsort(X,N)
    for i in range(N):
        if i != N - 1:
            print(u[i],end = " ")
        else:
            print(u[i])
    if s == u:
        print("Stable")
    else:
        print("Not stable")

Submission status: Accepted

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

def selection_sort(A,N):
    for i in range(N):
        minj = i
        for j in range(i+1,N):
            if int(A[j][1:])<int(A[minj][1:]):
                minj = j
        if minj != i:
            A[minj],A[i] = A[i],A[minj]
    return A
    
N = int(input())
A = input().split()

A_bubble = bubble_sort(A.copy(), N)
A_select = selection_sort(A.copy(), N)

print(*A_bubble)
print('Stable')
print(*A_select)
if A_select == A_bubble:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
from typing import List


def bubble_sort(A: List[str], N: int) -> List[str]:
    for i in range(N - 1):
        for j in range(N - 1, i, -1):
            if A[j - 1][1] > A[j][1]:
                A[j - 1], A[j] = A[j], A[j - 1]
    return A


def selection_sort(A: List[str], N: int) -> List[str]:
    for i in range(N - 1):
        tmp_min_index: int = i
        for j in range(i + 1, N):
            if A[tmp_min_index][1] > A[j][1]:
                tmp_min_index = j
        A[i], A[tmp_min_index] = A[tmp_min_index], A[i]
    return A


def is_stable(A: List[str], A_sorted: List[str], N: int) -> bool:
    for i in range(N - 1):
        for j in range(i + 1, N):
            # for a in range(N - 1):
            #     for b in range(a + 1, N):
            #         if A[i][1] == A[j][1] and A_sorted[a] == A[j] and A_sorted[b] == A[i]:
            #             return False
            if A[i][1] == A[j][1] and A_sorted.index(A[j]) < A_sorted.index(A[i]):
                return False
    return True


def main():
    N: int = int(input())
    A: List[str] = list(input().split())

    A_bubble = bubble_sort(A[:], N)
    A_selection = selection_sort(A[:], N)

    print(*A_bubble, sep=" ")
    print("Stable")
    print(*A_selection, sep=" ")
    print("Stable") if A_bubble == A_selection else print("Not stable")

    # print("Stable") if is_stable(A, A_bubble,
    #                              N) else print("Not stable")
    # print("Stable") if is_stable(A, A_selection,
    #                              N) else print("Not stable")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class Card:
    def __init__(self, suit, value, order):
        self.suit = suit
        self.value = value
        self.order = order
    def __str__(self):
        return self.suit + str(self.value)

n = int(input())
a = list(input().split())
cards = []
for i in range(n):
    c = Card(a[i][0], int(a[i][1]), i)
    cards.append(c)

c = cards + [] # copy list

# bubble sort
for i in range(n):
    for j in range(n-1, i, -1):
        if c[j].value < c[j-1].value:
            c[j], c[j-1] = c[j-1], c[j]
print(' '.join([str(c1) for c1 in c]))
for i in range(n-1):
    if c[i].value == c[i+1].value and c[i].order >= c[i+1].order:
        print('Not stable')
        break
else:
    print('Stable')

c = cards + [] # copy list

# selection sort
for i in range(n):
    minj = i
    for j in range(i, n):
        if c[j].value < c[minj].value:
            minj = j
    c[i], c[minj] = c[minj], c[i]
print(' '.join([str(c1) for c1 in c]))
for i in range(n-1):
    if c[i].value == c[i+1].value and c[i].order >= c[i+1].order:
        print('Not stable')
        break
else:
    print('Stable')

Submission status: Accepted

Solution code:
import copy
def BubbleSort(N, A):
    A = copy.deepcopy(A)
    for i in range(N-1):
        for j in range(N-1,i,-1):
            if int(A[j-1][1]) > int(A[j][1]):
                A[j-1], A[j] = A[j], A[j-1]
    return A

def SelectSort(N, A):
    A = copy.deepcopy(A)
    for i in range(N-1):
        minidx = i
        for j in range(i+1,N):
            if int(A[j][1]) < int(A[minidx][1]):
                minidx = j
        if minidx != i:
            A[i], A[minidx] = A[minidx], A[i]
    return A

def main():
    n = int(input());  L = input().split()
    B = BubbleSort(n, L)
    S = SelectSort(n, L)
    print(*B); print('Stable')
    print(*S); print('Not stable') if B != S else print('Stable')
main()

Submission status: Accepted

Solution code:
import sys, copy
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    C_tmp = LSS()
    C = [{'suit':'', 'value':0} for _ in range(N)]
    for i in range(N):
        C[i]['suit'] = C_tmp[i][0]
        C[i]['value'] = int(C_tmp[i][1:])

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

    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
            if i!=minj:
                C[i], C[minj] = C[minj], C[i]
        return C

    def isStable(C, C_s):
        isStable = True
        for i in range(1, 10):
            if [j['suit'] for j in C if j['value']==i]!=[j['suit'] for j in C_s if j['value']==i]:
                isStable = False
        ret = 'Stable' if isStable else 'Not stable'
        return ret

    C_bs = BubbleSort(copy.deepcopy(C), N)
    print(*[i['suit']+str(i['value']) for i in C_bs])
    print(isStable(C, C_bs))

    C_ss = SelectionSort(copy.deepcopy(C), N)
    print(*[i['suit']+str(i['value']) for i in C_ss])
    print(isStable(C, C_ss))

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import copy
def BubbleSort(C, N) :
    for i in range(N-1) :
        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 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]
    return(C)

def Stable(A, B, 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 A[i][1] == A[j][1] and A[i] == B[b] and A[j] == B[a] :
                        return "false"
    return "true"

N = int(input())
OrgC = list(map(str, input().split()))
BubC = copy.copy(OrgC)
SelC = copy.copy(OrgC)
print(" ".join(BubbleSort(BubC, N)))
if Stable(OrgC, BubC, N) == "false" :
    print("Not stable")
else :
    print("Stable")

print(" ".join(SelectionSort(SelC, N)))
if Stable(OrgC, SelC, N) == "false" :
    print("Not stable")
else :
    print("Stable")

Submission status: Accepted

Solution code:
def BubbleSort(C,N):
    for i in range(N):
        for j in reversed(range(i+1,N)):
            if C[j][1] < C[j-1][1]:
                sw = C[j]
                C[j] = C[j-1]
                C[j-1] = sw
    print(" ".join(C))

def SelectionSort(C,N):
    for i in range(N):
        minj = i
        for j in range(i,N):
            if C[j][1] < C[minj][1]:
                minj = j
        sw = C[i]
        C[i] = C[minj]
        C[minj] = sw
    print(" ".join(C))

n = int(input())
cardlistB = [x for x in input().split()]
cardlistS = []

for c in cardlistB:
    cardlistS.append(c)

BubbleSort(cardlistB,n)

print("Stable")

SelectionSort(cardlistS,n)

if cardlistB == cardlistS:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
n = int(input())
R = [x for x in input().split()]#リスト内包表記
R2=R.copy()

def selected_sort(a,n):
    for i in range(0,n-1):#一個前までやれば全てソートが完了する
        minj=i#未ソート部の先頭をminとみなす
        for j in range(i,n):
            if a[j][1]<a[minj][1]:#
                minj=j#最小インデックスの更新
                judge=True#インデックスが更新されたかどうかの判定
        a[i],a[minj]=a[minj],a[i]#最小値と未ソートの先頭をswap
    print(*a)

def bubble_sort(r,n):
    flag=True
    i=0
    count=0
    while flag:
        flag=False
        for i in range(n-1,i,-1):#iは1でとまらないとi-1が-1となってしまう
            if r[i][1]<r[i-1][1]:
                r[i],r[i-1]=r[i-1],r[i]#swap
                count+=1
                flag=True#入れ替える条件があって初めてtrueになる
    print(*r)

def isStable(a,b):
    if R==R2:
        print("Stable")
    else:
        print("Not stable")


bubble_sort(R,n)
print("Stable")

selected_sort(R2,n)
isStable(R,R2)

Submission status: Accepted

Solution code:
n = int(input())
C = list(map(str,input().split()))
data = [[] for i in range(9)]
for i in C:
    data[int(i[1])-1].append(i[0])
D = [s for s in C]
#print(data)
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]
print(" ".join(C))
flag = True
for i in range(9):
    if len(data[i]) >= 2:
        for j in range(len(data[i])-1):
            if C.index(data[i][j]+"{}".format(i+1)) > C.index(data[i][j+1]+"{}".format(i+1)):
                print("Not stable")
                flag = False
                break
        if not flag:
            break
else:
    print("Stable")
for i in range(n):
    minj = i
    for j in range(i,n):
        if int(D[j][1]) < int(D[minj][1]):
            minj = j
    else:
        D[i],D[minj] = D[minj],D[i]
print(" ".join(D))
flag = True
for i in range(9):
    if len(data[i]) >= 2:
        for j in range(len(data[i])-1):
            if D.index(data[i][j]+"{}".format(i+1)) > D.index(data[i][j+1]+"{}".format(i+1)):
                print("Not stable")
                flag = False
                break
        if not flag:
            break
else:
    print("Stable")

Submission status: Accepted

Solution code:
import copy
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
        if i != mini:
            tmp = a[i]
            a[i] = a[mini]
            a[mini] = tmp
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]:
                tmp = a[j]
                a[j] = a[j-1]
                a[j-1] = tmp

n = int(input())
a = list(input().split())
item = []
for i in a:
    item.append([i[0],int(i[1])])
a1 = copy.copy(item)
BubbleSort(a1)
ans1 = []
for i in a1:
    s = i[0] + str(i[1])
    ans1.append(s)
print(*ans1)
print("Stable")
a2 = copy.copy(item)
SelectionSort(a2)
ans2 = []
for i in a2:
    s = i[0] + str(i[1])
    ans2.append(s)
print(*ans2)
if ans1 == ans2:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
n = int(input())
A = [x for x in input().split()]
B = A.copy()
for i in range(n):
    for j in range(i+1,n)[::-1]:
        if A[j][1] < A[j-1][1]:
            A[j],A[j-1] = A[j-1],A[j]

print(*A)
print("Stable")

for i in range(n):
    minj = i
    for j in range(i,n):
        if B[j][1] < B[minj][1]:
            minj = j
    if minj != i:
        B[i],B[minj] = B[minj],B[i]
    
print(*B)

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

Submission status: Accepted

Solution code:
import copy

def BubbleSort(card):
    card_b = []
    card_b = copy.deepcopy(card)
    for i in range(len(card_b)-1):
        j = len(card_b)-1
        while i+1 <= j:
            if list(card_b[j])[1] < list(card_b[j-1])[1]:
                w = card_b[j]
                card_b[j] = card_b[j-1]
                card_b[j-1] = w
            j -= 1
    return card_b

def SelectionSort(card):
    card_s = []
    card_s = copy.deepcopy(card)
    for i in range(len(card_s)-1):
        mini = i
        j = i
        while len(card_s)-1 >= j:
            if list(card_s[j])[1] < list(card_s[mini])[1]:
                mini = j
            j += 1
        w = card_s[i]
        card_s[i] = card_s[mini]
        card_s[mini] = w
    return card_s

def CardPrint(card):
    i = 0
    for c in card:
        if i != n-1:
            print("{} ".format(c), end="")
        elif i == n-1:
            print(c)
        i += 1


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

r1 = []
r1 = BubbleSort(card)
CardPrint(r1)
print("Stable")

r2 = []
r2 = SelectionSort(card)
CardPrint(r2)
if r1 == r2:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
import copy
N = int(input())
C = input().split()
D = copy.copy(C)
for i in range(N):
    for j in range(i+1,N):
        k = N-j+i
        if int(C[k][1]) < int(C[k-1][1]):
            dummy = C[k]
            C[k] = C[k-1]
            C[k-1] = dummy

for i in range(N-1):
    print(f"{C[i]}",end =" ")
print(f"{C[N-1]}\nStable")
for i in range(N):
    minj = i
    for j in range(i,N):
        if int(D[j][1]) < int(D[minj][1]):
            minj = j
    dummy = D[i]
    D[i] = D[minj]
    D[minj] = dummy
for i in range(N-1):
    print(f"{D[i]}",end =" ")
flag = 0
for i in range(N):
    if C[i] != D[i]:
        flag = 1
        print(f"{D[N-1]}\nNot stable")
        break
if flag == 0:
    print(f"{D[N-1]}\nStable")

Submission status: Accepted

Solution code:
def BubbleSort(C,N):
    for a in range(0,N-1):
        for b in range(N-1,a,-1):
            if int(C[b][1]) < int(C[b-1][1]):
                C[b],C[b-1] = C[b-1],C[b]

def SelectionSort(C,N):
    for a in range(0,N-1):
        index_min = [x[1] for x in C[(a+1):]].index(min([x[1] for x in C[(a+1):]]))+a+1
        # print(f'{min(A[a+1:])} {index_min}')
        if C[a][1] > C[index_min][1]:
            C[a],C[index_min] = C[index_min],C[a]


N = int(input())
A = input().split()
B = A.copy()

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

SelectionSort(B,N)
print(*B)
if A == B:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

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

print(*a)
print('Stable')

for i in range(n):
    min=i
    for j in range(i,n):
        if b[min][1]>b[j][1]:
            min=j
    b[i],b[min]=b[min],b[i]
print(*b)
if a==b:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
def swap(a, i, j):
    k = a[j]
    a[j] = a[i]
    a[i] = k


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


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
        swap(A, i, minj)


N = int(input())
A = list(input().split())
B = A[:]

bubbleSort(A, N)
print(*A)
print("Stable")
selectionSort(B, N)
print(*B)
if A == B:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
import math
import itertools

def getNum(card: str) -> int:
  return int(card[1])

def checkStable(origin: list, sorted: list) -> str: # Stable or Not stable
  N_origin = [[] for _ in range(9)]
  for item in origin:
    num = getNum(item)
    N_origin[num-1].append(item)

  for item in sorted:
    num = getNum(item)    

    if N_origin[num-1][0] != item:
      return False
    else:
      N_origin[num-1].pop(0)

  return True

def main():
  n = int(input())
  A = list(input().split())
  len_A = len(A)  
  B = list(A)
  C = list(A)

  # bubble sort
  for i in range(len_A): 
    for j in reversed(range(i+1, len_A)):
      if getNum(B[j]) < getNum(B[j-1]):
        tmp = B[j]
        B[j] = B[j-1]
        B[j-1] = tmp

  # select sort
  for i in range(len_A):
    min = i
    for j in range(i, len_A):
      if getNum(C[j]) < getNum(C[min]):
        min = j
    
    if min != i:
      tmp = C[min]
      C[min] = C[i]
      C[i] = tmp

  print(*B) #bubble sort
  if checkStable(A, B):
    print('Stable')
  else:
    print('Not stable')
  print(*C) #select sort
  if checkStable(A, C):
    print('Stable')
  else:
    print('Not stable')

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
def card_encoder(a):
  result = []
  for i in a:
    s = list(map(str,i))
    c_attr = s[0]
    s.pop(0)
    c_num = int(''.join(s))
    result.append([c_attr,c_num])
  return result

def card_encoder2(a):
  result = []
  for i in a:
    s = list(map(str,i))
    s.pop(0)
    c_num = int(''.join(s))
    result.append(c_num)
  return result

def card_decoder(a):
  result = []
  for t in a:
    result.append(t[0] + str(t[1]))
  return result

def bubble_sort(a,n):
  a = card_encoder(a)
  flag = 1
  while flag:
    flag = 0
    for i in range(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
  a = card_decoder(a)
  return a
  
def selection_sort(a,n):
  a = card_encoder(a)
  for i in range(0,n):
    minv = i
    for j in range(i,n):
      if a[j][1] < a[minv][1]:
        minv = j
    if a[i][1] != a[minv][1]:
      temp = a[i]
      a[i] = a[minv]
      a[minv] = temp
  a = card_decoder(a)
  return a

def main():
  num = int(input())
  s = list(input().split())
  bubble1 = bubble_sort(s,num)
  select1 = selection_sort(s,num)
  print(' '.join(bubble1))
  print(is_stable(s,bubble1))
  print(' '.join(select1))
  print(is_stable(s,select1))

def is_stable(a_in, a_out):
  v_in = card_encoder2(a_in)
  n = len(a_in)
  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 v_in[i] == v_in[j] and a_in[i] == a_out[b] and a_in[j] == a_out[a]:
            return 'Not stable'
  return 'Stable'

main()

Submission status: Accepted

Solution code:
n = int(input())
*A, = input().split()
B = A[:]
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")

for i in range(n):
    mj = i
    for j in range(i, n):
        if B[j][1] < B[mj][1]:
            mj = j
    B[i], B[mj] = B[mj], B[i]
print(*B)
if A == B:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
import re

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:        
            ho = A[i]
            A[i] = A[minj]
            A[minj] = ho
    return A
def bubblesort(A,N):
    flag = 1 
    while flag:
        flag = 0
        for j in range(N-1,0,-1):
           if A[j][1] < A[j-1][1]:
                ho = A[j]
                A[j] = A[j-1]
                A[j-1] = ho
                flag = 1
    return A

n = int(input())
a = [i for i in input().split()]
c = a.copy()
e = a.copy()
b = bubblesort(a,n)
for i in range(len(b)):
    if i == len(b)-1:
        print(b[i])
    else:
        print(b[i],end=' ')            
f = sorted(e, key=lambda x:int((re.search(r"[0-9]+", x)).group(0)))
D = 0
for i in range(len(b)):
    if f[i] != b[i]:
        print('Not stable')
        D = 1
        break
if D == 0:
    print('Stable')
d = selectionSort(c,n)
for i in range(len(d)):
    if i == len(d)-1:
        print(d[i])
    else:
        print(d[i],end=' ')            
D = 0
for i in range(len(d)):
    if f[i] != d[i]:
        print('Not stable')
        D = 1
        break
if D == 0:
    print('Stable')

Submission status: Accepted

Solution code:
def chk_stable(re):
    for i in range(N-1):
        re_chk = list()
        re_chk.append(re[i])
        for j in range(i+1, N):
            if int(re[i][1]) == int(re[j][1]):
                re_chk.append(re[j])
        if len(re_chk) >= 2:
            for j in range(1, len(re_chk)):
                if A.index(re_chk[j]) < A.index(re_chk[j-1]):
                    return 'Not stable'
    return 'Stable'


def bubble():
    b_list = [i for i in A]
    flag = True
    while flag:
        flag = False
        for i in reversed(range(1, N)):
            if int(b_list[i][1]) < int(b_list[i-1][1]):
                tmp = b_list[i]
                b_list[i] = b_list[i-1]
                b_list[i-1] = tmp
                flag = True
    print(' '.join(b_list))
    return chk_stable(b_list)


def selection():
    s_list = [i for i in A]
    for i in range(N):
        min_i = i
        for j in range(i, N):
            if int(s_list[min_i][1]) > int(s_list[j][1]):
                min_i = j
        tmp = s_list[i]
        s_list[i] = s_list[min_i]
        s_list[min_i] = tmp
    print(' '.join(s_list))
    return chk_stable(s_list)


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

print(bubble())
print(selection())

Submission status: Accepted

Solution code:
N = int(input())
buble_A = list(map(str,input().split()))
selection_A=list(buble_A)
number=str(''.join(buble_A))
number=list(number[1::2])
number=[int(x) for x in number]
num_B=list(number)
num_S=list(number)

#バブルソート
flg=1
while flg:
    flg=0
    for i in range(N-1,0,-1):
        if num_B[i]<num_B[i-1]:
            num_B[i],num_B[i-1]=num_B[i-1],num_B[i]
            buble_A[i],buble_A[i-1]=buble_A[i-1],buble_A[i]
            flg=1

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

[print(buble_A[x],end=' ') for x in range(N-1)];print(buble_A[N-1]);print('Stable')

[print(selection_A[x],end=' ') for x in range(N-1)];print(selection_A[N-1]); print('Stable') if buble_A == selection_A else print('Not stable')

Submission status: Accepted

Solution code:
n = int(input())
c = input().split()
c = [(int(s[1]), s[0]) for s in c]
d = c.copy()

# BubbleSort
for i in range(0, n):
    for j in [n-k for k in range(1, n-i)]:
        if c[j][0] < c[j-1][0]:
            c[j], c[j-1] = c[j-1], c[j]

ans1 = " ".join([c[i][1] + str(c[i][0]) for i in range(n)])
print(ans1)
print("Stable")

#SelectionSort
for i in range(0, n):
    minj = i
    for j in range(i, n):
        if d[j][0] < d[minj][0]:
            minj = j
    d[i], d[minj] = d[minj], d[i]

ans2 = " ".join([d[i][1] + str(d[i][0]) for i in range(n)])
print(ans2)
if ans2 == ans1:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
def selectionSort(arr):
	icnt = 0
	for i in range(0, len(arr)):
		imin = i
		for j in range(i + 1, len(arr)):
			if arr[j][1] < arr[imin][1]:
				#			if arr[j] < arr[imin]:
				imin = j
		if imin != i:
			arr[i], arr[imin] = arr[imin], arr[i]
			icnt = icnt + 1


def bubbleSort(arr):
	flg = True
	cnt = 0
	while flg:
		flg = False
		for i in range(len(arr) - 1, 0, -1):
			if arr[i][1] < arr[i - 1][1]:
				#			if arr[i] < arr[i - 1]:
				arr[i - 1], arr[i] = arr[i], arr[i - 1]
				cnt = cnt + 1
				flg = True

def combine(arr):
	result = ''
	for i in arr:
		result = result + i[0] + str(i[1]) + ' '
	return result.rstrip(' ')

n = int(input())
a = list(input().split())  # [H4, C9, S4, D2, C3]
# a = list(map(int, input().split()))
b = []  # [[H,4], [C,9], [S,4], [D,2], [C,3]]
for i in range(0, len(a)):
	b.append([a[i][0], int(a[i][1])])
c = b.copy()
# c = b

bubbleSort(b)
result_b = combine(b)

selectionSort(c)
result_s = combine(c)

print(result_b)
print('Stable')

print(result_s)
if result_s == result_b:
	print('Stable')
else:
	print('Not stable')

Submission status: Accepted

Solution code:
import copy
num = int(input())
base_list = list(input().split())
a = copy.copy(base_list)
b = copy.copy(base_list)

for i in range(num):
    for j in reversed(range(i+1,num)):
        if a[j][1] < a[j-1][1]:
            a[j],a[j-1] = a[j-1],a[j]

print(" ".join([str(i) for i in a]))
print('Stable')

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

print(" ".join([str(i) for i in b]))
flg = False
for bubble,sele in zip(a,b):
    if bubble != sele:
        flg = True
        break

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

Submission status: Accepted

Solution code:
from typing import Any,Sequence
import  copy


def selectionSort(A:Sequence, N:int) -> None:

    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

        A[i], A[minj] = A[minj], A[i]



def bubble_sort(A:Sequence, N:int) -> None:

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

                A[j], A[j - 1] = A[j - 1], A[j]


def bool_isStable(C1:Sequence, C2:Sequence, N:int) -> bool:
    for i in range(N):
        if C1[i] != C2[i]:
            return False
    return  True


n = int(input())
B = list(map(str, input().split()))
C1 = n * []
C2 = n * []

C1 = copy.copy(B)
C2 = copy.copy(B)


bubble_sort(C1, n)
selectionSort(C2, n)


print(' '.join(map(str, C1)))
print('Stable')


print(' '.join(map(str, C2)))
if bool_isStable(C1, C2, n) == True:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
import copy

class Card():
    def __init__(self, str):
        self.id = str
        self.sort = str[0]
        self.value = int(str[1])


def selectionSort(A, N):
    for i in range(N-1):
        minj = i
        for j in range(i, N):
            if A[j].value < A[minj].value:
                minj = j
        if i != minj:
            temp = A[i]
            A[i] = A[minj]
            A[minj] = temp

def bubbleSort(l, n):
    flag = 1
    while flag:
        flag = 0
        for i in range(n-1, 0, -1):
            if l[i].value < l[i-1].value:
                temp = l[i]
                l[i] = l[i-1]
                l[i-1] = temp
                flag = 1

def isStable(input, output, N):
    for i in range(N-1):
        for j in range(i+1, N):
            for a in range(N-1):
                for b in range(a+1, N):
                    if input[i].value == input[j].value and input[i] == output[b] and input[j] == output[a]:
                        return False
    return True

N = int(input())
A = list(map(Card, input().split()))
A_b = copy.copy(A)
A_s = copy.copy(A)

bubbleSort(A_b, N)
print(" ".join(map(lambda x: x.id, A_b)))
if isStable(A, A_b, N):
    print("Stable")
else:
    print("Not stable")

selectionSort(A_s, N)
print(" ".join(map(lambda x: x.id, A_s)))
if isStable(A, A_s, N):
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

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

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]
#                 print(C, i, j)
    return C

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

ss = BubbleSort(ss, len(ss))
ss2 = SelectionSort(ss2, len(ss2))
output = [[str(t) for t in row ] for row in ss]
print(" ".join([ "".join(row) for row in output]))
print('Stable')
output = [[str(t) for t in row ] for row in ss2]
print(" ".join([ "".join(row) for row in output]))
if(ss == ss2):
    print('Stable')
else:
    print('Not stable')