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())
str_input = list(input().split())
T1 = [(S[0],int(S[1])) for S in str_input]
T2 = [(S[0],int(S[1])) for S in str_input]

def bubble_sort(N,T):
    for i in range(N):
        flag = True
        while flag:
            flag = False
            for j in range(N-1, i, -1):
                if T[j][1] < T[j-1][1]:
                    tmp = T[j]
                    T[j] = T[j-1]
                    T[j-1] = tmp
                    flag = True
    return T

def selection_sort(N,T):
    for i in range(N):
        min_index = i
        for j in range(i, N):
            if (T[j][1] < T[min_index][1]):
                min_index = j
        if (min_index != i):
            tmp = T[i]
            T[i] = T[min_index]
            T[min_index] = tmp
    return T

def is_stable(bT, sT):
    for i, st in enumerate(sT):
        if(st[0] != bT[i][0]):
            return False
    return True

def print_trump(T):
    strT = ['{}{}'.format(t[0],t[1]) for t in T]
    print(str(strT).replace(',','').replace('[','').replace(']','').replace("'",''))
    
bT = bubble_sort(N, T1)
sT = selection_sort(N, T2)
print_trump(bT)
print('Stable')
print_trump(sT)
stability = 'Stable' if is_stable(bT,sT) else 'Not stable'
print(stability)

Submission status: Accepted

Solution code:
import copy
def selection_sort(A):
    global c
    c=0 
    for i in range(0,len(A)-1):
        selection(A,i)
        
        
    return A

def selection(A,i):
    global c
    min=i
    for j in range(i+1,len(A)):
        if A[min][1]>A[j][1]:
            min=j
            
            
    A[i],A[min]=A[min],A[i]
    if not A[i]==A[min]:
        c+=1
    
def bubble_sort(A):
    for i in range(0,len(A)-1):
        bubble(A,i)
        
    return A

def bubble(A,i):
    for j in range(0,len(A)-1-i):
        if A[j][1]>A[j+1][1]:
            A[j],A[j+1]=A[j+1],A[j]
            
            
def is_stable(A, B):
    for i in range(len(B) - 1):
        if B[i][1] == B[i + 1][1]:
            if A.index(B[i]) > A.index(B[i + 1]):
                return 'Not stable'
    return 'Stable'



n=int(input())
A=input().split()
A_t=[(i[0],int(i[1])) for i in A]
A_t2=copy.copy(A_t)
B_t=bubble_sort(A_t)
B=[i[0]+str(i[1]) for i in B_t]
print(' '.join(B))
print(is_stable(A_t,B_t))

S_t=selection_sort(A_t2)
S=[i[0]+str(i[1]) for i in S_t]

print(' '.join(S))
print(is_stable(A_t,S_t))

Submission status: Accepted

Solution code:
import copy


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


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


n = int(input())
c = input().split()
b = BubbleSort(copy.deepcopy(c), n)
print(" ".join(b))
print("Stable")
s = SelectionSort(copy.deepcopy(c), n)
print(" ".join(s))
if b == s:
    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 C[j][1] < C[j-1][1]:
                C[j], C[j-1] = C[j-1], C[j]
    return C
                
                

def SelectionSort(C, N):
    #print(C)
    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]
        #print(C)
    return C


def IsStable(A, B):
    for i in range(len(A)):
        for j in range(i+1,len(A)):
            for a in range(len(B)):
                for b in range(a+1,len(B)):
                    if A[i][1] == A[j][1] and A[i] == B[b] and A[j] == B[a]:
                        return False
    return True
        
                
n = int(input())
a = input().split()
b = a.copy()
c = a.copy()
ans1 = []
ans2 = []
    
ans1 = BubbleSort(b, n)
print(*ans1)
if IsStable(a, ans1):
    print('Stable')
else:
    print('Not stable')

ans2 = SelectionSort(c, n)
print(*ans2)
if IsStable(a, ans2):
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
def bubbleSort(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 0

def selectionSort(b):
  for i in range(len(b)):
    minIndex = i
    for j in range(i+1,len(b)):
      if(int(b[j][1])<int(b[minIndex][1])):
        minIndex = j
        
    b[i],b[minIndex] = b[minIndex],b[i]
    
  return 0
        

n = input()
a = input().split()
b = a[:]

bubbleSort(a)
print(*a)
print("Stable")

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

Submission status: Accepted

Solution code:
from sys import stdin
from copy import deepcopy

N = int(stdin.readline().rstrip())
C = [x for x in stdin.readline().rstrip().split()]

def sortBubble(C, N):
    c = deepcopy(C)
    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]

    return c

