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):
import copy 

n = int(input())
c = input().split()
c_sel = copy.deepcopy(c)


ord_dict_def = {}
for i in range(n) :
    if int(c[i][1]) in ord_dict_def.keys() :
        ord_dict_def[int(c[i][1])] += c[i][0]
    else :
        ord_dict_def[int(c[i][1])] = c[i][0]
        

for i in range(n) :
    for j in range(n - 1, i, -1) :
        if int(c[j - 1][1]) > int(c[j][1]) :
            c[j - 1], c[j] = c[j], c[j - 1]


ord_dict_bubble = {}

for i in range(n) :
    if int(c[i][1]) in ord_dict_bubble.keys() :
        ord_dict_bubble[int(c[i][1])] += c[i][0]
    else :
        ord_dict_bubble[int(c[i][1])] = c[i][0]
        

for i in range(n) :
    cmin = i
    for j in range(i + 1, n) :
        if int(c_sel[j][1]) < int(c_sel[cmin][1]) :
            cmin = j
            
    if i != cmin :
        c_sel[i], c_sel[cmin] = c_sel[cmin], c_sel[i]


ord_dict_selection = {}

for i in range(n) :
    if int(c_sel[i][1]) in ord_dict_selection.keys() :
        ord_dict_selection[int(c_sel[i][1])] += c_sel[i][0]
    else :
        ord_dict_selection[int(c_sel[i][1])] = c_sel[i][0]
        
stability_bubble = "Stable"
stability_selection = "Stable"

for i in ord_dict_bubble.keys() :
    if ord_dict_def[i] != ord_dict_bubble[i] :
        stability_bubble = "Not stable"
        
    if ord_dict_def[i] != ord_dict_selection[i] :
        stability_selection = "Not stable"
        
print(" ".join(c))
print(stability_bubble)
print(" ".join(c_sel))
print(stability_selection)

Solution (Python):

A = []
B = []


LENGTH =int(input())
A = input().split()
B = 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 A == B:
        print("Stable")
    else:
        print("Not stable")

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

Solution (Python):
import copy

def print_list(A):
    print(*A, sep=" ")

def swap(a, b):
    return b, a

def val(str):
    return int(str[1])

def is_stable(_in, _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 val(_in[i]) == val(_in[j]) and _in[i] == _out[b] and _in[j] == _out[a]:
                        return False
    return True

def print_stable(_in, _out, n):
    if is_stable(_in, _out, n):
        print("Stable")
    else:
        print("Not stable")    

def find_minj(A, i, n):
    minj = i
    for j in range(i, n):
        if val(A[j]) < val(A[minj]):
            minj = j
    return minj        

def bubble_sort(A, n):
    A0 = copy.copy(A)
    flg = 1 
    i = 0
    while flg:
        flg = 0
        for j in range(n-1, i, -1):
            if val(A[j-1]) > val(A[j]):
                A[j-1], A[j] = swap(A[j-1], A[j])
                flg = 1
        i += 1
    print_list(A)
    print_stable(A0, A, n)

def selection_sort(A, n):
    A0 = copy.copy(A)
    for i in range(0, n):
        minj = find_minj(A, i, n)
        if val(A[i]) > val(A[minj]):
            A[i], A[minj] = swap(A[i], A[minj])
    print_list(A)
    print_stable(A0, A, n)

n = int(input())
A = list(map(str,input().split()))
B = copy.copy(A)

bubble_sort(A, n)
selection_sort(B, n)

Solution (Python):
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)

def judge(original, sorted_list):
    if original == sorted_list:
        print('Stable')
    else:
        print('Not stable')


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

bubble = BubbleSort(l2)
judge(l2_sort, bubble)

select = SelectSort(l2)
judge(l2_sort, select)

Solution (Python):
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 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)

def judge(original, sorted_list):
    if original == sorted_list:
        print('Stable')
    else:
        print('Not stable')


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

bubble = BubbleSort(l2)
judge(l2_sort, bubble)

select = SelectSort(l2)
judge(l2_sort, select)

