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 < C[j-1].value
4             swap C[j] and C[j-1] SelectionSort(C)
1 for i = 0 to C.length-1
2     mini = i
3     for j = i to C.length-1
4         if C[j].value < C[mini].value
5             mini = j
6     swap C[i] and C[mini] Note that, indices for array elements are based on 0-origin. 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

Solution (Python):
N = int(input())
card_list_source = input().split(' ')

def BubbleSort(card_list, N):
    for i in range(N):
        for j in reversed(range(i+1, N)):
            if int(card_list[j][1]) < int(card_list[j-1][1]):
                temp = card_list[j]
                card_list[j] = card_list[j-1]
                card_list[j-1] = temp
    return card_list

def SelectionSort(card_list, N):
    for i in range(N):
        min_index = i
        for j in range(i+1, N):
            if int(card_list[j][1]) < int(card_list[min_index][1]):
                min_index = j
        if min_index != i:
            temp = card_list[i]
            card_list[i] = card_list[min_index]
            card_list[min_index] = temp
    return card_list

def isStable(card_list_A, card_list_B):
    N = len(card_list_A)
    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 int(card_list_A[i][1]) == int(card_list_A[j][1]) and card_list_A[i] == card_list_B[b] and card_list_A[j] == card_list_B[a]:
                        return 'Not stable'
    return 'Stable'

def make_out_str(card_list):
    out_str = ''
    for i, card in enumerate(card_list):
        out_str += card
        if i < len(card_list) - 1:
            out_str += ' '
    return out_str

card_list_bubble = BubbleSort(card_list_source.copy(), N)
print(make_out_str(card_list_bubble))
print(isStable(card_list_bubble, card_list_source))

card_list_selection = SelectionSort(card_list_source.copy(), N)
print(make_out_str(card_list_selection))
print(isStable(card_list_selection, card_list_source))

Solution (Python):
class card:
    def __init__(self, card):
        self.suit = card[0]
        self.value = int(card[1])

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


def selectionSort(a, n):
    r = 0
    for i in range(n):
        minj = i
        for j in range(i, n):
            if a[j].value < a[minj].value:
                minj = j
        a[i], a[minj] = a[minj], a[i]


def bubbleSort(a, n):
    flag = True
    while flag:
        flag = False
        for j in range(n - 1, 0, -1):
            if a[j].value < a[j - 1].value:
                a[j], a[j - 1] = a[j - 1], a[j]
                flag = True


def copycard(cards):
    r = []
    for c in cards:
        r.append(card(c.suit + str(c.value)))
    return r


def compareCard(c1,c2):
    for i in range(len(c1)):
        if c1[i].suit != c2[i].suit or c1[i].value != c2[i].value:
            return False
    return True


n = int(input())
cards = list(map(card, input().split()))
cards1 = copycard(cards)
cards2 = copycard(cards)
bubbleSort(cards1, n)
print(*cards1)
print("Stable")
selectionSort(cards2, n)
print(*cards2)
if compareCard(cards1,cards2):
    print("Stable")
else:
    print("Not stable")

Solution (Python):
def check_stable(before_sort_list, after_sort_list):
    N = len(before_sort_list)
    for i in range(0, N, 1):
        for j in range(i+1, N, 1):
            for a in range(0, N, 1):
                for b in range(a+1, N, 1):
                    if before_sort_list[i][1] == before_sort_list[j][1] and before_sort_list[i] == after_sort_list[b] and before_sort_list[j] == after_sort_list[a]:
                        return False
    return True

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


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


num_cards = int(input())
cards = input().split(' ')

sorted_cards1 = bubble_sort(cards.copy(), num_cards)
sorted_cards2 = selection_sort(cards.copy(), num_cards)

print(' '.join(sorted_cards1))
print('Stable' if check_stable(cards, sorted_cards1) else 'Not stable')
print(' '.join(sorted_cards2))
print('Stable' if check_stable(cards, sorted_cards2) else 'Not stable')

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

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

