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())
c = input().split()
c_sel = copy.deepcopy(c)

# check stability of default array
ord_dict_def = {}
for i in range(n) :
    if int(c[i][1]) in ord_dict_def.keys() :
        ord_dict_def[int(c[i][1])] += c[i][0]
    else :
        ord_dict_def[int(c[i][1])] = c[i][0]
        
# do bubble 
for i in range(n) :
    for j in range(n - 1, i, -1) :
        if int(c[j - 1][1]) > int(c[j][1]) :
            c[j - 1], c[j] = c[j], c[j - 1]

# check stability for bubble
ord_dict_bubble = {}

for i in range(n) :
    if int(c[i][1]) in ord_dict_bubble.keys() :
        ord_dict_bubble[int(c[i][1])] += c[i][0]
    else :
        ord_dict_bubble[int(c[i][1])] = c[i][0]
        
# do selection
for i in range(n) :
    cmin = i
    for j in range(i + 1, n) :
        if int(c_sel[j][1]) < int(c_sel[cmin][1]) :
            cmin = j
            
    if i != cmin :
        c_sel[i], c_sel[cmin] = c_sel[cmin], c_sel[i]

# check stability for selection
ord_dict_selection = {}

for i in range(n) :
    if int(c_sel[i][1]) in ord_dict_selection.keys() :
        ord_dict_selection[int(c_sel[i][1])] += c_sel[i][0]
    else :
        ord_dict_selection[int(c_sel[i][1])] = c_sel[i][0]
        
stability_bubble = "Stable"
stability_selection = "Stable"

for i in ord_dict_bubble.keys() :
    if ord_dict_def[i] != ord_dict_bubble[i] :
        stability_bubble = "Not stable"
        
    if ord_dict_def[i] != ord_dict_selection[i] :
        stability_selection = "Not stable"
        
print(" ".join(c))
print(stability_bubble)
print(" ".join(c_sel))
print(stability_selection)

Submission status: Accepted

Solution code:
# 配列の宣言
A = []
B = []

# 文字列の取得と加工
LENGTH =int(input())
A = input().split()
B = A.copy()

def bubble (A, LENGTH):
    N = 0
    M = LENGTH - 1
    CHANGE = 0

    while N <= LENGTH -1:
        M = LENGTH - 1
        while M >= N + 1:
            if int(A[M][1:]) < int(A[M-1][1:]):
                tmp = A[M-1]
                A[M-1] = A[M]
                A[M] = tmp
                CHANGE += 1
            M -= 1
        N += 1

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

def selection (B, LENGTH):
    i = 0
    CHANGE_COUNT = 0

    while i <= LENGTH -1:
        j = i + 1
        mini = i
        while j <= LENGTH -1:
            if int(B[j][1:]) < int(B[mini][1:]):
                mini = j
            j += 1
        if mini != i:
            tmp = B[i]
            B[i] = B[mini]
            B[mini] = tmp
            CHANGE_COUNT += 1
        i += 1

    print(" ".join(map(str,B)))
    if A == B:
        print("Stable")
    else:
        print("Not stable")

bubble (A, LENGTH)
selection (B, LENGTH)

Submission status: Accepted

Solution code:
import copy

def print_list(A):
    print(*A, sep=" ")

def swap(a, b):
    return b, a

def val(str):
    return int(str[1])

def is_stable(_in, _out, n):
    for i in range(0, n):
        for j in range(i+1, n):
            for a in range(0, n):
                for b in range(a+1, n):
                    if val(_in[i]) == val(_in[j]) and _in[i] == _out[b] and _in[j] == _out[a]:
                        return False
    return True

def print_stable(_in, _out, n):
    if is_stable(_in, _out, n):
        print("Stable")
    else:
        print("Not stable")    

def find_minj(A, i, n):
    minj = i
    for j in range(i, n):
        if val(A[j]) < val(A[minj]):
            minj = j
    return minj        

def bubble_sort(A, n):
    A0 = copy.copy(A)
    flg = 1 #逆の隣接要素が存在する
    i = 0
    while flg:
        flg = 0
        for j in range(n-1, i, -1):
            if val(A[j-1]) > val(A[j]):
                A[j-1], A[j] = swap(A[j-1], A[j])
                flg = 1
        i += 1
    print_list(A)
    print_stable(A0, A, n)

