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())
A = [(s, int(a)) for s, a in input().split()]
B = [a for a in A]


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



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


print(*[s+str(a) for s, a in A])
print('Stable')
print(*[s+str(a) for s, a in B])
print('Stable' if A == B else 'Not stable')

Solution (Python):


import sys
import copy


class Card:
  def __init__(self, suit, value):
    self.suit = suit
    self.value = value


def isStable(C1, C2, N):
  for i in range(N):
    if (C1[i].suit != C2[i].suit):
      return False
  return True


def printCard(C):
  out = [(c.suit + c.value) for c in C]
  print(' '.join(out))


def validate_num_input(C, N):
  if len(C) != N:
    print("[ERROR] Number of Card caracter is invalid")
    sys.exit()


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:
        C[j], C[j - 1] = C[j - 1], C[j]
  return C


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
    C[i], C[minj] = C[minj], C[i]
  return C


def main():
  N = int(input())
  C = [x for x in input().split()]

  validate_num_input(C, N)

  C1 = [Card(c[0], c[1]) for c in C]
  C2 = copy.deepcopy(C1)

  C1 = bubbleSort(C1, N)
  printCard(C1)
  print("Stable")

  C2 = selectionSort(C2, N)
  printCard(C2)
  if (isStable(C1, C2, N)):
    print("Stable")
  else:
    print("Not stable")


if __name__ == '__main__':
  main()

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

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

def isStable(inp,outp,n):
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                for l in range(k+1,n):
                    if all((inp[i][1] == inp[j][1],inp[i] == outp[l],inp[j] == outp[k])): return False
    return True

if __name__ == "__main__":
    n = int(input())
    lst = [i for i in input().split()]
    a = lst[:]
    b = lst[:]
    bubbleSort(a,n)
    print(" ".join(a))
    print("Stable" if isStable(lst,a,n) else "Not stable")
    selectionsSort(b,n)
    print(" ".join(b))
    print("Stable" if isStable(lst,b,n) else "Not stable")

Solution (Python):
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):
    mj = i
    for j in range(i, n):
        if B[j][1] < B[mj][1]:
            mj = j
    B[i], B[mj] = B[mj], B[i]
print(*B)
if A == B:
    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
        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
def BubbleSort(n, A):
    cnt = 0
    flg = True
    while flg:
        flg = False
        for j in range(n-1, 0, -1):
            if int(A[j][1:2]) < int(A[j-1][1:2]):
                tmp = A[j]
                A[j] = A[j-1]
                A[j-1] = tmp
                cnt += 1
                flg = True
    
def SelectionSort(n, B):
    cnt = 0
    for i in range(n):
        minj = i
        for j in range(i+1, n):
            if int(B[j][1:2]) < int(B[minj][1:2]):
                minj = j
        if minj != i:
            tmp = B[i]
            B[i] = B[minj]
            B[minj] = tmp
            cnt += 1
    
def IsStable(A, B):
    for a1 in A:
        for b1 in B:
            if int(a1[1:2]) == int(b1[1:2]):
                if a1 == b1:
                    B.remove(b1)
                    break
                else:
                    return "Not stable"
            elif int(a1[1:2]) < int(b1[1:2]):
                break
    return "Stable"
    
n = int(input())
C = input().split()
A = copy.deepcopy(C)
B = copy.deepcopy(C)

BubbleSort(n, A)
print(" ".join(A))
print(IsStable(C, A))

SelectionSort(n, B)
print(" ".join(B))
print(IsStable(C, B))

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

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
        if A[i][-1:] != A[minj][-1:]:
            A[i],A[minj] = A[minj],A[i]
    return A
    
def isStable(st,list2):
    for i in range(1,len(st)):
        if list2[i][-1:] == list2[i-1][-1:]:
            if st[i] != list2[i]:
                return "Not stable"
    return "Stable"
    
num = int(input())
li1 = input().split()
stli = bubbleSort(li1[:],num)
li2 = bubbleSort(li1[:],num)
print(*li2,sep=" ")
print(isStable(stli,li2))
li3 = selectionSort(li1[:],num)
print(*li3,sep=" ")
print(isStable(stli[:],li3))

Solution (Python):
import copy

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

n = int(input())
c = [i for i in input().split()]
c1 = bubble_sort(n, copy.copy(c))
c2 = selection_sort(n, copy.copy(c))

