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:
n=int(input())
da=list(map(str,input().split()))
me=[i for i in range(n)]
def mark(kop):
    return int(kop[1])

da1=da[:]
for i in range(n):
    for j in range(n-1,i,-1):
        x=mark(da1[j])
        y=mark(da1[j-1])
        if x<y:
            da1[j],da1[j-1]=da1[j-1],da1[j]

da2=da[:]
for i in range(n):
    mian=i
    for j in range(i,n):
        x=mark(da2[j])
        y=mark(da2[mian])
        if x<y:
            mian=j
    da2[i],da2[mian]=da2[mian],da2[i]
    me[i],me[mian]=me[mian],me[i]
ans=True
for i  in range(1,n):
    if mark(da2[i])==mark(da2[i-1]) and me[i]<me[i-1]:
        ans=False
        break

for i in range(n):
    if i==n-1:
        print(da1[i])
    else:
        print(da1[i],end=' ')
print('Stable')
for i in range(n):
    if i ==n-1:
        print(da2[i])
    else:
        print(da2[i],end=' ')
if ans:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
N=int(input())
L=input().split( )
#リストがmutableなので以下ではコピーできていない
#B=L
#S=L
B=L[:]
S=L[:]
for i in range(N):
    j=N-1
    while j>i:
        if B[j][1]<B[j-1][1]:
            temp =B[j]
            B[j]=B[j-1]
            B[j-1]=temp

        j-=1

for i in range(N):
    minj= i
    j=i
    while j<N:
        if S[j][1]<S[minj][1]:
            minj=j
            j+=1
            #print(S[minj])
        else:j+=1

#j+=1してねぇｗ
#if終了後に交換なので以下のインデントはifと同列
#じゃなくてifより上でwhileと同列
#jでなくてi
#この辺散々間違えたが、間違えた時の挙動が追いきれない
    temp =S[i]
    S[i]=S[minj]
    S[minj]=temp
    #print(S,i,minj)

for i in range(N):
    if i!=N-1:
        print(f"{B[i]}",end=" ")
    else:
        print(f"{B[i]}")
print("Stable")

for i in range(N):
    if i!=N-1:
        print(f"{S[i]}",end=" ")
    else:
        print(f"{S[i]}")
flag=1
for i in range(N):
    if B[i]!=S[i]:
        flag=0
if flag==1:
    print("Stable")
if flag==0:
    print("Not stable")

Submission status: Accepted

Solution code:
import copy
n = int(input())
a = list(map(str, input().split()))
a_buble = copy.copy(a)
for i in range(n):
  for j in range(n-1,i,-1):
    if int(a_buble[j][1]) < int(a_buble[j-1][1]):
      temp = a_buble[j]
      a_buble[j] =a_buble[j-1]
      a_buble[j-1] = temp
      
print(" ".join(map(str,a_buble)))
print("Stable")

for i in range(0,n):
  minj = i
  for j in range(i,n):
    if int(a[j][1]) < int(a[minj][1]):
      minj = j
  temp = a[i]
  a[i] = a[minj]
  a[minj] = temp
print(" ".join(map(str,a)))
ans = "Stable"
for k in range(n):
  if a[k] != a_buble[k]:
    ans = "Not stable"
print(ans)

Submission status: Accepted

Solution code:
def bubble_sort(A, n):
    A = A[:]
    flag = True
    while flag:
        flag = False
        for i in range(n - 1, 0, -1):
            if int(A[i][1:]) < int(A[i - 1][1:]):
                A[i], A[i - 1] = A[i - 1], A[i]
                flag = True
    return A


def selection_sort(A, n):
    A = A[:]
    for start in range(n):
        smallest_i = start
        smallest = A[smallest_i]
        for i in range(start, n):
            if int(A[i][1:]) < int(smallest[1:]):
                smallest_i = i
                smallest = A[smallest_i]
        A[start], A[smallest_i] = A[smallest_i], A[start]
    return A