def selection_sort(A, n):
    A0 = copy.copy(A)
    for i in range(0, n):
        minj = find_minj(A, i, n)
        if val(A[i]) > val(A[minj]):
            A[i], A[minj] = swap(A[i], A[minj])
    print_list(A)
    print_stable(A0, A, n)

n = int(input())
A = list(map(str,input().split()))
B = copy.copy(A)

bubble_sort(A, n)
selection_sort(B, n)

Submission status: Accepted

Solution code:
class Card():
    def __init__(self, card):
        self.card = card
        self.mark = card[0]
        self.number = card[1]
        
    def __lt__(self, other):
        if not isinstance(other, Card):
            return NotImplemented
        return self.number < other.number
    
    def __eq__(self, other):
        if not isinstance(other, Card):
            return NotImplemented
        return self.mark == other.mark and self.number == other.number
        
    def __repr__(self):
        return '{}{}'.format(self.mark, self.number)

    def ls_sort(self):
        return


def BubbleSort(target):
    ls = target.copy()
    flag = 1
    while flag:
        flag = 0
        for i in range(len(ls)-1, 0, -1):
            if ls[i] < ls[i-1]:
                ls[i], ls[i-1] = ls[i-1], ls[i]
                flag = 1
    print(' '.join(map(str, ls)))
    return sorted(ls)


def SelectSort(target):
    ls = target.copy()
    for i in range(len(ls)):
        minj = i
        for j in range(i+1, len(ls)):
            if ls[j] < ls[minj]:
                minj = j
        if ls[i] != ls[minj]:
            ls[i], ls[minj] = ls[minj], ls[i]
    
    print(' '.join(map(str, ls)))
    return sorted(ls)

def judge(original, sorted_list):
    if original == sorted_list:
        print('Stable')
    else:
        print('Not stable')


_ = int(input())
l2 =  [Card(i) for i in input().split()]
l2_sort = sorted(l2)

bubble = BubbleSort(l2)
judge(l2_sort, bubble)

select = SelectSort(l2)
judge(l2_sort, select)

Submission status: Accepted

Solution code:
class Card():
    def __init__(self, card):
        self.card = card
        self.mark = card[0]
        self.number = card[1]
        
    def __lt__(self, other):
        if not isinstance(other, Card):
            return NotImplemented
        return self.number < other.number
    
    def __eq__(self, other):
        if not isinstance(other, Card):
            return NotImplemented
        return self.mark == other.mark and self.number == other.number
        
    def __repr__(self):
        return '{}{}'.format(self.mark, self.number)


def BubbleSort(target):
    ls = target.copy()
    flag = 1
    while flag:
        flag = 0
        for i in range(len(ls)-1, 0, -1):
            if ls[i] < ls[i-1]:
                ls[i], ls[i-1] = ls[i-1], ls[i]
                flag = 1
    print(' '.join(map(str, ls)))
    return sorted(ls)


def SelectSort(target):
    ls = target.copy()
    for i in range(len(ls)):
        minj = i
        for j in range(i+1, len(ls)):
            if ls[j] < ls[minj]:
                minj = j
        if ls[i] != ls[minj]:
            ls[i], ls[minj] = ls[minj], ls[i]
    
    print(' '.join(map(str, ls)))
    return sorted(ls)

def judge(original, sorted_list):
    if original == sorted_list:
        print('Stable')
    else:
        print('Not stable')


_ = int(input())
l2 =  [Card(i) for i in input().split()]
l2_sort = sorted(l2)

bubble = BubbleSort(l2)
judge(l2_sort, bubble)

select = SelectSort(l2)
judge(l2_sort, select)

Submission status: Accepted

Solution code:
class Card():
    def __init__(self, card):
        self.card = card
        self.mark = card[0]
        self.number = card[1]
        
    def __lt__(self, other):
        if not isinstance(other, Card):
            return NotImplemented
        return self.number < other.number
        
    def __repr__(self):
        return '{}{}'.format(self.mark, self.number)


def BubbleSort(target):
    ls = target.copy()
    flag = 1
    while flag:
        flag = 0
        for i in range(len(ls)-1, 0, -1):
            if ls[i] < ls[i-1]:
                ls[i], ls[i-1] = ls[i-1], ls[i]
                flag = 1
    print(' '.join(map(str, ls)))
    return sorted(ls)