print(*c1)
print('Stable')
print(*c2)
print('Stable' if c1 == c2 else 'Not stable')

Solution (Python):
import copy

def chk():
    for i in range(n-1):
        if L[i][1:2] == L[i+1][1:2]:
            stri = i
            a = strL.index(L[i])
            b = strL.index(L[i+1])
            if a > b:
                print("Not stable")
                return
    print("Stable")

n = int(input())
L = ['' for i in range(n)]

x = input()
for i in range(n):
    L[i] = x.split()[i]
strL = copy.copy(L)

for i in range(n-1):
    sta = n-1
    end = i
    j = sta
    while not j == end: 
        if L[j][1:2] < L[j-1][1:2]:
            tmp = L[j-1]
            L[j-1] = L[j]
            L[j] = tmp
        j -= 1
print(*L)
chk()

L = copy.copy(strL)
for i in range(n-1):
    min = i
    for j in range(i+1,n):
        if L[j][1:2] < L[min][1:2]:
            min = j
    if min == i:
        pass
    else:
        tmp = L[i]
        L[i] = L[min]
        L[min] = tmp

print(*L)
chk()

Solution (Python):
def BubbleSort(C,N):
  for _ in C:
    for i in range(len(C)-1, 0, -1):
      if C[i][-1:] < C[i-1][-1:]:
        C[i], C[i-1] = C[i-1], C[i]
  return C

def SelectionSort(C,N):
  for i in range(len(C)):
    min_pos = i
    for j in range(i+1, len(C)):
      if int(C[j][-1]) < int(C[min_pos][-1]):
        min_pos = j
    C[i], C[min_pos] = C[min_pos], C[i]
  return C

N = int(raw_input())
card = map(str, raw_input().split())

card0 = card
card1 = card[:]
card0 = BubbleSort(card0,N)
card1 = SelectionSort(card1,N)

print ' '.join(card0)
print "Stable"
print ' '.join(card1)
if card0 == card1:
  print "Stable"
else:
  print "Not stable"

Solution (Python):
n = int(input())
c = list(map(str, input().split()))
c_copy = list(c)

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

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

def is_stable(c1, c2):
    if c1 == c2:
        print("Stable")
    else:
        print("Not stable")

c1 = bubble_sort(c, n)
print(' '.join(c1))
print('Stable')
c2 = selection_sort(c_copy, n)
print(' '.join(c2))
is_stable(c1,c2)

Solution (Python):
class Card:
    def __init__(self, kind, number):
        self.kind = kind
        self.number = number

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

def selection_sort(C, N):
    for i in range(N):
        min_index = i
        for j in range(i, N):
            if C[j].number < C[min_index].number:
                min_index = j
        C[i], C[min_index] = C[min_index], C[i]
    return C

def check_stable(bubble_cards, selection_cards):
    res = 'Stable'
    for (b, s) in zip(bubble_cards, selection_cards):
        if b.kind != s.kind or b.number != s.number:
            res = 'Not stable'
    return res

n = int(input())
bubble_cards = []
for card in input().split():
    kind, number = list(card)
    bubble_cards.append(Card(kind, number))
selection_cards = bubble_cards[:]

bubble_cards = bubble_sort(bubble_cards, n)
ans = []
for c in bubble_cards:
    ans.append(''.join(c.kind + str(c.number)))
print(' '.join(ans))
print('Stable')

selection_cards = selection_sort(selection_cards, n)
ans = []
for c in selection_cards:
    ans.append(''.join(c.kind + str(c.number)))
print(' '.join(ans))
print(check_stable(bubble_cards, selection_cards))

Solution (Python):
n = int(input())
a = list(input().split())
b = list(a)


flag = True
while flag:
  flag = False
  for i in range(1,n)[::-1]:
    if a[i-1][1] > a[i][1]:
      a[i-1],a[i]=a[i],a[i-1]
      flag = True
print(" ".join(a))
def stable(b,a):
  for i in range(n):
    for j in range(i+1,n):
      if b[i][1] == b[j][1]:
        for k in range(n):
          for l in range(k+1,n):
            if a[k] == b[j] and a[l] == b[i]:
              print("Not stable")
              return
  print("Stable")
stable(b,a)
a = list(b)

