Problem:


Stable Sort

Let's arrange a deck of cards. There are totally 36 cards of 4 suits(S, H, C, D) and 9 values (1, 2, ... 9). For example, 'eight of heart' is represented by H8 and 'one of diamonds' is represented by D1.

Your task is to write a program which sorts a given set of cards in ascending order by their values using the Bubble Sort algorithms and the Selection Sort algorithm respectively. These algorithms should be based on the following pseudocode:

BubbleSort(C)
1 for i = 0 to C.length-1
2     for j = C.length-1 downto i+1
3         if C[j].value 

Input

The first line contains an integer N, the number of cards.

N cards are given in the following line. Each card is represented by two characters. Two consecutive cards are separated by a space character.

Output

In the first line, print the arranged cards provided by the Bubble Sort algorithm. Two consecutive cards should be separated by a space character.

In the second line, print the stability ("Stable" or "Not stable") of this output.

In the third line, print the arranged cards provided by the Selection Sort algorithm. Two consecutive cards should be separated by a space character.

In the fourth line, print the stability ("Stable" or "Not stable") of this output.

Constraints

1 ≤ N ≤ 36

Sample Input 1

5
H4 C9 S4 D2 C3

Sample Output 1

D2 C3 H4 S4 C9
Stable
D2 C3 S4 H4 C9
Not stable

Sample Input 2

2
S1 H1

Sample Output 2

S1 H1
Stable
S1 H1
Stable



Sample input:
5
H4 C9 S4 D2 C3


Sample output:
D2 C3 H4 S4 C9
Stable
D2 C3 S4 H4 C9
Not stable

Submission status: Accepted

Solution code:
def bubble_sort(card_list):
    # フラグを使わないので、card_list がどの程度ソート済みかに
    # 関わらず、常に N ^ 2 のオーダーになる。
    for i in range(len(card_list)):
        for j in range(len(card_list)-1, i, -1):
            if int(card_list[j][1]) < int(card_list[j-1][1]):
                card_list[j-1], card_list[j] = card_list[j], card_list[j-1]

def selection_sort(card_list):
    for i in range(len(card_list)):
        minj = i
        for j in range(i+1, len(card_list)):
            if int(card_list[j][1]) < int(card_list[minj][1]):
                minj = j
        
        if minj != i:
            card_list[minj], card_list[i] = card_list[i], card_list[minj]


def is_stable(before, after):
    """ソートが安定だったかどうかを判定する。

    ソート前と後のリスト in, out をとる。リスト中に全く同じカードはないと仮定している。
    """
    for i in range(len(before)):
        for j in range(i+1, len(before)):
            for a in range(len(after)):
                for b in range(a+1, len(after)):
                    if before[i][1] == before[j][1] and before[i] == after[b] and before[j] == after[a]:
                        return False

    return True



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

b_card_list = orig_card_list.copy()
s_card_list = orig_card_list.copy()

bubble_sort(b_card_list)
selection_sort(s_card_list)

print(*b_card_list)
if is_stable(orig_card_list, b_card_list):
    print('Stable')
else:
    print('Not stable')

print(*s_card_list)
if is_stable(orig_card_list, s_card_list):
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
n=int(input())
#A=list(map(int, input().split()))
B=list(input().split())
C=B.copy()

def bubblesort(A,n):
    #print(A)
    count=0
    flag=1
    while flag:
        flag=0
        for j in reversed(range(1,len(A))):
            if int(A[j][1])<int(A[j-1][1]):
                tmp=A[j-1]
                A[j-1]=A[j]
                A[j]=tmp
                flag=1
                count+=1
    return(A,count)

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

#バブルソートの結果と比較する
def isStable(result1, result2):
    if result1 == result2:
        return True
    return False


result1,count1=bubblesort(B,n)
print(" ".join([str(i) for i in result1]))
print("Stable")
result2,count2=selectsort(C,n)
print(" ".join([str(i) for i in result2]))
if isStable(result1, result2) == True:
    print("Stable")
else:
    print("Not stable")

#print(count)

Submission status: Accepted

Solution code:
import copy

n = int(input())
c = input().split()
bubble = copy.copy(c)
select = copy.copy(c)