def sortSelect(C, N):
    c = deepcopy(C)
    for i in range(N):
        minj = i
        for j in range(i, N):
            if c[j][1] < c[minj][1]:
                minj = j

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

    return c

def isStable(Cin, Cout):
    stable = sortBubble(Cin, len(Cin))
    if len(stable) != len(Cout):
        return False
    else:
        for i in range(len(Cin)):
            if Cout[i][0] != stable[i][0]:
                return False
        else:
            return True
            
def output(C, N, *f):
    for fn in f:
        sortedC = fn(C, N)
        print(*sortedC)
        if isStable(C, sortedC):
            print("Stable")
        else:
            print("Not stable")

output(C, N, sortBubble, sortSelect)

Submission status: Accepted

Solution code:
import copy
def bubblesort(card,maisu):
    for i in range(maisu):
        for j in reversed(range(i+1,maisu)):
            if card[j][1]<card[j-1][1]:
                card[j-1],card[j]=card[j],card[j-1]

def selectionsort(card,maisu):
    for i in range(maisu):
        mini=i
        for j in range(i,maisu):
            if card[j][1]<card[mini][1]:
                mini=j
        card[i],card[mini]=card[mini],card[i]

def output(card,maisu):
    joutai="Stable"
    for i in range(maisu):
        if i>0:
            print(" ",end="")
        print(card[i][0]+card[i][1],end="")
        if i<=maisu-2:
            if card[i][1]==card[i+1][1] and card[i][2]>card[i+1][2]:
                joutai="Not stable"
    print()
    print(joutai)
    
maisu=int(input())
card=list(map(str,input().split()))
for i in range(maisu):
    a=[]
    for j in card[i]:
        a.append(j)
    a.append(i)
    card[i]=a
    
card_bubble=copy.deepcopy(card)
card_selection=copy.deepcopy(card)

bubblesort(card_bubble,maisu)
output(card_bubble,maisu)

selectionsort(card_selection,maisu)
output(card_selection,maisu)

Submission status: Accepted

Solution code:
from copy import deepcopy


def printer(A):
    ret = str(A[0][1]) + str(A[0][0])
    for i in range(1, len(A)):
        ret += " " + str(A[i][1]) + str(A[i][0])
    print(ret)
    return True


def devide(card):
    ret = []
    for c in card:
        num = int(c[1])
        pic = c[0]
        ret.append((num, pic))
    return ret


def bubblesort(A):
    ret = 0
    flag = True
    num = len(A)
    while flag is True:
        flag = False
        for i in reversed(range(1, num)):
            if A[i - 1][0] > A[i][0]:
                tmp = A[i - 1]
                A[i - 1] = A[i]
                A[i] = tmp
                flag = True
                ret += 1
                # print(A)
        # num -= 1
    return ret


def selection_sort(A):
    ans = 0
    for i in range(len(A)):
        minj = i
        for j in range(i, len(A)):
            if A[minj][0] > A[j][0]:
                minj = j
        if i != minj:
            ans += 1
            tmp = A[i]
            A[i] = A[minj]
            A[minj] = tmp
    return ans


def isStable(card, sorted_card):
    if len(card) != len(sorted_card):
        return False
    for i in range(len(card)):
        c = card[i]
        s = sorted_card[i]
        if c[0] != s[0] or c[1] != s[1]:
            return False
    return True


n = int(input())
card = list(map(str, input().split()))

card = devide(card)
card_bubble = deepcopy(card)
card_selection = deepcopy(card)

bubblesort(card_bubble)
selection_sort(card_selection)

# print(card_bubble)
printer(card_bubble)
print("Stable")

printer(card_selection)
if isStable(card_bubble, card_selection) is True:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
import sys
from collections import namedtuple


class Card(namedtuple('Card', ('suit', 'value'))):
    __slots__ = ()

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


def bubble_sort(cards):
    n = len(cards)
    for i in range(n):
        for j in range(n - 1, i, -1):
            if cards[j - 1].value > cards[j].value:
                cards[j - 1], cards[j] = cards[j], cards[j - 1]


def selection_sort(cards):
    n = len(cards)
    for i in range(n):
        minj = min(range(i, n), key=lambda j: cards[j].value)
        if i != minj:
            cards[i], cards[minj] = cards[minj], cards[i]


