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: Wrong Answer

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

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

print(A[1][1:])

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 B == C:
        print("Stable")
    else:
        print("Not Stable")

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

Submission status: Wrong Answer

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

# 文字列の取得と加工
LENGTH =int(input())
A = input().split()
B = A.copy()
C = 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 B == C:
        print("Stable")
    else:
        print("Not Stable")

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

Submission status: Wrong Answer

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

# 文字列の取得と加工
LENGTH =int(input())
A = input().split()
B = A.copy()
C = 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 B == C:
        print("Stable")
    else:
        print("Not stable")

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

Submission status: Wrong Answer

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)


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

bubble = BubbleSort(l2)
if bubble == l2_sort:
    print('a')
else:
    print('b')

select = SelectSort(l2)
if select == l2_sort:
    print('a')
else:
    print('b')

Submission status: Wrong Answer

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(b)
print(stable(c, b))
print(s)
print(stable(c, s))

Submission status: Wrong Answer

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(c, f):
    for i in range(len(c) - 1):
        for j in range(i + 1, len(c)):
            # print(i, j)
            if f(c[i]) > f(c[j]):
                swap(c, i, j)
    return c

def selection_sort(c, f):
    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)
    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: Wrong Answer

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(i + 1, len(c)):
            # print(i, j)
            if f(c[i]) > f(c[j]):
                swap(c, i, j)
    return c

def insertion_sort(cs, f):
    c = cs[:]
    for i in range(1, len(c)):
        w = c[i]
        j = i - 1
        while j >= 0 and f(c[j]) > f(w):
            c[j + 1] = c[j]
            j -= 1
        c[j + 1] = w
    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: Wrong Answer

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, -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: Wrong Answer

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: Wrong Answer

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: Wrong Answer

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

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


def isStable(inn, 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 inn[i] == inn[j] and inn[i] == out[b] and inn[j] == out[a]:
            return print("Not stable")
  return print("Stable")

n = int(input())
c = list(map(str, input().split()))
before_c = list(c)
bubble_sort(c,n)
print(" ".join(map(str, c)))
isStable(before_c, bubble_sort(c,n), n)
selection_sort(c,n)
print(" ".join(map(str, c)))
isStable(before_c, selection_sort(c,n), n)

Submission status: Wrong Answer

Solution code:
def bubble_sort(a, n):
  for i in range(0,n):
    for j in range(n-1,i-1,-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

def isStable(buble, select, n):
  for i in range(0,n):
    if buble[i] != select[i]:
      return False
  return True

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 isStable(buble,select,n):
    print("Stable")
  else:
    print("Not stable")

Submission status: Wrong Answer

Solution code:
def bubble_sort(a, n):
  for i in range(0,n):
    for j in range(n-1,i-1,-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: Wrong Answer

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: Wrong Answer

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-1)):
            if lst[j]<lst[j-1]:
                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,size):
            if lst[mn]<lst[j]:
                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

    def __lt__(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: Wrong Answer

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]<lst[j-1]:
                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,size):
            if lst[mn]<lst[j]:
                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

    def __lt__(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: Wrong Answer

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


n = int(input())
cards = input().split()
bubble_cards = [i for i in bubble_sort(cards)]
selection_cards = [i for i in selection_sort(cards,n)]

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

Submission status: Wrong Answer

Solution code:
def bubble_sort(cards):
    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(cards):
    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 = [i for i in bubble_sort(cards)]
selection_cards = [i for i in 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: Wrong Answer

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]<numa[j-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]<numb[minj]:
			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: Wrong Answer

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, 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: Wrong Answer

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][1] == output[b][1] and Input[j][1] == output[a][1]:
						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: Wrong Answer

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][1] == output[b][1] and Input[j][1] == output[a][1]:
						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: Wrong Answer

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

# バブルソート
def bubble(a, n):
    for i in range(n):
        for j in range(n-1,i,-1):
            if int(a[j][1]) < int(a[j-1][1]):
                tmp = a[j]
                a[j] = a[j-1]
                a[j-1] = tmp
    return a

# 選択ソート
def selection(a, n):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if int(a[j][1]) < int(a[minj][1]):
                minj = j
        tmp = a[i]
        a[i] = a[minj]
        a[minj] = tmp
    return a