def BubbleSort(C, N):
    for i in range(0, 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 SelectionSort(C, N):
    for i in range(0, 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

BubbleSort(bubble, n)
SelectionSort(select, n)

print(*bubble)
print("Stable")
print(*select)

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

if isSame(bubble, select):
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
import copy

def show (a,n):
  for i in range(n):
    if i > 0:
      print("",end=" ")
    print(a[i],end="")
  print("")

def selectionSort(a,n):
  for i in range(n):
    minj = i
    for j in range(i,n):
      if a[j][1] < a[minj][1]:
        minj = j
    a[minj],a[i] = a[i],a[minj]
  show(a,n)

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]:
        a[j], a[j-1] = a[j-1],a[j]
  show(a,n)

n = int(input())
a1 = list(input().split())
a2 = copy.copy(a1)

BubbleSort(a1,n)
print("Stable")
selectionSort(a2,n)

for k in range(n):
  if a1[k] != a2[k]:
    print("Not stable")
    exit()

print("Stable")

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = input().split()
    B = A.copy()
    
    A = BubbleSort(A, N)
    print(*A)
    print('Stable')
    B = SelectionSort(B, N)
    print(*B)
    if A == B:
        print('Stable')
    else:
        print('Not stable')

def BubbleSort(A, N):
    count = 0
    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]
                count += 1
    return A

def SelectionSort(A, N):
    count = 0
    
    for i in range(N):
        mini = i
        for j in range(i,N):
            if A[j][1] < A[mini][1]:
                mini = j
        if A[i][1] > A[mini][1]:
            A[i], A[mini] = A[mini], A[i]
            count += 1
    return A

main()

Submission status: Accepted

Solution code:
class Card:
    __slots__ = ["mark", "value"]

    def __init__(self, text):
        self.mark = text[0]
        self.value = int(text[1])

    def __str__(self):
        return f"{self.mark}{self.value}"


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


def SelectionSort(lst):
    lst = lst.copy()
    for i in range(0, len(lst)):
        minj = i
        for j in range(i, len(lst)):
            if lst[j].value < lst[minj].value:
                minj = j
        lst[i], lst[minj] = lst[minj], lst[i]
    return lst

def check_stable(lst):
    for x in range(1, 10):
        if "".join(c.mark for c in lst if c.value == x) != "".join(c.mark for c in C if c.value == x):
            return False
    return True


input()
C = [Card(i) for i in input().split()]
B = BubbleSort(C)
S = SelectionSort(C)
print(" ".join(map(str, B)))
print("Stable" if check_stable(B) else "Not stable")
print(" ".join(map(str, S)))
print("Stable" if check_stable(S) else "Not stable")

Submission status: Accepted

Solution code:
import copy
def bubble(array):
    flag = set()
    for i in range(n):
        for j in range(1, n):
            if (array[j-1][1] > array[j][1]):
                tmp = array[j-1]
                array[j-1] = array[j]
                array[j] = tmp

    return array

def selection(array):
    flag = set()
    for i in range(0, n):
        minimum = i
        for j in range(i, n):
            if (array[j][1] < array[minimum][1]):
                minimum = j
        tmp = array[minimum]
        array[minimum] = array[i]
        array[i] = tmp

    return array

n = int(input())
array = input().split(" ")

for alg in [bubble, selection]:
    thirteen = [[] for _ in range(13)]
    for elmnt in array:
        thirteen[int(elmnt[1])-1].append(elmnt)
    sorted_ary = alg(copy.copy(array))

    sorted13 = [[] for _ in range(13)]
    for elmnt in sorted_ary:
        sorted13[int(elmnt[1])-1].append(elmnt)

    isStable = True
    print(" ".join(sorted_ary))
    for x, y in zip(thirteen, sorted13):
        if (x != y):
            isStable = False
    if isStable:
        print("Stable")
    else:
        print("Not stable")

Submission status: Accepted

Solution code:
#安定なソート
#ようわからん
#バブルソートはどうやっても安定的なことが言いたい？

#バブルソート
def bubble_sort(list, length):
    flag = 1
    while(flag):
        flag = 0
        for j in reversed(range(1, length)):
            if list[j][1] < list[j-1][1]:
                list[j], list[j-1] = list[j-1], list[j]
                flag = 1

    return list