def is_stable(ordered, original):
    for n in range(1, 10):
        f_original = filter(lambda c: int(c[1:]) == n, original)
        f_ordered = filter(lambda c: int(c[1:]) == n, ordered)
        for a, b in zip(f_ordered, f_original):
            if a != b:
                return False
    return True


n = int(input())
A = input().split()
bA = bubble_sort(A, n)
sA = selection_sort(A, n)
print(*bA, sep=" ")
print("Stable" if is_stable(bA, A) else "Not stable")
print(*sA, sep=" ")
print("Stable" if is_stable(sA, A) else "Not stable")

Submission status: Accepted

Solution code:
import copy
n=int(input())
a=list(input().split())
def BubbleSort(l,n):
    a=copy.deepcopy(l)
    for i in range(n):
        for j in reversed(range(i+1,n)):
            if int(a[j][1])<int(a[j-1][1]):
                a[j],a[j-1]=a[j-1],a[j]
    return a

def SelectionSort(l,n):
    a=copy.deepcopy(l)
    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 SP(l):
    for i in range(len(l)):
        if i !=len(l)-1:
            print(l[i],end=' ')
        else:
            print(l[i]) 

BS=BubbleSort(a,n)
SS=SelectionSort(a,n)
SP(BS)
print('Stable')
SP(SS)
if BS==SS:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
def bubbleSort(A,N):
    flag = 1
    count = 0
    while flag:
        flag = 0
        for j in range(N-1,0,-1):
            Aj = int(A[j][1])
            Aj_1 = int(A[j-1][1])
            if Aj < Aj_1:
                A[j],A[j-1] = A[j-1],A[j]
                flag = 1
                count += 1
    return A[:]

def selectionSort(A,N):
    count=0
    for i in range(N):
        minj = i
        for j in range(i,N):
            Aj = int(A[j][1])
            Aminj = int(A[minj][1])
            if Aj < Aminj:
                minj = j
        A[i],A[minj] = A[minj],A[i]
        if i != minj:
            count +=1
    return A[:]

N = int(input())
#table = input().split()
#for c in range(input().split()):
#    l.append(int(c[1],c[0]))
table = [x for x in input().split(' ')]
t = table[:]
u = table[:]
#B = A.copy

A=bubbleSort(t,N)
print('{0}'.format(' '.join(map(str,A))))
print('Stable')
B=selectionSort(u,N)
print('{0}'.format(' '.join(map(str,B))))
if A == B:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
def bubbleSort(x):
    A = x[:]
    flag_stable = True
    
    for i in range(1, len(A)):
        for j in range(1, len(A) - i + 1):
            if  A[j - 1][1] > A[j][1]:
                A[j], A[j - 1] = A[j - 1], A[j]

                if not flag_stable:
                    continue

                if A[j - 1][1:] == A[j][1:]:
                    flag_stable = False

    return A, flag_stable

def selectionSort(x):
    A = x[:]
    flag_stable = True

    for i in range(len(A)):
        minj = i

        for j in range(i + 1, len(A)):

            if A[j][1] < A[minj][1]:
                minj = j

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

            if not flag_stable:
                continue

            for k in range(i, minj):
                if A[k][1] == A[minj][1]:
                    flag_stable = False

    return A, flag_stable




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

card_bubbleSort, flag_stable_bubbleSort = bubbleSort(card)
card_selectionSort, flag_stable_selectionSort = selectionSort(card)


print(*card_bubbleSort)

if flag_stable_bubbleSort:
    print("Stable")
else:
    print("Not stable")

print(*card_selectionSort)

if flag_stable_selectionSort:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
from copy import deepcopy

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

def SelectionSort(a, N):
    for i in range(N):
        minj = i
        for j in range(i+1, N):
            if a[minj][1] > a[j][1]:
                minj = j
        a[minj], a[i] = a[i], a[minj]
    return a

def isStable(x, bubble):
    if x == bubble: return "Stable"
    else: return "Not stable"

if __name__ ==  "__main__":
    N = int(input())
    a = list(map(str, input().split()))
    bubble, selection = deepcopy(a), deepcopy(a)
    bubble = BubbleSort(bubble, N)
    selection = SelectionSort(selection, N)
    print(*bubble)
    print(isStable(bubble, bubble))
    print(*selection)
    print(isStable(selection, bubble))