Solution (Python):
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 __repr__(self):
        return '{}{}'.format(self.mark, self.number)


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)

def judge(original, sorted_list):
    if original == sorted_list:
        print('Stable')
    else:
        print('Not stable')


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

bubble = BubbleSort(l2)
judge(l2_sort, bubble)

select = SelectSort(l2)
judge(l2_sort, select)

Solution (Python):


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])
        
        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):
    
    for i in range(length):
        minj = i
        for j in range(i, length):
            if value(cards[j]) < value(cards[minj]):
                minj = j
        
            
        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(' '.join(b))
print(stable(c, b))
print(' '.join(s))
print(stable(c, s))

Solution (Python):



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):
            if f(c[j - 1]) > f(c[j]):
                swap(c, j - 1, j)
            
    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)
        
    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]))
    
    
    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))

Solution (Python):
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')

Solution (Python):
_, 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))

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

Solution (Python):
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")

Solution (Python):
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].num<lst[j-1].num:
                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+1,size):
            if lst[mn].num>lst[j].num:
                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


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"

Solution (Python):
def bubble_sort(A, N):
    cnt = 0
    flag = True
    while flag:
        flag = False
        for j in range(N - 1, 0, -1):
            if int(A[j - 1][1]) > int(A[j][1]):
                A[j - 1], A[j] = A[j], A[j - 1]
                flag = True
                cnt += 1
    return A

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

N = int(input())
A = input().split()
order_A = [[] for _ in range(10)]
for s in A:
    order_A[int(s[1])].append(s)

order_bubble = [[] for _ in range(10)]
b_sorted = bubble_sort(A[:], N)
for s in b_sorted:
    order_bubble[int(s[1])].append(s)
print(*b_sorted)
print('Stable' if order_A == order_bubble else 'Not stable')

s_stability = [[] for _ in range(10)]
s_sorted = selection_sort(A[:], N)
for s in s_sorted:
    s_stability[int(s[1])].append(s)
print(*s_sorted)
print('Stable' if order_A == s_stability else 'Not stable')

Solution (Python):
def bubble_sort(card_list):
    cards = [i for i in card_list]
    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(card_list):
    cards = [i for i in card_list]

    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 = bubble_sort(cards)
selection_cards = selection_sort(cards)

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

Solution (Python):
import copy
n=int(input())
num=input().split()
numa=copy.copy(num)
numb=copy.copy(num)


for i in range(0,n):
	a=0
	for j in range(n-1,i,-1):
		if numa[j][1:]<numa[j-1][1:]:
			a=numa[j]
			numa[j]=numa[j-1]
			numa[j-1]=a
print(' '.join(list(map(str,numa))))
print('Stable')


for i in range(0,n):
	minj=i
	b=0
	for j in range(i,n):
		if numb[j][1:]<numb[minj][1:]:
			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')

Solution (Python):
n = int(input())
a = [i for i in input().split()]
a2 = a.copy()
for i in range(n):
    for j in reversed(range(i+1, n)):
        if a[j][1] < a[j-1][1]:
            a[j], a[j-1] = a[j-1], a[j]
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")

Solution (Python):
def bubble_sort(array):
    n = len(array)

    while True:
        flag = False
        for i in range(1, n)[::-1]:
            if array[i-1][1] > array[i][1]:
                tmp = array[i]
                array[i] = array[i-1]
                array[i-1] = tmp
                flag = True
        if not flag:
            break
    return array

def selection_sort(array):
    n = len(array)

    for i in range(n):
        min_idx = i
        for j in range(i, n):
            if array[j][1] < array[min_idx][1]:
                min_idx = j
        if min_idx != i:
            tmp = array[i]
            array[i] = array[min_idx]
            array[min_idx] = tmp
    return array

def accum_hcsd_order(array):
    hcsd_order = {}
    for item in array:
        if item[1] in hcsd_order:
            hcsd_order[item[1]].append(item[0])
        else:
            hcsd_order[item[1]] = [item[0]]
    return hcsd_order


