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 sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque
import copy

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def bubble_sort(A, N):
    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]


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


def is_stable(bubble, selection):
    for b, s in zip(bubble, selection):
        if b != s:
            return False
    else:
        return True


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = sl()
    bubble_list = copy.copy(A)
    selection_list = copy.copy(A)

    bubble_sort(bubble_list, N)
    selection_sort(selection_list, N)
    print(*bubble_list)
    print('Stable')
    print(*selection_list)
    print('Stable' if is_stable(bubble_list, selection_list) else 'Not stable')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def bubbleSort(cards):
    for i, _ in enumerate(cards):
        for j in range(len(cards) -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 selectionSort(cards):
    for i in range(len(cards)):
        min_j = i
        for j in range(i, len(cards)):
            if int(cards[j][1]) < int(cards[min_j][1]):
                min_j = j
        cards[i], cards[min_j] = cards[min_j], cards[i]
    return cards
    
N = int(input())
A = input().split()

temp = A.copy()
bs = bubbleSort(temp)

temp = A.copy()
ss = selectionSort(temp)

print(' '.join(bs))
print('Stable')
print(' '.join(ss))
if [a[:1] for a in bs] == [a[:1] for a in ss]:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
def insertionSort(A, N):
    for i in range(1, N):
        v = A[i]
        j = i-1
        while A[j] > v and j >= 0:
            A[j+1], A[j] = A[j], A[j+1]
            j -= 1


def bubbleSort(A, N):
    flag = 1
    while flag:
        flag = 0
        for j in range(N-1, 0, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
                flag = 1


def bubbleSort_card(C, N):
    flag = 1
    while flag:
        flag = 0
        for j in range(N-1, 0, -1):
            if C[j][1] < C[j-1][1]:
                C[j], C[j-1] = C[j-1], C[j]
                flag = 1

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

def selectionSort(A, N):
    for i in range(N):
        minidx = i
        for j in range(i, N):
            if A[j] < A[minidx]:
                minidx = j
        A[i], A[minidx] = A[minidx], A[i]


N = int(input())
A = list(input().split())
C = A.copy()
bubbleSort_card(C,N)
selectionSort_card(A,N)
print(" ".join(C))
print('Stable')
print(" ".join(A))
for i in range(N):
    if A[i] != C[i]:
        print('Not stable')
        break
else:
    print('Stable')

Submission status: Accepted

Solution code:
import copy

n = int(input())

l = list(input().split())
C1 = []

for v in l:
    s = v[0]
    m = int(v[1])
    C1.append((s, m))

C2 = copy.deepcopy(C1)

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

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

result1 = [t[0]+str(t[1]) for  t in C1]
result2 = [t[0]+str(t[1]) for  t in C2]

print(" ".join(result1))
print("Stable")
print(" ".join(result2))
if result1 == result2:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
import copy


def BubbleSort(C, n):
    flag = 1
    while flag:
        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):
    for i in range(n-1):
        minj = i
        for j in range(i, n):
            if int(C[j][1]) < int(C[minj][1]):
                minj = j
        if minj != i:
            C[i], C[minj] = C[minj], C[i]
    return C


n = int(input())
C = list(input().split())
C2 = C.copy()

print(*BubbleSort(C, n), sep=' ')
print("Stable")
print(*SelectionSort(C2, n), sep=' ')
if C ==C2:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
from copy import copy

n = int(input())
cards = [(s[0],int(s[1])) for s in input().split()]

cards_1 = copy(cards)
cards_2 = copy(cards)

need_to_sort = True
while need_to_sort:
    need_to_sort = False
    for index in range(len(cards_1) - 1, 0, -1):
        if cards_1[index][1] < cards_1[index-1][1]:
            cards_1[index], cards_1[index-1] = cards_1[index-1], cards_1[index]
            need_to_sort = True

print(" ".join([s[0]+ str(s[1]) for s in cards_1]))
print("Stable")

for idx1 in range(len(cards_2)):
    mins = idx1
    for idx2 in range(idx1, len(cards_2)):
        if cards_2[idx2][1] < cards_2[mins][1]:
            mins = idx2
    
    if mins != idx1:
        cards_2[idx1], cards_2[mins] = cards_2[mins], cards_2[idx1]

print(" ".join([s[0]+ str(s[1]) for s in cards_2]))

is_stable = True
for index in range(n):
    if cards_1[index] != cards_2[index]:
        is_stable = False
        break

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	stable_sort
# CreatedDate:  2020-07-08 14:29:32 +0900
# LastModified: 2020-07-08 14:56:46 +0900
#


import os
import sys
from copy import deepcopy
# import numpy as np
# import pandas as pd


def BubbleSort(a, n):
    for i in range(n-1):
        for j in range(n-1, i, -1):
            if a[j-1][1] > a[j][1]:
                tmp = a[j-1]
                a[j-1] = a[j]
                a[j] = tmp


def SelectionSort(b, n):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if b[j][1] < b[minj][1]:
                minj = j
        tmp = b[minj]
        b[minj] = b[i]
        b[i] = tmp



def main():
    n = int(input())
    s = list(map(str, input().split()))
    a = deepcopy(s)
    b = deepcopy(s)
    BubbleSort(a, n)
    print(a[0], end='')
    for i in range(1, n):
        print(" {}".format(a[i]), end='')
    print()
    print("Stable")

    SelectionSort(b, n)
    print(b[0], end='')
    for i in range(1, n):
        print(" {}".format(b[i]), end='')
    print()
    for a_, b_ in zip(a, b):
        if a_!=b_:
            print("Not stable")
            return
    print("Stable")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, *aa = open(0).read().split()

def bubble(aa):
    aa = list(map(list, aa))
    n = len(aa)
    for i in range(n):
        for j in range(n-1, i, -1):
            if aa[j-1][1] > aa[j][1]:
                aa[j-1], aa[j] = aa[j], aa[j-1]
    aa = list(map(lambda x: ''.join(x), aa))
    return aa

def selection(aa):
    aa = list(map(list, aa))
    n = len(aa)
    for i in range(n):
        mini = i
        for j in range(i, n):
            if aa[j][1] < aa[mini][1]:
                mini = j
        aa[mini], aa[i] = aa[i], aa[mini]
    aa = list(map(lambda x: ''.join(x), aa))
    return aa

bres = bubble(aa)
sres = selection(aa)

print(*bres)
print('Stable')
print(*sres)
if bres == sres:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
import copy
import sys
input = sys.stdin.readline


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


def selection_sort(A):
    for i in range(len(A)):
        _min = i
        for j in range(i, len(A)):
            if int(A[j][1:]) < int(A[_min][1:]):
                _min = j
        A[i], A[_min] = A[_min], A[i]
    return A


def main():
    _ = input()
    A = input().strip().split()
    b_A = copy.deepcopy(A)
    bubble_sort(b_A)
    print(" ".join(b_A))
    print("Stable")

    selection_sort(A)
    print(" ".join(A))
    for b, s in zip(b_A, A):
        if b == s:
            continue
        else:
            print("Not stable")
            return
    print("Stable")
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def bubble_sort(A):
    cnt = 0
    for i in range(0, len(A) - 1):
        for j in range(len(A) - 1, i, -1):
            if A[j][1] < A[j - 1][1]:
                A[j - 1], A[j] = A[j], A[j - 1]
                cnt += 1


def selection_sort(A):
    for i in range(0, len(A)):
        min = i
        for j in range(i + 1, len(A)):
            if A[min][1] > A[j][1]:
                min = j
        A[i], A[min] = A[min], A[i]


def isStable(before, after):
    for i in range(0, len((before))):
        for j in range(i + 1, len(before)):
            for a in range(0, len(after)):
                for b in range(a + 1, len(after)):
                    if before[i][1] == before[j][1]:
                        if before[i] == after[b] and before[j] == after[a]:
                            return False
    return True


if __name__ == '__main__':
    n = int(input())
    l = input().split()
    m = l.copy()
    n = l.copy()
    bubble_sort(m)
    selection_sort(n)
    print(' '.join(m))
    print('Stable' if isStable(l, m) else 'Not stable')
    print(' '.join(n))
    print('Stable' if isStable(l, n) else 'Not stable')

Submission status: Accepted

Solution code:
from copy import deepcopy as copy
n=int(input())
A=input().split()
C=copy(A)
for i in range(n):
  for j in range(n-1,i,-1):
    if C[j][1] < C[j-1][1]:
      k=C[j]
      C[j]=C[j-1]
      C[j-1]=k
print(*C)
for i in range(n-1):
  if C[i][1]==C[i+1][1] and A.index(C[i])>A.index(C[i+1]):
    print('Not stable')
    break
else:print('Stable')
C=copy(A)
for i in range(n):
  minj = i
  for j in range(i,n):
    if C[j][1] < C[minj][1]:
      minj = j
  k=C[i]
  C[i]=C[minj]
  C[minj]=k
print(*C)
for i in range(n-1):
  if C[i][1]==C[i+1][1] and A.index(C[i])>A.index(C[i+1]):
    print('Not stable')
    break
else:print('Stable')

Submission status: Accepted

Solution code:
from collections import namedtuple
C = namedtuple("C", "m v")


def bubble_sort(A0):
    A = A0.copy()
    for i in range(n - 1):
        for j in range(n - 1, i, -1):
            if A[j].v < A[j - 1].v:
                A[j], A[j - 1] = A[j - 1], A[j]
    return A, True


def selection_sort(A0):
    A = A0.copy()
    for i in range(n - 1):
        k = i
        for j in range(i + 1, n):
            if A[k].v > A[j].v:
                k = j
        if k != i:
            A[k], A[i] = A[i], A[k]
    return A


lst = ["Not stable", "Stable"]
n = int(input())
A = [C(x[0], x[1]) for x in input().split()]

B, j = bubble_sort(A)
print(*[(B[i].m + B[i].v) for i in range(n)])
print(lst[j])

S = selection_sort(A)
print(*[(S[i].m + S[i].v) for i in range(n)])
print(lst[B == S])

Submission status: Accepted

Solution code:
n=int(input())
num_list1=list(map(str,input().split()))
num_list2=[]
input_list=[]

for k in num_list1:
    num_list2.append(k)
    input_list.append(k)


def bubble(num_list):
    i=0
    flag=True
    while flag:
        flag=False
        for j in range(len(num_list)-1,i,-1):
            if int(num_list[j-1][1])>int(num_list[j][1]):
                tmp=num_list[j-1]
                num_list[j-1]=num_list[j]
                num_list[j]=tmp
                flag=True
    return num_list 

def select(num_list):
    for i in range(0,len(num_list)):
        min=i
        for j in range(min+1,len(num_list)):
            if int(num_list[min][1])>int(num_list[j][1]):
                min=j
        tmp=num_list[i]
        num_list[i]=num_list[min]
        num_list[min]=tmp
    return num_list



def stable(input_list,output_list):
    for i in range(0,len(input_list)):
        for j in range(i+1,len(output_list)):
            for k in range(0,len(output_list)):
                for l in range(k+1,len(output_list)):
                    if input_list[i][1]==input_list[j][1] and input_list[i]==output_list[l] and input_list[j]==output_list[k]:
                        return "Not stable"
    return "Stable"

bubble=bubble(num_list1)
select=select(num_list2)


print(" ".join(bubble))
print(stable(input_list,bubble))
print(" ".join(select))
print(stable(input_list,select))

Submission status: Accepted

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

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


def main():
    N = int(input())
    cards1 = input().split()
    cards2 = cards1.copy()

    bubble_sorted = bubble_sort(cards1, N)
    print(*bubble_sorted)
    print("Stable")
    
    select_sorted = selection_sort(cards2, N)
    print(*select_sorted)
    if bubble_sorted == select_sorted:
        print("Stable")
    else:
        print("Not stable")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class Trump(str):
    def __init__(self, card):
        super().__init__()
        self.num = int(card[1])

def trump_bubble_sort(A, N):
    flg = True
    while flg:
        flg = False
        for i in range(1, N):
            if A[i - 1].num > A[i].num:
                A[i], A[i - 1] = A[i - 1], A[i]
                flg = True
    return A


def trump_selection_sort(A, N):
    for i in range(0, N-1):
        min_idx = i
        for j in range(i+1, N):
            if A[min_idx].num > A[j].num:
                min_idx = j
        A[i], A[min_idx] = A[min_idx], A[i]
        
    return A

N = int(input().rstrip())
A = [Trump(a) for a in input().rstrip().split()]
A_2 = A.copy()

bubble_result = trump_bubble_sort(A, N)
selection_result = trump_selection_sort(A_2, N)

stable = True
for i in range(0, N):
    if bubble_result[i] != selection_result[i]:
        stable = False
        break
print(" ".join(bubble_result))
print("Stable")
print(" ".join(selection_result))
print("Stable" if stable else "Not stable")

Submission status: Accepted

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

    print(*C)
    stableCheck(C, N)

def SelectionSort(C, N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if C[j][1:2] <  C[minj][1:2]:
                minj = j
        C[i], C[minj] = C[minj], C[i]
    print(*C)
    stableCheck(C, N)

def stableCheck(C, N):
    global lst
    flag = 1
    for i in range(N):
        for j in range(i+1, N):
            if lst[i][1:2] == lst[j][1:2]:
                fir = lst[i]
                sec = lst[j]
                for k in range(N):
                    if C[k] == fir:
                        recf = k

                    if C[k] == sec:
                        recs = k
                
                if recf > recs:
                    print("Not stable")
                    flag = 0
                    break
        
        if flag ==0:
            break

    if flag :
        print("Stable")

N = int(input())
lst = list(map(str, input().split()))
lst1 = copy.deepcopy(lst)
lst2 = copy.deepcopy(lst)

BubbleSort(lst1, N)
SelectionSort(lst2, N)

Submission status: Accepted

Solution code:
import copy
n = int(input())
c = input().split()
c = [[c[i][0], int(c[i][1])] for i in range(n)]
ba = copy.deepcopy(c)
sa = copy.deepcopy(c)

def bubble_sort(a, n):
    flag = 1
    i = 0
    while flag:
        flag = 0
        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]
                flag = 1
        i += 1
    return a

def selection_sort(a, n):
    for i in range(n-1):
        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]
    return a

