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


def bubble_sort(arr):
    no_swap = True
    
    for i in range(len(arr), 0, -1):
        if not no_swap:
            break
        for j in range(0, i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                
            no_swap = True
    

def selection_sort(arr):
    
    for i in range(0, len(arr)):
        min_index = i
        for j in range(i + 1, len(arr)):
            if arr[min_index] > arr[j]:
                min_index = j
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]
            
    


def is_stable(raw, sort_):
    N = len(raw)
    for i in range(N):
        for j in range(i + 1, N):
            for m in range(N):
                for n in range(m + 1, N):
                    if (raw[i].value == raw[j].value) and (raw[i] == sort_[n]) and (raw[j] == sort_[m]):
                        return 'Not stable'
    return 'Stable'

class Card:
    suit = ''
    value = 0

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

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

    def __eq__(self, rhv):
        return self.suit == rhv.suit and self.value == rhv.value

    def __ne__(self, rhv):
        return not (self == rhv)

    def __str__(self):
        return '%s%d'%(self.suit, self.value)

if __name__ == '__main__':
    N = int(input())
    raw = list(map(Card, input().split()))
    arr1 = []
    arr2 = []
    for i in raw:
        arr1.append(i)
        arr2.append(i)
    bubble_sort(arr1)
    result = is_stable(raw, arr1)
    print(' '.join(map(str, arr1)))
    
    print(result)
    selection_sort(arr2)
    print(' '.join(map(str, arr2)))
    result = is_stable(raw, arr2)
    print(result)

Solution (Python):
from sys import stdin
N = int(stdin.readline().rstrip())
cards = [list(c) for c in stdin.readline().rstrip().split()]
c_cards = cards.copy()

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 select_sort(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[i], a[minj] = a[minj], a[i]
    return a

bubbled = [''.join(c) for c in bubble_sort(cards, N)]
selected = [''.join(c) for c in select_sort(c_cards, N)]
print(*bubbled)
print('Stable')
print(*selected)
if selected == bubbled:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
class Card:
    def __init__(self, s):
        self.color = s[0]
        self.val = int(s[1])

    def __str__(self):
        return "%s%d" % (self.color, self.val)


if __name__ == '__main__':
    n = int(raw_input())
    A = map(Card, raw_input().split())
    B = A[:]

    
    for i in range(0, n):
        for j in range(n - 1, i, -1):
            if A[j].val < A[j - 1].val:
                A[j], A[j - 1] = A[j - 1], A[j]

    
    for i in range(0, n):
        minj = i
        for j in range(i, n):
            if B[j].val < B[minj].val:
                minj = j
        if minj != i:
            B[minj], B[i] = B[i], B[minj]

    for c in A:
        print c,
    print
    print "Stable"
    for c in B:
        print c,
    print
    flag = True
    for i in range(n):
        if A[i] != B[i]:
            flag = False
            break
    print "Stable" if flag else "Not stable"

Solution (Python):



def bubble_sort(A):
    for i in range(len(A)):
        flag = 1
        while flag:
            flag = 0
            for j in range(len(A)-1, i, -1):
                if A[j][1] < A[j-1][1]:
                    A[j], A[j-1] = A[j-1], A[j]
                    flag = 1
    return A

def sentaku_sort(A):
    for i in range(len(A)):
        min_n = i
        for j in range(i+1, len(A)):
            if A[j][1] < A[min_n][1]:
                min_n = j
        if min_n != i:
            A[i], A[min_n] = A[min_n], A[i]
    return A

def isStable(A, B):
    for i in range(len(A)):
        for j in range(i+1, len(A)):
            for a in range(len(A)):
                for b in range(a+1, len(A)):
                    if A[i][1] == A[j][1] and A[i] == B[b] and A[j] == B[a]:
                        return False
    return True
    

def hyoji(A):
    for i in range(len(A)):
        if i != len(A)-1:
            print(A[i], end = ' ')
        else:
            print(A[i])


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

B = bubble_sort(A[:])
hyoji(B)
if isStable(A, B):print('Stable')
else:print('Not stable')

C = sentaku_sort(A[:])
hyoji(C)
if isStable(A, C):print('Stable')
else:print('Not stable')

Solution (Python):
"""


 = sys.stdin.readline().rstrip()
 = list(sys.stdin.readline().rstrip())


 = int(sys.stdin.readline())
 = map(int, sys.stdin.readline().split())
 = list(map(int, sys.stdin.readline().split()))
 = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  


a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654


char_list = list("abcd") 
"""

import math
import sys
import itertools
import queue
from fractions import gcd


mod = 1000000007

if __name__ == "__main__":
    n = int(sys.stdin.readline())
    l = list(sys.stdin.readline().split())

    
    b = l[:]
    s = l[:]

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

    def SelectionSort(l,n):
        for i in range(n):
            minj=i
            for j in range(i,n):
                if l[j][1] < l[minj][1]:
                    minj = j
            if i!=minj:
                temp=l[minj]
                l[minj]=l[i]
                l[i]=temp

    BubbleSort(b,n)
    print(*b)
    print('Stable')
    SelectionSort(s,n)
    print(*s)
    
    print("Stable" if b==s else "Not stable")

Solution (Python):
def bubble(n,c):
    for i in range(n):
        ch=True
        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]
                ch=False
        if ch:
            break
    return c

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