for i in range(n):
    min_i = i
    for j in range(i+1,n):
        if a[j][1] < a[min_i][1]:
            min_i = j
    if i!= min_i:
        a[i],a[min_i]=a[min_i],a[i]
print(" ".join(map(str,a)))
stable(b,a)

Solution (Python):
def BubbleSort(C, N):
	for i in range(N):
		for j in reversed(range(i+1, N)):
			if C[j][1] < C[j-1][1]:
				C[j], C[j-1] = C[j-1],C[j]
	return C

def SelectionSort(C, N):
    for i in range(N):
        minj = i
        for j in range(i,N):
            if C[j][1] < C[minj][1]:
                minj = j
        C[i],C[minj] = C[minj],C[i]
    return C
        
N = int(input())
C = input().split()
bubble = BubbleSort(C[:], N)
select = SelectionSort(C[:], N)
print(*bubble)
print("Stable")
print(*select)
print(["Not stable", "Stable"][bubble==select])

Solution (Python):
import copy
class Card:
    def __init__(self, str):
        self.mark = str[0]
        self.number = int(str[1:])
        
    def __str__(self):
        return self.mark + str(self.number)
        
n = int(input())
card_list = [Card(c) for c in input().split()]

def bubble_sort(a):
    a = copy.copy(a)
    n = len(a)
    for i in range(n):
            for j in range(0, n-i-1):
                if a[j].number > a[j+1].number:
                    a[j], a[j+1] = a[j+1], a[j]
    return a
    
sorted_card_list1 = bubble_sort(card_list)
print(*sorted_card_list1)
print("Stable")

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

    
sorted_card_list2 = selection_sort(card_list)
print(*sorted_card_list2)
if sorted_card_list1 == sorted_card_list2:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
N = int(input())
A = list(map(lambda x: (x[0],int(x[1])),input().split()))

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

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

B = BubbleSort(A,N)
S = SelectionSort(A,N)

print(*list(map(lambda x:''.join(map(str,x)),B)))
print('Stable')
print(*list(map(lambda x:''.join(map(str,x)),S)))
print('Stable' if B==S else 'Not stable')

Solution (Python):
import copy

n = int(input())
cards = input().split()

def bubble_sort(cards, n):
    c = copy.copy(cards)
    for i in range(n):
        for j in range(n - 1, i, -1):
            if int(c[j][1]) < int(c[j-1][1]):
                tmp = c[j]
                c[j] = c[j-1]
                c[j-1] = tmp
    return c
    
bubble = bubble_sort(cards, n)


print(' '.join(bubble))

def is_stable(o, s):
    for i in range(n - 1):
        if int(s[i][1]) == int(s[i+1][1]):
            if o.index(s[i]) > o.index(s[i+1]):
                return False
    return  True

if is_stable(cards, bubble):
    print('Stable')
else:
    print('Not stable')


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

selection = selection_sort(cards, n)
print(' '.join(selection))

if is_stable(cards, selection):
    print('Stable')
else:
    print('Not stable')

Solution (Python):
import copy

def BubbleSort(C, N):
    stable = True

    for i in range(N):
        for j in range(i + 1, N)[::-1]:
            if C[j][2] < C[j - 1][2]:
                C[j], C[j - 1] = C[j - 1], C[j]

    
    AnswerPrint(C, IsStable(C))


def SelectionSort(C, N):
    stable = True

    for i in range(N):
        minj = i
        for j in range(i, N):
            if C[j][2] < C[minj][2]:
                minj = j

        C[i], C[minj] = C[minj], C[i]

    AnswerPrint(C, IsStable(C))


def IsStable(C):
    for index, c in enumerate(C):
        for i in range(index, len(C)):
            if (c[2] == C[i][2]) and (c[0] > C[i][0]):
                return False

    return True
                

def AnswerPrint(C, stable):
    out = ["{}{}".format(c[1], c[2]) for c in C]
    print(" ".join(out))

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



N = int(input())
inp = input().split()
C = [[index, c[0], int(c[1])] for index, c in enumerate(inp)]

BubbleSort(copy.copy(C), N)
SelectionSort(copy.copy(C), N)

Solution (Python):
n=int(input())
c=list(map(str, input().split()))

def bubble(c:list, n:int) -> str:
    if not isinstance(c, list):
        return None

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

    return " ".join(c)

def selection(c:list, n:int) -> str:
    if not isinstance(c, list):
        return None

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

    return " ".join(c)