def is_stable(original_list, sorted_list):
    for target in sorted_list:
        for original in original_list:
            if target[1] == original[1]:
                if target[0] != original[0]:
                    return "Not stable"
                original_list.remove(original)
                break
    return "Stable"
                
if __name__ == "__main__":
    import copy
    n = int(input())
    c = input().split()
    bubble_list = bubble_sort(copy.deepcopy(c), n)
    print(*bubble_list)
    print(is_stable(copy.deepcopy(c), bubble_list))
    selection_list = selection_sort(copy.deepcopy(c), n)
    print(*selection_list)
    print(is_stable(copy.deepcopy(c), selection_list))

Solution (Python):
class card:
    """
    suit: S, H, C, D
    number: 1~10
    """
    def __init__(self, card_input):
        self.suit = card_input[:1]
        self.number = int(card_input[1:])
    
    def __str__(self):
        return self.suit + str(self.number)


def print_list(a):
    out = ''
    for ai in a:
        out += str(ai) + ' '
    else:
        out = out[:-1]
    print(out)

def bubble_sort(a, n):
    for i in range(0, n):
        for j in range(n - 1, i, -1):
            if a[j].number < a[j - 1].number:
                tmp = a[j]
                a[j] = a[j - 1]
                a[j - 1] = tmp
    return a
                
def selection_sort(a, n):
    for i in range(0, n):
        minj = i
        for j in range(i, n):
            if a[j].number < a[minj].number:
                minj = j
        tmp = a[i]
        a[i] = a[minj]
        a[minj] = tmp
    return a

n = int(input())
input_cards = input().split(' ')
cards = []
for in_card in input_cards:
    cards.append(card(in_card))

bubble = bubble_sort(cards[:], n)
print_list(bubble)
print("Stable")

selection = selection_sort(cards[:], n)
print_list(selection)
if bubble == selection:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
from sys import stdin
from copy import deepcopy
from collections import namedtuple


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

def selectionSord(C, N):
    A = deepcopy(C)
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if A[j].value < A[minj].value:
                minj = j
        A[i], A[minj] = A[minj], A[i]
    return A

if __name__ == "__main__":
    Card = namedtuple("Card", ["char", "value"])
    N = int(stdin.readline())
    A = [Card(item[0], int(item[1])) for item in stdin.readline().split()]
    
    bubble = bubbleSort(A, N)
    print(*[item.char+str(item.value) for item in bubble])
    
    bubble_value = [item.value for item in bubble]
    bubble_stable = True
    for v in set(bubble_value):
        bubble_char = [item for item in bubble if item.value==v]
        original_char = [item for item in A if item.value==v]
        if bubble_char != original_char:
            bubble_stable = False
    print("Stable" if bubble_stable else "Not stable")
        
        
    
    selection = selectionSord(A, N)
    print(*[item.char+str(item.value) for item in selection])
    
    selection_value = [item.value for item in selection]
    selection_stable = True
    for v in set(selection_value):
        selection_char = [item for item in selection if item.value==v]
        original_char = [item for item in A if item.value==v]
        if selection_char != original_char:
            selection_stable = False
    print("Stable" if selection_stable else "Not stable")

Solution (Python):
import re
def bubbleSort(c):
	flag=True
	while(flag):
		flag=False
		for i in range(len(c)-1):
			if(c[i][1] > c[i+1][1]):
				c[i],c[i+1] = c[i+1],c[i]
				flag=True
	return c

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

n=int(input())
cards=list(input().split())
c=[]
for i in range(n):
	c.append([cards[i][0],int(cards[i][1])])
c2=c.copy()

bubble=bubbleSort(c)
bubble_str=re.sub("[\[\]\,]","",str(bubble))
bubble_str=re.sub("\' ","",bubble_str)
print(re.sub("\'","",bubble_str))
print("Stable")

select=selectionSort(c2)
select_str=re.sub("[\[\]\,]","",str(select))
select_str=re.sub("\' ","",select_str)
print(re.sub("\'","",select_str))
if(bubble_str == select_str):
	print("Stable")