#選択ソート
def selection_sort(list, length):
    for i in range(length):
        minpos = i
        for j in range(i, length):
            if list[minpos][1] > list[j][1]:
                minpos = j

        list[i], list[minpos] = list[minpos], list[i]

    return list

#安定かどうかを判定するために常に安定なソートであるバブルソートと比較する

length = int(input())
cards_ = input().split()
cards = []
cards2 = []

for c in cards_:
    cards.append([c[0], int(c[1:])])
for c in cards_:
    cards2.append([c[0], int(c[1:])])

b_list = bubble_sort(cards, length)
s_list = selection_sort(cards2, length)

result = ''
for b in b_list:
    result += b[0]+str(b[1]) + ' '
print(result[:-1])
print('Stable')

result = ''
for s in s_list:
    result += s[0]+str(s[1]) + ' '
print(result[:-1])

flag = 0
for i in range(len(b_list)):
    if b_list[i] != s_list[i]:
        print('Not stable')
        flag = 1
        break
if flag == 0:
    print('Stable')

Submission status: Accepted

Solution code:
import copy

n = int(input())
c = [[s[0], int(s[1])] for s in input().split()]

# BubbleSort
bub_c = copy.deepcopy(c)
for i in range(n):
    for j in range(n-1, i, -1):
        if bub_c[j][1] < bub_c[j-1][1]:
            bub_c[j], bub_c[j-1] = bub_c[j-1], bub_c[j]

# SelectionSort
sel_c = copy.deepcopy(c)
for i in range(n):
    minj = i
    for j in range(i, n):
        if sel_c[j][1] < sel_c[minj][1]:
            minj = j
    sel_c[i], sel_c[minj] = sel_c[minj], sel_c[i]

shaped_bub = " ".join([c[0] + str(c[1]) for c in bub_c])
shaped_sel = " ".join([c[0] + str(c[1]) for c in sel_c])
print(shaped_bub, "Stable", sep="\n")
if [b[0] for b in bub_c] == [b[0] for b in sel_c]:
    print(shaped_sel, "Stable", sep="\n")
else:
    print(shaped_sel, "Not stable", sep="\n")

Submission status: Accepted

Solution code:
import copy

class StableSort():
    def __init__(self):
        self.N = n
        self.C = copy.copy(c) #こうしないと書き換わってしまう


    def BS(self):
        A = [self.C[i][1] for i in range(self.N)] #数値
        if self.N == 1:
            C = " ".join(self.C)
            return C
        else:
            for i in range(self.N): #比較は常にリストの一番後ろからはじまる
                for j in range(self.N - i - 1):
                    if A[self.N - j - 1] < A[self.N - j - 2]: #常に安定である 
                        A[self.N - j - 1], A[self.N - j - 2] = A[self.N - j - 2], A[self.N - j - 1] 
                        self.C[self.N - j - 1], self.C[self.N - j - 2] = self.C[self.N - j - 2], self.C[self.N - j - 1] 

            C = " ".join(self.C)
            return C


    def SS(self):
        A = [self.C[i][1] for i in range(self.N)] #数値
        if self.N == 1:
            print(self.C[0] + "\n" + "stable")
        else:
            for i in range(self.N - 1):
                A_r = A[i:] #確定してないAの右側の領域
                mini = min(A_r)
                #AとA_rのインデックスは違うので，抜いた左側の分の+iの補正が必要
                mini_index = i + A_r.index(mini) 
                if A[i] > mini:
                    A[i], A[mini_index] = A[mini_index], A[i] 
                    self.C[i], self.C[mini_index] = self.C[mini_index], self.C[i] 

            C = " ".join(self.C) 
            return C

n = int(input())
c = list(input().split()) #トランプ

BS = StableSort().BS()
SS = StableSort().SS()

print(str(BS) + "\n" + "Stable")
if BS != SS:
    print(str(SS) + "\n" + "Not stable")
else:
    print(str(SS) + "\n" + "Stable")

Submission status: Accepted

Solution code:
import re
import copy
n = int(input())
str = input()
Origin = list(str.split())

