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:
import copy 
n = int(input())
#*L, = map(str, input().split())
#L = [int(i) for i in input().split()]
*L, = input().split()

A1 = copy.copy(L)
A2 = copy.copy(L)

def bubble_sort(A,N):
	for i in range(N):
		for j in reversed(range(i+1,N)):
			if int(A[j][1]) < int(A[j-1][1]):
				key = A[j]
				A[j] = A[j-1]
				A[j-1] = key
				#print("b",A)

"""
for i in range(N):
	for j in reversed(range(i+1,N)):
		if int(A[j][1]) < int(A[j-1][1]):
			key = A
			A[j] = A[j][0] + A[j-1][1]
			A[j-1] = key[j-1][0] + key[j][1]
			print(A)
"""


def selection_sort(A,N):
	for i in range(N):
		minj = i
		for j in range(i,N):
			if A[j][1] < A[minj][1]:
				minj = j
		if A[i][1] > A[minj][1]:
			key = A[i]
			A[i] = A[minj]
			A[minj] = key
			#print(A)

"""
def isStable(input,output):
	for i in range(len(inp)):
		if inp[i][1] == oup[i][1] and inp[i][0] != oup[i][0]:
			#print("False")
			return False
		else:
			True
"""



"""
if inp[i][1] == oup[i][1] and inp[i][0] != oup[i][0]:
	print("False")

print(inp[i][1])
print(oup[i][1])
print(inp[i][0])
print(oup[i][0])
"""

bubble_sort(A1,n)
selection_sort(A2,n)

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

Submission status: Accepted

Solution code:
def bubbleSort(matrix, N):
  for i in range(N):
    for j in reversed(range(i+1, N)):
      if matrix[j][1] < matrix[j-1][1]:
        matrix[j], matrix[j-1] = matrix[j-1], matrix[j]

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

def printList(matrix, N):
  matrix_cards = []
  for i in range(N):
    matrix_cards.append(matrix[i][0])
  print(" ".join(map(str, matrix_cards)))

n = int(input())
A = list(input().split())
B = [[] for i in range(n)]
C = [[] for i in range(n)]

for i in range(n):
  A[i] = [A[i], int(A[i][1:])]
  B[i] = A[i]
  C[i] = A[i]

bubbleSort(B, n)
selectionSort(C, n)

printList(B,n)
print("Stable")

printList(C,n)
if B == C:
  print("Stable")
else:
  print("Not stable")

Submission status: Accepted

Solution code:
def isStable(in_lst,out_lst):
    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 in_lst[i][1] == in_lst[j][1] and in_lst[i] == out_lst[b] and in_lst[j] == out_lst[a]:
                        return False
    return True

def isStable1(in_lst,out_lst):
    tmp = isStable(in_lst,out_lst)
    if tmp == True:
        print('Stable')
    else:
        print('Not stable')

n = int(input())
lst = list(map(str,input().split()))
ans_lst = lst.copy()
for i in range(0,n):
    for j in range(n-1,i,-1):
        if lst[j][1] < lst[j-1][1]:
            lst[j],lst[j-1] = lst[j-1],lst[j]

print(' '.join(lst))
isStable1(ans_lst,lst)

lst = ans_lst.copy()
for i in range(n):
    minj = i
    for j in range(i,n):
        if lst[j][1] < lst[minj][1]:
            minj = j
    lst[i],lst[minj] = lst[minj],lst[i]

print(' '.join(lst))
isStable1(ans_lst,lst)

Submission status: Accepted

Solution code:
# ALDS1_2_C: Stable Sort
N = int(input())
A = input().split()

#N = 5
#A = "H4 C9 S4 D2 C3".split()

#N = 2
#A = "S1 H1".split()

def insertionSort(A, N):
    #print(" ".join(map(str, A)))
    for i in range(1, N):
        v = A[i]
        j = i - 1
        while j >= 0 and int(A[j][1]) > int(v[1]):
            A[j+1] = A[j]
            j = j - 1
        A[j+1] = v
    #print(" ".join(map(str, A)))
    return " ".join(map(str, A))
    
stablesort = insertionSort(A.copy(), N)