else:
	print("Not stable")

Solution (Python):
def get_value(s):
    return int(s[1])

def get_suit(s):
    return s[0]

def bubble_sort(A):
    a = list(A)
    for i in range(0, len(a)):
        
        
        for j in range(len(a)-1, i, -1):
            if get_value(a[j-1]) > get_value(a[j]):
                a[j-1], a[j] = a[j], a[j-1]
    return a

def selection_sort(A):
    a = list(A)
    for i in range(len(A)-1):
        i_min = i
        for j in range(i+1, len(A)):
            if get_value(a[j]) < get_value(a[i_min]):
                i_min = j
        a[i], a[i_min] = a[i_min], a[i]
    return a

def is_stable(A_orig, A_sort):
    dict_orig = {}
    dict_sort = {}
    
    
    for i in range(10):
        dict_orig[i] = list()
        dict_sort[i] = list()
    
    
    for i in range(0, len(A_orig)):
        
        vo = get_value(A_orig[i])
        vs = get_value(A_sort[i])
        so = get_suit(A_orig[i])
        ss = get_suit(A_sort[i])
        
        dict_orig[vo].append(so)
        dict_sort[vs].append(ss)
    
    
    for i in range(10):
        for j in range(len(dict_orig[i])):
            if dict_orig[i][j] is not dict_sort[i][j]:
                return False
    return True

input()
input_arr = input().split()

arr_bubble = bubble_sort(input_arr)
arr_selection = selection_sort(input_arr)

print(' '.join(arr_bubble))
print('Stable' if is_stable(input_arr, arr_bubble) else 'Not stable')
print(' '.join(arr_selection))
print('Stable' if is_stable(input_arr, arr_selection) else 'Not stable')

Solution (Python):
import sys


def BubbleSort(C):
    for i in range(len(C)):
        for j in range(len(C)-1, i, -1):
            if C[j][1] < C[j-1][1]:
                C[j], C[j-1] = C[j-1], C[j]


def SelectionSort(C):
    for i in range(len(C)):
        mini = i
        for j in range(i, len(C)):
            if C[j][1] < C[mini][1]:
                mini = j
        C[i], C[mini] = C[mini], C[i]


def stable(cards, C):
    for a in range(len(C)-1):
        c1 = cards.index(C[a])
        c2 = cards.index(C[a+1])
        if C[a][1] == C[a+1][1] and c1 > c2:
            print("Not stable")
            break
    else:
        print("Stable")


def main():
    input = sys.stdin.readline
    N = int(input())
    cards = input().split()
    bs = [i for i in cards]
    ss = [i for i in cards]
    BubbleSort(bs)
    SelectionSort(ss)
    print(" ".join(bs))
    stable(cards, bs)
    print(" ".join(ss))
    stable(cards, ss)


if __name__ == "__main__":
    main()

Solution (Python):
def s_sort(A,N):

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

       if i != min_j:
           temp = A[i]
           A[i] = A[min_j]
           A[min_j] = temp

   return A

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

if __name__ == '__main__':
    n = int(input())
    R = list(map(str,input().split()))
    C = R[:]
    Sr = s_sort(R,n)
    Br = b_sort(C,n)

    fstable = Sr == Br

    print(" ".join(map(str,Br)))
    print("Stable")
    print(" ".join(map(str,Sr)))
    if(fstable == True):
       print("Stable")
    else:
       print("Not stable")

Solution (Python):
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]:
                x = c[j]
                c[j] = c[j-1]
                c[j-1] = x
    return c

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
        x = c[i]
        c[i] = c[minj]
        c[minj] = x
    return c

n = int(input())
c = list(map(str, input().split()))
c1 = copy.deepcopy(c)
c2 = copy.deepcopy(c)

c1 = BubbleSort(c1, n)
print(*c1)
print('Stable')

c2 = SelectionSort(c2, n)
print(*c2)
if c1 == c2:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
"""ALDS1_2_C"""

from collections import namedtuple
from copy import deepcopy

Card = namedtuple("Card", ("suit", "value"))

