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

class Cards:
    value = 0
    suit = ""

    def __init__(self,su,val):
        self.suit = su
        self.value = val
    
    def __str__(self):
        return f"{self.suit}{self.value}"

    def __eq__(self,other):
        if not isinstance(other, Cards):
            return NotImplemented
        
        return self.value == other.value and self.suit == other.suit


def cards_stablesort(C):
    lst = copy.deepcopy(C)
    n = len(lst)
    for i in range(1,n):
        j = i
        while(j > 0):
            if lst[j-1].value > lst[j].value:
                lst[j-1],lst[j] = lst[j],lst[j-1] #SWAP
                j -= 1
            else:
                break

    return lst

def cards_bubblesort(C):
    lst = copy.deepcopy(C)
    n = len(lst)

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

    return lst

def cards_selectionsort(C):
    lst = copy.deepcopy(C)
    n = len(lst)

    for i in range(n):
        minj = i

        for j in range(i,n):

            if lst[j].value < lst[minj].value:
                minj = j
        
        lst[i],lst[minj] = lst[minj],lst[i]

    return lst
    


n = int(input())

l = input().split()

C = []
for cd in l:
    C.append(Cards(cd[:1],int(cd[1:])))

stable_list = cards_stablesort(C)
bubble_list = cards_bubblesort(C)
select_list = cards_selectionsort(C)

print(*bubble_list)

if stable_list == bubble_list:
    print("Stable")
else:
    print("Not stable")

print(*select_list)

if stable_list == select_list:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
def bubble(b,p):
    for i in range(0,p):
        for j in reversed(range(i+1,n)):
            if int(b[j][1]) < int(b[j-1][1]):
                b[j],b[j-1] = b[j-1],b[j]
    return b

def selection(A,N):
    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
        if i != minj:
            A[i],A[minj] = A[minj],A[i]

    return A

n = int(input())
a = [s for s in input().split()]
c = a.copy()
print(" ".join(map(str,bubble(a,n))))
print("Stable")
d = selection(c,n)
print(" ".join(map(str,d)))
if a == d:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
import copy

def bubble(A, N):
    for i in range(0, N-1):
        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 selction(A, N):
    for i in range(0, N-1):
        minj = i
        for j in range(i+1, N):
            if A[j][1] < A[minj][1]:
                minj = j
        A[i], A[minj] = A[minj], A[i]
    return A
        
n = int(input())
a = list(map(str, input().split()))

b = copy.copy(a)
c = copy.copy(a)
bubble(b, n)
print(*b)
print("Stable")
selction(c, n)
print(*c)
if c == b:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
import copy
N = int(input())
lst1 = list(input().split())
lst2 = copy.copy(lst1)

def bubble_sort(lst):
    for i in range(N):
        for j in range(N-1,i,-1):
            if (int(lst[j][1]) < int(lst[j-1][1])):
                lst[j],lst[j-1] = lst[j-1],lst[j]
    return lst
    
def selection_sort(lst):
    for i in range(N):
        minj = i
        for j in range(i,N):
            if (int(lst[j][1]) < int(lst[minj][1])):
                minj = j
        lst[i],lst[minj] = lst[minj],lst[i]
    return lst

res1 = " ".join(bubble_sort(lst1))
res2 = " ".join(selection_sort(lst2))
print(res1)
print('Stable')
print(res2)
if (res1 == res2):
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
N = int(input())
A = list(input().split())
A_ = A.copy()
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]
s = ''
for a in A_:
    s += a + ' '
print(s.rstrip())
print('Stable')


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]

s_ = ''
for a in A:
    s_ += a + ' '
print(s_.rstrip())
if A == A_:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
def bubble_sort_index(n, number_from_cards):
    flag = True
    index_lists = list(range(n))
    while flag:
        flag = False
        for i in range(n - 1, 0, -1):
            if number_from_cards[i] < number_from_cards[i - 1]:
                number_from_cards[i], number_from_cards[i - 1] = number_from_cards[i - 1], number_from_cards[i]
                index_lists[i], index_lists[i - 1] = index_lists[i - 1], index_lists[i]
                flag = True
    return index_lists