ba = bubble_sort(ba, n)
sa = selection_sort(sa, n)

def is_stable(x, y):
    for i in range(n):
        if x[i][0] != y[i][0]:
            return False
    return True

fba = [i[0] + str(i[1]) for i in ba]
print(' '.join(fba))
print('Stable')
fsa = [i[0] + str(i[1]) for i in sa]
print(' '.join(fsa))
print('Stable' if is_stable(ba, sa) else 'Not stable')

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(lambda x: (int(x[1]), x), input().split()))

    # Bubble Sort
    B = A.copy()
    at_least_once = True
    while at_least_once:
        at_least_once = False
        for i in range(N - 1):
            if B[i][0] > B[i + 1][0]:
                B[i], B[i + 1] = B[i + 1], B[i]
                at_least_once = True
    print(" ".join(map(lambda x: x[1], B)))
    print("Stable")

    # Selection Sort
    B = A.copy()
    stability = "Stable"
    for i in range(N - 1):
        min_j = i
        for j in range(i, N):
            if B[j][0] < B[min_j][0]:
                min_j = j
        if min_j != i:
            if B[i][0] in list(map(lambda x: x[0], B[i + 1: min_j])):
                stability = "Not stable"
            B[i], B[min_j] = B[min_j], B[i]
    print(" ".join(map(lambda x: x[1], B)))
    print(stability)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin


def bubble_sort(A, N):
    for i in range(N-1):
        for j in range(N-1,0,-1):
            if int(A[j-1][1]) > int(A[j][1]):
                A[j], A[j-1] = A[j-1], A[j]
    return 'Stable'
                
def selection_sort(A, N, B):
    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 A == B:
        return 'Stable'
    else:
        return 'Not stable'

    
def main():
    read = stdin.readline
    N = int(read())
    data_for_bubble = list(map(str, read().split('\n')[0].split(' ')))
    data_for_selection = data_for_bubble.copy()
    bubble_result = bubble_sort(data_for_bubble, N)
    for i in range(N-1):
        print(data_for_bubble[i], end = ' ')
    print(data_for_bubble[N-1])
    print(bubble_result)
    selection_result = selection_sort(data_for_selection, N, data_for_bubble)
    for i in range(N-1):
        print(data_for_selection[i], end = ' ')
    print(data_for_selection[N-1])
    print(selection_result)
    
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
from copy import deepcopy
def selectionSort(A,N):
    lst=deepcopy(A)
    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)

def bubbleSort(A,N):
    lst=deepcopy(A)
    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)

a=int(input())
b=input().split(" ")
Selected=selectionSort(b,a)
Bubbled=bubbleSort(b,a)
IsStable="Stable"
for i in range(a):
    if Selected[i] != Bubbled[i]:
        IsStable="Not stable"

