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 re
import copy
pattern = r'([0-9])'
repatter = re.compile(pattern)

n = int(input())
text = input()

*lists, = text.split(" ")
lists2 = copy.copy(lists)
lists3 = copy.copy(lists)


# バブルソート
def bubble_sort(a):
    flag = 1
    i = 0
    while flag:
        flag = 0
        for j in range(n-1, i, -1):
            x = repatter.findall(a[j])
            y = repatter.findall(a[j-1])
            if x < y:
                a[j], a[j-1] = a[j-1], a[j]
                flag = 1
        i += 1
    print(*a)
    print("Stable")


# 選択ソート
def select_sort(a):
    for i in range(n):
        min_j = i
        for j in range(i+1, n):
            x = repatter.findall(a[j])
            y = repatter.findall(a[min_j])
            if x < y:
                min_j = j
        a[i], a[min_j] = a[min_j], a[i]
    print(*a)


def isStable(before, after):
    flag = True
    for i in range(n):
        for j in range(i+1, n):
            for a in range(n):
                for b in range(a+1, n):
                    x = repatter.findall(before[i])
                    y = repatter.findall(before[j])
                    if x == y and before[i] == after[b] and before[j] == after[a]:
                        flag = False
    if flag is True:
        print("Stable")
    else:
        print("Not stable")


bubble_sort(lists)
select_sort(lists2)
isStable(lists3, lists2)

Submission status: Accepted

Solution code:
n = int(input())
l = []
for i in input().split():
  t = []
  for j in i: t += [j]
  l += [t]

t = l[:]
f = 0
for i in range(n):
  for j in range(n-1, 0, -1):
    if t[j][1] < t[j-1][1]:
      t[j], t[j-1] = t[j-1], t[j]
    elif t[j][1] == t[j-1][1]:
      f += 1 if l.index(t[j-1]) > l.index(t[j]) else 0
print(*["{0}{1}".format(i[0], i[1]) for i in t])
print("Not stable" if f > 0 else "Stable")

x = l[:]
f = 0
for i in range(n):
  m = i
  for j in range(i, n):
    if x[j][1] < x[m][1]:
      m = j
    elif x[j][1] == x[m][1]:
      f += 1 if l.index(x[m]) > l.index(x[j]) else 0
  x[i], x[m] = x[m], x[i]
print(*["{0}{1}".format(i[0], i[1]) for i in x])
print("Not stable" if f > 0 else "Stable")

Submission status: Accepted

Solution code:
class Card:
    def __init__(self, label):
        suits = ['S', 'H', 'C', 'D']
        suit, value = list(label)
        assert(suit in suits and 0 < int(value) < 10)

        self.suit = suit
        self.value = int(value)

    def __eq__(self, other):
        """equal

        >>> Card('S1') == Card('D9')
        False
        >>> Card('D9') == Card('S1')
        False
        >>> Card('C5') == Card('C5')
        True
        """
        return self.value == other.value

    def __lt__(self, other):
        """less than

        >>> Card('S1') < Card('D9')
        True
        >>> Card('D9') < Card('S1')
        False
        """
        return self.value < other.value

    def __gt__(self, other):
        """greater than

        >>> Card('S1') > Card('D9')
        False
        >>> Card('D9') > Card('S1')
        True
        """
        return self.value > other.value

    def __hash__(self):
        return hash((self.suit, self.value))

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


def bubble_sort(deck):
    """sort deck by bubble sort

    >>> deck = [Card('H4'), Card('C9'), Card('S4'), Card('D2'), Card('C3')]
    >>> print(" ".join([str(c) for c in bubble_sort(deck)]))
    D2 C3 H4 S4 C9
    """
    size = len(deck)
    for i in range(size):
        for j in reversed(range(i+1, size)):
            if deck[j] < deck[j-1]:
                deck[j-1], deck[j] = deck[j], deck[j-1]

    return deck


def selection_sort(deck):
    """sort deck by selection sort

    >>> deck = [Card('H4'), Card('C9'), Card('S4'), Card('D2'), Card('C3')]
    >>> print(" ".join([str(c) for c in selection_sort(deck)]))
    D2 C3 S4 H4 C9
    """
    size = len(deck)
    for i in range(size):
        mini = i
        for j in range(i, size):
            if deck[mini] > deck[j]:
                mini = j
        deck[i], deck[mini] = deck[mini], deck[i]

    return deck