Submission status: Accepted

Solution code:
N = int(input())
A = list(input().split())
number = [int(a[1]) for a in A]
mark = [a[0] for a in A]

def bubbleSort(C_number, C_mark, N):
    for i in range(N):
        for j in reversed(range(i+1, N)):
            if C_number[j] < C_number[j-1]:
                # 番号の順番交換
                temp = C_number[j]
                C_number[j] = C_number[j-1]
                C_number[j-1] = temp
                # マークも順番交換
                temp = C_mark[j]
                C_mark[j] = C_mark[j-1]
                C_mark[j-1] = temp
    return C_number, C_mark

def selectionSort(num, mark, N):
    for i in range(N):
        min_val = min(num[i:])
        min_index = num[i:].index(min_val) + i
        if num[i] != min_val:
            # 番号の順番交換
            temp = num[i]
            num[i] = min_val
            num[min_index] = temp
            # マークも順番交換
            temp = mark[i]
            mark[i] = mark[min_index]
            mark[min_index] = temp

    return num, mark

b_num, b_mark = bubbleSort(number.copy(), mark.copy(), N)
s_num, s_mark = selectionSort(number, mark, N)

b = [b_mark[i]+str(b_num[i]) for i in range(N)]
s = [s_mark[i]+str(s_num[i]) for i in range(N)]

print(*b)
print("Stable")
print(*s)
is_same = [b[i]==s[i] for i in range(N)]
if all(is_same):
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
n = int(input())
card_input = list(input().split())

# bubble
card_bubble = card_input.copy()
for i in range(n):
    for j in range(n-1,i,-1):
        if int(card_bubble[j][1])<int(card_bubble[j-1][1]):
            card_bubble[j], card_bubble[j-1] = card_bubble[j-1], card_bubble[j]

# select
card_select = card_input.copy()
for i in range(n):
    mini = i
    for j in range(i,n):
        if  int(card_select[j][1])<int(card_select[mini][1]):
            mini = j
    card_select[mini], card_select[i] = card_select[i], card_select[mini]


    
def output(card):
    string = ''
    for i in card[:-1]:
        string += i + ' '
    string += card[-1]
    print(string)
    
output(card_bubble)
print('Stable')
output(card_select)
if card_bubble==card_select:print('Stable')
else:print('Not stable')

Submission status: Accepted

Solution code:
import copy

N = int(input())
C = list(list(input().split()))
Cb, Cs = copy.copy(C), copy.copy(C)


def BubbleSort(C, N):
    for i in range(N):
        for j in range(N-1, i, -1):
            if C[j-1][1] > C[j][1]:
                C[j-1], C[j] = C[j], C[j-1]
    for i in range(N):
        C[i] = "".join(C[i])
    print(" ".join(map(str, C)))


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

def StableCheck(Cin, Cout, N):
    for i in range(1,10):
        check1, check2 = [], []
        for j1 in Cin:
            if str(i) in j1:
                check1.append(j1)
        for j2 in Cout:
            if str(i) in j2:
                check2.append(j2)
        if check1 != check2:
            print("Not stable")
            exit()
    print("Stable")

BubbleSort(Cb, N)
StableCheck(C, Cb, N)
SelectionSort(Cs, N)
StableCheck(C, Cs, N)

Submission status: Accepted

Solution code:
#ALDS1_2_C
n = int(input())
a_master = input()

#BubbleSort
a = [[i[0],i[1]] for i in a_master.split()]
for ni in range(n):
   for ii in range(n-1, ni, -1):
      if int(a[ii][1]) < int(a[ii-1][1]):
        a[ii], a[ii-1] = a[ii-1], a[ii]
b_ans = " ".join(["".join(i) for i in a])
print(b_ans)
print("Stable")
#SelectionSort
a = [[i[0],i[1]] for i in a_master.split()]
for ni in range(n):
  mini = ni
  for ii in range(ni,n):
    if int(a[ii][1]) < int(a[mini][1]):
      mini = ii
  a[ni], a[mini] = a[mini], a[ni]