print(" ".join(Bubbled),"Stable"," ".join(Selected),IsStable,sep="\n")

Submission status: Accepted

Solution code:
#import copy

n=int(input())
A=input().split()
C=A[:] #参照渡しのため

def bubble_sort(n,A):
  flag=True
  i=0
  while flag:
    flag=False
    for j in reversed(range(i+1,n)):
      if int(A[j][1])<int(A[j-1][1]):
        tmp=A[j]
        A[j]=A[j-1]
        A[j-1]=tmp
        flag=True
    i+=1
  return A

def selection_sort(n,A):
  for i in range(n):
    minj=i
    for j in range(i+1,n):
      #print(A[minj],A[j])
      if int(A[j][1])<int(A[minj][1]):
        minj=j
    tmp=A[i]
    A[i]=A[minj]
    A[minj]=tmp
    # 途中で入れ替わるからnot stable
    #print("---")
  return A

x=bubble_sort(n,A)
y=selection_sort(n,C)
print(*x) # stable
print('Stable')
print(*y) # not stable
print('Stable' if x==y else 'Not stable')

Submission status: Accepted

Solution code:
def bubleSort(table):
    table = table.copy()
    for nAchieve in range(len(table)):
        for i in range(len(table) - 1, nAchieve, -1):
            if table[i][1] < table[i - 1][1]:
                table[i], table[i - 1] = table[i - 1], table[i]
    return table