def selection_sort_index(n, number_from_cards):
    index_list = list(range(n))
    for i in range(n):
        min_j = i
        for j in range(i, n):
            if number_from_cards[min_j] > number_from_cards[j]:
                min_j = j
        if min_j == i:
            continue
        number_from_cards[i], number_from_cards[min_j] = number_from_cards[min_j], number_from_cards[i]
        index_list[i], index_list[min_j] = index_list[min_j], index_list[i]
    return index_list


def main():
    N = int(input())
    true_cards = input().split(' ')
    number_from_cards = [int(c[-1]) for c in true_cards]
    sorted_index_lists_for_bubble = bubble_sort_index(N, number_from_cards.copy())
    sorted_bubble = [true_cards[index] for index in sorted_index_lists_for_bubble]

    sorted_index_lists_for_selection = selection_sort_index(N, number_from_cards.copy())
    sorted_selection = [true_cards[index] for index in sorted_index_lists_for_selection]

    print(' '.join(sorted_bubble))
    print('Stable')
    print(' '.join(sorted_selection))
    if sorted_bubble == sorted_selection:
        print('Stable')
    else:
        print('Not stable')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy

def bubble_sort(a, n):
    a = copy.deepcopy(a)
    count = 0
    flag = 1
    
    while flag:
        flag = 0
        
        for j in range(n-1, 0, -1):
            if int(a[j][1]) < int(a[j-1][1]):
                a[j-1], a[j] = a[j], a[j-1]
                flag = 1
                count += 1
                
    return a, count

def selection_sort(a, n):
    a = copy.deepcopy(a)
    
    count = 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 minj != i:
          count += 1
          a[minj], a[i] = a[i], a[minj]
        
    return a, count

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

bubble_sorted, _ = bubble_sort(a=cards, n=n)
selection_sorted, _ = selection_sort(a=cards, n=n)


print(" ".join(bubble_sorted))
print("Stable")
print(" ".join(selection_sorted))

stable_flag = True
for i in range(n):
    if bubble_sorted[i] != selection_sorted[i]:
      stable_flag = False
      

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

Submission status: Accepted

Solution code:
def bubble_sort(C, N):
    flag = 1
    while flag:
        flag = 0
        for j in range(1, N):
            if list(C[j])[1] < list(C[j-1])[1]:
                C[j], C[j-1] = C[j-1], C[j]
                flag = 1
        N -= 1
    return C

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

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

st = [''] * 9
bubble_st = [''] * 9
selection_st = [''] * 9
bubble_c = bubble_sort(C[:], N)
selection_c = selction_sort(C[:], N)
for i in range(N):
    st[int(list(C[i])[1])-1] += list(C[i])[0]
    bubble_st[int(list(bubble_c[i])[1])-1] += list(bubble_c[i])[0]
    selection_st[int(list(selection_c[i])[1])-1] += list(selection_c[i])[0]
print(' '.join(bubble_c))
if st == bubble_st:
    print('Stable')
else:
    print('Not stable')
print(' '.join(selection_c))
if st == selection_st:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
class Card():
    def __init__(self, suit, value):
        self.suit = suit
        self.value = value
    
    def __eq__(self, ins):
        if not isinstance(ins, Card):
            return NotImplemented
        return self.suit == ins.suit and self.value == ins.value

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]

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

def printCard(C, N):
    c = [C[i].suit + C[i].value for i in range(N)]
    print(' '.join(c))