def bubbleSort(A, N):
    flag = True
    i = 0
    while(flag):
        flag = False
        for j in reversed(range(1, N)):
            if int(A[j][1]) < int(A[j-1][1]):                
                A[j], A[j-1] = A[j-1], A[j]
                flag = True
                i += 1
                #print(A)
    print(" ".join(map(str, A)))
    #print(i)
    return " ".join(map(str, A))
    
bubble = bubbleSort(A.copy(), N)
if bubble == stablesort:
    print("Stable")
else:
    print("Not stable")

def selectionSort(A, N):
    e = 0
    for i in range(N):
        minj = i
        for j in range(i, N):
            if int(A[j][1]) < int(A[minj][1]):
                minj = j
        if i != minj:
            A[i], A[minj] = A[minj], A[i]
            e += 1
            #print(A)
    print(" ".join(map(str, A)))
    #print(e)
    return " ".join(map(str, A))
    
selection = selectionSort(A.copy(), N)
if selection == stablesort:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
def check(orijinal,A):
    A2 = [int(x[1]) for x in A]
    orijinal2 = [int(x[1]) for x in orijinal]
    B=[x for x in set(A2) if  A2.count(x)>1]
    flag=True
    if len(B)!=0:
        count=0
        soeji=[]
        for fig in B:
            a=[i for i, x in enumerate(orijinal2) if x == fig]
            b=[i for i, x in enumerate(A2) if x == fig]
            orijinal3=[orijinal[k] for k  in a]
            A3 = [A[k] for k in b]
            if orijinal3!=A3:
                flag=False
                break
    if flag:
        print("Stable")
    else:
        print("Not stable")
def selectSort(N,A):
    count=0
    orijinal=A[:]
    B=[ int(x[1]) for x in A]
    C=list(range(N))
    for i in range(N):
        min=i
        for j in range(i,N):
            if B[j] < B[min]:
                min=j
        if i<=min:
            count+=1
            # for k in range(N): print(A[k], end=' \n'[k + 1 == N])
            A[i],A[min]=A[min],A[i]
            B[i], B[min] = B[min], B[i]

    for k in range(N):print(A[k],end=' \n'[k+1==N])
    check(orijinal,A)



def bubbleSort(N,A):
    i=0
    flag=True
    count=0
    orijinal = A[:]
    B = [int(x[1]) for x in A]
    while flag:
        flag=False
        for j in range(N-1,i,-1):
            if B[j]<B[j-1]:#ソート必須
                A[j],A[j-1]=A[j-1],A[j]
                B[j], B[j - 1] = B[j-1], B[j]
                count+=1
                flag=True


        i += 1
    for i in range(N):print(A[i],end=' \n'[i+1==N])
    check(orijinal, A)

N=int(input())
A=[(x) for x in input().split()]
B=A[:]
bubbleSort(N,A)
selectSort(N,B)

Submission status: Accepted

Solution code:
class Card:
    def __init__(self, info):
        self.suit = info[0]
        self.number = info[1]
    
    def getSuit(self):
        return self.suit
    
    def getNumber(self):
        return self.number
    
    def __repr__(self):
        return self.suit + str(self.number)
    
def isSameCard(card1, card2):
    return card1.getNumber() == card2.getNumber() and card1.getSuit() == card2.getSuit()

def bubbleSort(Ain, N):
    for i in range(0,N):
        for j in range(N-1, i, -1):
            if Ain[j].getNumber() < Ain[j-1].getNumber():
                temp = Ain[j]
                Ain[j] = Ain[j-1]
                Ain[j-1] = temp

def selectionSort(Ain, N):
    for i in range(0,N):    # iは最小のカードが入る場所
        minj = i
        for j in range(i+1,N):   # jは最小候補カードのインデックス
            if Ain[j].getNumber() < Ain[minj].getNumber():
                minj = j
        temp = Ain[i]
        Ain[i] = Ain[minj]
        Ain[minj] = temp

def printCards(Ain, N):
    for i in range(N-1):
        print(str(Ain[i]) + " ", end="")
    print(str(Ain[N-1]))

N = int(input())
Ain = [Card(info) for info in input().split()]
Ab = [i for i in Ain]
As = [i for i in Ain]
bubbleSort(Ab, N)
selectionSort(As, N)
printCards(Ab, N)
print("Stable")
printCards(As, N)
for i in range(0,N):
    if not isSameCard(Ab[i], As[i]):
        print("Not stable")
        break
    elif i != N-1:
        continue
    print("Stable")