n=int(input())
c=list(input().split())
c2=c[:]
ba=bubble(n,c2)
print(*ba)
print("Stable")
sa=selection(n,c)
print(*sa)
print("Stable" if sa==ba else "Not stable")

Solution (Python):
import copy
def p(a):
    for i in a[:-1]:
        print(i,end=' ')
    print(a[-1])


def selection_sort(a):
    cnt = 0
    for i in range(len(a)-1):
        fl = 0
        min = i
        for j in range(i+1,len(a)):
            if a[j][1]<a[min][1]:
                fl=1
                min = j
        cnt+=fl
        tmp = a[min]
        a[min] = a[i]
        a[i] = tmp


def bubble_sort(a):
    for i in range(len(a)-1):
        for j in range(i+1,len(a))[::-1]:
            if a[j-1][1]>a[j][1]:
                tmp = a[j]
                a[j] = a[j-1]
                a[j-1] = tmp


n = int(input())
l = list(input().split())
a = copy.copy(l)
bubble_sort(l)
selection_sort(a)
p(l)
print('Stable')
p(a)
if a==l:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
def bubble(A):
    flag = 1
    n = len(A)
    cnt = 0
    while flag:
        flag = 0
        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 = 1
        cnt += 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):
def BubbleSortChar(c,n):
    num = [int(s[1]) for s in c]
    for i in range(n):
        
        for j in range(n-1,i,-1):
            
            if num[j-1] > num[j]:
                
                tmp = num[j-1]
                num[j-1] = num[j]
                num[j] = tmp
                
                tmp = c[j-1]
                c[j-1] = c[j]
                c[j] = tmp
    return " ".join(c)

def SelectionSortChar(c,n):
    num = [int(s[1]) for s in c]
    for i in range(n):
        
        minj = i
        for j in range(i,n):
            if num[j] < num[minj]:
                minj = j
        
        tmp = c[minj]
        c[minj] = c[i]
        c[i] = tmp
        
        tmp = num[minj]
        num[minj] = num[i]
        num[i] = tmp

    return " ".join(c)






N = int(input())
S1 = input().split(" ")
S2 = [s for s in S1]

C1 = BubbleSortChar(S1,N)
print(C1)
print("Stable")


C2 = SelectionSortChar(S2,N)
print(C2)
if C1==C2:
    print("Stable")
else:
    print("Not stable")

Solution (Python):



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

N = int(input())
C = input().split()
C1 = C.copy()
C2 = C.copy()

BSC = BubbleSort(C1)
print(" ".join(BSC))
print("Stable")
SSC = SelectionSort(C2)
print(" ".join(SSC))
if BSC == SSC:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
import copy

array_to_str = lambda A: ' '.join([str(a) for a in A])
input_number = lambda: int(input())
input_num_array = lambda: [int(a) for a in input().split()]
input_array = lambda: input().split()

def bubble_sort(C, A, N):
  flag = 1
  while flag:
    flag = 0
    for j in range(N)[:0:-1]:
      if A[j] < A[j-1]:
        A[j],A[j-1] = A[j-1], A[j]
        C[j],C[j-1] = C[j-1], C[j]
        flag = 1
  print(' '.join(C))
  print('Stable')

def selection_sort(C, A, N):
  stability = True
  for i in range(N):
    minj = i
    for j in range(i,N):
      if A[j] < A[minj]:
        minj = j

    
    

    C[i], C[minj] = C[minj], C[i]
    A[i], A[minj] = A[minj], A[i]
        
  print(' '.join(C))
  