cards = [Card(suit, value) for suit, value in sys.stdin.readlines()[1].strip().split()]

bubbled = cards[:]
bubble_sort(bubbled)
print(' '.join([str(c) for c in bubbled]))
print('Stable')

selected = cards[:]
selection_sort(selected)
print(' '.join([str(c) for c in selected]))
print('Stable' if selected == bubbled else 'Not stable')

Submission status: Accepted

Solution code:

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

	return A

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

	return A

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

	fStable = SR == BR

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

Submission status: Accepted

Solution code:
import copy
n = int(input())
b = list(map(str, input().split()))
a = copy.copy(b)
c = copy.copy(b)
k = 'Stable'

flag = 1
i = 0
while flag:
    flag = 0
    for j in range(n - 1, i, -1):
        if b[j][1] < b[j - 1][1]:
            t = b[j]
            b[j] = b[j - 1]
            b[j - 1] = t
            flag = 1
    i += 1

for i in range(0, n - 1):
    print(b[i], end=' ')
print(b[n - 1])
print(k)

for i in range(0, n):
    minj = i
    for j in range(i + 1, n):
        if a[j][1] < a[minj][1]:
            minj = j
    t = a[i]
    a[i] = a[minj]
    a[minj] = t

fl = 0
for i in range(0, n):
    for j in range(i+1, n):
        if a[i][1] == a[j][1]:
            for q in range(0, n):
                if c[q][1] == a[i][1]:
                    if c[q][0] == a[i][0]:
                        break
                    else:
                        fl = 1
if fl == 1:
    k = 'Not stable'


for i in range(0, n - 1):
    print(a[i], end=' ')
print(a[n - 1])
print(k)

Submission status: Accepted

Solution code:
import re

def BubbleSort(C, N, A):
    for i in range(0,N,1):
        for j in range(N-1, i, -1):
            #print(str(N)+' '+str(i)+' '+str(j))
            if C[j] < C[j-1]:
                C[j],C[j-1] = C[j-1],C[j]
                A[j],A[j-1] = A[j-1],A[j]
            #print(A)
    return A

def SelectionSort(C, N, A):
    for i in range(0,N,1):
        minj = i
        for j in range(i,N,1):
            #print(str(N)+' '+str(i)+' '+str(j))
            if C[j] < C[minj]:
                minj = j
        C[i], C[minj] = C[minj], C[i]
        A[i], A[minj] = A[minj], A[i]
        #print(A)
    return A

if __name__ == '__main__':
    #print(list(range(0,5,1)))
    N = int(input())
    A = input()
    C = list(map(int,re.sub(r'\D', ' ', A).split()))
    CC = list(re.sub(r'[^A-Z]', ' ', A).split())
    A = A.split()

    BSA = BubbleSort(C[:],N,A[:])
    print(' '.join(BSA))
    print('Stable')
    SSA = SelectionSort(C[:],N,A[:])
    print(' '.join(SSA))
    print('Stable' if (BSA == SSA) else 'Not stable')

Submission status: Accepted

Solution code:
import copy
def bubbleSort(A, N):
    cnt = 0
    flag = 1
    while flag:
        flag = 0
        for j in range(N - 1, 0, -1):
            if A[j][1] < A[j - 1][1]:
                A[j], A[j - 1] = A[j - 1], A[j]
                flag = 1
                cnt = cnt + 1
    return cnt


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

def prArr(A, N):
    for i in range(N):
        if i != 0:
            print(" ", end = "")
        print(A[i], end = "")
    print()

    
N = int(input())
A = [i for i in input().split()]
B = copy.deepcopy(A)

bubbleSort(A, N)
selectionSort(B, N)

prArr(A, N)
print("Stable")

prArr(B, N)
print("Stable" if A == B else "Not stable")

Submission status: Accepted

Solution code:
import copy

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

def bubblesort(n,a):
    flag = 1
    while flag:
        flag = False
        for i in reversed(range(1,n)):
            if a[i-1].value > a[i].value:
                a[i], a[i-1] = a[i-1], a[i]
                flag = True
    return a

def selectionsort(n,a):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if a[j].value < a[minj].value:
                minj = j
        a[i], a[minj] = a[minj], a[i]
    return a

def is_stable(before, after):
    n = 9
    lb = [[] for _ in range(n)]
    la = [[] for _ in range(n)]
    for i in range(len(before)):
        lb[before[i].value-1].append(before[i].suit)
        la[after[i].value-1].append(after[i].suit)
    if la == lb:
        print('Stable')
    else:
        print('Not stable')


