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:
def bubble_sort(a, n):
    for i in range(n):
        for j in range(n - 1, i, -1):
            if a[j]['value'] < a[j - 1]['value']:
                tmp = a[j]
                a[j] = a[j - 1]
                a[j - 1] = tmp


def selection_sort(a, n):
    is_stable = True

    for i in range(n):
        minj = i
        samei = n
        for j in range(i+1, n, 1):
            if a[j]['value'] == a[i]['value']:
                samei = j
            if a[j]['value'] < a[minj]['value']:
                minj = j
                if samei < minj:
                    is_stable = False
        tmp = a[i]
        a[i] = a[minj]
        a[minj] = tmp

    return is_stable

def print_list_split_whitespace(a):
    for x in a[:-1]:
        print(x['design'] + str(x['value']), end=' ')
    print(a[-1]['design'] + str(a[-1]['value']))


n = int(input())

a = input().split()
for i in range(n):
    s = a[i]
    a[i] = {'design': s[0], 'value': int(s[1])}
b = a.copy()
c = a.copy()

bubble_sort(a, n)
print_list_split_whitespace(a)

print("Stable")

is_stable = selection_sort(b, n)
print_list_split_whitespace(b)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
#-*- coding: utf-8 -*-


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


def bubble_sort(l):
    N = len(l)
    for i in range(0, N):
        for j in range(N - 1, i, -1):
            if int(l[j][1]) < int(l[j - 1][1]):
                l[j], l[j - 1] = l[j - 1], l[j]
    pass


if __name__ == '__main__':
    N = raw_input()
    l1 = raw_input().split()
    l2 = l1[:]
    bubble_sort(l1)
    print ' '.join(l1)
    print "Stable"
    selection_sort(l2)
    print ' '.join(l2)
    if l1 == l2:
        print "Stable"
    else:
        print "Not stable"

Submission status: Accepted

Solution code:
def print_list(array):
    for i,e in enumerate(array):
        if i == N - 1:
            print(e)
        else:
            print(e, end=" ")

def bubbleSort():
    for i in range(N-1):
        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

def selectionSort():
    for i in range(N):
        min_index = i
        for j in range(i, N):
            if int(B[min_index][1:]) > int(B[j][1:]):
                min_index = j
        if i != min_index:
            w = B[i]; B[i] = B[min_index]; B[min_index] = w

N = int(input())
A = input().split()
B = list(A)
bubbleSort()
print_list(A)
print("Stable")
selectionSort()
print_list(B)
if A == B:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
import copy

def BubbleSort(C, N):
    for i in range(0,N):
        for j in range(N-1,i,-1):
            if C[j][1:] < C[j-1][1:]:
                #  C[j] と C[j-1] を交換
                C[j] , C[j-1] = C[j-1] , C[j]
    ret = " ".join(C)
    print(ret)
    print("Stable")
    return ret

def SelectionSort(C, N):
    for i in range(0,N):
        minj = i
        for j in range(i,N):
            if C[j][1:] < C[minj][1:]:
                minj = j
        # C[i] と C[minj] を交換
        C[i] , C[minj] = C[minj] , C[i]
    ret = " ".join(C)
    print(ret)
    return ret

N = int(input())
C = input().split(" ")
ret_B = BubbleSort(copy.deepcopy(C),N)
ret_S = SelectionSort(copy.deepcopy(C),N)
if ret_B == ret_S:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
from sys import stdin
def stdinput():
    return stdin.readline().strip()

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

def main():
    n = int(stdinput())
    A = list(map(Card, stdinput().split()))

    bubble_sorted = bubble_sort(A[:], len(A))
    selection_sorted = selection_sort(A[:], len(A))

    print(' '.join(map(lambda c: c.value2, bubble_sorted)))
    print('Stable' if is_stable(A, bubble_sorted) else 'Not stable')
    print(' '.join(map(lambda c: c.value2, selection_sorted)))
    print('Stable' if is_stable(A, selection_sorted) else 'Not stable')


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

def selection_sort(A, N):
    for i in range(N):
        min_idx = i
        for j in range(i+1, N):
            if A[j].value < A[min_idx].value:
                min_idx = j
        if min_idx != i:
            A[i], A[min_idx] = A[min_idx], A[i]
    return A