def is_stable_sorted(org, deck):
    """check if deck is sorted by stable manner

    >>> c1 = Card('S1')
    >>> c2 = Card('D1')
    >>> is_stable_sorted([c1, c2], [c1, c2])
    True
    >>> is_stable_sorted([c1, c2], [c2, c1])
    False
    """
    idx = {c:i for (i, c) in enumerate(org)}
    return all([c1 < c2 or idx[c1] < idx[c2]
                for (c1, c2) in zip(deck[:-1], deck[1:])])


def check_stable(org, deck):
    if is_stable_sorted(org, deck):
        return "Stable"
    else:
        return "Not stable"


def run():
    _ = int(input()) # flake8: noqa
    deck = []
    for lb in input().split():
        deck.append(Card(lb))

    db = bubble_sort(deck[:])
    print(" ".join([str(c) for c in db]))
    print(check_stable(deck, db))

    ds = selection_sort(deck[:])
    print(" ".join([str(c) for c in ds]))
    print(check_stable(deck, ds))


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
n = int(input())
*bLst, = input().split()
iLst = bLst[:]

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

print(*bLst)
print("Stable")

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

print(*iLst)
if bLst == iLst:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
def bubble_sort(seq):
    for i in range(len(seq)):
        flag = 0
        for j in range(len(seq)-1,i,-1):
            if seq[j-1][1] > seq[j][1]:
                seq[j-1],seq[j] = seq[j],seq[j-1]
                flag = 1
        if flag == 0: break
    return seq


def selection_sort(seq):
    for i in range(len(seq)):
        mini = i
        for j in range(i,len(seq)):
            if seq[mini][1] > seq[j][1]:mini = j
        seq[i],seq[mini] = seq[mini],seq[i]
    return seq



n = int(input())
*seq,= input().split()
seq2 = seq[:]

bl = bubble_sort(seq)
print(*bl)
print("Stable")
sl = selection_sort(seq2)
print(*sl)
if bl == sl:print("Stable")
else:print("Not stable")

Submission status: Accepted

Solution code:
def selection_sort(A):
    steps = 0
    N = len(A)
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if A[minj][0] > A[j][0]:
                minj = j
        if i != minj:
            steps += 1
        A[minj], A[i] = A[i], A[minj]

    # [print(A[idx], end=' ') if idx != len(A) - 1 else print(A[idx]) for idx in range(len(A))]
    # print(steps)
    return A


def bubbleSort(A):
    steps = 0
    flag = 1
    completed_idx = 0
    while flag:
        flag = 0
        for i in range(len(A) - 1, completed_idx, -1):
            if A[i - 1][0] > A[i][0]:
                A[i - 1], A[i] = A[i], A[i - 1]
                steps += 1
                flag = 1
        completed_idx += 1

    # for e in A[:-1]:
    #     print(e, end=' ')
    # print(A[-1])
    # print(steps)
    return A

d = dict()
N = int(input())
A = [(int(elem[1:]), elem[0]) for elem in input().split()]

for elem in A:
    if elem[0] not in d:
        d[elem[0]] = elem[1]
    else:
        d[elem[0]] += elem[1]

is_stable = True
A_bubble = bubbleSort(A[:])
st = A_bubble[0][1]
cur_val = A_bubble[1][0]
prev_val = A_bubble[0][0]
for e in A_bubble[1:]:
    cur_val = e[0]
    if cur_val != prev_val:
        if st != d[prev_val]:
            is_stable = False
            break
        st = ''
    st += e[1]
    prev_val = cur_val
[print(A_bubble[idx][1] + str(A_bubble[idx][0]), end=' ') if idx != len(A_bubble) - 1 else print(A_bubble[idx][1] + str(A_bubble[idx][0])) for idx in range(len(A_bubble))]
print('Stable' if is_stable else 'Not stable')