def selectionSort(table):
    table = table.copy()
    for nAchieve in range(len(table)):
        minimum_index = nAchieve
        for i in range(nAchieve + 1, len(table)):
            if table[minimum_index][1] > table[i][1]:
                minimum_index = i
        if minimum_index != nAchieve:
            table[nAchieve], table[minimum_index] = table[minimum_index], table[nAchieve]
    return table


def checkStable(stable, comparison):
    if stable == comparison:
        return 'Stable'
    else:
        return 'Not stable'


element = int(input())
table = list(map(str, input().split()))

y = selectionSort(table)
x = bubleSort(table)
print(' '.join(map(str, x)))
print('Stable')
print(' '.join(map(str, y)))
print(checkStable(x, y))

Submission status: Accepted

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


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

    return A


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

    return A


def check_stable(A, cards):
    for num in range(1, 10):
        As = []
        Cs = []
        for a in A:
            if a.value == num:
                As.append(a.card)
        for c in cards:
            if c.value == num:
                Cs.append(c.card)

        if As != Cs:
            print("Not stable")
            return
    else:
        print("Stable")
        return


def main():
    N = int(input())
    cards = [Card(i) for i in input().split()]
    bubble_cards = bubbleSort(cards.copy(), N)
    selection_cards = selectionSort(cards.copy(), N)

    print(*[bc.card for bc in bubble_cards])
    check_stable(bubble_cards, cards)
    print(*[sc.card for sc in selection_cards])
    check_stable(selection_cards, cards)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin


def bubble_sort(A, N):  # N個の要素を含む0-オリジンの配列 A
  #A = [int(a[1]) for a in A]
  flag = True  # 逆の隣接要素が存在する
  exchange_cnt = 0
  while flag:
    flag = False
    for j in range(N - 1, 0, -1):
      if int(A[j][1]) < int(A[j - 1][1]):
        A[j], A[j - 1] = A[j - 1], A[j]
        flag = True
        exchange_cnt += 1
  return A#exchange_cnt

def selection_sort(A, N):  #N個の要素を含む0-オリジンの配列 A
  # A = [int(a[1]) for a in A]
  exchange_cnt = 0
  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
    else:
      if i != minj:
        A[i], A[minj] = A[minj], A[i]
        exchange_cnt += 1
  return A#exchange_cnt

n = int(stdin.readline().rstrip())
A = list(stdin.readline().split())

ans = bubble_sort(list(A), n)
print(' '.join(map(str, ans)))
print('Stable')

ans2 = selection_sort(A, n)
print(' '.join(map(str,ans2)))
print('Stable' if ans2==ans else 'Not stable')

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(str, input().split()))
l_1 = []
l_2 = []
ans = []

for cha in A:
    l_1.append([cha[:1], int(cha[1:])])
    l_2.append([cha[:1], int(cha[1:])])