def SelectSort(target):
    ls = target.copy()
    for i in range(len(ls)):
        minj = i
        for j in range(i+1, len(ls)):
            if ls[j] < ls[minj]:
                minj = j
        if ls[i] != ls[minj]:
            ls[i], ls[minj] = ls[minj], ls[i]
    
    print(' '.join(map(str, ls)))
    return sorted(ls)

def judge(original, sorted_list):
    if original == sorted_list:
        print('Stable')
    else:
        print('Not stable')


_ = int(input())
l2 =  [Card(i) for i in input().split()]
l2_sort = sorted(l2)

bubble = BubbleSort(l2)
judge(l2_sort, bubble)

select = SelectSort(l2)
judge(l2_sort, select)

Submission status: Accepted

Solution code:
# Stable Sort

length = int(input())
cards = input().rstrip().split()
cards1 = [card for card in cards]
cards2 = [card for card in cards]

def value(n):
    number = n[1:]
    return int(number)

def char(cards):
    charSets = [[] for i in range(10)]
    for i in range(length):
        char = cards[i][:1]
        val = value(cards[i])
        # print('絵柄: ' + char + ', 数字: ' + str(val))
        charSets[val].append(char)
    return charSets

def bubble(cards):
    for i in range(length):
        j = length - 1
        while j > i:
            if value(cards[j]) < value(cards[j - 1]):
                cards[j], cards[j - 1] = cards[j - 1], cards[j]
            j -= 1
    return cards

def selection(cards):
    # count = 0
    for i in range(length):
        minj = i
        for j in range(i, length):
            if value(cards[j]) < value(cards[minj]):
                minj = j
        #if minj != i:
            # count += 1
        cards[i], cards[minj] = cards[minj], cards[i]
    return cards

def stable(cards1, cards2):
    if char(cards1) == char(cards2):
        return 'Stable'
    else:
        return 'Not stable'

c = cards
b = bubble(cards1)
s = selection(cards2)

print(' '.join(b))
print(stable(c, b))
print(' '.join(s))
print(stable(c, s))

Submission status: Accepted

Solution code:
#! /usr/local/bin/python3
# coding: utf-8

def swap(c, i, j):
    t = c[i]
    c[i] = c[j]
    c[j] = t

def bubble_sort(cs, f):
    c = cs[:]
    for i in range(len(c) - 1):
        for j in range(len(c) - 1, i, -1):
            if f(c[j - 1]) > f(c[j]):
                swap(c, j - 1, j)
            # print(i, j, c)
    return c

def selection_sort(cs, f):
    c = cs[:]
    for i in range(len(c)):
        minj = i
        for j in range(i, len(c)):
            if f(c[j]) < f(c[minj]):
                minj = j
        swap(c, i, minj)
        # print(c)
    return c

def to_group(c):
    b = {}
    for i in c:
        if not(i[1] in b):
            b[i[1]] = [i]
        else:
            b[i[1]] = b[i[1]] + [i]
    return b

def is_stable(c, s): 
    bc = to_group(c)
    bs = to_group(s(c, lambda x: x[1]))
    # print(bc)
    # print(bs)
    for k in bc:
        if bc[k] != bs[k]:
            return "Not stable"
    return "Stable"

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

print(" ".join(bubble_sort(c, lambda x: x[1])))
print(is_stable(c, bubble_sort))

print(" ".join(selection_sort(c, lambda x: x[1])))
print(is_stable(c, selection_sort))

Submission status: Accepted

Solution code:
N = int(input())
C1 = list(input().split()) 
C2 = C1[:]

def get_card_suit(card):
    return card[:1]

def get_card_value(card):
    return card[1:]

def bubble_sort(card):
    r_exists = True

    while r_exists == True:

        r_exists = False

        i = N - 1

        while i >= 1:

            if get_card_value(card[i]) < get_card_value(card[i - 1]):
                
                card[i], card[i - 1] = card[i - 1], card[i]

                r_exists = True
            
            i -= 1

def select_sort(card):
    i = 0

    while i < N:

        min_j = i
        j = i

        while j < N:

            if get_card_value(card[j]) < get_card_value(card[min_j]):

                min_j = j

            j += 1

        card[i], card[min_j] = card[min_j], card[i]

        i += 1

def output(card):
    s = ''

    for x in card:

        s = s + str(x) + ' '

    print(s.rstrip())