if __name__ == '__main__':
    n = int(input())
    cards = [Card(x[0], int(x[1])) for x in input().split()]

    bubble_cards = bubblesort(n, copy.deepcopy(cards))
    selection_cards = selectionsort(n, copy.deepcopy(cards))

    print(' '.join(map(lambda x: x.suit+str(x.value), bubble_cards)))
    is_stable(cards, bubble_cards)

    print(' '.join(map(lambda x: x.suit+str(x.value), selection_cards)))
    is_stable(cards, selection_cards)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

from copy import deepcopy

"""
stable sort
"""
N = int(input())
cN = list(map(str, input().split()))
cN2 = deepcopy(cN)

# bubble sort
for i in range(N):
    for j in range(N-1, i, -1):
        if int(cN[j][1]) < int(cN[j-1][1]):
            tmp = cN[j]
            cN[j] = cN[j-1]
            cN[j-1] = tmp
print(' '.join(cN))
print('Stable')

# selection sort
for i in range(N):
    minj = i
    for j in range(i, N):
        if int(cN2[j][1]) < int(cN2[minj][1]):
            minj = j
    tmp = cN2[i]
    cN2[i] = cN2[minj]
    cN2[minj] = tmp
print(' '.join(cN2))

for i in range(N):
    if cN[i] != cN2[i]:
        print('Not stable')
        exit()
print('Stable')

Submission status: Accepted

Solution code:
import copy

n = int(input())
check = True
a = input().split()

a = [(x[0], int(x[1])) for x in a]
b = copy.deepcopy(a)

#Bubble Sort
flag = True
i = 0
while flag:
    flag = False

    for j in range(n-1, i, -1):
        if a[j][1] < a[j-1][1]:
            tmp = a[j]
            a[j] = a[j-1]
            a[j-1] = tmp
            flag = True

    i += 1

#Selection sort
for i in range(0, n):
    minj = i
    for j in range(i, n):
        if b[j][1] < b[minj][1]:
            minj = j
   
    if i != minj:
        tmp = b[i]
        b[i] = b[minj]
        b[minj] = tmp


for i in range(len(a)):
    if i!=len(a)-1:
        print(a[i][0], end="")
        print(a[i][1], end=" ")
    else:
        print(a[i][0], end="")
        print(a[i][1], end="")
print()
print("Stable")

for i in range(len(b)):
    if i!=len(b)-1:
        print(b[i][0], end="")
        print(b[i][1], end=" ")
    else:
        print(b[i][0], end="")
        print(b[i][1], end="")

print()

for i in range(len(b)):
    if a[i][0] != b[i][0]:
        print("Not stable")
        check = False
        break
if check:
    print("Stable")

Submission status: Accepted

Solution code:
n=int(input())
l1=list(input().split())
l2=l1.copy()
 
def bubble(L,N):
    c=0
    for i in range(N):
        j=N-1
        while j>0:
            if int(L[j][1])<int(L[j-1][1]):
                L[j],L[j-1]=L[j-1],L[j]
            j-=1
    print(" ".join(L))

bubble(l1,n)
print("Stable")

def select(L,N):
    for i in range(N):
        L2=[int(L[k][1]) for k in range(N)]
        j = L2[i:].index(min(L2[i:])) + i
        L[i], L[j] = L[j], L[i]
    print(" ".join(map(str,L)))

select(l2,n)
if l1==l2:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/2/ALDS1_2_C


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


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


def solve():
    n = int(input())
    l = input().split()
    m = l.copy()

    l = BubbleSort(l, n)
    m = SelectionSort(m, n)

    print(' '.join(l))
    print('Stable')
    print(' '.join(m))
    if l == m:
        print('Stable')
    else:
        print('Not stable')


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n=int(input())
lst=list(input().split())
lst1=[""]*n
lst2=[""]*n
for i in range(n):
    lst1[i]=lst[i]
    lst2[i]=lst[i]

for i in range(n-1):
    for j in range(i+1,n)[::-1]:
        if int(lst1[j][1])<int(lst1[j-1][1]):
            lst1[j],lst1[j-1]=lst1[j-1],lst1[j]
print(*lst1)
print("Stable")

for i in range(n-1):
    minlst=min([int(lst2[_][1]) for _ in range(i,n)])
    if minlst==int(lst2[i][1]):continue
    for j in range(i+1,n):
        if minlst==int(lst2[j][1]):
            lst2[i],lst2[j]=lst2[j],lst2[i]
            break