s_ans = " ".join(["".join(i) for i in a])
print(s_ans)
if b_ans == s_ans:
  print("Stable")
else:
  print("Not stable")

Submission status: Accepted

Solution code:
import re
import copy

N = int(input())
list = list(input().split())
pattern = '[DHSC]'

def bubble_sort(N, cards):
  flag = 1
  while flag == 1:
    flag = 0
    for i in range(N - 1, 0, -1):
      if int(re.sub(pattern, '', cards[i])) < int(re.sub(pattern, '', cards[ i - 1])):
        cards[i], cards[i - 1] = cards[i - 1], cards[i]
        flag = 1
  print(' '.join(cards))
  print('Stable')
  return cards

def selection_sort(N, cards):
  for i in range(N):
    minj = i
    for j in range(i, N):
      # print(j)
      if int(re.sub(pattern, '', cards[j])) < int(re.sub(pattern, '', cards[minj])):
        minj = j

    cards[i], cards[minj] = cards[minj], cards[i]

  print(' '.join(cards))
  return cards

bubblelist = bubble_sort(N, copy.deepcopy(list))
selectionlist = selection_sort(N, copy.deepcopy(list))

print('Not stable') if bubblelist != selectionlist else print('Stable')

Submission status: Accepted

Solution code:
num = int(input())
card_list = [x for x in input().split()]
origin = card_list[:]
card_list2 = origin[:]
cards = {x : int(x[1]) for x in card_list}

for i in range(num):
    for j in range(num-1, i, -1):
        if cards[card_list[j]] < cards[card_list[j-1]]:
            card_list[j], card_list[j-1] = card_list[j-1], card_list[j]
print(' '.join(card_list))
print('Stable')

for i in range(num):
    minj = i
    for j in range(i, num):
        if cards[card_list2[j]] < cards[card_list2[minj]]:
            minj = j
    card_list2[i], card_list2[minj] = card_list2[minj], card_list2[i]
print(' '.join(card_list2))

if card_list == card_list2:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
import copy

def bubble_sort(data_bubble):
    for i in range(len(data_bubble)):
        for j in range(len(data_bubble)-1, i, -1):
            if data_bubble[j][1] < data_bubble[j-1][1]:
                data_bubble[j], data_bubble[j-1] = data_bubble[j-1], data_bubble[j]
    return data_bubble


def selection_sort(data_selec):
    for i in range(len(data_selec)):
        minj = i
        for j in range(i, len(data_selec)):
            if data_selec[j][1] < data_selec[minj][1]:
                minj = j
        data_selec[i], data_selec[minj] = data_selec[minj], data_selec[i]
    return data_selec


def set_list(data):
    base_list = [[], [], [], [], [], [], [], [], []]
    for elem in data:
        base_list[int(elem[1]) - 1].append(elem)
    return base_list


def is_stable(base, compare):
    base_list = set_list(base)
    compare_list = set_list(compare)
    for i, num in enumerate(base_list):
        for j, key in enumerate(num):
            if key != compare_list[i][j]:
                return 'Not stable'
    return 'Stable'


_ = int(input())
data = list(input().split())
bubble_list = copy.copy(data)
bubble_list = bubble_sort(bubble_list)
print(*bubble_list)
print(is_stable(data, bubble_list))
selection_list = copy.copy(data)
selection_list = selection_sort(selection_list)
print(*selection_list)
print(is_stable(data, selection_list))

Submission status: Accepted

Solution code:
N = int(input())
C1 = input().split()
C2 = [i for i in C1]


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


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


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


def isStable(C1, C2):
    for i1, i2 in zip(C1, C2):
        if i1 != i2:
            return False
    return True

BubbleSort(C1, N)
print(' '.join(C1))
print('Stable')

SelectionSort(C2, N)
print(' '.join(C2))
ans = 'Stable' if isStable(C1, C2) else 'Not stable'
print(ans)

Submission status: Accepted

Solution code:
def bubble(A):
    flag = True
    n = len(A)
    i = 0
    while flag:
        flag = False
        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]:
                minj = j
        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: Accepted