def BubbleSort(C, N):
  for i in range(N):
    nums = []
    for j in range(i+1, N):
      nums.append(j)
    nums.sort(reverse=True)
    for num in nums:
      if C[num][1] < C[num-1][1]:
        C[num], C[num-1] = C[num-1], C[num]
    a = []
    for cha in C:
      a.append(''.join(map(str, cha)))
  ans.append(' '.join(map(str, a)))
  print(ans[0])
  print('Stable')
  
BubbleSort(l_1, N)

def SelectionSort(D, N):
  for i in range(N):
    index = i
    for j in range(i, N):
      if D[j][1] < D[index][1]:
        index = j
    D[i], D[index] = D[index], D[i]
  b = []
  for cha in D:
    b.append(''.join(map(str, cha)))
  ans.append(' '.join(map(str, b)))
  if ans[0] == ans[1]:
    print(ans[1])
    print('Stable')
  else:
    print(ans[1])
    print('Not stable')

SelectionSort(l_2, N)

Submission status: Accepted

Solution code:
from sys import stdin
N = int(input())
A = [{'value': int(x[1]), 'type': x[0]} for x in stdin.readline().split(' ')]
S = 'Stable'
NS = 'Not stable'


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


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


A_bubble = bubble_sort(A.copy())
A_selection = selection_sort(A.copy())


def is_stable(origin, arr):
    for i in range(N):
        for j in range(i+1, N):
            for a in range(0, N):
                for b in range(a+1, N):
                    if (arr[i]['value'] == arr[j]['value']) & \
                            (arr[i] == origin[b]) & (arr[j] == origin[a]):
                        return False

    return True


print(' '.join(map(lambda x: x['type'] + str(x['value']), A_bubble)))
print(S)

print(' '.join(map(lambda x: x['type'] + str(x['value']), A_selection)))
if (is_stable(A_bubble, A_selection)):
    print(S)
else:
    print(NS)

Submission status: Accepted

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


def bubble(a):
    num = [int(i[1]) for i in a]
    char = [i[0] for i in a]
    for i in range(n):
        for j in range(n-1, i, -1):
            if num[j] < num[j-1]:
                num[j], num[j-1] = num[j-1], num[j]
                char[j], char[j-1] = char[j-1], char[j]
    else:
        a_new = [char[i] + str(num[i]) for i in range(n)]
        return a_new


def selection(a):
    num = [int(i[1]) for i in a]
    char = [i[0] for i in a]
    minj = 0
    stay = True
    same_exi = False
    for i in range(n):
        minj = i
        for j in range(i, n):
            if num[minj] > num[j]:
                minj = j
                if same_exi:
                    stay = False
            if num[i] == num[j]:
                same_exi = True
        else:
            num[i], num[minj] = num[minj], num[i]
            char[i], char[minj] = char[minj], char[i]
    else:
        a_new = [char[i] + str(num[i]) for i in range(n)]
        return a_new, stay


def print_space(li):
    for i in range(len(li)-1):
        print(li[i], end=' ')
    else:
        print(li[-1])



cards_bu = bubble(cards)
cards_sl = selection(cards)

sl_list = cards_sl[0]
sl_stay = cards_sl[1]

print_space(cards_bu)
print('Stable')

print_space(sl_list)
if sl_list == cards_bu:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
def bubbleSort(A, N):
    cnt = 0
    flg = True
    while flg:
        flg = False
        for i in range(N - 1):
            if A[i][1] > A[i + 1][1]:
                tmp = A[i]
                A[i] = A[i + 1]
                A[i + 1] = tmp
                flg = True
                cnt += 1
    return A, cnt


def selectionSort(A, N):
    cnt = 0
    for i in range(N):
        minJ = i
        for j in range(i, N):
            if A[minJ][1] > A[j][1]:
                minJ = j
        if A[i][1] != A[minJ][1]:
            tmp = A[i]
            A[i] = A[minJ]
            A[minJ] = tmp
            cnt += 1
    return A, cnt


def resolve():
    import copy
    N = int(input())
    A = [i for i in input().split()]
    B = copy.deepcopy(A)
    ansA, cnt = bubbleSort(A, N)
    print(*ansA)
    print("Stable")
    ansB, cnt = selectionSort(B, N)
    print(*ansB)
    if ansA == ansB:
        print("Stable")
    else:
        print("Not stable")


resolve()