print(*lst2)
print("Stable" if lst1==lst2 else "Not stable")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def bubble_sort(num_list):
    flag = 1
    while flag:
        flag = 0
        for i in range(len(num_list)-1,0,-1):
            if int(num_list[i][1:]) < int(num_list[i-1][1:]):
                num_list[i],num_list[i-1] = num_list[i-1],num_list[i]
                flag = 1

def selectin_sort(num_list):
    for i in range(len(num_list)):
        min_idx = i
        for j in range(i,len(num_list)):
            if int(num_list[j][1:]) < int(num_list[min_idx][1:]):
                min_idx = j
        num_list[i],num_list[min_idx] = num_list[min_idx],num_list[i]

n = input()
card_list_1 = [i for i in input().split()]
card_list_2 = [i for i in card_list_1]
bubble_sort  (card_list_1)
selectin_sort(card_list_2)

print(' '.join(card_list_1))
print('Stable')
print(' '.join(card_list_2))
if card_list_1 == card_list_2:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
def bubble_sort(card, n):
    flag = 1
    while flag:
        flag = 0
        for i in range(n-1, 0, -1):
            if card[i][1] < card[i-1][1]:
                card[i], card[i-1] = card[i-1], card[i]
                flag = 1
    print(' '.join(map(str, card)))
    return card

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

    print(' '.join(map(str, card)))
    return card

def isStable(stable_sorted, target):
    for i in range(len(stable_sorted)):
        if stable_sorted[i] != target[i]:
            return "Not stable"
    return "Stable"

def main():
    n = int(input())
    card = input().split()

    bubble_sorted_card = bubble_sort(card.copy(), n)
    print(isStable(bubble_sorted_card, bubble_sorted_card))

    selection_sorted_card = selection_sort(card.copy(), n)
    print(isStable(bubble_sorted_card, selection_sorted_card))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

def getCardString(A):
    maplist=[]
    for a in A:
        maplist.append(a.getCard())
    return ' '.join(maplist)

n=int(input())
cardsA=[]
cardsB=[]
for data in input().split():
    charList=list(data)
    cardsA.append(Card(charList[0],int(charList[1])))
    cardsB.append(Card(charList[0],int(charList[1])))
bubble=getCardString(BubbleSort(cardsA))
select=getCardString(SelectionSort(cardsB))
print(bubble)
print('Stable')
print(select)
print('Stable' if select==bubble else 'Not stable')

Submission status: Accepted

Solution code:
import copy

n = int(input())

blist = list(map(str, input().split()))
slist = copy.deepcopy(blist)

cnt = 0

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


for i in range(n):
    minj = i
    for j in range(i, n):
        if slist[j][1] < slist[minj][1]:
            minj = j
    if i != minj:
        cnt += 1
        slist[i], slist[minj] = slist[minj], slist[i]

for i in range(n):
    if i == n-1:
        print(blist[i])
    else:
        print(blist[i] + " ", end="")

print("Stable")

for i in range(n):
    if i == n-1:
        print(slist[i])
    else:
        print(slist[i] + " ", end="")

for b, s, in zip(blist, slist):
    if b != s:
        print("Not stable")
        exit()

print("Stable")

Submission status: Accepted

Solution code:
def bubblesort(A, N):
    for i in range(N):
        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]
    print(*A)
    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]
    print(*A)
    return A
def judge(A,B,N):
    stable = True
    for m in range(N):
        for n in range(m+1, N):
            for x in range(N):
                for y in range(x+1,N):
                    if A[m][1]==A[n][1] and A[m]==B[y] and A[n]==B[x]:
                        stable = False
    if stable:
        return "Stable"
    else:
        return "Not stable"

N = int(input())
A = list(map(str, input().split(" ")))
B = A.copy()
Bubble = bubblesort(B,N)
print(judge(A,Bubble, N))
B = A.copy()
Selection = selectionsort(B,N)
print(judge(A,Selection, N))

Submission status: Accepted

Solution code:

def showList(A, N):
    for i in range(N-1):
        print(A[i],end=' ')
    print(A[N-1])

def get_intlist(A):
    list_int = [int(x[1:]) for x in A]
    return list_int 

def bubbleSort(A, N):
    """
    バブルソート
    O(n^2)のアルゴリズム
    """
    B = get_intlist(A)
    flag = 1
    count = 0
    while flag:
        flag = 0
        for i in range(N-1, 0, -1):
            if B[i] < B[i-1]:
                v = A[i]
                A[i] = A[i-1]
                A[i-1] = v

                v = B[i]
                B[i] = B[i-1]
                B[i-1] = v
                flag = 1
    return A