Submission status: Accepted

Solution code:
# Stable Sort
N = int(input())
A = [(s, int(a)) for s, a in input().split()]
B = [a for a in A]

# Bubble
for i in range(N):
    for j in range(i+1, N)[::-1]:
        if A[j-1][1] > A[j][1]:
            A[j], A[j-1] = A[j-1], A[j]


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


print(*[s+str(a) for s, a in A])
print('Stable')
print(*[s+str(a) for s, a in B])
print('Stable' if A == B else 'Not stable')

Submission status: Accepted

Solution code:
#! /usr/bin/env python3
# -*- coding: utf-8 -*-
import sys
import copy


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


def isStable(C1, C2, N):
  for i in range(N):
    if (C1[i].suit != C2[i].suit):
      return False
  return True


def printCard(C):
  out = [(c.suit + c.value) for c in C]
  print(' '.join(out))


def validate_num_input(C, N):
  if len(C) != N:
    print("[ERROR] Number of Card caracter is invalid")
    sys.exit()


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


def selectionSort(C, N):
  for i in range(N):
    minj = i
    for j in range(i, N):
      if C[j].value < C[minj].value:
        minj = j
    C[i], C[minj] = C[minj], C[i]
  return C


def main():
  N = int(input())
  C = [x for x in input().split()]

  validate_num_input(C, N)

  C1 = [Card(c[0], c[1]) for c in C]
  C2 = copy.deepcopy(C1)

  C1 = bubbleSort(C1, N)
  printCard(C1)
  print("Stable")

  C2 = selectionSort(C2, N)
  printCard(C2)
  if (isStable(C1, C2, N)):
    print("Stable")
  else:
    print("Not stable")


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
def bubbleSort(c,n):
    for i in range(n):
        for j in range(i+1,n)[::-1]:
            if int(c[j-1][1]) > int(c[j][1]): c[j],c[j-1] = c[j-1],c[j]
    return

def selectionsSort(c,n):
    for i in range(n):
        minj = i
        for j in range(i,n):
            if int(c[minj][1]) > int(c[j][1]): minj = j
        c[i],c[minj] = c[minj],c[i]
    return 

def isStable(inp,outp,n):
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                for l in range(k+1,n):
                    if all((inp[i][1] == inp[j][1],inp[i] == outp[l],inp[j] == outp[k])): return False
    return True

if __name__ == "__main__":
    n = int(input())
    lst = [i for i in input().split()]
    a = lst[:]
    b = lst[:]
    bubbleSort(a,n)
    print(" ".join(a))
    print("Stable" if isStable(lst,a,n) else "Not stable")
    selectionsSort(b,n)
    print(" ".join(b))
    print("Stable" if isStable(lst,b,n) else "Not stable")

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
        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 BubbleSort(n, A):
    cnt = 0
    flg = True
    while flg:
        flg = False
        for j in range(n-1, 0, -1):
            if int(A[j][1:2]) < int(A[j-1][1:2]):
                tmp = A[j]
                A[j] = A[j-1]
                A[j-1] = tmp
                cnt += 1
                flg = True
    
def SelectionSort(n, B):
    cnt = 0
    for i in range(n):
        minj = i
        for j in range(i+1, n):
            if int(B[j][1:2]) < int(B[minj][1:2]):
                minj = j
        if minj != i:
            tmp = B[i]
            B[i] = B[minj]
            B[minj] = tmp
            cnt += 1
    
def IsStable(A, B):
    for a1 in A:
        for b1 in B:
            if int(a1[1:2]) == int(b1[1:2]):
                if a1 == b1:
                    B.remove(b1)
                    break
                else:
                    return "Not stable"
            elif int(a1[1:2]) < int(b1[1:2]):
                break
    return "Stable"
    
n = int(input())
C = input().split()
A = copy.deepcopy(C)
B = copy.deepcopy(C)

BubbleSort(n, A)
print(" ".join(A))
print(IsStable(C, A))

SelectionSort(n, B)
print(" ".join(B))
print(IsStable(C, B))

Submission status: Accepted