def is_stable(A, B):
    for i in range(1, 10):
        sub_A = list(filter(lambda c: c.value == i, A))
        sub_B = list(filter(lambda c: c.value == i, B))
        for a, b in zip(sub_A, sub_B):
            if a.value2 != b.value2:
                return False
    return True

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

class Card:

	def __init__(self, card):
		self.card = card
		self.mark = card[0]
		self.value = int(card[1])

	def __str__(self):
		return self.card

def print_arr(arr):
	for i in range(len(arr)):
		sys.stdout.write(str(arr[i]))
		if i != len(arr) - 1:
			sys.stdout.write(' ')
	print()

def swap(arr, i, j):
	temp = arr[i]
	arr[i] = arr[j]
	arr[j] = temp

def bubble_sort(arr, n):
	swap_count = 0
	for i in range(0, n):
		for j in range(n - 1, i, -1):
			if arr[j].value < arr[j - 1].value:
				swap(arr, j, j - 1)
				swap_count += 1
	return swap_count

def selection_sort(arr, n):
	stable = True
	for i in range(n):
		minj = i
		for j in range(i, n):
			if arr[j].value < arr[minj].value:
				minj = j
		if minj != i:
			for k in range(i + 1, minj):
				if arr[k].value == arr[i].value: stable = False
			swap(arr, i, minj)
	return stable

n = int(input())
arr = list(map(str, input().split()))
cards1 = [None] * n
cards2 = [None] * n
for i in range(n):
	cards1[i] = Card(arr[i])
	cards2[i] = Card(arr[i])

swap_count = bubble_sort(cards1, n)
stable = selection_sort(cards2, n)

print_arr(cards1)
print('Stable')
print_arr(cards2)
if stable == True:
	print('Stable')
else:
	print('Not stable')

Submission status: Accepted

Solution code:
import sys

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

	def __str__(self):
		return self.card

def swap(arr, i, j):
	temp = arr[i]
	arr[i] = arr[j]
	arr[j] = temp

def bubble_sort(arr):
	n = len(arr)
	for i in range(0, n):
		for j in range(n - 1, i, -1):
			if arr[j].value < arr[j - 1].value:
				swap(arr, j, j - 1)

def selection_sort(arr):
	n = len(arr)
	for i in range(n):
		minj = i
		for j in range(i, n):
			if arr[j].value < arr[minj].value:
				minj = j
		if minj != i:
			swap(arr, i, minj)

n = int(input())
arr = list(map(str, input().split()))
cards1 = [None] * n
cards2 = [None] * n
for i in range(n):
	cards1[i] = Card(arr[i])
	cards2[i] = Card(arr[i])

bubble_sort(cards1)
selection_sort(cards2)

for i in range(n):
	sys.stdout.write(cards1[i].card)
	if i != n - 1:
		sys.stdout.write(' ')
print()
print('Stable')

stable = True
for i in range(n):
	if cards1[i].card != cards2[i].card: stable = False
	sys.stdout.write(cards2[i].card)
	if i != n - 1:
		sys.stdout.write(' ')
print()
if stable == True:
	print('Stable')
else:
	print('Not stable')

Submission status: Accepted

Solution code:
import sys

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

	def __str__(self):
		return self.card

def print_arr(arr1, arr2):
	n = len(arr1)
	stable = True
	for i in range(n):
		if arr2 != None and arr1[i].card != arr2[i].card: stable = False
		sys.stdout.write(str(arr1[i]))
		if i != n - 1:
			sys.stdout.write(' ')
	print()
	return stable

def swap(arr, i, j):
	temp = arr[i]
	arr[i] = arr[j]
	arr[j] = temp

def bubble_sort(arr):
	n = len(arr)
	for i in range(0, n):
		for j in range(n - 1, i, -1):
			if arr[j].value < arr[j - 1].value:
				swap(arr, j, j - 1)

def selection_sort(arr):
	n = len(arr)
	for i in range(n):
		minj = i
		for j in range(i, n):
			if arr[j].value < arr[minj].value:
				minj = j
		if minj != i:
			swap(arr, i, minj)