# bubble sort
A = copy.deepcopy(Origin)   #list はMutableなのでおおもとからコピーすると元も変わる
B = []*n

for i in range(n):
    B.append(int(re.sub("\\D","",A[i])))
flag = 1
i = 0
while flag:
    flag = 0
    for j in range(n-1,i,-1):
        if B[j] < B[j-1]:
            buf1 = B[j-1]
            buf2 = A[j-1]
            B[j-1] = B[j]
            A[j-1] = A[j]
            B[j] = buf1
            A[j] = buf2
            flag = 1
    i += 1

# selection sort
C = copy.deepcopy(Origin)
D = []*n
for i in range(n):
    D.append(int(re.sub("\\D","",C[i])))
for k in range(n):
    min_k = k
    for l in range(k,n):
        if D[l] < D[min_k]:
            min_k = l
    if min_k != k:#未ソートの部分の一番左がMinjの場合には何もしない
        buf1 = D[k]
        buf2 = C[k]
        D[k] = D[min_k]
        C[k] = C[min_k]
        D[min_k] = buf1
        C[min_k] = buf2

for i in range(n):
    if i != n-1:print(A[i],"",end="")
    else: print(A[i])
print("Stable")
for i in range(n):
    if i != n-1:print(C[i],"",end="")
    else: print(C[i])

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

Submission status: Accepted

Solution code:
import copy


class Card:
    def __init__(self, pair):
        self.suit = pair[0]
        self.value = int(pair[1])

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


def bubble_sort(a, n):
    for i in range(0, n):
        for j in range(n-1, i, -1):
            if a[j].value < a[j-1].value:
                a[j], a[j-1] = a[j-1], a[j]


def selection_sort(a, n):
    for i in range(0, n):
        min_j = i
        for j in range(i, n):
            if a[j].value < a[min_j].value:
                min_j = j
        a[i], a[min_j] = a[min_j], a[i]


def equals(cards1, cards2):
    for card1, card2 in zip(cards1, cards2):
        if card1.suit != card2.suit:
            return False
    return True


def main():
    # input
    n = int(input())
    cards1 = list(map(Card, input().split(' ')))
    cards2 = copy.deepcopy(cards1)

    # sort
    bubble_sort(cards1, n)
    selection_sort(cards2, n)

    # output
    print(' '.join(map(str, cards1)))
    print('Stable')
    print(' '.join(map(str, cards2)))
    if equals(cards1, cards2):
        print('Stable')
    else:
        print('Not stable')


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(str,input().split()))
import copy
b=copy.copy(a)
k=copy.copy(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]
for i in range(n):
	mini=i
	for j in range(i,n):
		if int(b[j][1])<int(b[mini][1]):
			mini=j
	b[i],b[mini]=b[mini],b[i]
print(*a)
print("Stable")
print(*b)
r=True
for i in range(n):
	if not r:
		break
	for j in range(i+1,n):
		for aa in range(n):
			for bb in range(aa+1,n):
				if k[i][0]==k[j][0] and k[i]==b[bb] and k[j]==a[aa]:
					r=False
					break
if r==False:
	print("Not stable")
else:
	print("Stable")

Submission status: Accepted

Solution code:
from copy import copy
N, *A = open(0).read().split()
N = int(N)
S = ['S', 'H', 'D', 'C']
T = [0 for _ in range(N)]
for id, s in enumerate(A):
    T[id] = S.index(s[0]) * 9 + int(s[1]) - 1
B, C = copy(T), copy(T)
for i in range(N):
    for j in range(N-1, i, -1):
        if B[j] % 9 < B[j-1] % 9:
            B[j], B[j-1] = B[j-1], B[j]