def is_stable():
    i = 0

    while i < N:
        if get_card_suit(C1[i]) != get_card_suit(C2[i]):
            return False
        i += 1
    
    return True

bubble_sort(C1)
select_sort(C2)

output(C1)
print('Stable')

output(C2)
if is_stable() == True:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
_, cards = input(), input().split()

def bubble_sort(array):
    A = array[:]
    for i in range(len(A)):
        for j in range(1, len(A) - i):
            if int(A[j - 1][1]) > int(A[j][1]):
                A[j], A[j - 1] = A[j - 1], A[j]
    return A

def selection_sort(array):
    A = array[:]
    for i in range(len(A)):
        minn = i
        for j in range(i, len(A)):
            if int(A[j][1]) < int(A[minn][1]): minn = j
        A[i], A[minn] = A[minn], A[i]
    return A
def is_stable(org, sorted):

    def get_same_numbers(array):
        result = {}
        for i in range(1, 10):
            result[i] = []
            for j in range(len(array)):
                if int(array[j][1]) == i:
                    result[i].append(array[j])
        return [cards for _, cards in result.items() if len(cards) >= 2]

    return "Stable" if get_same_numbers(org) == get_same_numbers(sorted) else "Not stable"

a = bubble_sort(cards)
print(" ".join(a))
print(is_stable(cards, a))
b = selection_sort(cards)
print(" ".join(b))
print(is_stable(cards, b))

Submission status: Accepted