n = int(input())
arr = list(map(str, input().split()))
cards1 = [None] * n
cards2 = [None] * n
for i in range(n):
	cards1[i] = Card(arr[i])
	cards2[i] = Card(arr[i])

bubble_sort(cards1)
selection_sort(cards2)

print_arr(cards1, None)
print('Stable')

stable = print_arr(cards2, cards1)
if stable == True:
	print('Stable')
else:
	print('Not stable')

Submission status: Accepted

Solution code:
import sys

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

	def __str__(self):
		return self.card

def print_cards(arr_print, arr_compare):
	n = len(arr_print)
	same = True
	for i in range(n):
		if arr_compare != None and arr_print[i].card != arr_compare[i].card: same = False
		sys.stdout.write(str(arr_print[i]))
		if i != n - 1:
			sys.stdout.write(' ')
	print()
	return same

def swap(arr, i, j):
	temp = arr[i]
	arr[i] = arr[j]
	arr[j] = temp

def bubble_sort(arr):
	n = len(arr)
	for i in range(0, n):
		for j in range(n - 1, i, -1):
			if arr[j].value < arr[j - 1].value:
				swap(arr, j, j - 1)

def selection_sort(arr):
	n = len(arr)
	for i in range(n):
		minj = i
		for j in range(i, n):
			if arr[j].value < arr[minj].value:
				minj = j
		if minj != i:
			swap(arr, i, minj)

n = int(input())
arr = list(map(str, input().split()))
cards1 = [None] * n
cards2 = [None] * n
for i in range(n):
	cards1[i] = Card(arr[i])
	cards2[i] = Card(arr[i])

bubble_sort(cards1)
selection_sort(cards2)

print_cards(cards1, None)
print('Stable')

stable = print_cards(cards2, cards1)
if stable == True:
	print('Stable')
else:
	print('Not stable')

Submission status: Accepted

Solution code:
import sys

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

def print_cards(arr_print, arr_compare):
	n = len(arr_print)
	same = True
	for i in range(n):
		if arr_compare != None and arr_print[i].card != arr_compare[i].card: same = False
		sys.stdout.write(arr_print[i].card)
		if i != n - 1:
			sys.stdout.write(' ')
	print()
	return same

def swap(arr, i, j):
	temp = arr[i]
	arr[i] = arr[j]
	arr[j] = temp

def bubble_sort(arr):
	n = len(arr)
	for i in range(0, n):
		for j in range(n - 1, i, -1):
			if arr[j].value < arr[j - 1].value:
				swap(arr, j, j - 1)

def selection_sort(arr):
	n = len(arr)
	for i in range(n):
		minj = i
		for j in range(i, n):
			if arr[j].value < arr[minj].value:
				minj = j
		if minj != i:
			swap(arr, i, minj)

n = int(input())
arr = list(map(str, input().split()))
cards1 = [None] * n
cards2 = [None] * n
for i in range(n):
	cards1[i] = Card(arr[i])
	cards2[i] = Card(arr[i])

bubble_sort(cards1)
selection_sort(cards2)

print_cards(cards1, None)
print('Stable')

stable = print_cards(cards2, cards1)
if stable == True:
	print('Stable')
else:
	print('Not stable')

Submission status: Accepted

Solution code:
import sys

class Card:
	def __init__(self, card):
		self.card = card
		self.mark = card[0]
		self.value = card[1]
	
	def equals(self, other):
		if self.mark != other.mark: return False
		if self.value != other.value: return False
		return True

	def __str__(self):
		return self.card

def print_cards(cards, cards_):
	n = len(cards)
	same = True
	for i in range(n):
		if cards_ != None and cards[i].equals(cards_[i]) == False:
			same = False
		sys.stdout.write(str(cards[i])) 
		if i != n - 1:
			sys.stdout.write(' ')
	print()
	return same	

def swap(cards, i, j):
	temp = cards[i]
	cards[i] = cards[j]
	cards[j] = temp

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