def selectionSort(A, N):
    """
    選択ソート
    O(n^2)のアルゴリズム
    """
    B = get_intlist(A)
    for i in range(N):
        minj = i
        for j in range(i,N):
            if B[j] < B[minj]:
                minj = j
        if minj != i:
            t = B[minj]
            B[minj] = B[i]
            B[i] = t

            t = A[minj]
            A[minj] = A[i]
            A[i] = t
    return A

N = int(input())
A = [x for x in input().split(' ')]
A_ss = A.copy()
bub = bubbleSort(A,N)
showList(bub,N)
print('Stable')
sel = selectionSort(A_ss,N)
showList(sel,N)
if sel == bub:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
#! python3
# stableSort.py - 安定的なソートを行っているかどうか判別するプログラム

# インプットの例
# 5
# H4 C9 S4 D2 C3

# コマンド引数から値を受け取る
number = int(input())
array = input().split(' ')
bubble_array = array.copy()
select_array = array.copy()

# bubblesortのアルゴリズム
def bubbleSort(array, number):
    flag = 1
    i = 0
    while flag ==1:
        flag = 0
        for j in range(number-1, i, -1):
            if array[j][1] < array[j-1][1]:
                tmp = array[j]
                array[j] = array[j-1]
                array[j-1] = tmp
                flag = 1
    map_list = map(str, array)
    a = ' '.join(map_list)
    print(a)
    return array

# 選択ソートのアルゴリズム
def selectionSort(array, number):
    # counter = 0
    for i in range(number-1):
        mini_j = i
        for j in range(i + 1, number):
            if int(array[mini_j][1]) > int(array[j][1]):
                mini_j = j

        #if int(array[i][1]) > int(array[mini_j][1]):
        v = array[i]
        array[i] = array[mini_j]
        array[mini_j] = v
            # counter += 1

    map_list = map(str, array)
    a = ' '.join(map_list)
    print(a)
    return array

# 安定ソートかどうかを判別する
def isStable(input, output):
    for i in range(0, number):
        for j in range(i+1, number):
            for a in range(0, number):
                for b in range(a+1, number):
                    if input[i][1] == input[j][1] and input[i] == output[b] and input[j] == output[a]:
                        return 'Not stable'
    return 'Stable'

input = array
output_bubble = bubbleSort(bubble_array, number)
# print(output_bubble)
print(isStable(input, output_bubble))

output_select = selectionSort(select_array, number)
# print(output_select)
print(isStable(input, output_select))

Submission status: Accepted

Solution code:
import 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]
                
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
        if i != minj:
            c[i], c[minj] = c[minj], c[i]
            
            
n = int(input())
a = input().split()
b = copy.copy(a)

bubblesort(a,n)
for i in range(n-1):
    print(a[i], end=' ')
print(a[-1])
print('Stable')
selectionsort(b,n)
for i in range(n-1):
    print(b[i], end=' ')
print(b[-1])
if a == b:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
N = int(input())
A = []
for card in input().split():
    A.append([card[0], int(card[1])])
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]
A = " ".join([i + str(j) for i, j in A])
print(A)   
print("Stable")
for i in range(N-1):
    minj = i
    for j in range(i, N):
        if B[minj][1] > B[j][1]:
            minj = j
    B[i], B[minj] = B[minj], B[i]
B = " ".join([i + str(j) for i, j in B])
print(B)

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

Submission status: Accepted

Solution code:
import copy
n = int(input())
a = input().split()
a_bubble = a
a_selection = copy.deepcopy(a)
flag = 1
k = 0
while flag == 1:
    flag = 0
    for i in range(n-1,k,-1):
        if int(a_bubble[i-1][1]) > int(a_bubble[i][1]):
            a_bubble[i],a_bubble[i-1] = a_bubble[i-1],a_bubble[i]
            flag = 1
    k += 1
print(" ".join(a_bubble))
print("Stable")
for i in range(n):
    minj = i
    for j in range(i,n):
        if int(a_selection[j][1]) < int(a_selection[minj][1]):
            minj = j
    a_selection[i],a_selection[minj] = a_selection[minj],a_selection[i]
print(" ".join(a_selection))
if a_selection == a_bubble:
    print("Stable")
else:
    print("Not stable")