def isStable(inc, outc, 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 inc[i].value == inc[j].value and inc[i] == outc[b] and inc[j] == outc[a]:
                        return False
    return True


n = int(input())
input_cards = [Card(*c) for c in input().split()]
output_cards = input_cards.copy()
bubbleSort(output_cards, n)
printCard(output_cards, n)
if isStable(input_cards, output_cards, n):
    print('Stable')
else:
    print('Not stable')
output_cards = input_cards.copy()
selectionSort(output_cards, n)
printCard(output_cards, n)
if isStable(input_cards, output_cards, n):
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
import copy

n = int(input())
arr1 = [(int(x[-1]), x) for x in list(input().split())]
arr2 = copy.copy(arr1)

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

def select_sort(arr, n):
  for i in range(n):
    minj = i
    for j in range(i, n):
      if arr[j][0] < arr[minj][0]:
        minj = j
    arr[i],arr[minj] = arr[minj],arr[i]

def check_stable(input, output):
  return 'Stable' if input == output else 'Not stable'

def arr_to_map(input):
  return ' '.join([x[1] for x in input])

bubble_sort(arr1, n)
select_sort(arr2, n)

print (arr_to_map(arr1))
print ('Stable')
print (arr_to_map(arr2))
print (check_stable(arr1, arr2))

Submission status: Accepted

Solution code:
N = int(input())
card_list_source = input().split(' ')

def BubbleSort(card_list, N):
    for i in range(N):
        for j in reversed(range(i+1, N)):
            if int(card_list[j][1]) < int(card_list[j-1][1]):
                temp = card_list[j]
                card_list[j] = card_list[j-1]
                card_list[j-1] = temp
    return card_list

def SelectionSort(card_list, N):
    for i in range(N):
        min_index = i
        for j in range(i+1, N):
            if int(card_list[j][1]) < int(card_list[min_index][1]):
                min_index = j
        if min_index != i:
            temp = card_list[i]
            card_list[i] = card_list[min_index]
            card_list[min_index] = temp
    return card_list

def isStable(card_list_A, card_list_B):
    N = len(card_list_A)
    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 int(card_list_A[i][1]) == int(card_list_A[j][1]) and card_list_A[i] == card_list_B[b] and card_list_A[j] == card_list_B[a]:
                        return 'Not stable'
    return 'Stable'

def make_out_str(card_list):
    out_str = ''
    for i, card in enumerate(card_list):
        out_str += card
        if i < len(card_list) - 1:
            out_str += ' '
    return out_str

card_list_bubble = BubbleSort(card_list_source.copy(), N)
print(make_out_str(card_list_bubble))
print(isStable(card_list_bubble, card_list_source))

card_list_selection = SelectionSort(card_list_source.copy(), N)
print(make_out_str(card_list_selection))
print(isStable(card_list_selection, card_list_source))

Submission status: Accepted

Solution code:
class card:
    def __init__(self, card):
        self.suit = card[0]
        self.value = int(card[1])

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


def selectionSort(a, n):
    r = 0
    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]


def bubbleSort(a, n):
    flag = True
    while flag:
        flag = False
        for j in range(n - 1, 0, -1):
            if a[j].value < a[j - 1].value:
                a[j], a[j - 1] = a[j - 1], a[j]
                flag = True


def copycard(cards):
    r = []
    for c in cards:
        r.append(card(c.suit + str(c.value)))
    return r


def compareCard(c1,c2):
    for i in range(len(c1)):
        if c1[i].suit != c2[i].suit or c1[i].value != c2[i].value:
            return False
    return True


n = int(input())
cards = list(map(card, input().split()))
cards1 = copycard(cards)
cards2 = copycard(cards)
bubbleSort(cards1, n)
print(*cards1)
print("Stable")
selectionSort(cards2, n)
print(*cards2)
if compareCard(cards1,cards2):
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
def check_stable(before_sort_list, after_sort_list):
    N = len(before_sort_list)
    for i in range(0, N, 1):
        for j in range(i+1, N, 1):
            for a in range(0, N, 1):
                for b in range(a+1, N, 1):
                    if before_sort_list[i][1] == before_sort_list[j][1] and before_sort_list[i] == after_sort_list[b] and before_sort_list[j] == after_sort_list[a]:
                        return False
    return True

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


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


num_cards = int(input())
cards = input().split(' ')

sorted_cards1 = bubble_sort(cards.copy(), num_cards)
sorted_cards2 = selection_sort(cards.copy(), num_cards)

print(' '.join(sorted_cards1))
print('Stable' if check_stable(cards, sorted_cards1) else 'Not stable')
print(' '.join(sorted_cards2))
print('Stable' if check_stable(cards, sorted_cards2) else 'Not stable')

Submission status: Accepted