def check_stable(array, hcsd_order):
    tgt_hcsd_order = accum_hcsd_order(array)

    for no, hcsd in hcsd_order.items():
        if len(hcsd) == 1:
            continue
        tgt_hcsd = tgt_hcsd_order[no]
        for src, tgt in zip(hcsd, tgt_hcsd):
            if src != tgt:
                return False
    return True


def main():
    n = int(input())
    array = [(x[0], int(x[1:])) for x in input().split()]
    str_stable_or_not = {True: "Stable", False: "Not stable"}

    hcsd_order = accum_hcsd_order(array)

    
    array_b = array[:]
    array_b = bubble_sort(array_b)
    print(" ".join(map(lambda x: "{}{}".format(x[0],x[1]), array_b)))
    print(str_stable_or_not[check_stable(array_b, hcsd_order)])

    
    array_s = array[:]
    array_s = selection_sort(array_s)
    print(" ".join(map(lambda x: "{}{}".format(x[0], x[1]), array_s)))
    print(str_stable_or_not[check_stable(array_s, hcsd_order)])

    return

main()

Solution (Python):
n = int(input())
A = input().rstrip().split()
B = list(map(lambda x:int(x[1]), A))
C = list(enumerate(B))
D = list(enumerate(B))

Cb = C
nums = [n - i for i in range(1, n)]
flag = 1

while flag == 1:
    flag = 0
    for j in nums:
        if Cb[j][1] < Cb[j - 1][1]:
            Cb[j], Cb[j - 1] = Cb[j - 1], Cb[j]
            flag = 1
        else:
            pass
Ab = [A[Cb[i][0]] for i in range(n)]
print(*Ab)
bstable = 1
for j in range(n - 1):
    if Cb[j + 1][1] == Cb[j][1] and Cb[j + 1][0] < Cb[j][0]:
        bstable = 0
        break
if bstable == 1:
    print("Stable")
else:
    print("Not stable")

Cs = D
for i in range(n):
    minj = i
    for j in range(i, n):
        if Cs[j][1] < Cs[minj][1]:
            minj = j
        else:
            pass
    Cs[i], Cs[minj] = Cs[minj], Cs[i]
    
As = [A[Cs[i][0]] for i in range(n)]
print(*As)
cstable = 1
for j in range(n - 1):
    if Cs[j + 1][1] == Cs[j][1] and Cs[j + 1][0] < Cs[j][0]:
        cstable = 0
        break
if cstable == 1:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
def bubble(A):
    
    flag =True;
    n=len(A)
    i=0
    while flag:
        flag=False
        for j in range(n-1,i,-1):
           if A[j][1]<A[j-1][1]:
               A[j],A[j-1]=A[j-1],A[j]
               flag=True
        i+=1
 
 

def selection(A):
    n=len(A)
    for i in range(n):
        minj=i
        for j in range(i,n):
            if A[j][1]<A[minj][1]:
                minj=j
        if i!=minj:
            A[i],A[minj]=A[minj],A[i]
             
   
           
n=int(input())
ss=[x for x in input().split()]     
ss2=ss.copy()
 
 
bubble(ss)
for i in range(len(ss)-1):
    print(ss[i],end=' ')
print(ss[-1])
print('Stable')
    
 
selection(ss2)
for i in range(len(ss2)-1):
    print(ss2[i],end=' ')
print(ss2[-1])
if ss==ss2:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
import copy
n = int(input())
A = list(map(str,input().split()))
B = copy.copy(A)

def BubbleSort(A,n):
    for i in range(n):
        for j in range(n-1,i,-1):
            if int(A[j][1:2])<int(A[j-1][1:2]):
                v = A[j]
                A[j] = A[j-1]
                A[j-1] = v
    return A

def SelectionSort(A,n):
    for i in range(n):
        minj = i
        for j in range(i,n):
            if int(A[j][1:2])<int(A[minj][1:2]):
                minj = j
        v = A[i]
        A[i] = A[minj]
        A[minj] = v
    return A