N = input_number()
C = input_array()
A = [int(c[1]) for c in C]
A_copy = copy.copy(A)
C_copy = copy.copy(C)
bubble_sort(C_copy, A_copy, N)
selection_sort(C, A, N)
print('Stable' if C == C_copy else 'Not stable')

Solution (Python):
def bubble_sort(arr):
    n = len(arr)
    flag = True
    i = 0
    while flag:
        flag = False
        for j in range(n - 1, 0, -1):
            if int(arr[j][1]) < int(arr[j - 1][1]):
                arr[j], arr[j - 1] = arr[j - 1], arr[j]
                flag = True
        i += 1
    return arr


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


def is_stable(arr, arr_sorted):
    print("Stable" if arr_sorted == sorted(arr, key=lambda x:int(x[1])) else "Not stable")


n = int(input())
arr = input().split()
arr_b = bubble_sort(arr[:])
arr_s = selection_sort(arr[:])

print(*arr_b)
is_stable(arr, arr_b)
print(*arr_s)
is_stable(arr, arr_s)

Solution (Python):
n=int(input())
bubble=input().split()
select=bubble[:]
for i in range(n):
    for j in range(n-1,i,-1):
        if int(bubble[j][1])<int(bubble[j-1][1]):
            bubble[j],bubble[j-1]=bubble[j-1],bubble[j]

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

for i in range(n-1):
    print(bubble[i],end=" ")
print(bubble[n-1])
print("Stable")
for i in range(n-1):
    print(select[i],end=" ")
print(select[n-1])
if bubble==select:
    print("Stable")
else:
    print("Not stable")

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


def selection_sort(a_list):
    n = len(a_list)
    for i in range(0, n):
        mini = i
        for j in range(i, n):
            if a_list[j][1] < a_list[mini][1]:
                mini = j
        if i != mini:
            a_list[i], a_list[mini] = a_list[mini], a_list[i]
    return a_list


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

bubble_sorted = bubble_sort(a_list[:])
print(' '.join(map(str, bubble_sorted)))
print('Stable')
selection_sorted = selection_sort(a_list[:])
print(' '.join(map(str, selection_sorted)))
if bubble_sorted == selection_sorted:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
import sys

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

        A[i], A[minj] = A[minj], A[i]
    return A

def bubble_sort(n, A):

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

def is_stable(in_data, out_data):
    len_data = len(in_data)

    for i in range(len_data):
        for j in range(i+1, len_data):
            for a in range(len_data):
                for b in range(a+1, len_data):
                    if in_data[i][1] == in_data[j][1] and\
                       in_data[i] == out_data[b] and\
                       in_data[j] == out_data[a]:
                        return False

    return True

n = int(sys.stdin.readline().strip())
card = sys.stdin.readline().strip().split(' ')

raw = card[:]
bs = bubble_sort(n, raw)
raw = card[:]
ss = selection_sort(n, raw)

print(' '.join(bs))

if is_stable(card, bs):
    print('Stable')
else:
    print('Not stable')

print(' '.join(ss))

if is_stable(card, ss):
    print('Stable')
else:
    print('Not stable')

Solution (Python):
n=int(input())
da=list(map(str,input().split()))
me=[i for i in range(n)]
def mark(kop):
    return int(kop[1])

da1=da[:]
for i in range(n):
    for j in range(n-1,i,-1):
        x=mark(da1[j])
        y=mark(da1[j-1])
        if x<y:
            da1[j],da1[j-1]=da1[j-1],da1[j]

da2=da[:]
for i in range(n):
    mian=i
    for j in range(i,n):
        x=mark(da2[j])
        y=mark(da2[mian])
        if x<y:
            mian=j
    da2[i],da2[mian]=da2[mian],da2[i]
    me[i],me[mian]=me[mian],me[i]
ans=True
for i  in range(1,n):
    if mark(da2[i])==mark(da2[i-1]) and me[i]<me[i-1]:
        ans=False
        break

for i in range(n):
    if i==n-1:
        print(da1[i])
    else:
        print(da1[i],end=' ')
print('Stable')
for i in range(n):
    if i ==n-1:
        print(da2[i])
    else:
        print(da2[i],end=' ')
if ans:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
N=int(input())
L=input().split( )



B=L[:]
S=L[:]
for i in range(N):
    j=N-1
    while j>i:
        if B[j][1]<B[j-1][1]:
            temp =B[j]
            B[j]=B[j-1]
            B[j-1]=temp

        j-=1