Solution code:
def bubble_sort(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 selection_sort(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 is_stable(original_list, sorted_list):
    for target in sorted_list:
        for original in original_list:
            if target[1] == original[1]:
                if target[0] != original[0]:
                    return "Not stable"
                original_list.remove(original)
                break
    return "Stable"
                
if __name__ == "__main__":
    import copy
    n = int(input())
    c = input().split()
    bubble_list = bubble_sort(copy.deepcopy(c), n)
    print(*bubble_list)
    print(is_stable(copy.deepcopy(c), bubble_list))
    selection_list = selection_sort(copy.deepcopy(c), n)
    print(*selection_list)
    print(is_stable(copy.deepcopy(c), selection_list))

Submission status: Accepted

Solution code:
class card:
    """
    suit: S, H, C, D
    number: 1~10
    """
    def __init__(self, card_input):
        self.suit = card_input[:1]
        self.number = int(card_input[1:])
    
    def __str__(self):
        return self.suit + str(self.number)


def print_list(a):
    out = ''
    for ai in a:
        out += str(ai) + ' '
    else:
        out = out[:-1]
    print(out)

def bubble_sort(a, n):
    for i in range(0, n):
        for j in range(n - 1, i, -1):
            if a[j].number < a[j - 1].number:
                tmp = a[j]
                a[j] = a[j - 1]
                a[j - 1] = tmp
    return a
                
def selection_sort(a, n):
    for i in range(0, n):
        minj = i
        for j in range(i, n):
            if a[j].number < a[minj].number:
                minj = j
        tmp = a[i]
        a[i] = a[minj]
        a[minj] = tmp
    return a

n = int(input())
input_cards = input().split(' ')
cards = []
for in_card in input_cards:
    cards.append(card(in_card))

bubble = bubble_sort(cards[:], n)
print_list(bubble)
print("Stable")

selection = selection_sort(cards[:], n)
print_list(selection)
if bubble == selection:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
from sys import stdin
from copy import deepcopy
from collections import namedtuple
#stdin = open("input.txt")

def bubbleSort(C, N):
    A = deepcopy(C)
    flag = True
    while flag:
        flag = False
        for j in range(N-1, 0, -1):
            if A[j].value < A[j-1].value:
                A[j], A[j-1] = A[j-1], A[j]
                flag = True
    return A

def selectionSord(C, N):
    A = deepcopy(C)
    for i in range(0, 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

if __name__ == "__main__":
    Card = namedtuple("Card", ["char", "value"])
    N = int(stdin.readline())
    A = [Card(item[0], int(item[1])) for item in stdin.readline().split()]
    
    bubble = bubbleSort(A, N)
    print(*[item.char+str(item.value) for item in bubble])
    
    bubble_value = [item.value for item in bubble]
    bubble_stable = True
    for v in set(bubble_value):
        bubble_char = [item for item in bubble if item.value==v]
        original_char = [item for item in A if item.value==v]
        if bubble_char != original_char:
            bubble_stable = False
    print("Stable" if bubble_stable else "Not stable")
        
        
    
    selection = selectionSord(A, N)
    print(*[item.char+str(item.value) for item in selection])
    
    selection_value = [item.value for item in selection]
    selection_stable = True
    for v in set(selection_value):
        selection_char = [item for item in selection if item.value==v]
        original_char = [item for item in A if item.value==v]
        if selection_char != original_char:
            selection_stable = False
    print("Stable" if selection_stable else "Not stable")

Submission status: Accepted

Solution code:
import re
def bubbleSort(c):
	flag=True
	while(flag):
		flag=False
		for i in range(len(c)-1):
			if(c[i][1] > c[i+1][1]):
				c[i],c[i+1] = c[i+1],c[i]
				flag=True
	return c

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

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

bubble=bubbleSort(c)
bubble_str=re.sub("[\[\]\,]","",str(bubble))
bubble_str=re.sub("\' ","",bubble_str)
print(re.sub("\'","",bubble_str))
print("Stable")

select=selectionSort(c2)
select_str=re.sub("[\[\]\,]","",str(select))
select_str=re.sub("\' ","",select_str)
print(re.sub("\'","",select_str))
if(bubble_str == select_str):
	print("Stable")
else:
	print("Not stable")

Submission status: Accepted

Solution code:
def get_value(s):
    return int(s[1])

def get_suit(s):
    return s[0]

def bubble_sort(A):
    a = list(A)
    for i in range(0, len(a)):
        
        
        for j in range(len(a)-1, i, -1):
            if get_value(a[j-1]) > get_value(a[j]):
                a[j-1], a[j] = a[j], a[j-1]
    return a

def selection_sort(A):
    a = list(A)
    for i in range(len(A)-1):
        i_min = i
        for j in range(i+1, len(A)):
            if get_value(a[j]) < get_value(a[i_min]):
                i_min = j
        a[i], a[i_min] = a[i_min], a[i]
    return a

def is_stable(A_orig, A_sort):
    dict_orig = {}
    dict_sort = {}
    
    # dict初期化
    for i in range(10):
        dict_orig[i] = list()
        dict_sort[i] = list()
    
    # dictに値設定
    for i in range(0, len(A_orig)):
        
        vo = get_value(A_orig[i])
        vs = get_value(A_sort[i])
        so = get_suit(A_orig[i])
        ss = get_suit(A_sort[i])
        
        dict_orig[vo].append(so)
        dict_sort[vs].append(ss)
    
    # stableかどうか検証
    for i in range(10):
        for j in range(len(dict_orig[i])):
            if dict_orig[i][j] is not dict_sort[i][j]:
                return False
    return True

input()
input_arr = input().split()

arr_bubble = bubble_sort(input_arr)
arr_selection = selection_sort(input_arr)

print(' '.join(arr_bubble))
print('Stable' if is_stable(input_arr, arr_bubble) else 'Not stable')
print(' '.join(arr_selection))
print('Stable' if is_stable(input_arr, arr_selection) else 'Not stable')

Submission status: Accepted

Solution code:
import sys


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


def SelectionSort(C):
    for i in range(len(C)):
        mini = i
        for j in range(i, len(C)):
            if C[j][1] < C[mini][1]:
                mini = j
        C[i], C[mini] = C[mini], C[i]


def stable(cards, C):
    for a in range(len(C)-1):
        c1 = cards.index(C[a])
        c2 = cards.index(C[a+1])
        if C[a][1] == C[a+1][1] and c1 > c2:
            print("Not stable")
            break
    else:
        print("Stable")


def main():
    input = sys.stdin.readline
    N = int(input())
    cards = input().split()
    bs = [i for i in cards]
    ss = [i for i in cards]
    BubbleSort(bs)
    SelectionSort(ss)
    print(" ".join(bs))
    stable(cards, bs)
    print(" ".join(ss))
    stable(cards, ss)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def s_sort(A,N):

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

       if i != min_j:
           temp = A[i]
           A[i] = A[min_j]
           A[min_j] = temp

   return A

def b_sort(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[:]
    Sr = s_sort(R,n)
    Br = b_sort(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

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]:
                x = c[j]
                c[j] = c[j-1]
                c[j-1] = x
    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
        x = c[i]
        c[i] = c[minj]
        c[minj] = x
    return c

n = int(input())
c = list(map(str, input().split()))
c1 = copy.deepcopy(c)
c2 = copy.deepcopy(c)

c1 = BubbleSort(c1, n)
print(*c1)
print('Stable')

c2 = SelectionSort(c2, n)
print(*c2)
if c1 == c2:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
"""ALDS1_2_C"""

from collections import namedtuple
from copy import deepcopy

Card = namedtuple("Card", ("suit", "value"))

def bubble(cards):
    cards = deepcopy(cards)
    N = len(cards)
    for i in range(N):
        for j in range(N-1, i, -1):
            if cards[j].value < cards[j-1].value:
                cards[j], cards[j-1] = cards[j-1], cards[j]
    return cards


def selection(cards):
    cards = deepcopy(cards)
    N = len(cards)
    for i in range(N):
        argmin = i
        for j in range(i, N):
            if cards[j].value < cards[argmin].value:
                argmin = j
        cards[i], cards[argmin] = cards[argmin], cards[i]
    return cards


def print_cards(cards):
    for i, card in enumerate(cards):
        end = "" if i == len(cards) - 1 else " "
        print(card.suit, card.value, sep="", end=end)
    print()


def main():
    _ = input()
    cards = [Card(i[0], int(i[1])) for i in input().split()]
    bubble_sorted = bubble(cards)
    selection_sorted = selection(cards)

    print_cards(bubble_sorted)
    print("Stable")
    print_cards(selection_sorted)
    if bubble_sorted == selection_sorted:
        print("Stable")
    else:
        print("Not stable")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy

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

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

def selection_sort(sel_C, N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if int(sel_C[j][1]) < int(sel_C[minj][1]):
                minj = j
        tmp = sel_C[i]
        sel_C[i] = sel_C[minj]
        sel_C[minj] = tmp
    return sel_C

def check_stable(C1, C2):
    C_order_table = {}
    sorted_C_order_table = {}
    for i in range(len(C1)):
        if C_order_table.get(C1[i][1]):
            C_order_table[C[i][1]] += C1[i][0]
        else:
            C_order_table[C1[i][1]] = C1[i][0]
        
        if sorted_C_order_table.get(C2[i][1]):
            sorted_C_order_table[C2[i][1]] += C2[i][0]
        else:
            sorted_C_order_table[C2[i][1]] = C2[i][0]
    
    is_stable = True
    for n in range(1, 10):
        if C_order_table.get(str(n)) != sorted_C_order_table.get(str(n)):
            is_stable = False
            break
    
    if is_stable:
        print('Stable')
    else:
        print('Not stable')

bubble_C = copy.copy(C)
sel_C = copy.copy(C)

sorted_C = bubble_sort(bubble_C, N)
print(" ".join(sorted_C))
check_stable(C, sorted_C)

sorted_C = selection_sort(sel_C, N)
print(" ".join(sorted_C))
check_stable(C, sorted_C)

Submission status: Accepted

Solution code:
n=int(input())
cards=input().split()
cards2=cards[:]
flag=1
while flag:
  flag=0
  for i in range(n-1,0,-1):
    if cards[i][1] < cards[i-1][1]:
      cards[i], cards[i-1]=cards[i-1],cards[i]
      flag=1
print(" ".join(cards))
print("Stable")

for i in range(n):
  minj = i
  for j in range(i,n):
    if cards2[j][1] < cards2[minj][1]:
      minj = j
  if i != minj:
    cards2[i], cards2[minj]=cards2[minj],cards2[i]
print(" ".join(cards2))
if cards == cards2:
  print("Stable")
else:
  print("Not stable")

Submission status: Accepted

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

def BubbleSort(A, N):
    for i in range(N):      # iは未ソートの部分列の先頭のインデックス
        for j in range(N-1, i, -1):     # 隣接要素を比較するのは未ソート部分列の末尾から先頭まで
            if A[j-1][1] > A[j][1]:           # 隣接要素を比較
                A[j-1], A[j] = A[j], A[j-1]     # 大小関係が逆の場合、交換
    return A


def SelectionSort(B, N):
    for i in range(N):
        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]       
    return B

ans_b = BubbleSort(A, N)
print(*ans_b)
print("Stable")
ans_s = SelectionSort(B, N)
print(*ans_s)
if ans_b == ans_s:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
def bubble_sort(a,n):
    for i in range(n):
        for j in range(n-1,i,-1):
            if a[j][1] < a[j-1][1]:
                a[j], a[j-1] = a[j-1], a[j]
    return a

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

def is_stable(a, sa, n):
    stable = True
    for i in range(n-1):
        if sa[i][1] == sa[i+1][1] and a.index(sa[i]) > a.index(sa[i+1]):
                stable = False
                break
    if stable:
        print('Stable')
    else:
        print('Not stable')

n = int(input())
a = [ (s[0], int(s[1:])) for s in input().split() ]
ba = bubble_sort(a.copy(),n)
print(*[ s[0]+str(s[1]) for s in ba])
is_stable(a,ba,n)
ia = selection_sort(a.copy(),n)
print(*[ s[0]+str(s[1]) for s in ia])
is_stable(a,ia,n)

Submission status: Accepted

Solution code:
def BubbleSort(a, n):
    flag = 1
    count = 0
    i = 0
    while flag:
        flag = 0
        for j in reversed(range(i+1,n)):
            if a[j][1] < a[j-1][1]:
                c = a[j]
                a[j] = a[j-1]
                a[j-1] = c
                flag = 1
                count += 1
        i += 1

def SelectionSort(a, N):
    count = 0
    minj = 0
    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:
            count += 1      
        c = a[i]
        a[i] = a[minj]
        a[minj] = c

n = int(input())
s = [x for x in input().split()]
s1 = s.copy()

BubbleSort(s,n)
for i in range(len(s)-1):
    print(s[i],end=' ')
print(s[-1])
print('Stable')

SelectionSort(s1,n)

for i in range(len(s1)-1):
    print(s1[i],end=' ')
print(s1[-1])
if s==s1:
    print('Stable')
else:
    print('Not stable')