Solution code:
def bubbleSort(A, N):
    flag = True
    while flag:
        flag = False
        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 = True
    return A

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 A[i][-1:] != A[minj][-1:]:
            A[i],A[minj] = A[minj],A[i]
    return A
    
def isStable(st,list2):
    for i in range(1,len(st)):
        if list2[i][-1:] == list2[i-1][-1:]:
            if st[i] != list2[i]:
                return "Not stable"
    return "Stable"
    
num = int(input())
li1 = input().split()
stli = bubbleSort(li1[:],num)
li2 = bubbleSort(li1[:],num)
print(*li2,sep=" ")
print(isStable(stli,li2))
li3 = selectionSort(li1[:],num)
print(*li3,sep=" ")
print(isStable(stli[:],li3))

Submission status: Accepted

Solution code:
import copy

def bubble_sort(n, c):
  for i in range(n):
    for j in reversed(range(i + 1, n)):
      if int(c[j][1:]) < int(c[j - 1][1:]):
        c[j], c[j - 1] = c[j - 1], c[j]
  return c

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

n = int(input())
c = [i for i in input().split()]
c1 = bubble_sort(n, copy.copy(c))
c2 = selection_sort(n, copy.copy(c))

print(*c1)
print('Stable')
print(*c2)
print('Stable' if c1 == c2 else 'Not stable')

Submission status: Accepted

Solution code:
import copy

def chk():
    for i in range(n-1):
        if L[i][1:2] == L[i+1][1:2]:
            stri = i
            a = strL.index(L[i])
            b = strL.index(L[i+1])
            if a > b:
                print("Not stable")
                return
    print("Stable")

n = int(input())
L = ['' for i in range(n)]

x = input()
for i in range(n):
    L[i] = x.split()[i]
strL = copy.copy(L)

for i in range(n-1):
    sta = n-1
    end = i
    j = sta
    while not j == end: 
        if L[j][1:2] < L[j-1][1:2]:
            tmp = L[j-1]
            L[j-1] = L[j]
            L[j] = tmp
        j -= 1
print(*L)
chk()

L = copy.copy(strL)
for i in range(n-1):
    min = i
    for j in range(i+1,n):
        if L[j][1:2] < L[min][1:2]:
            min = j
    if min == i:
        pass
    else:
        tmp = L[i]
        L[i] = L[min]
        L[min] = tmp

print(*L)
chk()

Submission status: Accepted

Solution code:
def BubbleSort(C,N):
  for _ in C:
    for i in range(len(C)-1, 0, -1):
      if C[i][-1:] < C[i-1][-1:]:
        C[i], C[i-1] = C[i-1], C[i]
  return C

def SelectionSort(C,N):
  for i in range(len(C)):
    min_pos = i
    for j in range(i+1, len(C)):
      if int(C[j][-1]) < int(C[min_pos][-1]):
        min_pos = j
    C[i], C[min_pos] = C[min_pos], C[i]
  return C

N = int(raw_input())
card = map(str, raw_input().split())

card0 = card
card1 = card[:]
card0 = BubbleSort(card0,N)
card1 = SelectionSort(card1,N)

print ' '.join(card0)
print "Stable"
print ' '.join(card1)
if card0 == card1:
  print "Stable"
else:
  print "Not stable"

Submission status: Accepted

Solution code:
n = int(input())
c = list(map(str, input().split()))
c_copy = list(c)

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], c[j - 1] = c[j - 1], c[j]
    return c

def selection_sort(c, n):
    for i in range(n):
        minj = i
        for j in range(i+1, n):
            if c[minj][1] > c[j][1]:
                minj = j
        c[minj],c[i]=c[i],c[minj]
    return c

def is_stable(c1, c2):
    if c1 == c2:
        print("Stable")
    else:
        print("Not stable")

c1 = bubble_sort(c, n)
print(' '.join(c1))
print('Stable')
c2 = selection_sort(c_copy, n)
print(' '.join(c2))
is_stable(c1,c2)

Submission status: Accepted

Solution code:
class Card:
    def __init__(self, kind, number):
        self.kind = kind
        self.number = number

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

def selection_sort(C, N):
    for i in range(N):
        min_index = i
        for j in range(i, N):
            if C[j].number < C[min_index].number:
                min_index = j
        C[i], C[min_index] = C[min_index], C[i]
    return C