d = c[:]
bub=bubble(c, n)
print(bub)
print("Stable")
sel=selection(d, n)
print(sel)
if sel == bub:
    print("Stable")
else :
    print("Not stable")

Solution (Python):
import sys
import math
import copy
from typing import Tuple, List
input = sys.stdin.readline

class Card:
    def __init__(self, idx):
        self.number = int(idx[1])
        self.design = idx[0]
    def __repr__(self):
        return "{}{}".format (self.design, self.number)


def  print_vec (A: list):
    print (" ".join(map (str, A)))

def swap (A: List, i: int, j: int) -> None:
    temp = A [i]
    A [i] = A [j]
    A [j] = temp



def bubble_sort (C: List [Card]) -> List [Card]:
    for i in range (len (C)):
        for j in range (len (C) - 1, i, -1):
            if C [j].number < C [j-  1].number:
                swap (C, j, j-1)
    return C

def selection_sort (C: List [Card]) -> List [Card]:
    for i in range (len (C)):
        minj = i
        for j in range (i, len (C)):
            if C [j].number < C [minj].number:
                minj = j
        if i != minj:
            swap (C, i, minj)
    return C

if __name__ == "__main__":
    n = int(input())
    vec =  list (map (lambda x: Card (x), input ().split ()))
    bubble_result = bubble_sort (copy.copy (vec))
    print_vec(bubble_result)
    print ("Stable")
    selection_result = selection_sort(copy.copy (vec))
    print_vec (selection_result)
    flag=  True
    for i in range (len (bubble_result)):
        if bubble_result [i] != selection_result [i]:
            flag = False
    if flag:
        print ("Stable")
    else:
        print ("Not stable")

Solution (Python):
N = int(input())
A = list(input().split(" "))

class Card:
    def __init__(self,suit,num):
        self.suit = suit
        self.value = int(num)
        self.id = suit+num
        
    

B_bubble = [Card(a[0],a[1])for a in A]
B_selection = [b for b in B_bubble]

B_id = [b.id for b in B_bubble]

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:
                tmp = C[j]
                C[j] = C[j-1]
                C[j-1] = tmp
        
    return C
    
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
      tmp = C[i]
      C[i] = C[minj]
      C[minj] = tmp
      
    return C

def stable_check(B_id,C_id):
    tmp = C_id[0]
    for i in range(1,len(C_id)):
        c = C_id[i]
        if c[1]!=tmp[1]:
            tmp = c
            continue
        if B_id.index(tmp)>B_id.index(c):
            return "Not stable" 
        tmp = c
    return "Stable"
    

C_bubble =  [b.id for b in BubbleSort(B_bubble,N)]
print(" ".join(C_bubble))

print(stable_check(B_id,C_bubble))

C_selection =  [b.id for b in SelectionSort(B_selection,N)]
print(" ".join(C_selection))

print(stable_check(B_id,C_selection))

Solution (Python):
def bubble_sort(N ,num1, suit1): 
   
   
   for i in range(N): 
      for j in range(N-1, i, -1): 
         if num1[j] < num1[j-1]: 
            num1[j], num1[j-1] = num1[j-1], num1[j]
            suit1[j], suit1[j-1] = suit1[j-1], suit1[j]
   return join_trump(N, num1, suit1)

def selection_sort(N, num2, suit2): 
   for i in range(N):
      minj = i 
      for j in range(i+1, N): 
         if num2[j] < num2[minj]: 
            minj = j 
      if num2[minj] < num2[i]: 
         num2[i], num2[minj] = num2[minj], num2[i] 
         suit2[i], suit2[minj] = suit2[minj], suit2[i]
   return join_trump(N, num2, suit2)

def join_trump(N, num3, suit3):
   trump = [''] * N
   for i in range(N):
      trump[i] = suit3[i] + str(num3[i])
   return trump


def is_stable(x, y, N): 
   for i in range(N):
      if x[i]!=y[i]:
         print('Not stable')
         return 0
   print('Stable')

N = int(input()) 

trump = input().split() 
suit1 = [''] * N 
num1 = [0] * N   
for i in range(N):           
   suit1[i] = trump[i][0]     
   num1[i] = int(trump[i][1]) 
suit2, num2 = suit1[:], num1[:]





bubble_ans = bubble_sort(N, num1, suit1)
print(*bubble_ans)
print('Stable')