Solution code:
def bubble_sort(a, n):
  for i in range(0,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(b, n):
  for i in range(0,n):
    minj = i
    for j in range(i, n):
      if b[j][1] < b[minj][1]:
        minj = j
    b[i], b[minj] = b[minj], b[i]
  return b

if __name__ == '__main__':
  n = int(input())
  a = list(map(str, input().split()))
  b = a[:]
  buble = bubble_sort(a,n)
  select = selection_sort(b,n)
  print(" ".join(map(str, buble)))
  print("Stable")
  print(" ".join(map(str, select)))
  if select == buble:
    print("Stable")
  else:
    print("Not stable")

Submission status: Accepted

Solution code:
n = int(input())
*s1, = input().split()
s2 = s1[:]

def bubbleSort(s):
    flag = True
    while flag:
        flag = False
        for i in range(n-1):
            if int(s[i][1]) > int(s[i+1][1]):
                s[i],s[i+1] = s[i+1],s[i]
                flag = True
    return s

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

print(' '.join(bubbleSort(s1)))
print("Stable")
print(' '.join(selectionSort(s2)))
if s1 == s2:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
from copy import  deepcopy
def bubble_sort(lst):
    size=len(lst)
    for i in xrange(size):
        for j in reversed(range(i+1,size)):
            if lst[j].num<lst[j-1].num:
                tmp=lst[j]
                lst[j]=lst[j-1]
                lst[j-1]=tmp
def selection_sort(lst):
    size=len(lst)
    for i in xrange(size):
        mn=i
        for j in xrange(i+1,size):
            if lst[mn].num>lst[j].num:
                mn=j
        tmp=lst[i]
        lst[i]=lst[mn]
        lst[mn]=tmp
class pock:
    def __init__(self,val):
        self.val=val
        self.num=int(val[1:])
    def __gt__(self,other):
        return self.num>other.num


num=raw_input().strip()
inp=raw_input().strip().split()
arr=[]
for ii in inp:
    arr.append(pock(ii))
bubb=deepcopy(arr)
bubble_sort(bubb)
insec=deepcopy(arr)
selection_sort(insec)
print " ".join(pp.val for pp in bubb)
print "Stable"

print " ".join(pp.val for pp in insec)
ok=1
ln=len(arr)
for i  in xrange(ln):
    if(bubb[i].val!=insec[i].val):
        ok=0
        break
if ok==1:
    print "Stable"
else:
    print "Not stable"

Submission status: Accepted

Solution code:
def bubble_sort(A, N):
    cnt = 0
    flag = True
    while flag:
        flag = False
        for j in range(N - 1, 0, -1):
            if int(A[j - 1][1]) > int(A[j][1]):
                A[j - 1], A[j] = A[j], A[j - 1]
                flag = True
                cnt += 1
    return A

def selection_sort(A, N):
    cnt = 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
        A[i], A[minj] = A[minj], A[i]
        if i != minj:
            cnt += 1
    return A

N = int(input())
A = input().split()
order_A = [[] for _ in range(10)]
for s in A:
    order_A[int(s[1])].append(s)

order_bubble = [[] for _ in range(10)]
b_sorted = bubble_sort(A[:], N)
for s in b_sorted:
    order_bubble[int(s[1])].append(s)
print(*b_sorted)
print('Stable' if order_A == order_bubble else 'Not stable')

s_stability = [[] for _ in range(10)]
s_sorted = selection_sort(A[:], N)
for s in s_sorted:
    s_stability[int(s[1])].append(s)
print(*s_sorted)
print('Stable' if order_A == s_stability else 'Not stable')

Submission status: Accepted

Solution code:
def bubble_sort(card_list):
    cards = [i for i in card_list]
    list_length = len(cards)

    for i in range(list_length):
        for j in range(list_length-1,i,-1):
            if int(cards[j][1:]) < int(cards[j-1][1:]):
                cards[j],cards[j-1] = cards[j-1],cards[j]
    return cards

def selection_sort(card_list):
    cards = [i for i in card_list]

    list_length = len(cards)

    for i in range(list_length):
        min_element = i
        for j in range(i+1,list_length):
            if int(cards[j][1:]) < int(cards[min_element][1:]):
                min_element = j
        cards[i],cards[min_element] = cards[min_element],cards[i]
    return cards

n = int(input())
cards = input().split()
bubble_cards = bubble_sort(cards)
selection_cards = selection_sort(cards)

print(' '.join(bubble_cards))
print('Stable')
print(' '.join(selection_cards))
if bubble_cards == selection_cards:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
import copy
n=int(input())
num=input().split()
numa=copy.copy(num)
numb=copy.copy(num)

#buble
for i in range(0,n):
	a=0
	for j in range(n-1,i,-1):
		if numa[j][1:]<numa[j-1][1:]:
			a=numa[j]
			numa[j]=numa[j-1]
			numa[j-1]=a
print(' '.join(list(map(str,numa))))
print('Stable')

#select
for i in range(0,n):
	minj=i
	b=0
	for j in range(i,n):
		if numb[j][1:]<numb[minj][1:]:
			minj=j
	b=numb[minj]
	numb[minj]=numb[i]
	numb[i]=b
print(' '.join(list(map(str,numb))))
if numb==numa:
	print('Stable')
else:
	print('Not stable')

Submission status: Accepted

Solution code:
n = int(input())
a = [i for i in input().split()]
a2 = a.copy()
for i in range(n):
    for j in reversed(range(i+1, n)):
        if a[j][1] < a[j-1][1]:
            a[j], a[j-1] = a[j-1], a[j]
for s in range(n):
    minj = s 
    for t in range(s+1, n):
        if a2[t][1] < a2[minj][1]:
            minj = t
    if a2[s] != a2[minj]:
        a2[s], a2[minj] = a2[minj], a2[s]
print(*a)
print("Stable")
print(*a2)
if a == a2:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
def bubble_sort(array):
    n = len(array)

    while True:
        flag = False
        for i in range(1, n)[::-1]:
            if array[i-1][1] > array[i][1]:
                tmp = array[i]
                array[i] = array[i-1]
                array[i-1] = tmp
                flag = True
        if not flag:
            break
    return array

def selection_sort(array):
    n = len(array)

    for i in range(n):
        min_idx = i
        for j in range(i, n):
            if array[j][1] < array[min_idx][1]:
                min_idx = j
        if min_idx != i:
            tmp = array[i]
            array[i] = array[min_idx]
            array[min_idx] = tmp
    return array

def accum_hcsd_order(array):
    hcsd_order = {}
    for item in array:
        if item[1] in hcsd_order:
            hcsd_order[item[1]].append(item[0])
        else:
            hcsd_order[item[1]] = [item[0]]
    return hcsd_order


def check_stable(array, hcsd_order):
    tgt_hcsd_order = accum_hcsd_order(array)

    for no, hcsd in hcsd_order.items():
        if len(hcsd) == 1:
            continue
        tgt_hcsd = tgt_hcsd_order[no]
        for src, tgt in zip(hcsd, tgt_hcsd):
            if src != tgt:
                return False
    return True


def main():
    n = int(input())
    array = [(x[0], int(x[1:])) for x in input().split()]
    str_stable_or_not = {True: "Stable", False: "Not stable"}

    hcsd_order = accum_hcsd_order(array)

    # bubble_sort
    array_b = array[:]
    array_b = bubble_sort(array_b)
    print(" ".join(map(lambda x: "{}{}".format(x[0],x[1]), array_b)))
    print(str_stable_or_not[check_stable(array_b, hcsd_order)])

    # selection_sort
    array_s = array[:]
    array_s = selection_sort(array_s)
    print(" ".join(map(lambda x: "{}{}".format(x[0], x[1]), array_s)))
    print(str_stable_or_not[check_stable(array_s, hcsd_order)])

    return

main()

Submission status: Accepted

Solution code:
n = int(input())
A = input().rstrip().split()
B = list(map(lambda x:int(x[1]), A))
C = list(enumerate(B))
D = list(enumerate(B))

Cb = C
nums = [n - i for i in range(1, n)]
flag = 1

while flag == 1:
    flag = 0
    for j in nums:
        if Cb[j][1] < Cb[j - 1][1]:
            Cb[j], Cb[j - 1] = Cb[j - 1], Cb[j]
            flag = 1
        else:
            pass
Ab = [A[Cb[i][0]] for i in range(n)]
print(*Ab)
bstable = 1
for j in range(n - 1):
    if Cb[j + 1][1] == Cb[j][1] and Cb[j + 1][0] < Cb[j][0]:
        bstable = 0
        break
if bstable == 1:
    print("Stable")
else:
    print("Not stable")

Cs = D
for i in range(n):
    minj = i
    for j in range(i, n):
        if Cs[j][1] < Cs[minj][1]:
            minj = j
        else:
            pass
    Cs[i], Cs[minj] = Cs[minj], Cs[i]
    
As = [A[Cs[i][0]] for i in range(n)]
print(*As)
cstable = 1
for j in range(n - 1):
    if Cs[j + 1][1] == Cs[j][1] and Cs[j + 1][0] < Cs[j][0]:
        cstable = 0
        break
if cstable == 1:
    print("Stable")
else:
    print("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
        if i!=minj:
            A[i],A[minj]=A[minj],A[i]
             
   
           
n=int(input())
ss=[x for x in input().split()]     
ss2=ss.copy()
 
 
bubble(ss)
for i in range(len(ss)-1):
    print(ss[i],end=' ')
print(ss[-1])
print('Stable')
    
 
selection(ss2)
for i in range(len(ss2)-1):
    print(ss2[i],end=' ')
print(ss2[-1])
if ss==ss2:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

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

def BubbleSort(A,n):
    for i in range(n):
        for j in range(n-1,i,-1):
            if int(A[j][1:2])<int(A[j-1][1:2]):
                v = A[j]
                A[j] = A[j-1]
                A[j-1] = v
    return A

def SelectionSort(A,n):
    for i in range(n):
        minj = i
        for j in range(i,n):
            if int(A[j][1:2])<int(A[minj][1:2]):
                minj = j
        v = A[i]
        A[i] = A[minj]
        A[minj] = v
    return A

print(' '.join(BubbleSort(A,n)))
print('Stable')
print(' '.join(SelectionSort(B,n)))
if BubbleSort(A,n) == SelectionSort(B,n):
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
N = int(input())
array = list(input().split())
array2 = array[:]
array3 = array[:]

def bubble_sort(array, N):
	flag = 1
	i = 0
	while flag:
		flag = 0 
		j = N-1
		while j > i:
			if array[j][1] < array[j-1][1]:
				array[j], array[j-1] = array[j-1], array[j]
			j -= 1
			flag = 1
		i += 1


def selection_sort(array, n):
	for i in range(n):
		minij = i 
		for j in range(i, n):
			if array[j][1] < array[minij][1]:
			    minij = j 
		array[i], array[minij] = array[minij], array[i]

def is_stable(Input, output, 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 Input[i][1] == Input[j][1] and Input[i] == output[b] and Input[j] == output[a]:
						return False
	return True 

bubble_sort(array, N)
print(' '.join(array))
print('Stable')
selection_sort(array2,N)
print(' '.join(array2))
if is_stable(array3, array2, N):
	print('Stable')
else:
	print('Not stable')

Submission status: Accepted

Solution code:
import copy

def bubble_sort(a):
    ba = copy.copy(a)
    flag = True
    for i in range(0, n):
        if not flag:
            break
        flag = False
        for j in range(n-1, 0, -1):
            if int(ba[j][1]) < int(ba[j-1][1]):
                ba[j], ba[j-1] = ba[j-1], ba[j]
                flag = True

    return ba

def selection_sort(a):
    sa = copy.copy(a)
    for i in range(n):
        flag = False
        minj = i
        for j in range(i, n):
            if int(sa[j][1]) < int(sa[minj][1]):
                minj = j
                flag = True
        if flag:
            sa[i], sa[minj] = sa[minj], sa[i]

    return sa

def is_stable(ba, sa):
    for b, s in zip(ba, sa):
        if b != s:
            return 'Not stable'
    return 'Stable'


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

ba = bubble_sort(a)
print(' '.join(map(str, ba)))
print('Stable')

sa = selection_sort(a)
print(' '.join(map(str, sa)))
print(is_stable(ba, sa))

Submission status: Accepted

Solution code:
from typing import List


def get_value(card: str) -> int:
    return card[1]


def bublle_sort(C: List[str]) -> None:
    for i in range(len(C)):
        for j in reversed(range(i + 1, len(C))):
            if get_value(C[j]) < get_value(C[j - 1]):
                C[j], C[j - 1] = C[j - 1], C[j]


def selection_sort(C: List[str]) -> None:
    for i in range(len(C)):
        min_j = i
        for j in range(i, len(C)):
            if get_value(C[j]) < get_value(C[min_j]):
                min_j = j
        C[i], C[min_j] = C[min_j], C[i]


def is_stable(A_in, A_out) -> bool:
    for i in range(len(A_in)):
        for j in range(i + 1, len(A_in)):
            for a in range(len(A_out)):
                for b in range(a + 1, len(A_out)):
                    if get_value(A_in[i]) == get_value(A_in[j]) and A_in[i] == A_out[b] and A_in[j] == A_out[a]:
                        return False
    return True


N = int(input())
C = [str(i) for i in input().split()]
C1 = [i for i in C]
C2 = [i for i in C]

bublle_sort(C1)
print(' '.join(C1))
if is_stable(C, C1):
    print('Stable')
else:
    print('Not stable')

selection_sort(C2)
print(' '.join(C2))
if is_stable(C, C2):
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
def bubble_sort(C, N):
    card = []
    for c in C:
        card.append({'suit': c[0], 'value': int(c[1])})
            
    for i in range(N):
        for j in range(N-1, i, -1):
            if card[j]['value'] < card[j-1]['value']:
                card[j], card[j-1] = card[j-1], card[j]

    new_C = []
    for i in range(N):
        new_C.append(card[i]['suit'] + str(card[i]['value']))
        
    return new_C


def selection_sort(C, N):
    card = []
    for c in C:
        card.append({'suit': c[0], 'value': int(c[1])})

    for i in range(N):
        min_j = i
        for j in range(i, N):
            if card[j]['value'] < card[min_j]['value']:
                min_j = j
        card[i], card[min_j] = card[min_j], card[i]
        
    new_C = []
    for i in range(N):
        new_C.append(card[i]['suit'] + str(card[i]['value']))
        
    return new_C


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

C_b = bubble_sort(C, N)
C_s = selection_sort(C, N)

print(' '.join(C_b))
print('Stable')

print(' '.join(C_s))
if C_s == C_b:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

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


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


def print_list(a):
    print(" ".join([s + v for s, v in a]))


def is_stable(l1, l2):
    def get_original_index(v):
        for i, e in enumerate(l1):
            if v == e:
                return i
        return Exception("bug")

    before = l2[0]
    for e in l2[1:]:
        if before[1] == e[1]:
            # print(before, e)
            bi = get_original_index(before)
            ei = get_original_index(e)
            # print(bi, ei)
            if bi > ei:
                return False
        before = e

    return True


n = int(input())
tmp = input().split()
a = []
for v in tmp:
    a.append((v[0], v[1]))

bs_result = bubble_sort(a, n)
ss_result = selection_sort(a, n)

print_list(bs_result)
if is_stable(a, bs_result):
    print("Stable")
else:
    print("Not stable")

print_list(ss_result)
if is_stable(a, ss_result):
    print("Stable")
else:
    print("Not stable")