def check_stable(bubble_cards, selection_cards):
    res = 'Stable'
    for (b, s) in zip(bubble_cards, selection_cards):
        if b.kind != s.kind or b.number != s.number:
            res = 'Not stable'
    return res

n = int(input())
bubble_cards = []
for card in input().split():
    kind, number = list(card)
    bubble_cards.append(Card(kind, number))
selection_cards = bubble_cards[:]

bubble_cards = bubble_sort(bubble_cards, n)
ans = []
for c in bubble_cards:
    ans.append(''.join(c.kind + str(c.number)))
print(' '.join(ans))
print('Stable')

selection_cards = selection_sort(selection_cards, n)
ans = []
for c in selection_cards:
    ans.append(''.join(c.kind + str(c.number)))
print(' '.join(ans))
print(check_stable(bubble_cards, selection_cards))

Submission status: Accepted

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

#bub sort
flag = True
while flag:
  flag = False
  for i in range(1,n)[::-1]:
    if a[i-1][1] > a[i][1]:
      a[i-1],a[i]=a[i],a[i-1]
      flag = True
print(" ".join(a))
def stable(b,a):
  for i in range(n):
    for j in range(i+1,n):
      if b[i][1] == b[j][1]:#i<j
        for k in range(n):
          for l in range(k+1,n):
            if a[k] == b[j] and a[l] == b[i]:
              print("Not stable")
              return
  print("Stable")
stable(b,a)
a = list(b)
#sel sort
for i in range(n):
    min_i = i
    for j in range(i+1,n):
        if a[j][1] < a[min_i][1]:
            min_i = j
    if i!= min_i:
        a[i],a[min_i]=a[min_i],a[i]
print(" ".join(map(str,a)))
stable(b,a)

Submission status: Accepted

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

def SelectionSort(C, N):
    for i in range(N):
        minj = i
        for j in range(i,N):
            if C[j][1] < C[minj][1]:
                minj = j
        C[i],C[minj] = C[minj],C[i]
    return C
        
N = int(input())
C = input().split()
bubble = BubbleSort(C[:], N)
select = SelectionSort(C[:], N)
print(*bubble)
print("Stable")
print(*select)
print(["Not stable", "Stable"][bubble==select])

Submission status: Accepted

Solution code:
import copy
class Card:
    def __init__(self, str):
        self.mark = str[0]
        self.number = int(str[1:])
        
    def __str__(self):
        return self.mark + str(self.number)
        
n = int(input())
card_list = [Card(c) for c in input().split()]

def bubble_sort(a):
    a = copy.copy(a)
    n = len(a)
    for i in range(n):
            for j in range(0, n-i-1):
                if a[j].number > a[j+1].number:
                    a[j], a[j+1] = a[j+1], a[j]
    return a
    
sorted_card_list1 = bubble_sort(card_list)
print(*sorted_card_list1)
print("Stable")

def selection_sort(a):
    a = copy.copy(a)
    n = len(a)
    for i in range(n):
        min_index = i
        for j in range(i+1,n):
            if a[j].number < a[min_index].number:
                min_index = j
        if i != min_index:
            a[i],a[min_index] = a[min_index],a[i]
    return a

    
sorted_card_list2 = selection_sort(card_list)
print(*sorted_card_list2)
if sorted_card_list1 == sorted_card_list2:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(lambda x: (x[0],int(x[1])),input().split()))

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

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

B = BubbleSort(A,N)
S = SelectionSort(A,N)

print(*list(map(lambda x:''.join(map(str,x)),B)))
print('Stable')
print(*list(map(lambda x:''.join(map(str,x)),S)))
print('Stable' if B==S else 'Not stable')

Submission status: Accepted

Solution code:
import copy

n = int(input())
cards = input().split()
#print(cards)
def bubble_sort(cards, n):
    c = copy.copy(cards)
    for i in range(n):
        for j in range(n - 1, i, -1):
            if int(c[j][1]) < int(c[j-1][1]):
                tmp = c[j]
                c[j] = c[j-1]
                c[j-1] = tmp
    return c
    
bubble = bubble_sort(cards, n)
#print(cards)
#print(bubble)
print(' '.join(bubble))