def selection_sort(cards):
	n = len(cards)
	for i in range(n):
		mini = i
		for j  in range(i, n):
			if cards[j].value < cards[mini].value:
				mini = j
		if mini != i:
			swap(cards, i, mini)
		
n = int(input())
input_list = list(map(str, input().split()))
cards1 = [None] * n
cards2 = [None] * n
for i in range(n):
	cards1[i] = Card(input_list[i])
	cards2[i] = Card(input_list[i])
	
bubble_sort(cards1)
selection_sort(cards2)

print_cards(cards1, None)
print('Stable')

stable = print_cards(cards2, cards1)
if stable == True:
	print('Stable')
else:
	print('Not stable')

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    cards = list(map(str, input().split()))
    bubbleSortedCards = cards[:]
    selectionSortedCards = cards[:]


    bubbleSort(bubbleSortedCards, n)
    print(' '.join(map(str, bubbleSortedCards)))
    print('Stable')

    selectionSort(selectionSortedCards, n)
    print(' '.join(map(str, selectionSortedCards)))
    print(isStable(bubbleSortedCards, selectionSortedCards, n))


def bubbleSort(numbers, n):
    for i in range(n - 1, 0, -1):
        for j in range(i):
            if int(numbers[j][1]) > int(numbers[j + 1][1]):
                numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]

def selectionSort(numbers, n):
    minj = 0

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

        if i != minj:
            numbers[i], numbers[minj] = numbers[minj], numbers[i]

def isStable(bubbleSortedCards, selectionSortedCards, n):
    for i in range(n):
        if bubbleSortedCards[i] != selectionSortedCards[i]:
            return 'Not stable'

    return 'Stable'

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class Card:
    def __init__(self, mark, value):
        self.mark = mark
        self.value = value

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

    def __lt__(self, other):
        return self.value < other.value

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


def BubbleSort(arr):
    res = [Card(c.mark, c.value) for c in arr]
    swap_flg = True
    i = 0
    while swap_flg:
        swap_flg = False
        for j in range(len(res) - 1, i, -1):
            if (res[j] < res[j - 1]):
                res[j], res[j - 1] = res[j - 1], res[j]
                swap_flg = True
        i += 1
    return res


def SelectionSort(arr):
    res = [Card(c.mark, c.value) for c in arr]
    for i in range(0, len(res)):
        minj = i
        for j in range(i, N):
            if res[j] < res[minj]:
                minj = j
        if (i != minj):
            res[i], res[minj] = res[minj], res[i]
    return res


def isStable(in_arr, out_arr):
    stable_arr = BubbleSort(in_arr)
    return all(out_arr[i] == stable_arr[i] for i in range(0, len(out_arr)))


N = int(input())
arr = [Card(s[0], int(s[1])) for s in input().split()]
b_arr = BubbleSort(arr)
print(' '.join(map(str, b_arr)))
print('Stable' if isStable(arr, b_arr) else 'Not stable')
s_arr = SelectionSort(arr)
print(' '.join(map(str, s_arr)))
print('Stable' if isStable(arr, s_arr) else 'Not stable')

Submission status: Accepted

Solution code:
import copy
N = int(input())
A = input().split()
B = copy.copy(A)
boo = 1
while boo:
    boo = 0
    for i in range(N-1):
        if A[i][1] > A[i+1][1]:
            A[i], A[i+1] = A[i+1], A[i]
            boo = 1
print(*A)
print("Stable")
for i in range(N):
    mi = i
    for j in range(i,N):
        if B[mi][1] > B[j][1]:
            mi = j
    B[i], B[mi] = B[mi], B[i]
if A==B:
    print(*B)
    print("Stable")
else:
    print(*B)
    print("Not stable")

Submission status: Accepted

Solution code:
def bubbleSort(cards, N):
    flag = True
    while flag:
        flag = False
        for j in range(N-1, 0, -1):
            if cards.numbers[j] < cards.numbers[j - 1]:
                cards.swap(j, j-1)
                flag = True
    return cards