def bubble(cards):
    cards = deepcopy(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:
                cards[j], cards[j-1] = cards[j-1], cards[j]
    return cards


def selection(cards):
    cards = deepcopy(cards)
    N = len(cards)
    for i in range(N):
        argmin = i
        for j in range(i, N):
            if cards[j].value < cards[argmin].value:
                argmin = j
        cards[i], cards[argmin] = cards[argmin], cards[i]
    return cards


def print_cards(cards):
    for i, card in enumerate(cards):
        end = "" if i == len(cards) - 1 else " "
        print(card.suit, card.value, sep="", end=end)
    print()


def main():
    _ = input()
    cards = [Card(i[0], int(i[1])) for i in input().split()]
    bubble_sorted = bubble(cards)
    selection_sorted = selection(cards)

    print_cards(bubble_sorted)
    print("Stable")
    print_cards(selection_sorted)
    if bubble_sorted == selection_sorted:
        print("Stable")
    else:
        print("Not stable")


if __name__ == "__main__":
    main()

Solution (Python):
import copy

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

def bubble_sort(bubble_C, N):
    for i in range(N):
        for j in range(i+1, N)[::-1]:
            if int(bubble_C[j][1]) < int(bubble_C[j-1][1]):
                tmp = bubble_C[j]
                bubble_C[j] = bubble_C[j-1]
                bubble_C[j-1] = tmp
    return bubble_C

def selection_sort(sel_C, N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if int(sel_C[j][1]) < int(sel_C[minj][1]):
                minj = j
        tmp = sel_C[i]
        sel_C[i] = sel_C[minj]
        sel_C[minj] = tmp
    return sel_C

def check_stable(C1, C2):
    C_order_table = {}
    sorted_C_order_table = {}
    for i in range(len(C1)):
        if C_order_table.get(C1[i][1]):
            C_order_table[C[i][1]] += C1[i][0]
        else:
            C_order_table[C1[i][1]] = C1[i][0]
        
        if sorted_C_order_table.get(C2[i][1]):
            sorted_C_order_table[C2[i][1]] += C2[i][0]
        else:
            sorted_C_order_table[C2[i][1]] = C2[i][0]
    
    is_stable = True
    for n in range(1, 10):
        if C_order_table.get(str(n)) != sorted_C_order_table.get(str(n)):
            is_stable = False
            break
    
    if is_stable:
        print('Stable')
    else:
        print('Not stable')

bubble_C = copy.copy(C)
sel_C = copy.copy(C)

sorted_C = bubble_sort(bubble_C, N)
print(" ".join(sorted_C))
check_stable(C, sorted_C)

sorted_C = selection_sort(sel_C, N)
print(" ".join(sorted_C))
check_stable(C, sorted_C)

Solution (Python):
n=int(input())
cards=input().split()
cards2=cards[:]
flag=1
while flag:
  flag=0
  for i in range(n-1,0,-1):
    if cards[i][1] < cards[i-1][1]:
      cards[i], cards[i-1]=cards[i-1],cards[i]
      flag=1
print(" ".join(cards))
print("Stable")

for i in range(n):
  minj = i
  for j in range(i,n):
    if cards2[j][1] < cards2[minj][1]:
      minj = j
  if i != minj:
    cards2[i], cards2[minj]=cards2[minj],cards2[i]
print(" ".join(cards2))
if cards == cards2:
  print("Stable")
else:
  print("Not stable")

Solution (Python):
N = int(input())
A = input().split()
B = A[:]

def BubbleSort(A, N):
    for i in range(N):      
        for j in range(N-1, i, -1):     
            if A[j-1][1] > A[j][1]:           
                A[j-1], A[j] = A[j], A[j-1]     
    return A


def SelectionSort(B, N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if B[minj] [1]> B[j][1]:
                minj = j
        B[i], B[minj] = B[minj], B[i]       
    return B

ans_b = BubbleSort(A, N)
print(*ans_b)
print("Stable")
ans_s = SelectionSort(B, N)
print(*ans_s)
if ans_b == ans_s:
    print("Stable")
else:
    print("Not stable")

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

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

def is_stable(a, sa, n):
    stable = True
    for i in range(n-1):
        if sa[i][1] == sa[i+1][1] and a.index(sa[i]) > a.index(sa[i+1]):
                stable = False
                break
    if stable:
        print('Stable')
    else:
        print('Not stable')

n = int(input())
a = [ (s[0], int(s[1:])) for s in input().split() ]
ba = bubble_sort(a.copy(),n)
print(*[ s[0]+str(s[1]) for s in ba])
is_stable(a,ba,n)
ia = selection_sort(a.copy(),n)
print(*[ s[0]+str(s[1]) for s in ia])
is_stable(a,ia,n)

Solution (Python):
def BubbleSort(a, n):
    flag = 1
    count = 0
    i = 0
    while flag:
        flag = 0
        for j in reversed(range(i+1,n)):
            if a[j][1] < a[j-1][1]:
                c = a[j]
                a[j] = a[j-1]
                a[j-1] = c
                flag = 1
                count += 1
        i += 1

def SelectionSort(a, N):
    count = 0
    minj = 0
    for i in range(n):
        minj = i
        for j in range(i,n):
            if a[j][1] < a[minj][1]:
                minj = j
        if i != minj:
            count += 1      
        c = a[i]
        a[i] = a[minj]
        a[minj] = c

n = int(input())
s = [x for x in input().split()]
s1 = s.copy()

BubbleSort(s,n)
for i in range(len(s)-1):
    print(s[i],end=' ')
print(s[-1])
print('Stable')

SelectionSort(s1,n)

for i in range(len(s1)-1):
    print(s1[i],end=' ')
print(s1[-1])
if s==s1:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
def bubble_sort(card_list):
    
    
    for i in range(len(card_list)):
        for j in range(len(card_list)-1, i, -1):
            if int(card_list[j][1]) < int(card_list[j-1][1]):
                card_list[j-1], card_list[j] = card_list[j], card_list[j-1]

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


def is_stable(before, after):
    """ソートが安定だったかどうかを判定する。

    ソート前と後のリスト in, out をとる。リスト中に全く同じカードはないと仮定している。
    """
    for i in range(len(before)):
        for j in range(i+1, len(before)):
            for a in range(len(after)):
                for b in range(a+1, len(after)):
                    if before[i][1] == before[j][1] and before[i] == after[b] and before[j] == after[a]:
                        return False

    return True



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

b_card_list = orig_card_list.copy()
s_card_list = orig_card_list.copy()

bubble_sort(b_card_list)
selection_sort(s_card_list)

print(*b_card_list)
if is_stable(orig_card_list, b_card_list):
    print('Stable')
else:
    print('Not stable')

print(*s_card_list)
if is_stable(orig_card_list, s_card_list):
    print('Stable')
else:
    print('Not stable')

Solution (Python):
n=int(input())

B=list(input().split())
C=B.copy()

def bubblesort(A,n):
    
    count=0
    flag=1
    while flag:
        flag=0
        for j in reversed(range(1,len(A))):
            if int(A[j][1])<int(A[j-1][1]):
                tmp=A[j-1]
                A[j-1]=A[j]
                A[j]=tmp
                flag=1
                count+=1
    return(A,count)

def selectsort(A,n):
    count=0
    for i in range(len(A)):
        minj=i
        
        for j in range(i,len(A)):
            if int(A[j][1])<int(A[minj][1]):
                minj=j
                
        if i!=minj:
            A[i],A[minj]=A[minj],A[i]
            count+=1
    
    return(A,count)


def isStable(result1, result2):
    if result1 == result2:
        return True
    return False


result1,count1=bubblesort(B,n)
print(" ".join([str(i) for i in result1]))
print("Stable")
result2,count2=selectsort(C,n)
print(" ".join([str(i) for i in result2]))
if isStable(result1, result2) == True:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
import copy

n = int(input())
c = input().split()
bubble = copy.copy(c)
select = copy.copy(c)

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

def SelectionSort(C, N):
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if int(C[j][1]) < int(C[minj][1]):
                minj = j
        temp = C[i]
        C[i] = C[minj]
        C[minj] = temp
    return C

BubbleSort(bubble, n)
SelectionSort(select, n)

print(*bubble)
print("Stable")
print(*select)

def isSame(C1, C2):
    for i in range(0, len(C1)):
        if C1[i] != C2[i]:
            return False
    return True

if isSame(bubble, select):
    print("Stable")
else:
    print("Not stable")

Solution (Python):
import copy

def show (a,n):
  for i in range(n):
    if i > 0:
      print("",end=" ")
    print(a[i],end="")
  print("")

def selectionSort(a,n):
  for i in range(n):
    minj = i
    for j in range(i,n):
      if a[j][1] < a[minj][1]:
        minj = j
    a[minj],a[i] = a[i],a[minj]
  show(a,n)

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

n = int(input())
a1 = list(input().split())
a2 = copy.copy(a1)

BubbleSort(a1,n)
print("Stable")
selectionSort(a2,n)

for k in range(n):
  if a1[k] != a2[k]:
    print("Not stable")
    exit()

print("Stable")

Solution (Python):
def main():
    N = int(input())
    A = input().split()
    B = A.copy()
    
    A = BubbleSort(A, N)
    print(*A)
    print('Stable')
    B = SelectionSort(B, N)
    print(*B)
    if A == B:
        print('Stable')
    else:
        print('Not stable')

def BubbleSort(A, N):
    count = 0
    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]
                count += 1
    return A

def SelectionSort(A, N):
    count = 0
    
    for i in range(N):
        mini = i
        for j in range(i,N):
            if A[j][1] < A[mini][1]:
                mini = j
        if A[i][1] > A[mini][1]:
            A[i], A[mini] = A[mini], A[i]
            count += 1
    return A

main()

Solution (Python):
class Card:
    __slots__ = ["mark", "value"]

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

    def __str__(self):
        return f"{self.mark}{self.value}"


def BubbleSort(lst):
    lst = lst.copy()
    for i in range(0, len(lst)):
        for j in range(len(lst) - 1, i, -1):
            if lst[j].value < lst[j -1].value:
                lst[j], lst[j - 1] = lst[j - 1], lst[j]
    return lst


def SelectionSort(lst):
    lst = lst.copy()
    for i in range(0, len(lst)):
        minj = i
        for j in range(i, len(lst)):
            if lst[j].value < lst[minj].value:
                minj = j
        lst[i], lst[minj] = lst[minj], lst[i]
    return lst

def check_stable(lst):
    for x in range(1, 10):
        if "".join(c.mark for c in lst if c.value == x) != "".join(c.mark for c in C if c.value == x):
            return False
    return True


input()
C = [Card(i) for i in input().split()]
B = BubbleSort(C)
S = SelectionSort(C)
print(" ".join(map(str, B)))
print("Stable" if check_stable(B) else "Not stable")
print(" ".join(map(str, S)))
print("Stable" if check_stable(S) else "Not stable")

Solution (Python):
import copy
def bubble(array):
    flag = set()
    for i in range(n):
        for j in range(1, n):
            if (array[j-1][1] > array[j][1]):
                tmp = array[j-1]
                array[j-1] = array[j]
                array[j] = tmp

    return array

def selection(array):
    flag = set()
    for i in range(0, n):
        minimum = i
        for j in range(i, n):
            if (array[j][1] < array[minimum][1]):
                minimum = j
        tmp = array[minimum]
        array[minimum] = array[i]
        array[i] = tmp

    return array

n = int(input())
array = input().split(" ")

for alg in [bubble, selection]:
    thirteen = [[] for _ in range(13)]
    for elmnt in array:
        thirteen[int(elmnt[1])-1].append(elmnt)
    sorted_ary = alg(copy.copy(array))

    sorted13 = [[] for _ in range(13)]
    for elmnt in sorted_ary:
        sorted13[int(elmnt[1])-1].append(elmnt)

    isStable = True
    print(" ".join(sorted_ary))
    for x, y in zip(thirteen, sorted13):
        if (x != y):
            isStable = False
    if isStable:
        print("Stable")
    else:
        print("Not stable")

Solution (Python):





def bubble_sort(list, length):
    flag = 1
    while(flag):
        flag = 0
        for j in reversed(range(1, length)):
            if list[j][1] < list[j-1][1]:
                list[j], list[j-1] = list[j-1], list[j]
                flag = 1

    return list


def selection_sort(list, length):
    for i in range(length):
        minpos = i
        for j in range(i, length):
            if list[minpos][1] > list[j][1]:
                minpos = j

        list[i], list[minpos] = list[minpos], list[i]

    return list



length = int(input())
cards_ = input().split()
cards = []
cards2 = []

for c in cards_:
    cards.append([c[0], int(c[1:])])
for c in cards_:
    cards2.append([c[0], int(c[1:])])

b_list = bubble_sort(cards, length)
s_list = selection_sort(cards2, length)

result = ''
for b in b_list:
    result += b[0]+str(b[1]) + ' '
print(result[:-1])
print('Stable')

result = ''
for s in s_list:
    result += s[0]+str(s[1]) + ' '
print(result[:-1])

flag = 0
for i in range(len(b_list)):
    if b_list[i] != s_list[i]:
        print('Not stable')
        flag = 1
        break
if flag == 0:
    print('Stable')

Solution (Python):
import copy

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


bub_c = copy.deepcopy(c)
for i in range(n):
    for j in range(n-1, i, -1):
        if bub_c[j][1] < bub_c[j-1][1]:
            bub_c[j], bub_c[j-1] = bub_c[j-1], bub_c[j]


sel_c = copy.deepcopy(c)
for i in range(n):
    minj = i
    for j in range(i, n):
        if sel_c[j][1] < sel_c[minj][1]:
            minj = j
    sel_c[i], sel_c[minj] = sel_c[minj], sel_c[i]

shaped_bub = " ".join([c[0] + str(c[1]) for c in bub_c])
shaped_sel = " ".join([c[0] + str(c[1]) for c in sel_c])
print(shaped_bub, "Stable", sep="\n")
if [b[0] for b in bub_c] == [b[0] for b in sel_c]:
    print(shaped_sel, "Stable", sep="\n")
else:
    print(shaped_sel, "Not stable", sep="\n")

Solution (Python):
import copy

class StableSort():
    def __init__(self):
        self.N = n
        self.C = copy.copy(c) 


    def BS(self):
        A = [self.C[i][1] for i in range(self.N)] 
        if self.N == 1:
            C = " ".join(self.C)
            return C
        else:
            for i in range(self.N): 
                for j in range(self.N - i - 1):
                    if A[self.N - j - 1] < A[self.N - j - 2]: 
                        A[self.N - j - 1], A[self.N - j - 2] = A[self.N - j - 2], A[self.N - j - 1] 
                        self.C[self.N - j - 1], self.C[self.N - j - 2] = self.C[self.N - j - 2], self.C[self.N - j - 1] 

            C = " ".join(self.C)
            return C


    def SS(self):
        A = [self.C[i][1] for i in range(self.N)] 
        if self.N == 1:
            print(self.C[0] + "\n" + "stable")
        else:
            for i in range(self.N - 1):
                A_r = A[i:] 
                mini = min(A_r)
                
                mini_index = i + A_r.index(mini) 
                if A[i] > mini:
                    A[i], A[mini_index] = A[mini_index], A[i] 
                    self.C[i], self.C[mini_index] = self.C[mini_index], self.C[i] 

            C = " ".join(self.C) 
            return C

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

BS = StableSort().BS()
SS = StableSort().SS()

print(str(BS) + "\n" + "Stable")
if BS != SS:
    print(str(SS) + "\n" + "Not stable")
else:
    print(str(SS) + "\n" + "Stable")