Solution code:
import copy

def bubble_sort(A, N):
	cnt = 0
	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 A

def selection_sort(A, N):
	cnt = 0
	for i in range(N):
		minj = i
		for j in range(i, N):
			if A[j][1:] < A[minj][1:]:
				minj = j
		A[i], A[minj] = A[minj], A[i]

	return A

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

B = bubble_sort(copy.copy(A), N)
print(' '.join(B))
print('Stable')
C = selection_sort(copy.copy(A), N)
print(' '.join(C))
if B==C:
	print('Stable')
else:
	print('Not stable')

Submission status: Accepted

Solution code:
n = int(input())
cards = input().split()
cards_s, cards_b = cards[:], cards[:]
flag_s, flag_b = False, False
for i in range(n):
    # for Selection Sort
    mini = i
    for j in range(i, n):
        if cards_s[j][1] < cards_s[mini][1]:
            mini = j
    if mini != i:
        cards_s[i], cards_s[mini] = cards_s[mini], cards_s[i]
    # for Bubble Sort    
    for j in range(n-1, i, -1):
        if cards_b[j][1] < cards_b[j-1][1]:
            cards_b[j], cards_b[j-1] = cards_b[j-1], cards_b[j]
for i in range(n-1):
    for j in range(i+1,n):
        # for Selection Sort
        if cards_s[i][1] == cards_s[j][1]:
            flag_s = flag_s or (cards.index(cards_s[i]) > cards.index(cards_s[j]))
        # for Bubble Sort     
        if cards_b[i][1] == cards_b[j][1]:
            flag_b = flag_b or (cards.index(cards_b[i]) > cards.index(cards_b[j]))
# for Bubble Sort 
for i in range(n-1):
    print(cards_b[i], end = ' ')
print(cards_b[n-1])
if flag_b:
    print('Not stable')
else:
    print('Stable')
# for Selection Sort
for i in range(n-1):
    print(cards_s[i], end = ' ')
print(cards_s[n-1])
if flag_s:
    print('Not stable')
else:
    print('Stable')

Submission status: Accepted

Solution code:
def BubbleSort(A):
    loop = len(A)-1
    for i in range(loop):
        for j in range(loop-i):
            if A[j][1] > A[j+1][1]:
                A[j],A[j+1] = A[j+1],A[j]

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

    
N = int(input())
S = input().strip().split()
SS = S.copy()

BubbleSort(S)
for i in range(N):
    if i == N-1:
        print(S[i])
    else:
        print(S[i],end=' ')
print('Stable')

        
SelectionSort(SS)
for i in range(N):
    if i == N-1:
        print(SS[i])
    else:
        print(SS[i],end=' ')
if SS == S:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
def bubbleSort(A,N):
    flag = 1
    sortedIndex = 0
    i = 0
    while flag == 1:
        flag = 0
        for j in range(N-1,sortedIndex,-1):
            if int(A[j][1]) < int(A[j-1][1]):
                v = A[j]
                A[j] = A[j-1]
                A[j-1] = v
                flag = 1
                i += 1