def is_stable(o, s):
    for i in range(n - 1):
        if int(s[i][1]) == int(s[i+1][1]):
            if o.index(s[i]) > o.index(s[i+1]):
                return False
    return  True

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


def selection_sort(cards, n):
    c = copy.copy(cards)
    for i in range(n):
        minj = i
        for j in range(i, n):
            if int(c[j][1]) < int(c[minj][1]):
                minj = j
        tmp = c[i]
        c[i] = c[minj]
        c[minj] = tmp
    return c

selection = selection_sort(cards, n)
print(' '.join(selection))

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

Submission status: Accepted

Solution code:
import copy

def BubbleSort(C, N):
    stable = True

    for i in range(N):
        for j in range(i + 1, N)[::-1]:
            if C[j][2] < C[j - 1][2]:
                C[j], C[j - 1] = C[j - 1], C[j]

    
    AnswerPrint(C, IsStable(C))


def SelectionSort(C, N):
    stable = True

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

        C[i], C[minj] = C[minj], C[i]

    AnswerPrint(C, IsStable(C))


def IsStable(C):
    for index, c in enumerate(C):
        for i in range(index, len(C)):
            if (c[2] == C[i][2]) and (c[0] > C[i][0]):
                return False

    return True
                

def AnswerPrint(C, stable):
    out = ["{}{}".format(c[1], c[2]) for c in C]
    print(" ".join(out))

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



N = int(input())
inp = input().split()
C = [[index, c[0], int(c[1])] for index, c in enumerate(inp)]

BubbleSort(copy.copy(C), N)
SelectionSort(copy.copy(C), N)

Submission status: Accepted

Solution code:
n=int(input())
c=list(map(str, input().split()))

def bubble(c:list, n:int) -> str:
    if not isinstance(c, list):
        return None

    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 " ".join(c)

def selection(c:list, n:int) -> str:
    if not isinstance(c, list):
        return None

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

    return " ".join(c)
d = c[:]
bub=bubble(c, n)
print(bub)
print("Stable")
sel=selection(d, n)
print(sel)
if sel == bub:
    print("Stable")
else :
    print("Not stable")

Submission status: Accepted

Solution code:
import sys
import math
import copy
from typing import Tuple, List
input = sys.stdin.readline

class Card:
    def __init__(self, idx):
        self.number = int(idx[1])
        self.design = idx[0]
    def __repr__(self):
        return "{}{}".format (self.design, self.number)


def  print_vec (A: list):
    print (" ".join(map (str, A)))

def swap (A: List, i: int, j: int) -> None:
    temp = A [i]
    A [i] = A [j]
    A [j] = temp



def bubble_sort (C: List [Card]) -> List [Card]:
    for i in range (len (C)):
        for j in range (len (C) - 1, i, -1):
            if C [j].number < C [j-  1].number:
                swap (C, j, j-1)
    return C

def selection_sort (C: List [Card]) -> List [Card]:
    for i in range (len (C)):
        minj = i
        for j in range (i, len (C)):
            if C [j].number < C [minj].number:
                minj = j
        if i != minj:
            swap (C, i, minj)
    return C

if __name__ == "__main__":
    n = int(input())
    vec =  list (map (lambda x: Card (x), input ().split ()))
    bubble_result = bubble_sort (copy.copy (vec))
    print_vec(bubble_result)
    print ("Stable")
    selection_result = selection_sort(copy.copy (vec))
    print_vec (selection_result)
    flag=  True
    for i in range (len (bubble_result)):
        if bubble_result [i] != selection_result [i]:
            flag = False
    if flag:
        print ("Stable")
    else:
        print ("Not stable")

Submission status: Accepted

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

class Card:
    def __init__(self,suit,num):
        self.suit = suit
        self.value = int(num)
        self.id = suit+num
        
    

B_bubble = [Card(a[0],a[1])for a in A]
B_selection = [b for b in B_bubble]

B_id = [b.id for b in B_bubble]

def BubbleSort(C,N):
    for i in range(N):
        for j in range(N-1,i,-1):
            if C[j].value < C[j-1].value:
                tmp = C[j]
                C[j] = C[j-1]
                C[j-1] = tmp
        #print([b.id for b in C])
    return C
    