is_stable = True
A_slt = selection_sort(A[:])
st = A_slt[0][1]
cur_val = A_slt[1][0]
prev_val = A_slt[0][0]
for e in A_slt[1:]:
    cur_val = e[0]
    if cur_val != prev_val:
        if st != d[prev_val]:
            is_stable = False
            break
        st = ''
    st += e[1]
    prev_val = cur_val

[print(A_slt[idx][1] + str(A_slt[idx][0]), end=' ') if idx != len(A_slt) - 1 else print(A_slt[idx][1] + str(A_slt[idx][0])) for idx in range(len(A_slt))]
print('Stable' if is_stable else 'Not stable')
#
# 5
# H4 C9 S4 D2 C3

Submission status: Accepted

Solution code:
def bubbleSort(c):
    for i in range(0, len(c) - 1):
        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(0, len(c)):
        minj = i
        for j in range(i, len(c)):
            if c[j][1] < c[minj][1]:
                minj = j
        c[i], c[minj] = c[minj], c[i]


def isStable(c1, c2):
    for i in range(0, len(c1)):
        if c1[i][0] != c2[i][0]:
            return False
    return True


import copy
n = int(input())
c1 = input().split()
c2 = copy.copy(c1)

bubbleSort(c1)
selectionSort(c2)
print(*c1)
print("Stable")
print(*c2)
print("Stable") if isStable(c1, c2) else print("Not stable")

Submission status: Accepted

Solution code:
#! python3
# stable_sort.py

import copy

def num_from_card(card):
    return int(card[1:])

def bubble_sort(A, N):
    A_ = copy.copy(A)
    flag = True
    while flag:
        flag = False
        for i in range(N-1, 0, -1):
            if num_from_card(A_[i]) < num_from_card(A_[i-1]):
                A_[i-1], A_[i] = A_[i], A_[i-1]
                flag = True
    return A_

def selection_sort(A, N):
    A_ = copy.copy(A)
    for i in range(N-1):
        minj = i
        for j in range(i, N):
            if num_from_card(A_[j]) < num_from_card(A_[minj]):
                minj = j
        if i != minj:
            A_[i], A_[minj] = A_[minj], A_[i]
    return A_

def is_stable(A, sorted_A, N):
    A_nums = [int(x[1:]) for x in A]
    same_num = [x for x in set(A_nums) if A_nums.count(x) > 1]
    A_symbols, sorted_A_symbols = [], []
    flag = 'Stable'
    for num in same_num:
        if [card[0] for card in A if int(card[1:]) == num] != [card[0] for card in sorted_A if int(card[1:]) == num]:
            flag = 'Not stable'
            break
    return flag

N = int(input())
cards = [x for x in input().split(' ')]

bubble_sorted = bubble_sort(cards, N)
selection_sorted = selection_sort(cards, N)