def selectionSort(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
        v = A[i]
        A[i] = A[minj]
        A[minj] = v

def isStable(before,after,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 before[i][1] == before[j][1] and before[i] == after[b] and before[j] == after[a]:
                        #print("i={} j={} a={} b={}".format(i,j,a,b))
                        return False
    return True

def bubble_is_stable(A,N):
    bubble = A.copy()
    bubbleSort(bubble,N)
    bubble_is_stable = isStable(A,bubble,N)
    bubblestr = ''
    for i in range(N):
        bubblestr += "{} ".format(bubble[i])
    print(bubblestr[:len(bubblestr)-1])
    if bubble_is_stable:
        print('Stable')
    else:
        print('Not stable')

def selection_is_stable(A,N):
    selection = A.copy()
    selectionSort(selection,N)
    selection_is_stable = isStable(A,selection,N)
    selectionstr = ''
    for i in range(N):
        selectionstr += "{} ".format(selection[i])
    print(selectionstr[:len(selectionstr)-1])
    if selection_is_stable:
        print('Stable')
    else:
        print('Not stable')

if __name__ == '__main__':
    N = int(input())
    A = [ _ for _ in input().split()]
    bubble_is_stable(A,N)
    selection_is_stable(A,N)

Submission status: Accepted

Solution code:
n = int(input())
a = list(input().split())
b = a[:]
s = "Stable"
c, d = [[] for i in range(9)], [[] for i in range(9)]
for i in range(n):
    c[int(a[i][1])-1].append(a[i][0])
for _ in range(n):
    for i in range(n-1,0,-1):
        if int(b[i][1]) < int(b[i-1][1]):
            b[i], b[i-1] = b[i-1], b[i]
print(" ".join(map(str,b)))
print(s)
for i in range(n):
    min = a[n-1]
    ch = n - 1
    for j in range(n-2,i-1,-1):
        if int(a[j][1]) <= int(min[1]):
            min = a[j]
            ch = j
    a[i], a[ch] = a[ch], a[i]
for i in range(n):
    d[int(a[i][1])-1].append(a[i][0])
if c != d:
    s = "Not stable"
print(" ".join(map(str,a)))
print(s)

Submission status: Accepted

Solution code:


import re

N = int(input())

def val(stri):
    a = re.sub(r'\D', '', stri)
    a = int(a)
    return a

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

def selec_sort(N, A):
    for i in range(N):
        minj = i
        for j in range(i + 1, N):
            if val(A[j]) < val(A[minj]):
                minj = j
        A[i], A[minj] = A[minj], A[i]
    return A
    
def isStable(inp, out):
    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 val(inp[i]) == val(inp[j]) and inp[i] == out[b] and inp[j] == out[a]:
                        return False
    return True



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

    ST = ''
    for i in A:
        ST += i + ' '
    ST.rstrip(' ')

    bubble_sort(N, A)
    B = ST.split()

    print(*A)
    


    if isStable(A, B):
        print('Stable')
    else:
        print('Not stable')
    A = ST.split()
    selec_sort(N, A)
    B = ST.split()

    print(*A)
    

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

main()

Submission status: Accepted

Solution code:
def bubble_sort(C, N):
    for i in range(N):
        for j in range(N-1, i, -1):
            if C[j][1] < C[j-1][1]:
                C[j-1], C[j] = C[j], C[j-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
        C[i], C[minj] = C[minj], C[i]


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

C1 = cards.copy()
bubble_sort(C1, N)
print(" ".join(C1))
print("Stable")

C2 = cards.copy()
selection_sort(C2, N)
print(" ".join(C2))
if C1 == C2:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
n = int(input())
a = [i for i in input().split()]
b = [a[i] for i in range(n)]
def bubbleSort(A):
    for i in range(n):
        for j in range(i+1,n)[::-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(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

bubbleSort(a)
selectionSort(b)

print(' '.join(a))
print("Stable")
print(' '.join(b))
if a == b:
    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(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(0, 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 check(C0, C1):
    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 C0[i][1] == C0[j][1] and C0[i] == C1[b] and C0[j] == C1[a]:
                        return False
    return True
 
def toStr(a):
    return str(a[0])+str(a[1])
 
N = int(input())
src = [(str(char[0]), int(char[1])) for char in input().split()]
 
out_1 = bubbleSort(src[:], N)
out_2 = selectionSort(src[:], N)
# &は2進数
# リストは参照渡し
for out in [out_1, out_2]:
    ans = map(toStr, out)
    print(*ans)
    if check(src, out):
        print('Stable')
    else:
        print('Not stable')

Submission status: Accepted

Solution code:
def readInt():
  return int(input())


def bubleSort(l, n):
    for i in range(1, n):
        for j in range(n - i):
            if l[j][1] > l[j + 1][1]:
                l[j], l[j + 1] = l[j + 1], l[j]
    return l


def selectionSort(l, n):
    for i in range(n):
        mini = i
        for j in range(i, n):
            if l[j][1] < l[mini][1]:
                mini = j
        l[i], l[mini] = l[mini], l[i]
    return l

def readInts():
  return [int(i) for i in input().split()]
N = readInt()
AS = input().split()

import copy

stable = bubleSort(copy.deepcopy(AS), N)
notstable = selectionSort(AS, N)

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

Submission status: Accepted

Solution code:
def bubblesort(c, n):
    for i in range(n):
        for j in range(n-1, i, -1):
            if int(c[j][1]) < int(c[j-1][1]):
                c[j], c[j-1] = c[j-1], c[j]
def selectionsort(c, n):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if int(c[j][1]) < int(c[minj][1]):
                minj = j
        c[i], c[minj] = c[minj], c[i]
n = int(input())
a = list(input().split())
b = [i for i in a]
bubblesort(a, n)
selectionsort(b, n)
print(' '.join(a))
print('Stable')
print(' '.join(b))
print('Stable' if a == b else 'Not stable')

Submission status: Accepted

Solution code:
def bubble_sort(A,N,M):
    flag = 1
    while flag:
        flag = 0
        for i in range(N-1,0,-1):
            if A[i] < A[i-1]:
                tmp = A[i]
                tmp2 = M[i]
                A[i] = A[i-1]
                M[i] = M[i-1]
                A[i-1] = tmp
                M[i-1] = tmp2
                flag = 1
    return M

def choice_sort(A,N,M):
    for i in range(N):
        top = A[i]
        tp = M[i]
        mini = min(A[i:])
        if top > mini:
            tmp = top
            tmpIndex = A[i:].index(mini) + i
            A[i] = mini
            A[tmpIndex] = tmp
            M[i] = M[tmpIndex]
            M[tmpIndex] = tp
    return M

time = int(input())
nums = list(input().split(" "))
numnum = []
for i in nums:
    numnum.append(list(i)[1])
numnum2 = numnum.copy()
memo = []
for i in range(time):
    memo.append(i)
memo2 = memo.copy()

bubble_order = bubble_sort(numnum,time,memo)
answer = ""
for i in bubble_order:
    answer += str(nums[i])
    answer += ' '
print(answer[:-1])
print("Stable")

choice_order = choice_sort(numnum2,time,memo2)
answer2 = ""
for i in choice_order:
    answer2 += str(nums[i])
    answer2 += ' '
print(answer2[:-1])


if answer[:-1] == answer2[:-1]:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
class Card:
    def __init__(self, suit='', num=''):
        self.suit = suit
        self.num = num
    def __str__(self):
        return "" + self.suit + self.num

def bubble_sort(list):
    for i in range(n):
        for j in range(n - 1, i, -1):
            if list[j].num < list[j - 1].num:
                tmp = list[j]
                list[j] = list[j - 1]
                list[j - 1] = tmp

def selection_sort(list):
    for i in range(n):
        mini = i
        for j in range(i+1, n):
            if list[j].num < list[mini].num:
                mini = j
        tmp = list[mini]
        list[mini] = list[i]
        list[i] = tmp

n = int(input())
inputs = [string for string in input().split(" ")]

cards = []
for i in range(n):
    cards.append(Card(inputs[i][0], inputs[i][1]))

selection_cards = cards.copy()

bubble_sort(cards)
selection_sort(selection_cards)

bubble_result = str(cards[0])
for i in range(1, n):
    bubble_result += " " + str(cards[i]);
print(bubble_result)
print("Stable")

selection_result = str(selection_cards[0])
stable_flag = (cards[0] == selection_cards[0])
for i in range(1, n):
    if cards[i] != selection_cards[i]:
        stable_flag = False
    selection_result += " " + str(selection_cards[i])
print(selection_result)
if stable_flag:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
import copy as c
n,*a=open(0).read().split()
n=int(n)
b=c.deepcopy(a)
for i in range(n):
    for j in range(n-1,0,-1):
        if int(b[j][1])<int(b[j-1][1]):
            b[j],b[j-1]=b[j-1],b[j]
print(*b)
print("Stable")

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]
print(*a)
if a!=b:
    print("Not stable")
else:
    print("Stable")