B = list(map(lambda n: S[n // 9] + str(n % 9 + 1), B))
print(' '.join(B))
print('Stable')
for i in range(N):
    minj = i
    for j in range(i, N):
        if C[j] % 9 < C[minj] % 9:
            minj = j
    if i != minj:
        C[i], C[minj] = C[minj], C[i]
C = list(map(lambda n: S[n // 9] + str(n % 9 + 1), C))
print(' '.join(C))
print('Stable' if B == C else 'Not stable')

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

def bubbleSort(A, N):
    flag = 1
    while flag:
        flag = 0;
        for i in reversed(range(1, N)):
            if A[i-1].value > A[i].value:
                A[i-1], A[i] = A[i] , A[i-1]
                flag = 1;
    showResult(A)
    return A

def selectionSort(A, N):
    for i in range(0, N):
        minj = i
        mink = i
        for j in range(i, N):
            if A[mink].value > A[j].value:
                mink = j
        if minj != mink:
            A[minj], A[mink] = A[mink], A[minj]
    showResult(A)
    return A



def showResult(B):
    for i in range(N-1):
        print(B[i].suit+str(B[i].value), end = " ")
    print(B[N-1].suit+str(B[N-1].value))

def isStable(rawA, sortedA):
    rawDic = listToDic(rawA)
    sortedDic = listToDic(sortedA)
    flag = 1
    for key in rawDic:
        if len(rawDic[key]) >= 2:
            for i in range(len(rawDic[key])-1):
                if rawDic[key][i] != sortedDic[key][i]:
                    
                    flag = 0
    if flag:
        print("Stable")
    else:
        print("Not stable")

def listToDic(raw):
    rawDic = {}
    for i in range(len(raw)):
        if rawDic.get(raw[i].value) != None:
            rawDic[raw[i].value].append(raw[i].suit)
        else:
            rawDic[raw[i].value] = [raw[i].suit]
    return rawDic

N = int(input())
A = list(input().split()) 
B = []
for i in range(0, N):
    B.append(Card(A[i][:1], A[i][1:]))
C = tuple(B)
"""
C = []
for i in range(0, N):
    C.append(Card(A[i][:1], A[i][1:]))
D = []
for i in range(0, N):
    D.append(Card(A[i][:1], A[i][1:]))
E = []
for i in range(0, N):
    E.append(Card(A[i][:1], A[i][1:]))

F = tuple(B)
print(B)
"""

bubbleA = bubbleSort(B.copy(), N)
isStable(B.copy(), bubbleA)
selectionA = selectionSort(B.copy(), N)
isStable(B.copy(), selectionA)

Submission status: Accepted

Solution code:
N = int(input())

card1 = input()
card2 = card1.split()
card3 = card1.split()

for i in range(N-1):
  for j in range(N-1):
    if card2[N-1-j][1] < card2[N-2-j][1]:
      a = card2[N-1-j]
      b = card2[N-2-j]
      card2[N-2-j] = a
      card2[N-1-j] = b

print(" ".join(map(str,card2)))
print("Stable")

for i in range(N):
  minj = i
  for j in range(i,N):
    if card3[j][1] < card3[minj][1]:
      minj = j
  if not card3[i][1] == card3[minj][1]:
    a = card3[i]
    b = card3[minj]
    card3[i] = b
    card3[minj] = a

print(" ".join(map(str,card3)))


if card2 == card3:
  print("Stable")
else:
  print("Not stable")

Submission status: Accepted

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

def selectionSort(C, N):
    count = 0
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if int(C[j][1])<int(C[minj][1]):
                minj = j
        if minj != i:
            (C[i], C[minj]) = (C[minj], C[i])
            count += 1
    print(" ".join(C))

def isStable(C1, C2, N):
    for i in range(N):
        if C1[i] != C2[i]:
            return "Not stable"
    return "Stable"

n = int(input())
card = list(input().split())
card2 = card[:]

bubbleSort(card, n)
print("Stable")
selectionSort(card2, n)
print(isStable(card, card2, n))

Submission status: Accepted

Solution code:
import copy

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


A1 = copy.deepcopy(A)
for i in range(N-1):
    for j in reversed(range(i+1, N)):
        if A1[j][1] < A1[j-1][1]:
            A1[j], A1[j-1] = A1[j-1], A1[j]
print(*A1)
print('Stable')

A2 = copy.deepcopy(A)
for i in range(N-1):
    minj = i
    for j in range(i+1, N):
        if A2[j][1] < A2[minj][1]:
            minj = j
    A2[i], A2[minj] = A2[minj], A2[i]
print(*A2)

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

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

def BubbleSort(aa,n):
    for i in range(n):
        for j in range(i,0,-1):
            if int(aa[j-1][1])<=int(aa[j][1]):break
            aa[j-1],aa[j]=aa[j],aa[j-1]
    return aa

def main():
    n = int(input())
    #aa = list(map(int, input().split()))
    aa=input().split()
    atoi={}
    for i,a in enumerate(aa):
        atoi[a]=i

    sorted_aa=BubbleSort(aa[:],n)
    stable=True
    for a0,a1 in zip(sorted_aa,sorted_aa[1:]):
        if a0[1]==a1[1] and atoi[a0]>atoi[a1]:
            stable=False
    print(*sorted_aa)
    print("Stable") if stable else print("Not stable")

    sorted_aa=SelectionSort(aa[:],n)
    stable=True
    for a0,a1 in zip(sorted_aa,sorted_aa[1:]):
        if a0[1]==a1[1] and atoi[a0]>atoi[a1]:
            stable=False
    print(*sorted_aa)
    print("Stable") if stable else print("Not stable")

main()

Submission status: Accepted

Solution code:
import copy
N = int(input())
A = list(input().split())
C = []
C = copy.deepcopy(A)

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

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


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

Submission status: Accepted

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

def bubbleSort(A, N):
    flag = 1
    
    while flag:
        flag = 0
        for i in range(N-1, 0, -1):
            if A[i][1] < A[i-1][1]:
                temp = A[i]
                A[i] = A[i-1]
                A[i-1] = temp
                flag = 1
    return " ".join(map(str, A))
    
bubbleSort(A, N)
print(bubbleSort(A, N))
print("Stable")

def selectionSort(A, N):
    for j in range(N):
        C = []
        for i in range(N):
            C.append((A[i][1]))
            
        idx = C[j:].index(min(C[j:])) + j
        
        if A[idx][1] < A[j][1]:
            temp = A[j]
            A[j] = A[idx]
            A[idx] = temp

    return " ".join(map(str, A))

print(selectionSort(B, N))
if bubbleSort(A, N) == selectionSort(B, N):
    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, i, -1):
        if A[j][1] < A[j-1][1]:
            A[j], A[j-1] = A[j-1], A[j]

print(*A, sep=' ')
print('Stable')

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

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

Submission status: Accepted

Solution code:
def bubble_sort(arr, n):
    for i in range(n):
        for j in reversed(range(i + 1, n)):
            if arr[j - 1].value > arr[j].value:
                arr[j - 1], arr[j] = arr[j], arr[j - 1]
    return arr


def selection_sort(arr, n):
    for i in range(n):
        min_idx = i
        for j in range(i, n):
            if arr[j].value < arr[min_idx].value:
                min_idx = j
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr


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


def is_stable(stable_arr, target_arr):
    for s, t in zip(stable_arr, target_arr):
        if s.str != t.str:
            return False
    return True


def main():
    n = int(input())
    # cards = ["H4", "C9", "S4", "D2", "C3"]
    cards = input().split()
    arr = [Card(card_str) for card_str in cards]
    # n = 5
    b_arr = bubble_sort(arr, n)
    print(" ".join([b.str for b in b_arr]))
    print("Stable")
    arr = [Card(card_str) for card_str in cards]
    s_arr = selection_sort(arr, n)
    print(" ".join([s.str for s in s_arr]))
    if is_stable(b_arr, s_arr):
        print("Stable")
    else:
        print("Not stable")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import copy
sys.setrecursionlimit(10 ** 7)

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

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

N = int(input())
C1 = list(input().split())
C2 = copy.deepcopy(C1)
bC = bubbleSort(C1)
sC = selectionSort(C2)

print(*bC)
s = "Stable" #BubbleSort is stable sort!
print(s)

print(*sC)
s = "Stable"
for i in range(len(sC)-1):
    if sC[i][1] == bC[i][1] and sC[i][0] != bC[i][0]:
        s = "Not stable"
        break
print(s)

Submission status: Accepted

Solution code:
import copy
N=int(input())
c1=list(input().split())
c2=copy.deepcopy(c1)
c3=copy.deepcopy(c1)
def bubble(card):
    for i in range(N):
        for j in [N-x for x in range(1,N-i)]:
            if int(card[j][1]) < int(card[j-1][1]):
                s= card[j]
                card[j]=card[j-1]
                card[j-1]=s
    return card
def selection(card):
    for i in range(N):
        minj = i
        for j in range(i,N):
            if int(card[j][1]) < int(card[minj][1]):
                minj = j
        s = card[i]
        card[i]=card[minj]
        card[minj]=s
    return card
def stable(card):
    j=0
    for i in range(N-1):
        if int(card[i][1]) == int(card[i+1][1]):
            if c3.index(card[i]) > c3.index(card[i+1]):
                j=1
                break
    if j == 0:
        return 'Stable'
    else:
        return 'Not stable' 
print(*bubble(c1))
print(stable(bubble(c1)))
print(*selection(c2))
print(stable(selection(c2)))

Submission status: Accepted

Solution code:
import copy
N = int(input())
A = list(input().split())
B = []
for i in A:
    temp = list(i)
    B.append(temp)
C = copy.copy(B)

def bubble_sort(A):
    for i in range(len(A)):
        for j in range(len(A)-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 selection_sort(A):
    for i in range(len(A)):
        minj = i
        for j in range(i+1,len(A)):
            if int(A[minj][1]) > int(A[j][1]):
                minj = j
        A[minj],A[i] = A[i],A[minj]
    return A

ans = []
for k in bubble_sort(B):
    ans.append(k[0]+k[1])
print(*ans)
print("Stable")

ans_2 = []
for k in selection_sort(C):
    ans_2.append(k[0]+k[1])

print(*ans_2)

if ans == ans_2:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
def bubbleSort(numlist):
    n = len(numlist)
    flag = True
    for i in range(n):
        if flag is False:
            break
        flag = False
        for j in range(n - 1, i, -1):
            if numlist[j][1] < numlist[j - 1][1]:
                numlist[j], numlist[j - 1] = numlist[j - 1], numlist[j]
                flag = True

def selectionSort(numlist):
    n = len(numlist)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if numlist[min_index][1] > numlist[j][1]:
                min_index = j
        
        if min_index != i:
            numlist[min_index], numlist[i] = numlist[i], numlist[min_index]

def print_numlist(numlist):
    if len(numlist) == 1:
        print(numlist[0])
    else:
        n = len(numlist)
        for i in range(n - 1):
            print(numlist[i], end=' ')
        print(numlist[-1])

if __name__ == '__main__':
    n = int(input())
    numlist = [num for num in input().replace('\n', '').split(' ')]
    numlist2 = numlist.copy()
    bubbleSort(numlist)
    print_numlist(numlist)
    print('Stable')
    selectionSort(numlist2)
    print_numlist(numlist2)
    flag = True
    for i in range(len(numlist)):
        if numlist[i] != numlist2[i]:
            flag = False
            break
    if flag:
        print('Stable')
    else:
        print('Not stable')

Submission status: Accepted

Solution code:
def to_int(A):
    return int(A[1])

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

def selection_sort(N, A):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if to_int(A[j]) < to_int(A[minj]):
                minj = j
        a = A[i]
        A[i] = A[minj]
        A[minj] = a
    return A

def is_stable(bubble, selection):
    if bubble == selection:
        return "Stable"
    else:
        return "Not stable"

if __name__ == "__main__":
    N = int(input())
    A = input().split(" ")
    bubble = bubble_sort(N, A[:])
    selection = selection_sort(N, A[:])
    print(" ".join(bubble))
    print("Stable")
    print(" ".join(selection))
    print(is_stable(bubble, selection))

Submission status: Accepted

Solution code:
n = int(input())
trump = input().split()

def bubbleSort(trump, n):
    c = trump[::]
    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))
    print('Stable')
    return c

def selectionSort(trump, n):
    c = trump[::]
    for i in range(n):
        minj = i
        for j in range(i+1, n):
            if int(c[j][1]) < int(c[minj][1]):
                minj = j
        c[i], c[minj] = c[minj], c[i]
    print(' '.join(c))
    return c

if bubbleSort(trump, n) == selectionSort(trump, n):
    print('Stable')
else:
    print('Not stable')