for i in range(N):
    minj= i
    j=i
    while j<N:
        if S[j][1]<S[minj][1]:
            minj=j
            j+=1
            
        else:j+=1






    temp =S[i]
    S[i]=S[minj]
    S[minj]=temp
    

for i in range(N):
    if i!=N-1:
        print(f"{B[i]}",end=" ")
    else:
        print(f"{B[i]}")
print("Stable")

for i in range(N):
    if i!=N-1:
        print(f"{S[i]}",end=" ")
    else:
        print(f"{S[i]}")
flag=1
for i in range(N):
    if B[i]!=S[i]:
        flag=0
if flag==1:
    print("Stable")
if flag==0:
    print("Not stable")

Solution (Python):
import copy
n = int(input())
a = list(map(str, input().split()))
a_buble = copy.copy(a)
for i in range(n):
  for j in range(n-1,i,-1):
    if int(a_buble[j][1]) < int(a_buble[j-1][1]):
      temp = a_buble[j]
      a_buble[j] =a_buble[j-1]
      a_buble[j-1] = temp
      
print(" ".join(map(str,a_buble)))
print("Stable")

for i in range(0,n):
  minj = i
  for j in range(i,n):
    if int(a[j][1]) < int(a[minj][1]):
      minj = j
  temp = a[i]
  a[i] = a[minj]
  a[minj] = temp
print(" ".join(map(str,a)))
ans = "Stable"
for k in range(n):
  if a[k] != a_buble[k]:
    ans = "Not stable"
print(ans)

Solution (Python):
def bubble_sort(A, n):
    A = A[:]
    flag = True
    while flag:
        flag = False
        for i in range(n - 1, 0, -1):
            if int(A[i][1:]) < int(A[i - 1][1:]):
                A[i], A[i - 1] = A[i - 1], A[i]
                flag = True
    return A


def selection_sort(A, n):
    A = A[:]
    for start in range(n):
        smallest_i = start
        smallest = A[smallest_i]
        for i in range(start, n):
            if int(A[i][1:]) < int(smallest[1:]):
                smallest_i = i
                smallest = A[smallest_i]
        A[start], A[smallest_i] = A[smallest_i], A[start]
    return A


def is_stable(ordered, original):
    for n in range(1, 10):
        f_original = filter(lambda c: int(c[1:]) == n, original)
        f_ordered = filter(lambda c: int(c[1:]) == n, ordered)
        for a, b in zip(f_ordered, f_original):
            if a != b:
                return False
    return True


n = int(input())
A = input().split()
bA = bubble_sort(A, n)
sA = selection_sort(A, n)
print(*bA, sep=" ")
print("Stable" if is_stable(bA, A) else "Not stable")
print(*sA, sep=" ")
print("Stable" if is_stable(sA, A) else "Not stable")

Solution (Python):
import copy
n=int(input())
a=list(input().split())
def BubbleSort(l,n):
    a=copy.deepcopy(l)
    for i in range(n):
        for j in reversed(range(i+1,n)):
            if int(a[j][1])<int(a[j-1][1]):
                a[j],a[j-1]=a[j-1],a[j]
    return a

def SelectionSort(l,n):
    a=copy.deepcopy(l)
    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]
    return a

def SP(l):
    for i in range(len(l)):
        if i !=len(l)-1:
            print(l[i],end=' ')
        else:
            print(l[i]) 

BS=BubbleSort(a,n)
SS=SelectionSort(a,n)
SP(BS)
print('Stable')
SP(SS)
if BS==SS:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
def bubbleSort(A,N):
    flag = 1
    count = 0
    while flag:
        flag = 0
        for j in range(N-1,0,-1):
            Aj = int(A[j][1])
            Aj_1 = int(A[j-1][1])
            if Aj < Aj_1:
                A[j],A[j-1] = A[j-1],A[j]
                flag = 1
                count += 1
    return A[:]

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

N = int(input())



table = [x for x in input().split(' ')]
t = table[:]
u = table[:]


A=bubbleSort(t,N)
print('{0}'.format(' '.join(map(str,A))))
print('Stable')
B=selectionSort(u,N)
print('{0}'.format(' '.join(map(str,B))))
if A == B:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
def bubbleSort(x):
    A = x[:]
    flag_stable = True
    
    for i in range(1, len(A)):
        for j in range(1, len(A) - i + 1):
            if  A[j - 1][1] > A[j][1]:
                A[j], A[j - 1] = A[j - 1], A[j]

                if not flag_stable:
                    continue

                if A[j - 1][1:] == A[j][1:]:
                    flag_stable = False

    return A, flag_stable