def selectionSort(cards,N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if cards.numbers[j] < cards.numbers[minj]:
                minj = j
        if minj != i:
            cards.swap(i, minj)
    return cards

class Cards(object):
    
    def __init__(self, cards):
        self.cards = cards
        self.numbers = [int(card[1]) for card in cards]

    def filter_by_number(self, number):
        return [card for card in self.cards if card.endswith(str(number))]

    def swap(self, i, j):
        self.cards[i], self.cards[j] = self.cards[j], self.cards[i]
        self.numbers = [int(card[1]) for card in self.cards]

    def show(self):
        print(' '.join(self.cards))

    def is_stable(self, cards):
        for n in range(1,10):
            suits_x = self.filter_by_number(str(n))
            suits_y = cards.filter_by_number(str(n))
            if suits_x != suits_y:
                return False
        return True

    def copy(self):
        return Cards([card for card in self.cards])

def run():
    n = int(input())
    cards = Cards(input().split())
    cards_sorted = bubbleSort(cards.copy(),n)
    cards_sorted.show()
    if cards.is_stable(cards_sorted):
        print('Stable')
    else:
        print('Not stable')

    cards_sorted = selectionSort(cards.copy(),n)
    cards_sorted.show()
    if cards.is_stable(cards_sorted):
        print('Stable')
    else:
        print('Not stable')

if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
import copy

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

def is_stable(sorted_list):
    for i in range(len(sorted_list)-1):
        if sorted_list[i][1] == sorted_list[i+1][1]:
            for j in range(len(A)):
                if A[j] == sorted_list[i]:
                    smaller_idx = j
                if A[j] == sorted_list[i+1]:
                    larger_idx = j
            if smaller_idx > larger_idx:
                return False
    return True

def print_stable_or_not(is_stable):
    if is_stable:
        print("Stable")
    else:
        print("Not stable")

def bubble_sort(A1):
    flg = True
    while flg:
        for i in range(N):
            flg = False
            for j in range(N-1, i, -1):
                if int(A1[j-1][1]) > int(A1[j][1]):
                    A1[j-1], A1[j] = A1[j], A1[j-1]
                    flg = True
    print(" ".join(A1))
    print_stable_or_not(is_stable(A1))

def insertion_sort(A2):
    for i in range(N-1):
        min_idx = i
        for j in range(i+1, N):
            if int(A2[min_idx][1]) > int(A2[j][1]):
                min_idx = j
        if min_idx != i:
            A2[i], A2[min_idx] = A2[min_idx], A2[i]
    print(" ".join(A2))
    print_stable_or_not(is_stable(A2))

if __name__ == '__main__':
    A1 = copy.deepcopy(A)
    A2 = copy.deepcopy(A)
    bubble_sort(A1)
    insertion_sort(A2)

Submission status: Accepted

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


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


def isStableSort(initialArray, resultArray):
    n = len(initialArray)
    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 initialArray[i][1] == initialArray[j][1]:
                        if initialArray[i] == resultArray[b]:
                            if initialArray[j] == resultArray[a]:
                                return False
    
    return True


n = int(input())
array = [x for x in input().split()]
cards = [[a[0], a[1]] for a in array]
cardsForBubble = cards[:]
cardsForSelection = cards[:]

bSort = bubbleSort(cardsForBubble)
sSort = selectionSort(cardsForSelection)

resultForBubble = []
resultForSelection = []

for b in bSort:
    resultForBubble.append(''.join(b))
for s in sSort:
    resultForSelection.append(''.join(s))

print(*resultForBubble)
if isStableSort(array, resultForBubble):
    print("Stable")
else:
    print("Not stable")

print(*resultForSelection)
if isStableSort(array, resultForSelection):
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
N = int(input())
l = input().split()
l2 = l[:]
for j in range(N):
    for i in range(N-1):
        if l[i][1] > l[i+1][1]:
            l[i], l[i+1] = l[i+1], l[i]
for i in range(0,len(l)-1):
    print(l[i],end=' ')
print(l[N-1])
print("Stable")

for j in range(0,len(l2)-1):
    min = l2[j][1]
    a = j
    for i in range(j,len(l2)):
        if min > l2[i][1]:
            min = l2[i][1]
            a = i
    l2[j],l2[a] = l2[a],l2[j]
for i in range(0,len(l2)-1):
    print(l2[i],end=' ')
print(l2[N-1])
if l==l2:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

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

def BubbleSort(C, n):
    for i in range(n-1):
        for w in range(i+1, n):
            j = n-w+i
            if (C[j][1] < C[j-1][1]):
                a = C[j]
                C[j] = C[j-1]
                C[j-1] = a
def SelectionSort(C, n):
    for i in range(n):
        mini = i
        for j in range(i+1,n):
            if (C[j][1] < C[mini][1]):
                mini = j
        if(mini != i):
            a = C[i]
            C[i] = C[mini]
            C[mini] = a
## l[1]이 str 이라는것에 주의 int(l[1])을 해줘야함 --> 이거 때문에 20분 디버깅 소비
def stable(A,B):
    count = [0 for i in range(9)]
    for l in A:
        count[int(l[1]) - 1] += 1
    ilist = [] ##安定なiのリスト
    for i in range(1,10):
        if (count[i-1] > 1):
            awlist = []
            for l in A:
                if(int(l[1]) == i):
                    awlist.append(l[0])
            bwlist = []
            for l in B:
                if(int(l[1]) == i):
                    bwlist.append(l[0])
            if (awlist == bwlist):
                ilist.append(i)
            
        else:
            ilist.append(i)
    if (len(ilist) == 9):
        print('Stable',end = '')
    else:
        print('Not stable', end = '')
                  

Blist = list(clist)
BubbleSort(Blist, n)
for i in range(n):
    if (i == n-1):
        print('{}{}'.format(Blist[i][0],Blist[i][1]), end = '')
    else : 
        print('{}{}'.format(Blist[i][0],Blist[i][1]), end = ' ')
print()
stable(clist, Blist)
print()

Slist = list(clist)
SelectionSort(Slist, n)
for i in range(n):
    if(i == n-1):
        print('{}{}'.format(Slist[i][0],Slist[i][1]), end = '')
    else:
        print('{}{}'.format(Slist[i][0],Slist[i][1]), end = ' ')
print()
stable(clist, Slist)
print()

Submission status: Accepted

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

def BubbleSort(C, n):
    for i in range(n-1):
        for w in range(i+1, n):
            j = n-w+i
            if (C[j][1] < C[j-1][1]):
                a = C[j]
                C[j] = C[j-1]
                C[j-1] = a
def SelectionSort(C, n):
    for i in range(n):
        mini = i
        for j in range(i+1,n):
            if (C[j][1] < C[mini][1]):
                mini = j
        if(mini != i):
            a = C[i]
            C[i] = C[mini]
            C[mini] = a
## l[1]이 str 이라는것에 주의 int(l[1])을 해줘야함 --> 이거 때문에 20분 디버깅 소비
def stable(A,B):
    count = [0 for i in range(9)]
    for l in A:
        count[int(l[1]) - 1] += 1
    ilist = [] ##安定なiのリスト
    for i in range(1,10):
        if (count[i-1] > 1):
            awlist = []
            for l in A:
                if(int(l[1]) == i):
                    awlist.append(l[0])
            bwlist = []
            for l in B:
                if(int(l[1]) == i):
                    bwlist.append(l[0])
            if (awlist == bwlist):
                ilist.append(i)
            
        else:
            ilist.append(i)
    if (len(ilist) == 9):
        print('Stable',end = '')
    else:
        print('Not stable', end = '')
                  

Blist = list(clist)
BubbleSort(Blist, n)
for i in range(n):
    if (i == n-1):
        print('{}{}'.format(Blist[i][0],Blist[i][1]), end = '')
    else : 
        print('{}{}'.format(Blist[i][0],Blist[i][1]), end = ' ')
print()
stable(clist, Blist)
print()

Slist = list(clist)
SelectionSort(Slist, n)
for i in range(n):
    if(i == n-1):
        print('{}{}'.format(Slist[i][0],Slist[i][1]), end = '')
    else:
        print('{}{}'.format(Slist[i][0],Slist[i][1]), end = ' ')
print()
stable(clist, Slist)
print()

Submission status: Accepted

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

class Card:
    def __init__(self, str):
        self.suit  = str[0]
        self.value = int(str[1])

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

def swap(A, i, j):
    tmp  = A[i]
    A[i] = A[j]
    A[j] = tmp

def BubbleSort(C, N):
    for i in range(N):
        for j in range(N-1, i, -1):
            if C[j].value < C[j-1].value:
                swap(C, j, j-1)  # C[j] と C[j-1] を交換

def SelectionSort(C, N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if C[j].value < C[minj].value:
                minj = j
        swap(C, i, minj)  # C[i] と C[minj] を交換

def isStable(A, B):
    for i in range(1, len(B)):
        if B[i-1].value == B[i].value:
            for j in range(len(A)):
                if A[j] == B[i-1]: break
                if A[j] == B[i]:   return False
    return True

N = int(input())
A = [Card(t) for t in input().split()]
if len(A) != N: raise

B = A[:]
S = A[:]
BubbleSort(B, N)
SelectionSort(S, N)
print(' '.join(map(str, B)))
print('Stable' if isStable(A, B) else 'Not stable')
print(' '.join(map(str, S)))
print('Stable' if isStable(A, S) else 'Not stable')

Submission status: Accepted

Solution code:
n = int(input())
*A, = input().split()
B = A[:]
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]
print(*A)
print("Stable")
 
for i in range(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]
print(*B)
if A == B:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
from copy import copy

def bubbleSort(arr):
    cp_arr = copy(arr)
    indices = list(range(len(cp_arr)))
    
    finished_flag = False
    while not finished_flag:
        finished_flag = True

        for i in range(len(cp_arr)-1):
            if cp_arr[i] > cp_arr[i+1]:
                finished_flag = False

                t = cp_arr[i]
                cp_arr[i] = cp_arr[i+1]
                cp_arr[i+1] = t

                t = indices[i]
                indices[i] = indices[i+1]
                indices[i+1] = t
    return indices

def selectionSort(arr):
    cp_arr = copy(arr)
    indices = list(range(len(cp_arr)))

    for i in range(len(cp_arr)):
        min = i
        for j in range(i+1, len(cp_arr)):
            if cp_arr[j] < cp_arr[min]:
                min = j

        t = cp_arr[i]
        cp_arr[i] = cp_arr[min]
        cp_arr[min] = t

        t = indices[i]
        indices[i] = indices[min]
        indices[min] = t

    return indices

if __name__ == "__main__":
    input()
    cards = input().split()
    values = list(map(lambda x: int(x[1]), cards))
    bubbleSorted_indices = bubbleSort(values)
    selectionSorted_indices = selectionSort(values)
    bubble_stable = True
    selection_stable = True
    for i in range(len(values)-1):
        if values[bubbleSorted_indices[i]] == values[bubbleSorted_indices[i+1]] and bubbleSorted_indices[i] > bubbleSorted_indices[i+1]:
            bubble_stable = False
        if values[selectionSorted_indices[i]] == values[selectionSorted_indices[i+1]] and selectionSorted_indices[i] > selectionSorted_indices[i+1]:
            selection_stable = False
    bubble_sorted = [cards[i] for i in bubbleSorted_indices]
    selection_sorted = [cards[i] for i in selectionSorted_indices]
    print(" ".join(bubble_sorted))
    print("Stable" if bubble_stable else "Not stable") 
    print(" ".join(selection_sorted))
    print("Stable" if selection_stable else "Not stable")

Submission status: Accepted

Solution code:
input_line = int(input())
out_selection = input().split()
out_bubble = out_selection[:]

# bubblesort                                                                                  
for i in range(input_line):
    for j in range(input_line-1, i, -1):
        if out_bubble[j][1] < out_bubble[j-1][1]:
            out_bubble[j], out_bubble[j-1] = out_bubble[j-1],out_bubble[j]
print(*out_bubble)
print("Stable")

# selectionsort                                                                               
for i in range(input_line):
    minj = i
    for j in range(i, input_line):
        if out_selection[j][1] < out_selection[minj][1]:
            minj = j
    out_selection[i], out_selection[minj] = out_selection[minj], out_selection[i]

print(*out_selection)
print("Stable" if out_bubble == out_selection else "Not stable")