selec_ans = selection_sort(N, num2, suit2)
print(*selec_ans)
is_stable(bubble_ans, selec_ans, N)

Solution (Python):
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
        if i != minj:
            A[i], A[minj] = A[minj], A[i]

    return A


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]

    return A


if __name__ == '__main__':
    n = int(input())
    R = list(map(str, input().split()))
    C = R[:]
    BR = bubbleSort(R, n)
    SR = selectionSort(C, n)

    fStable = SR == BR

    print(*BR)
    print("Stable")
    print(*SR)
    if (fStable == True):
        print("Stable")
    else:
        print("Not stable")

Solution (Python):
import copy

def bubbleSort(A, N):
    count = 0
    for i in range(1, N):
        for j in reversed(range(i, N)):
            if A[j][1] < A[j-1][1]:
                A[j], A[j-1] = A[j-1], A[j]
                count += 1

def selectionSort(A, N):
    count = 0
    for i in range(N):
        min = i
        for j in range(i, N):
            if A[j][1] < A[min][1]:
                min = j
        if min != i:
            A[i], A[min] = A[min], A[i]
            count += 1

def prArr(A, N):
    for i in range(N):
        if i != 0:
            print(" ", end = "")
        print(A[i], end = "")
    print()

N = int(input())
A = [i for i in input().split()]
B = copy.deepcopy(A)

bubbleSort(A, N)
selectionSort(B, N)

prArr(A, N)
print("Stable")
prArr(B, N)
print("Stable" if A == B else "Not stable")

Solution (Python):
N = int(input()) 
C = list(input().split())
C1 = C[:]
C2 = C[:]

def func(C):
    nums = []
    for i in range(N-1):
        for j in range(i+1,N):
            if C[i][1] in nums:
                continue
            elif C[i][1] == C[j][1]:
                nums.append(C[i][1])
    nums.sort()

    test = []
    for i in range(len(nums)):
        A = []
        for j in range(N):
            if C[j][1] == nums[i]:
                A.append(C[j])
        test.append(A)
    return test

def isStable(A,B):
    if func(A) == func(B):
        print("Stable")
    else:
        print("Not stable")

for i in range(N):
    for j in range(N-1,i,-1):
        if int(C1[j][1]) < int(C1[j-1][1]):
            C1[j],C1[j-1] = C1[j-1],C1[j]
print(*C1)
isStable(C,C1)

for i in range(N):
    minj = i
    for j in range(i,N):
        if int(C2[j][1]) < int(C2[minj][1]):
            minj = j
    C2[i],C2[minj] = C2[minj],C2[i]
print(*C2)
isStable(C,C2)

Solution (Python):
import copy

class card:
    def __init__(self, s):
        self.value = int(s[1:])
        self.mark = s[0]
        self.s = s
    
    def __repr__(self):
        return self.s
        
def isstable(Cin, Cout, 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 Cin[i].value==Cin[j].value and Cout[a].s==Cin[j].s and Cout[b].s == Cin[i].s:
                        return False
    return True
    
def BubbleSort(C, N):
    Cin = copy.copy(C)
    for i in range(N):
        for j in range(N-1, i, -1):
            if C[j].value < C[j-1].value:
                C[j], C[j-1] = C[j-1], C[j]
    print(*C)

    if isstable(Cin, C, N):
        print('Stable')
    else:
        print('Not stable')

def SelectionSort(C,N):
    Cin = copy.copy(C)
    for i in range(N):
        minj = i
        for j in range(i, N):
            if C[j].value < C[minj].value:
                minj = j
        if minj!=i:
            C[i], C[minj] = C[minj], C[i]

    print(*C)
    if isstable(Cin, C, N):
        print('Stable')
    else:
        print('Not stable')

N = int(input())
C = list(map(card, input().split()))



BubbleSort(copy.copy(C), N)
SelectionSort(copy.copy(C), N)

Solution (Python):
import copy
N = int(input())
A = [[i for i in item] for item in input().split()]

B = copy.deepcopy(A)

def bubbleSort(A, N):
    for i in range(N):
        for i in reversed(range(i, N-1)):
            if A[i][1] > A[i+1][1]:
                A[i], A[i+1] = A[i+1], A[i]

    res = []
    for item in A:
        temp_res = ''
        for i in item:
            temp_res += i
        res.append(temp_res)
    return res



def selectionSort(A, N):
    cnt = 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:
            A[i], A[minj] = A[minj], A[i]
    
    res = []
    for item in A:
        temp_res = ''
        for i in item:
            temp_res += i
        res.append(temp_res)
    return res

A_res = bubbleSort(A, N)
B_res = selectionSort(B, N)

print(*A_res)
print('Stable')
print(*B_res)
if A_res == B_res:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
n = int(input())
l = input().split(" ")
L = l[:]
for k in range(n - 1):
    for j in range(n - 1, 0, -1):
        if L[j][1:] < L[j - 1][1:]:
            L[j], L[j - 1] = L[j - 1], L[j]
    m = l[k:].index(min(l[k:], key=lambda x: x[1]))
    if m != 0:
        l[k], l[m + k] = l[m + k], l[k]
print(*L)
print("Stable")
print(*l)
print(['Not s', 'S'][l == L] + 'table')

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]
        