def selectionSort(x):
    A = x[:]
    flag_stable = True

    for i in range(len(A)):
        minj = i

        for j in range(i + 1, len(A)):

            if A[j][1] < A[minj][1]:
                minj = j

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

            if not flag_stable:
                continue

            for k in range(i, minj):
                if A[k][1] == A[minj][1]:
                    flag_stable = False

    return A, flag_stable




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

card_bubbleSort, flag_stable_bubbleSort = bubbleSort(card)
card_selectionSort, flag_stable_selectionSort = selectionSort(card)


print(*card_bubbleSort)

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

print(*card_selectionSort)

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

Solution (Python):
from copy import deepcopy

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

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

def isStable(x, bubble):
    if x == bubble: return "Stable"
    else: return "Not stable"

if __name__ ==  "__main__":
    N = int(input())
    a = list(map(str, input().split()))
    bubble, selection = deepcopy(a), deepcopy(a)
    bubble = BubbleSort(bubble, N)
    selection = SelectionSort(selection, N)
    print(*bubble)
    print(isStable(bubble, bubble))
    print(*selection)
    print(isStable(selection, bubble))

Solution (Python):
N = int(input())
A = list(input().split())
number = [int(a[1]) for a in A]
mark = [a[0] for a in A]

def bubbleSort(C_number, C_mark, N):
    for i in range(N):
        for j in reversed(range(i+1, N)):
            if C_number[j] < C_number[j-1]:
                
                temp = C_number[j]
                C_number[j] = C_number[j-1]
                C_number[j-1] = temp
                
                temp = C_mark[j]
                C_mark[j] = C_mark[j-1]
                C_mark[j-1] = temp
    return C_number, C_mark

def selectionSort(num, mark, N):
    for i in range(N):
        min_val = min(num[i:])
        min_index = num[i:].index(min_val) + i
        if num[i] != min_val:
            
            temp = num[i]
            num[i] = min_val
            num[min_index] = temp
            
            temp = mark[i]
            mark[i] = mark[min_index]
            mark[min_index] = temp

    return num, mark

b_num, b_mark = bubbleSort(number.copy(), mark.copy(), N)
s_num, s_mark = selectionSort(number, mark, N)

b = [b_mark[i]+str(b_num[i]) for i in range(N)]
s = [s_mark[i]+str(s_num[i]) for i in range(N)]

print(*b)
print("Stable")
print(*s)
is_same = [b[i]==s[i] for i in range(N)]
if all(is_same):
    print("Stable")
else:
    print("Not stable")

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


card_bubble = card_input.copy()
for i in range(n):
    for j in range(n-1,i,-1):
        if int(card_bubble[j][1])<int(card_bubble[j-1][1]):
            card_bubble[j], card_bubble[j-1] = card_bubble[j-1], card_bubble[j]


card_select = card_input.copy()
for i in range(n):
    mini = i
    for j in range(i,n):
        if  int(card_select[j][1])<int(card_select[mini][1]):
            mini = j
    card_select[mini], card_select[i] = card_select[i], card_select[mini]


    
def output(card):
    string = ''
    for i in card[:-1]:
        string += i + ' '
    string += card[-1]
    print(string)
    
output(card_bubble)
print('Stable')
output(card_select)
if card_bubble==card_select:print('Stable')
else:print('Not stable')

Solution (Python):
import copy

N = int(input())
C = list(list(input().split()))
Cb, Cs = copy.copy(C), copy.copy(C)


def BubbleSort(C, N):
    for i in range(N):
        for j in range(N-1, i, -1):
            if C[j-1][1] > C[j][1]:
                C[j-1], C[j] = C[j], C[j-1]
    for i in range(N):
        C[i] = "".join(C[i])
    print(" ".join(map(str, C)))


def SelectionSort(C, N):
    for i in range(N):
        minj = i
        for j in range(i,N):
            if C[minj][1] > C[j][1]:
                minj = j
        C[i], C[minj] = C[minj], C[i]
    for i in range(N):
        C[i] = "".join(C[i])
    print(" ".join(map(str, C)))

def StableCheck(Cin, Cout, N):
    for i in range(1,10):
        check1, check2 = [], []
        for j1 in Cin:
            if str(i) in j1:
                check1.append(j1)
        for j2 in Cout:
            if str(i) in j2:
                check2.append(j2)
        if check1 != check2:
            print("Not stable")
            exit()
    print("Stable")