def SelectionSort(C, N):
    for i in range(N):
      minj = i
      for j in range(i,N):
        if C[j].value < C[minj].value:
          minj = j
      tmp = C[i]
      C[i] = C[minj]
      C[minj] = tmp
      #print([b.id for b in C])
    return C

def stable_check(B_id,C_id):
    tmp = C_id[0]
    for i in range(1,len(C_id)):
        c = C_id[i]
        if c[1]!=tmp[1]:
            tmp = c
            continue
        if B_id.index(tmp)>B_id.index(c):
            return "Not stable" 
        tmp = c
    return "Stable"
    

C_bubble =  [b.id for b in BubbleSort(B_bubble,N)]
print(" ".join(C_bubble))
#C_bubble_id = [b.id for b in C_bubble]
print(stable_check(B_id,C_bubble))

C_selection =  [b.id for b in SelectionSort(B_selection,N)]
print(" ".join(C_selection))
#C_selection_id = [b.id for b in C_selection]
print(stable_check(B_id,C_selection))

Submission status: Accepted

Solution code:
def bubble_sort(N ,num1, suit1): # バブルソート(常に安定)
   # print('\nnum1 & suit1 adress')
   # print(id(num1), id(suit1))
   for i in range(N): # 未ソート部分列は一つずつ減っていく
      for j in range(N-1, i, -1): # 一番後ろ(配列的にはN-1番目)から未ソート部分列の先頭(i+1)まで
         if num1[j] < num1[j-1]: # 後ろより前の方が大きかったら交換
            num1[j], num1[j-1] = num1[j-1], num1[j]
            suit1[j], suit1[j-1] = suit1[j-1], suit1[j]
   return join_trump(N, num1, suit1)

def selection_sort(N, num2, suit2): # 選択ソート(常に安定ではない)
   for i in range(N):
      minj = i # とりあえず未ソート部分列の先頭A[i]を一番小さいことにしておく(indexを記憶)
      for j in range(i+1, N): # 未ソート部分列の次から最後まで，より小さいものを探す
         if num2[j] < num2[minj]: # もし小さいのがあれば
            minj = j # 最小値のindexを変更
      if num2[minj] < num2[i]: # 未ソート部分列中の最小値と未ソート部分列の先頭を比較
         num2[i], num2[minj] = num2[minj], num2[i] # 先頭の方が大きければ入れ替える
         suit2[i], suit2[minj] = suit2[minj], suit2[i]
   return join_trump(N, num2, suit2)

def join_trump(N, num3, suit3):
   trump = [''] * N
   for i in range(N):
      trump[i] = suit3[i] + str(num3[i])
   return trump

# Selection Sortが安定かどうかを調べる
def is_stable(x, y, N): # x: bubble_ans, y: selec_ans
   for i in range(N):
      if x[i]!=y[i]:
         print('Not stable')
         return 0
   print('Stable')

N = int(input()) # カード枚数の入力
# card = list(map(int, input().split())) # 「1 2 3…」のような配列入力
trump = input().split() # 今回は文字列入力なのでこれだけでよい
suit1 = [''] * N # トランプの絵札だけ用配列
num1 = [0] * N   # トランプの数字だけ用配列
for i in range(N):           # トランプの絵札を数字を別々にする
   suit1[i] = trump[i][0]     # 絵札だけ
   num1[i] = int(trump[i][1]) # 数字だけ
suit2, num2 = suit1[:], num1[:]
# print('\nnum & suit adress')
# print(id(num1), id(suit1))
# print(id(num2), id(suit2))

# # Bubble Sortによる出力(常に安定)
bubble_ans = bubble_sort(N, num1, suit1)
print(*bubble_ans)
print('Stable')

# # Selection Sortによる出力(安定とは限らない)
selec_ans = selection_sort(N, num2, suit2)
print(*selec_ans)
is_stable(bubble_ans, selec_ans, N)

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:
            A[i], A[minj] = A[minj], A[i]

    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:]:
                A[j], A[j - 1] = A[j - 1], A[j]

    return A


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

    fStable = SR == BR

    print(*BR)
    print("Stable")
    print(*SR)
    if (fStable == True):
        print("Stable")
    else:
        print("Not stable")