# 安定性判定
def stable(in_a, out_a, 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 in_a[i] == in_a[j] and in_a[i] == out_a[b] and in_a[j] == out_a[a]:
                        return False
    return True

print(' '.join(bubble(a,n)))
print(stable(a, bubble(a,n), n))
print(' '.join(selection(a,n)))
print(stable(a, selection(a,n), n))

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
def show(array):
    for i in range(len(array)):
        if (i+1) >= len(array):
            print(array[i])
        else:
            print(array[i], end=' ')


def bubble_sort(c, n):
    for i in range(0, 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(0, n):
        
        minj = i
        for j in range(i+1, n):
            if c[j][1:] < c[minj][1:]:
                minj = j
        # if i != minj:
        c[i], c[minj] = c[minj], c[i]
    return c


def main():
    N = int(input())
    cards = list(input().split(' '))
    cards2 = cards.copy()

    # value_sorted = sorted(cards, key=lambda x: x[1:])
    bubble_result = bubble_sort(cards, N)
    print(cards2)
    selection_result = selection_sort(cards2, N)

    show(bubble_result)
    print('Stable')
    show(selection_result)
    if bubble_result == selection_result:
        print('Stable')
    else:
        print('Not stable')


main()

Submission status: Wrong Answer

Solution code:
import copy

def bubble(N, A):
    for i in range(N - 1):
        for j in reversed(range(1, N)):
            if A[j - 1][1] > A[j][1]:
                tmp = A[j]
                A[j] = A[j - 1]
                A[j - 1] = tmp

def select(N, A):
    for i in range(N):
        min = i
        for j in range(i, N):
            if A[min][1] > A[j][1]:
                min = j
        tmp = A[i]
        A[i] = A[min]
        A[min] = tmp

N = int(input())

#カード入力
S = [i for i in input().split()]
B = copy.deepcopy(S)

bubble(N, B)
select(N, S)

print(B)
print(S)

Submission status: Wrong Answer

Solution code:
import copy

def bubble(N, A):
    for i in range(N - 1):
        for j in reversed(range(1, N)):
            if A[j - 1][1] > A[j][1]:
                tmp = A[j]
                A[j] = A[j - 1]
                A[j - 1] = tmp

def select(N, A):
    for i in range(N):
        min = i
        for j in range(i, N):
            if A[min][1] > A[j][1]:
                min = j
        tmp = A[i]
        A[i] = A[min]
        A[min] = tmp

def st(B, S):
    for i in range(N):
        if B[i] == S[i]:
            return False
    return True

N = int(input())
#カード入力
S = [i for i in input().split()]
B = copy.deepcopy(S)

bubble(N, B)
select(N, S)

print(" ".join(B))
print("Stable")
print(" ".join(S))
if st(B, S) == True:
    print("Stable")
else:
    print("Not Stable")

Submission status: Wrong Answer

Solution code:
import copy

def bubble(N, A):
    for i in range(N - 1):
        for j in reversed(range(1, N)):
            if A[j - 1][1] > A[j][1]:
                tmp = A[j]
                A[j] = A[j - 1]
                A[j - 1] = tmp

def select(N, A):
    for i in range(N):
        min = i
        for j in range(i, N):
            if A[min][1] > A[j][1]:
                min = j
        tmp = A[i]
        A[i] = A[min]
        A[min] = tmp

def st(B, S):
    for i in range(N):
        if B[i] == S[i]:
            return False
    return True

N = int(input())
#カード入力
S = [i for i in input().split()]
B = copy.deepcopy(S)

bubble(N, B)
select(N, S)

print(" ".join(B))
print("Stable")
print(" ".join(S))
if st(B, S) == True:
    print("Stable")
else:
    print("Not stable")

Submission status: Wrong Answer

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

cb = c[:]
for i in range(n):
	for j in range(n-1,i,-1):
		if cb[j][1] < cb[j-1][1]:
			cb[j-1],cb[j] = cb[j],cb[j-1]
print(*cb)
print('Stable')

cs = c[:]
for i in range(n):
	m = min(range(i,n), key=lambda j: cs[j][1])
	if i != m:
		cs[i],cs[m] = cs[m],cs[i]
print(*cs)
print(('' if cb == cs else 'Not ') + 'Stable')

Submission status: Wrong Answer

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

cb = c[:]
for i in range(n):
	for j in range(n-1,i,-1):
		if cb[j][1] < cb[j-1][1]:
			cb[j-1],cb[j] = cb[j],cb[j-1]
print(*cb)
print('Stable')

cs = c[:]
for i in range(n):
	m = min(range(i,n), key=lambda j: cs[j][1])
	if i != m:
		cs[i],cs[m] = cs[m],cs[i]
print(*cs)
print(('' if cb == cs else 'Not ') + 'stable')

Submission status: Wrong Answer

Solution code:
def BubbleSort(A, N):
    flag = 1
    while flag:
        flag = 0
        for j in reversed(range(1, N)):
            if A[j]['value']<A[j-1]['value']:
                A[j], A[j-1] = A[j-1], A[j]
                flag = 1
    return A

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

def IsStable(answer, target):
    N = len(answer)
    for i in range(N):
        if answer[i]['value'] != target[i]['value']:
            return False
    return True

# Stable Sort
N = int(input())
A = list(
    map(lambda x: {'body': x, 'value': int(x[1])}, input().split())
)
bubble = BubbleSort(A, N)
selection = SelectionSort(A, N)
print(' '.join(map(lambda x: x['body'],bubble)))
print('Stable')
print(' '.join(map(lambda x: x['body'], selection)))
if IsStable(bubble, selection):
    print('Stable')
else:
    print('Not stable')