BubbleSort(Cb, N)
StableCheck(C, Cb, N)
SelectionSort(Cs, N)
StableCheck(C, Cs, N)

Solution (Python):

n = int(input())
a_master = input()


a = [[i[0],i[1]] for i in a_master.split()]
for ni in range(n):
   for ii in range(n-1, ni, -1):
      if int(a[ii][1]) < int(a[ii-1][1]):
        a[ii], a[ii-1] = a[ii-1], a[ii]
b_ans = " ".join(["".join(i) for i in a])
print(b_ans)
print("Stable")

a = [[i[0],i[1]] for i in a_master.split()]
for ni in range(n):
  mini = ni
  for ii in range(ni,n):
    if int(a[ii][1]) < int(a[mini][1]):
      mini = ii
  a[ni], a[mini] = a[mini], a[ni]
s_ans = " ".join(["".join(i) for i in a])
print(s_ans)
if b_ans == s_ans:
  print("Stable")
else:
  print("Not stable")

Solution (Python):
import re
import copy

N = int(input())
list = list(input().split())
pattern = '[DHSC]'

def bubble_sort(N, cards):
  flag = 1
  while flag == 1:
    flag = 0
    for i in range(N - 1, 0, -1):
      if int(re.sub(pattern, '', cards[i])) < int(re.sub(pattern, '', cards[ i - 1])):
        cards[i], cards[i - 1] = cards[i - 1], cards[i]
        flag = 1
  print(' '.join(cards))
  print('Stable')
  return cards

def selection_sort(N, cards):
  for i in range(N):
    minj = i
    for j in range(i, N):
      
      if int(re.sub(pattern, '', cards[j])) < int(re.sub(pattern, '', cards[minj])):
        minj = j

    cards[i], cards[minj] = cards[minj], cards[i]

  print(' '.join(cards))
  return cards

bubblelist = bubble_sort(N, copy.deepcopy(list))
selectionlist = selection_sort(N, copy.deepcopy(list))

print('Not stable') if bubblelist != selectionlist else print('Stable')

Solution (Python):
num = int(input())
card_list = [x for x in input().split()]
origin = card_list[:]
card_list2 = origin[:]
cards = {x : int(x[1]) for x in card_list}

for i in range(num):
    for j in range(num-1, i, -1):
        if cards[card_list[j]] < cards[card_list[j-1]]:
            card_list[j], card_list[j-1] = card_list[j-1], card_list[j]
print(' '.join(card_list))
print('Stable')

for i in range(num):
    minj = i
    for j in range(i, num):
        if cards[card_list2[j]] < cards[card_list2[minj]]:
            minj = j
    card_list2[i], card_list2[minj] = card_list2[minj], card_list2[i]
print(' '.join(card_list2))

if card_list == card_list2:
    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):
import copy

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


def selection_sort(data_selec):
    for i in range(len(data_selec)):
        minj = i
        for j in range(i, len(data_selec)):
            if data_selec[j][1] < data_selec[minj][1]:
                minj = j
        data_selec[i], data_selec[minj] = data_selec[minj], data_selec[i]
    return data_selec


def set_list(data):
    base_list = [[], [], [], [], [], [], [], [], []]
    for elem in data:
        base_list[int(elem[1]) - 1].append(elem)
    return base_list


def is_stable(base, compare):
    base_list = set_list(base)
    compare_list = set_list(compare)
    for i, num in enumerate(base_list):
        for j, key in enumerate(num):
            if key != compare_list[i][j]:
                return 'Not stable'
    return 'Stable'


_ = int(input())
data = list(input().split())
bubble_list = copy.copy(data)
bubble_list = bubble_sort(bubble_list)
print(*bubble_list)
print(is_stable(data, bubble_list))
selection_list = copy.copy(data)
selection_list = selection_sort(selection_list)
print(*selection_list)
print(is_stable(data, selection_list))

Solution (Python):
N = int(input())
C1 = input().split()
C2 = [i for i in C1]


def cVal(s):
    return int(s[1])


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


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


def isStable(C1, C2):
    for i1, i2 in zip(C1, C2):
        if i1 != i2:
            return False
    return True

BubbleSort(C1, N)
print(' '.join(C1))
print('Stable')

SelectionSort(C2, N)
print(' '.join(C2))
ans = 'Stable' if isStable(C1, C2) else 'Not stable'
print(ans)