def selection_sort(a, n):
    for i in range(n):
        min = i
        for j in range(i, n):
            if a[j][1] < a[min][1]:
                min = j
        if min != i:
            a[min], a[i] = a[i], a[min]
            

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

B_A = O_A[:]
S_A = O_A[:]

bubble_sort(B_A, N)
selection_sort(S_A, N)
print(*B_A)
print('Stable')
print(*S_A)
for i in range(N):
    if B_A[i] != S_A[i]:
        print('Not stable')
        break
else:
    print('Stable')

Solution (Python):
def bubble_sort(A, N):
    A = list(A)
    for i in range(1, N):
        for j in range(0, N-i):
            if A[j][1] > A[j+1][1]:
                A[j], A[j+1] = A[j+1], A[j]
    tmp = []
    for x, y in A:
        tmp.append(x+str(y))
    return tmp


def selection_sort(A, N):
    A = list(A)
    for i in range(0, N-1):
        pivot = i
        for j in range(i+1, N):
            if A[pivot][1] > A[j][1]:
                pivot = j
        if pivot != i:
            A[pivot], A[i] = A[i], A[pivot]
    tmp = []
    for x, y in A:
        tmp.append(x+str(y))
    return tmp


N = int(input())
X = list(map(str, input().split()))
A = []
for x in X:
    A.append((x[0], int(x[1])))
A = tuple(A)
a = bubble_sort(A, N)
print(*a)
print('Stable')
b = selection_sort(A, N)
print(*b)
if a == b:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
from copy import copy
from collections import defaultdict


def bubblesort(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 selectionsort(C, N):
    for i in range(N):
        minj = i
        for j in range(i+1, N):
            if int(C[j][-1]) < int(C[minj][-1]):
                minj = j
        C[i], C[minj] = C[minj], C[i]
    return C
  

def soot_order(C):
    ret = defaultdict(list)
    for c in C:
        soot = c[0]
        number = c[1]
        ret[number].append(soot)
    return ret


def judge_stable(C, N, order):
    
    cursor = 0
    stable = True
    while cursor < N:
        number = C[cursor][1]
        soots = order[number]
        for soot in soots:
            if C[cursor][0] != soot:
                print("Not stable")
                stable = False
                cursor += N
                break
            else:
                cursor += 1
    if stable:
        print("Stable")
        

def main():
    N = int(input())
    C = [c for c in input().split()]    
    
    order = soot_order(C)
    
    _C = copy(C)
    C_order = bubblesort(_C, N)
    print(' '.join(C_order))
    
    judge_stable(C_order, N, order)
    
    C_order = selectionsort(C, N)
    print(' '.join(C_order))
    
    judge_stable(C_order, N, order)
    
    
if __name__=="__main__":
    main()

Solution (Python):
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]
    print(' '.join(a))

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
        if minj != i:
            a[i],a[minj] = a[minj],a[i]
    a = [str(s) for s in a]
    print(' '.join(a))

def isStable(a, a2):
    """
    :param a: Stable-sorted list (Bubble sort)
    :param a2: List to check if isStable
    :return: Boolean
    """
    if a == a2:
        return True
    else:
        return False

n = int(input())
a = list(input().split())
a2 = a[::]

bubbleSort(a,n)
print('Stable')
selectionSort(a2,n)
print('Stable' if isStable(a, a2) else 'Not stable')