print(' '.join(bubble_sorted))
print(is_stable(cards, bubble_sorted, N))
print(' '.join(selection_sorted))
print(is_stable(cards, selection_sorted, N))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 28 09:21:55 2018
ALDS-1-2c
@author: maezawa
"""

def selection(a, n):
    """
    Selection Sort of array a, n=len(a)
    
    配列aｆは参照渡しなのでa自身が変化する（ソートされる）
    """
    cnt = 0
    for i in range(n):
        flag = 0
        minj = i
        for j in range(i+1,n):
            if int(a[j][1]) < int(a[minj][1]):
                minj = j
                flag = 1
        if flag == 1:
            temp = a[minj]
            a[minj] = a[i]
            a[i] = temp
            cnt += 1
    return cnt

def bubble(a, n):
    cnt = 0
    for i in range(n):
        for j in reversed(range(i+1,n)):
            if int(a[j][1]) < int(a[j-1][1]):
                temp = a[j]
                a[j] = a[j-1]
                a[j-1] = temp
                cnt += 1
    return cnt

def print_array(a):
    ans = str(a[0])
    for i in range(1,n):
        ans += ' '+str(a[i])  
    print(ans)

def is_stable(a, b):
    for card1 in range(len(a)):
        for card2 in range(card1+1,len(a)):
            if a[card1][1] == a[card2][1]:
                if b.index(a[card1]) > b.index(a[card2]):
                    return 'Not stable'
    return 'Stable'

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

bub = a[:]
cnt = bubble(bub, n)   
print_array(bub)
print(is_stable(a, bub))

sel = a[:]
cnt = selection(sel, n)   
print_array(sel)
print(is_stable(a, sel))

Submission status: Accepted

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

Submission status: Accepted

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

def value(a, i):
    return int(a[i][-1])

def isstable(s, a, n):
    for i in range(n - 1):
        if value(a, i) == value(a, i + 1):
            v1 = s.index(a[i])
            v2 = s.index(a[i + 1])
            if v1 > v2:
                return "Not stable"
    return "Stable"

for i in range(n - 1):
    for j in range(i + 1, n)[::-1]:
        if value(a, j) < value(a, j - 1):
            a[j], a[j - 1] = a[j - 1], a[j]
print(" ".join(a))
print(isstable(s.split(), a, n))

a = s.split()

for i in range(n - 1):
    minj = i
    for j in range(i + 1, n):
        if value(a, j) < value(a, minj):
            minj = j
    a[i], a[minj] = a[minj], a[i]
print(" ".join(a))
print(isstable(s.split(), a, n))

Submission status: Accepted

Solution code:
n = int(input())
deck = input().split()

bd = list(deck)
for i in range(n):
    for j in reversed(range(i + 1, n)):
        if bd[j][1] < bd[j - 1][1]:
            bd[j], bd[j - 1] = bd[j - 1], bd[j]
print(' '.join(bd))
print('Stable')

sd = list(deck)
for i in range(n):
    mi = i
    for j in range(i, n):
        if sd[j][1] < sd[mi][1]:
            mi = j
    sd[i], sd[mi] = sd[mi], sd[i]
print(' '.join(sd))

if (bd == sd):
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
from typing import List, NamedTuple


class Card(NamedTuple):
    suit: str
    value: int


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


def selection_sort(cards: List[Card]):
    for i in range(len(cards)):
        minj = i
        for j in range(i, len(cards)):
            if cards[j].value < cards[minj].value:
                minj = j
        cards[i], cards[minj] = cards[minj], cards[i]


def gen_numbet_card_pair(cards: List[Card]):
    return {n: [c for c in cards if c.value == n] for n in range(1, 10)}


def is_stable(in_cards: List[Card], out_cards: List[Card]):
    in_lists = gen_numbet_card_pair(in_cards)
    out_lists = gen_numbet_card_pair(out_cards)
    for n in range(10):
        if in_lists.get(n, []) != out_lists.get(n, []):
            return False
    return True


def printing(arr, f):
    b_arr = arr.copy()
    f(b_arr)
    print(" ".join([c.suit+str(c.value) for c in b_arr]))
    print("Stable" if is_stable(arr, b_arr) else "Not stable")


n = int(input())
cards: List[Card] = [Card(suit=x[0], value=int(x[1])) for x in input().split(" ")]
printing(cards, bubble_sort)
printing(cards, selection_sort)

Submission status: Accepted

Solution code:
# #バブルソート
# def BubbleSort(C,N):
#     for i in range (0,N,1):
#         for j in range(N-1,i-1,-1):
#             if int(C[j][1:2]) < int(C[j-1][1:2]):
#                 tmp = C[j]
#                 C[j] = C[j-1]
#                 C[j-1] = tmp
#     print(' '.join(C))

#バブルソート
def BubbleSort(C,N):
    flag = 1
    while flag:
        flag = 0
        for j in range(N-1,0,-1):
            if int(C[j][1:2]) < int(C[j-1][1:2]):
                tmp = C[j]
                C[j] = C[j-1]
                C[j-1] = tmp
                flag = 1
    print(' '.join(C))
    
    
                
                
#選択ソート
def SelectionSort(C,N):
    for i in range(0,N,1):
        minj = i
        for j in range(i,N,1):
            if int(C[j][1:2]) < int(C[minj][1:2]):
                minj = j
        tmp = C[i]
        C[i] = C[minj]
        C[minj] = tmp
    print(' '.join(C))
        
#安定かどうかの判定
def isStable(inp, 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):
#                     print("inp(i,j):",inp[i],inp[j],"out(b,a):",out[b],out[a]+"\n")
                    if int(inp[i][1]) == int(inp[j][1]) and inp[i] == out[b] and inp[j] == out[a]:
                        print('Not stable')
                        return
    print('Stable')


#愚直に調べるパターン
N = int(input())
A = list(input().split())
Bubble_A = A.copy()
Selection_A = A.copy()

BubbleSort(Bubble_A,N)
isStable(A,Bubble_A,N)
SelectionSort(Selection_A,N)
isStable(A,Selection_A,N)

Submission status: Accepted

Solution code:
#バブルソート
def BubbleSort(C,N):
    for i in range (0,N,1):
        for j in range(N-1,i,-1):
            if int(C[j][1:2]) < int(C[j-1][1:2]):
                tmp = C[j]
                C[j] = C[j-1]
                C[j-1] = tmp
    print(' '.join(C))

    
                
#選択ソート
def SelectionSort(C,N):
    for i in range(0,N,1):
        minj = i
        for j in range(i,N,1):
            if int(C[j][1:2]) < int(C[minj][1:2]):
                minj = j
        tmp = C[i]
        C[i] = C[minj]
        C[minj] = tmp
    print(' '.join(C))



N = int(input())
A = list(input().split())
Bubble_A = A.copy()
Selection_A = A.copy()

BubbleSort(Bubble_A,N)
print("Stable")
SelectionSort(Selection_A,N)
flag = True
for Bubble,Selection in zip(Bubble_A,Selection_A):
    if Bubble != Selection:
        flag = False
if flag :
    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

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

if __name__ == '__main__':
    n = int(input())
    B = input().split()
    C_bubble = bubble_sort(copy.deepcopy(B))
    print(*C_bubble)
    print('Stable')
    C_selection = selection_sort(copy.deepcopy(B))
    print(*C_selection)
    if C_bubble == C_selection:
        print('Stable')
    else:
        print('Not stable')

Submission status: Accepted

Solution code:
def bubbleSort(c, n):
    flag = 1
    while(flag) :
        flag = 0
        for i in reversed(range(1,n)):
            if(c[i][1] < c[i-1][1]):
                c[i], c[i-1] = c[i-1], c[i]
                flag = 1
    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

def isStable(c1, c2, n):
    for i in range(n):
        if(c1[i] != c2[i]):
            return False
    return True

n = int(input())
c = input().split(' ')
trump = [list(i) for i in c]
bubble = ["".join(s) for s in bubbleSort(trump, n)]
trump = [list(i) for i in c]
selection = ["".join(s) for s in selectionSort(trump, n)]
str_bubble = " ".join(bubble)
str_selection = " ".join(selection)
print(str_bubble)
print('Stable')
print(str_selection)
if isStable(bubble, selection, n):
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

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


def BubbleSort(C, N):
    flag = 1
    while flag == 1:
        flag = 0
        for i in range(N - 1, 0, -1):
            if int(C[i][1]) < int(C[i - 1][1]):
                C[i], C[i - 1] = C[i - 1], C[i]
                flag = 1
    return C


def SelectionSort(C, N):
    flag = 0

    for i in range(N):

        if N == 1:
            break

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

        if flag == 1:
            C[i], C[minj] = C[minj], C[i]

        flag = 0

    return C


def print_line(A):
    for i in range(len(A)):
        if i == len(A) - 1:
            print('{0}{1}'.format(A[i][0], A[i][1]))
        else:
            print('{0}{1} '.format(A[i][0], A[i][1]), end='')


def check_stable(Bubble_A, Select_A):
    for i in range(len(Select_A)):
        if Bubble_A[i][0] != Select_A[i][0]:
            print('Not stable')
            break
        elif i == len(Select_A) - 1:
            print('Stable')


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

A = [A[i:i+2] for i in range(0, len(A), 3)]

Bubble_A = BubbleSort(A[:], N)
Select_A = SelectionSort(A[:], N)

print_line(Bubble_A)
print('Stable')
print_line(Select_A)
check_stable(Bubble_A, Select_A)

Submission status: Accepted

Solution code:
# -*- coding: UTF-8 -*-
#Stable Sort
import copy

def bubble_sort(bubble_N,bubble_A):
    #バブルソート
    flag = 1
    bi = 0
    # Sort処理（自分メモ：flagが0になったらループを抜ける）
    while flag:
        flag = 0
        for bj in reversed(range(bi + 1, bubble_N)):
            if bubble_A[bj][1:2] < bubble_A[bj - 1][1:2]:
                tmp = bubble_A[bj - 1]
                bubble_A[bj - 1] = bubble_A[bj]
                bubble_A[bj] = tmp
            flag = 1
        bi += 1

def selection_sort(selection_N,selection_A):
    #選択ソート
    for si in range(selection_N):
        cnt_flg = 0
        minj = si
        for sj in range(si, selection_N):
            if selection_A[sj][1:2] < selection_A[minj][1:2]:
                minj = sj
                cnt_flg = 1
        tmp = selection_A[si]
        selection_A[si] = selection_A[minj]
        selection_A[minj] = tmp

#標準入力から
N = int(input()) #要素数
B_A = list(input().split()) #バブルソート対象（スペース区切り→配列に展開）
S_A = copy.deepcopy(B_A) #選択ソート対象（コピー）

bubble_sort(N,B_A) #バブルソート実施
selection_sort(N,S_A) #選択ソート実施
ans_bubble = ' '.join(map(str,B_A)) #配列を文字列に戻す
ans_selection = ' '.join(map(str,S_A)) #配列を文字列に戻す

#バブルソート結果の出力（常にStable）
print(ans_bubble)
print("Stable")

#選択ソート結果の出力（バブルソート結果と比較してStable判断）
print(ans_selection)
if ans_bubble == ans_selection:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
def bubble_sort(n, key=0):
    c = 0
    r = [x if isinstance(x, list) else [x] for x in n[:]]
    l = len(r) - 1
    for i in range(0, l):
        for j in range(l, i, -1):
            if r[j][key] < r[j-1][key]:
                r[j], r[j-1] = r[j-1], r[j]
                c += 1
    r = [x[0] if len(x) == 1 else x for x in r]
    return {'list': r, 'count': c}

def selection_sort(n, key=0):
    c = 0
    r = [x if isinstance(x, list) else [x] for x in n[:]]
    l = len(r)
    for i in range(0, l):
        mini = i
        for j in range(i, l):
            if (r[j][key] < r[mini][key]):
                mini = j
        if mini != i:
            r[i], r[mini] = r[mini], r[i]
            c += 1
    r = [x[0] if len(x) == 1 else x for x in r]
    return {'list': r, 'count': c}

def card_format(cards):
    return ' '.join([x[0] + str(x[1]) for x in cards])

if __name__ == '__main__':
    n = int(input())
    c = list(map(list, input().split(' ')))
    c = [[x[0], int(x[1])] for x in c]
    bsc = card_format(bubble_sort(c, 1)['list'])
    ssc = card_format(selection_sort(c, 1)['list'])
    print(bsc)
    print('Stable')
    print(ssc)
    print('Stable' if bsc == ssc else 'Not stable')

Submission status: Accepted

Solution code:
def BubbleSort(C, N):

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

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

def isStable(C1, C2, N):
    if C1 != C2:
        return "Not stable"
    return "Stable"

Num = int(input())
Cards = [x for x in input().split()]
card1 = BubbleSort(list(Cards), Num)
card2 = SelectionSort(list(Cards), Num)

print(" ".join(card1))
print(isStable(card1, card1, Num))
print(" ".join(card2))
print(isStable(card1, card2, Num))

Submission status: Accepted

Solution code:
def print_list(l):
    for i, n in enumerate(l):
        if i == N - 1:
            print(l[i])
        else:
            print(l[i], end=' ')

N = int(input())
A = input().split()
B = list(A)
for i in range(N):
    for j in range(N-1, i, -1):
        if int(A[j][1]) < int(A[j-1][1]):
            w = A[j]; A[j] = A[j-1]; A[j-1] = w
print_list(A)
print('Stable')

for i in range(N):
    min_j = i
    for j in range(i, N):
        if int(B[j][1]) < int(B[min_j][1]):
            min_j = j
    w = B[i]; B[i] = B[min_j]; B[min_j] = w
print_list(B)
if A == B:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
from copy import deepcopy

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


def bubble_sort(ary):
    for i in range(N):

        for j in range(N - 1, i, -1):
            if int(ary[j][1:]) < int(ary[j - 1][1:]):
                ary[j], ary[j - 1] = ary[j - 1], ary[j]


def selection_sort(ary):

    for i in range(0, N):
        minj = i

        for j in range(i, N):
            if int(ary[j][1:]) < int(ary[minj][1:]):
                minj = j

        ary[i], ary[minj] = ary[minj], ary[i]


def naive_check(oary, nary):
    for i in range(1, N - 1):
        for j in range(i + 1, N):
            for a in range(1, N - 1):
                for b in range(a + 1, N):

                    if int(oary[i][1:]) == int(nary[j][1:]):
                        if oary[i] == nary[b]:
                            if oary[j] == nary[a]:
                                return False

    return True


def is_stable(oary, nary):

    if naive_check(oary, nary):
        print('Stable')
    else:
        print('Not stable')


bary = deepcopy(oary)
bubble_sort(bary)
print(' '.join(bary))
print('Stable')
# is_stable(oary, bary)

sary = deepcopy(oary)
selection_sort(sary)
print(' '.join(sary))
if bary == sary:
    print('Stable')
else:
    print('Not stable')
# is_stable(oary, sary)

Submission status: Accepted

Solution code:
# ALDS1_2_C.
# バブルソートと選択ソートの安定性。
from math import sqrt, floor

class card:
    def __init__(self, _str):
        # S3とかH8をもとに初期化。
        self.kind = _str  # 出力用。
        self.suit = _str[0]
        self.value = int(_str[1])

def cardinput():
    # カードの配列からオブジェクトの配列を生成。
    a = input().split()
    cards = []
    for i in range(len(a)):
        cards.append(card(a[i]))
    return cards

def show(a):
    # 配列の中身を出力する。
    _str = ""
    for i in range(len(a) - 1):
        _str += a[i].kind + " "
    _str += a[len(a) - 1].kind
    print(_str)

def bubble_sort(a):
    # aをバブルソートする(交換回数をreturnする)。
    count = 0
    for i in range(1, len(a)):
        k = i - 1
        while k >= 0:
            # a[i]を前の数と交換していき、前の方が小さかったら止める。
            if a[k].value > a[k + 1].value:
                a[k], a[k + 1] = a[k + 1], a[k]
                count += 1
            else: break
            k -= 1
    return count

def selection_sort(a):
    # 選択ソート。その番号以降の最小値を順繰りにもってくる。
    # 交換回数は少ないが比較回数の関係で結局O(n^2)かかる。
    count = 0
    for i in range(len(a)):
        # a[i]からa[len(a) - 1]のうちa[j]が最小っていうjを取る。
        # このときiとjが違うならカウントする。
        # というかa[i]とa[j]が違う時カウントでしたね。
        minj = i
        for j in range(i, len(a)):
            if a[j].value < a[minj].value: minj = j
        if a[i].value > a[minj].value: count += 1; a[i], a[minj] = a[minj], a[i]
    return count

def main():
    N = int(input())
    cards = cardinput()
    # バブルソートは安定。同じvalueなら団子のようにくっつくから。
    # 選択ソートは交換が飛び越えるので不安定。よって、
    # バブルの結果と比較すれば安定か不安定かが分かる。
    _copy = [cards[i] for i in range(N)]

    bubble_sort(cards)
    selection_sort(_copy)

    show(cards)
    print("Stable")
    show(_copy)

    is_stable = True
    for i in range(N):
        for j in range(i + 1, N):
            if _copy[i].value != _copy[j].value: continue
            if _copy[i].suit != cards[i].suit: is_stable = False; break
    if is_stable: print("Stable")
    else: print("Not stable")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#coding:utf-8
from copy import deepcopy

n = int(input())
A = list(input().split())
B = deepcopy(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]


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
        A[i], A[minj] = A[minj], A[i]
        
                
BubbleSort(A,n)
SelectionSort(B,n)
A = " ".join([data for data in A])
B = " ".join([data for data in B])

print(A)
print("Stable")

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