print(' '.join(BubbleSort(A,n)))
print('Stable')
print(' '.join(SelectionSort(B,n)))
if BubbleSort(A,n) == SelectionSort(B,n):
    print('Stable')
else:
    print('Not stable')

Solution (Python):
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] == output[b] and Input[j] == output[a]:
						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')

Solution (Python):
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))

Solution (Python):
from typing import List


def get_value(card: str) -> int:
    return card[1]


def bublle_sort(C: List[str]) -> None:
    for i in range(len(C)):
        for j in reversed(range(i + 1, len(C))):
            if get_value(C[j]) < get_value(C[j - 1]):
                C[j], C[j - 1] = C[j - 1], C[j]


def selection_sort(C: List[str]) -> None:
    for i in range(len(C)):
        min_j = i
        for j in range(i, len(C)):
            if get_value(C[j]) < get_value(C[min_j]):
                min_j = j
        C[i], C[min_j] = C[min_j], C[i]


def is_stable(A_in, A_out) -> bool:
    for i in range(len(A_in)):
        for j in range(i + 1, len(A_in)):
            for a in range(len(A_out)):
                for b in range(a + 1, len(A_out)):
                    if get_value(A_in[i]) == get_value(A_in[j]) and A_in[i] == A_out[b] and A_in[j] == A_out[a]:
                        return False
    return True


N = int(input())
C = [str(i) for i in input().split()]
C1 = [i for i in C]
C2 = [i for i in C]

bublle_sort(C1)
print(' '.join(C1))
if is_stable(C, C1):
    print('Stable')
else:
    print('Not stable')

selection_sort(C2)
print(' '.join(C2))
if is_stable(C, C2):
    print('Stable')
else:
    print('Not stable')

Solution (Python):
def bubble_sort(C, N):
    card = []
    for c in C:
        card.append({'suit': c[0], 'value': int(c[1])})
            
    for i in range(N):
        for j in range(N-1, i, -1):
            if card[j]['value'] < card[j-1]['value']:
                card[j], card[j-1] = card[j-1], card[j]

    new_C = []
    for i in range(N):
        new_C.append(card[i]['suit'] + str(card[i]['value']))
        
    return new_C


def selection_sort(C, N):
    card = []
    for c in C:
        card.append({'suit': c[0], 'value': int(c[1])})

    for i in range(N):
        min_j = i
        for j in range(i, N):
            if card[j]['value'] < card[min_j]['value']:
                min_j = j
        card[i], card[min_j] = card[min_j], card[i]
        
    new_C = []
    for i in range(N):
        new_C.append(card[i]['suit'] + str(card[i]['value']))
        
    return new_C


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

C_b = bubble_sort(C, N)
C_s = selection_sort(C, N)

print(' '.join(C_b))
print('Stable')

print(' '.join(C_s))
if C_s == C_b:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
def bubble_sort(c, n):
    c = c.copy()
    for i in range(n):
        for j in range(0, n - 1):
            if c[j][1] > c[j + 1][1]:
                c[j], c[j + 1] = c[j + 1], c[j]
    return c


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


def print_list(a):
    print(" ".join([s + v for s, v in a]))


def is_stable(l1, l2):
    def get_original_index(v):
        for i, e in enumerate(l1):
            if v == e:
                return i
        return Exception("bug")

    before = l2[0]
    for e in l2[1:]:
        if before[1] == e[1]:
            
            bi = get_original_index(before)
            ei = get_original_index(e)
            
            if bi > ei:
                return False
        before = e

    return True


n = int(input())
tmp = input().split()
a = []
for v in tmp:
    a.append((v[0], v[1]))

bs_result = bubble_sort(a, n)
ss_result = selection_sort(a, n)

print_list(bs_result)
if is_stable(a, bs_result):
    print("Stable")
else:
    print("Not stable")

print_list(ss_result)
if is_stable(a, ss_result):
    print("Stable")
else:
    print("Not stable")

Solution (Python):
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
        
        c[i], c[minj] = c[minj], c[i]
    return c


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

    
    bubble_result = bubble_sort(cards, N)
    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()