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 = list(map(str, input().split()))
b = a.copy()


def bubble_sort():
    for i in range(n):
        for j in reversed(range(i+1, n)):
            num = int(a[j][1])
            num_ = int(a[j-1][1])
            if num < num_:
                a[j], a[j-1] = a[j-1], a[j]
    return a


def selection_sort():
    for i in range(n):
        minv = int(b[i][1])
        mink = i
        for j in range(i, n):
            if int(b[j][1]) < minv:
                minv = int(b[j][1])
                mink = j
        if int(b[i][1]) != minv:
            b[i], b[mink] = b[mink], b[i]
    return b


bubble = bubble_sort()
selection = selection_sort()


def check_stable():
    if selection == bubble:
        return 'Stable'
    else:
        return 'Not stable'


check_selection = check_stable()


print(*bubble)
print('Stable')
print(*selection)
print(check_selection)

Solution (Python):
import copy

def Bubble_Sort(n,cards):

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

def Selection_Sort(n,cards):

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

def Print_cards(n,cards):

	for i in range(n-1):
		print(f"{cards[i][0]}{cards[i][1]} ",end='')
	print(f"{cards[n-1][0]}{cards[n-1][1]}")


def isStable(n,original,sorted):

	for i in range(n):
		for j in range(i+1,n):
			for a in range(n):
				for b in range(a+1,n):
					if int(original[i][1]) == int(original[j][1]) and original[i] == sorted[b] and original[j] == sorted[a]:
						return False

	return True

def test():

	n = int(input())
	cards_original = input().split()
	cards_for_Bubble = copy.deepcopy(cards_original)
	cards_for_Selection = copy.deepcopy(cards_original)

	Bubble_Sort(n,cards_for_Bubble)
	Print_cards(n,cards_for_Bubble)
	if isStable(n,cards_original,cards_for_Bubble) == True:
		print("Stable")
	else:
		print("Not stable")

	Selection_Sort(n,cards_for_Selection)
	Print_cards(n,cards_for_Selection)
	if isStable(n,cards_original,cards_for_Selection) == True:
		print("Stable")
	else:
		print("Not stable")

if __name__ == "__main__":
	test()

Solution (Python):

N = int(input())
*A, = input().split()

def stableSort(N,A):
    cnum1 = [(a[0], int(a[1:])) for a in A]
    
    
    flag = 1
    i = 0
    while i < N-1:
        for j in range(N-1, i, -1):
            if cnum1[j][1] < cnum1[j-1][1]:
                tmp = cnum1[j]
                cnum1[j] = cnum1[j-1]
                cnum1[j-1] = tmp
        i += 1
    print(' '.join([''.join([cn[0], str(cn[1])]) for cn in cnum1]))
    print('Stable')
    
    
    cnum2 = [(a[0], int(a[1:])) for a in A]
    count = 0
    for i in range(N):
        minj = i
        for j in range(i+1, N):
            if cnum2[j][1] < cnum2[minj][1]:
                minj = j
        if not minj == i:
            tmp = cnum2[i]
            cnum2[i] = cnum2[minj]
            cnum2[minj] = tmp
            count += 1
    print(' '.join([''.join([cn[0], str(cn[1])]) for cn in cnum2]))
    print('Not stable' if cnum1 != cnum2 else 'Stable' )

stableSort(N,A)

Solution (Python):
def bubble(A,n):
	A = A.copy()
	for i in range(n):
		for j in range(n-1,i,-1):
			if A[j][1]<A[j-1][1]:
				A[j],A[j-1]=A[j-1],A[j]
	return A

def selection(A,n):	
	A=A.copy()
	for i in range(n-1):
		minj = i
		for j in range(i+1,n):
			if A[j][1]<A[minj][1]:
				minj=j
		A[i],A[minj]=A[minj],A[i]
	return A


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

C1,C2=bubble(A,n),selection(A,n)

print(' '.join(C1))
print('Stable')
print(' '.join(C2))
flag = 1
for i in range(n):
	if C1[i]!=C2[i]:
		flag=0
if flag:
	print('Stable')
else:
	print('Not stable')

Solution (Python):
import copy



cards_origin = []



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


def SelectionSort(count, cards):
    for i in range(count):
        minj = i
        for j in range(i, count):
            if cards[j][1] < cards[minj][1]:
                minj = j
        cards[i], cards[minj] = cards[minj], cards[i]
        

def SuitOrder(cards, numbers):
    for i in range(len(cards)):
        numbers[cards[i][1]].append(cards[i][0])


def IsStable(numbers1, numbers2):
    for i in range(len(numbers1)):
        if numbers1[i] != numbers2[i]:
            return "Not stable"

    return "Stable"



if __name__ == "__main__":

    
    in_count = int(input())
    in_cards = input().split(" ")

    
    for i in range(in_count):
        cards_origin.append([in_cards[i][0], int(in_cards[i][1])])

    
    cards_bubble = copy.deepcopy(cards_origin)
    cards_selection = copy.deepcopy(cards_origin)

    
    BubbleSort(in_count, cards_bubble)
    SelectionSort(in_count, cards_selection)

    
    
    order_origin = []
    order_bubble = []
    order_selection = []
    for i in range(10):
        order_origin.append([])
        order_bubble.append([])
        order_selection.append([])

    
    SuitOrder(cards_origin, order_origin)
    SuitOrder(cards_bubble, order_bubble)
    SuitOrder(cards_selection, order_selection)
    

    bubble_is_stable = IsStable(order_origin, order_bubble)
    selection_is_stable = IsStable(order_origin, order_selection)

    
    for i in range(len(cards_bubble)):
        print("%s%d" % (cards_bubble[i][0], cards_bubble[i][1]), end="")
        if i != len(cards_bubble)-1:
            print(" ", end="")
    print()
    print(bubble_is_stable)


    for i in range(len(cards_selection)):
        print("%s%d" % (cards_selection[i][0], cards_selection[i][1]), end="")
        if i != len(cards_selection)-1:
            print(" ", end="")
    print()
    print(selection_is_stable)

Solution (Python):
N = int(input())
C = [x for x in input().split()]

def BubbleSort(C):
    N = len(C)
    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 = len(C)
    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

D1 = C[:]


D1 = BubbleSort(D1)
for i in range(N-1):
    print(D1[i], end=" ")
print(D1[N-1])
print("Stable")

D2 = C[:]
D2 = SelectionSort(D2)
for i in range(N-1):
    print(D2[i], end=" ")
print(D2[N-1])
if D1 ==D2:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
import copy
def convert(list):
    res=" ".join(map(str, list))
    return res

n=int(input())
a=list(map(str,input().split()))

b=a[:]
s=copy.deepcopy(a)

for i in range(n-1):
    for j in reversed(range(i+1,n)):
        if b[j][1]<b[j-1][1]:
            bj=b[j]
            b[j]=b[j-1]
            b[j-1]=bj
bub=convert(b)
print(bub)
print("Stable")

for k in range(n):
    minl=k
    for l in range(k,n):
        if s[minl][1]>s[l][1]:
            minl=l

    if minl!=k:
        sk=s[k]
        s[k]=s[minl]
        s[minl]=sk

se=convert(s)
print(se)
if s==b:
    print("Stable")
else:
    print("Not stable")

Solution (Python):


def printout(array, n):
    output = ""
    for i in range(n - 1):
        output += str(array[i]) + " "
    output += str(array[N - 1])
    print(output)


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


def linearsearch(subarray):
    
    min = int(subarray[0][1])
    min_index = 0;
    for i in range(1,len(subarray)):
        if min > int(subarray[i][1]):
            min = int(subarray[i][1])
            min_index = i
    return min_index


def selection_sort(array):
    index,tmp = 0,0
    for i in range(N):
        index = linearsearch(array[i:]) + i

        if index != i:
            
            tmp = array[index]
            array[index] = array[i]
            array[i] = tmp
    return array


N = int(input())
array = [i for i in input().split()]
array1 = bubble_sort(array[:])
array2 = selection_sort(array[:])
original_array = array[:]

printout(array1,N)
print("Stable")
printout(array2,N)
if array1 == array2:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
def getInput():
    n = int(input())
    a = [i for i in input().split(" ")]
    return n, a

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

def swap(x, y):
    v = x
    x = y
    y = v
    return x, y

def bubbleSort(n, a):
    cnt = 0
    for j in range(n):
        init = True
        for i in range(n-1, -1, -1):
            if init:
                init = False
                continue
            if getNum(a[i]) > getNum(a[i+1]):
                a[i], a[i+1] = swap(a[i], a[i+1])
                cnt += 1
    print(" ".join([str(i) for i in a]))
    return a

def selectionSort(n, a):
    cnt = 0
    for i in range(n):
        id_min = i
        for j in range(i+1, n):
            if getNum(a[j]) < getNum(a[id_min]):
                id_min = j
        if id_min != i:
            a[i], a[id_min] = swap(a[i], a[id_min])
            cnt += 1
    print(" ".join([str(i) for i in a]))
    return a

def checkStability(n, a_sample, a):
    for i in range(n-1):
        flag1 = False
        flag2 = False
        if getNum(a_sample[i]) == getNum(a_sample[i+1]):
            for j in range(n):
                if a[j] == a_sample[i+1]:
                    flag1 = True
                if a[j] == a_sample[i]:
                    flag2 = True
                if (flag1==True)&(flag2==False):
                    print("Not stable")
                    return
    print("Stable")
    return


from copy import deepcopy
N, A = getInput()
a_bs = bubbleSort(deepcopy(N), deepcopy(A))
checkStability(deepcopy(N), deepcopy(a_bs), deepcopy(A))
a_ss = selectionSort(deepcopy(N), deepcopy(A))
checkStability(deepcopy(N), deepcopy(a_ss), deepcopy(A))

Solution (Python):
import copy

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

def bubbleSort(C, N):
    for i in reversed(range(N)):
        for j in range(i):
            if C[j].value > C[j+1].value:
                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 C[j].value < C[minj].value:
                minj = j
        C[i], C[minj] = C[minj], C[i]

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

def main():
    N = int(input())
    list = input().split(" ")
    
    cards1 = []
    for i in range(N):
        card = Card()
        card.suit = list[i][0]
        card.value = int(list[i][1:])
        cards1.append(card)
    cards2 = copy.deepcopy(cards1)

    bubbleSort(cards1, N)
    selectionSort(cards2, N)

    for c in cards1:
        if c == cards1[len(cards1)-1]:
            print(c.suit + str(c.value))
            print("Stable")
        else:
            print(c.suit + str(c.value), end=" ")

    for c in cards2:
        if c == cards2[len(cards2)-1]:
            print(c.suit + str(c.value))
            if isSame(cards1,cards2,N):
                print("Stable")
            else:
                print("Not stable")
        else:
            print(c.suit + str(c.value), end=" ")

if __name__ == "__main__":
    main()

Solution (Python):
num_inputs = int(input())
l_origin = input().split(' ')

flag = True
l_bubble = l_origin[:]
while flag:
    flag = False
    for i in reversed(range(1, num_inputs)):
        if int(l_bubble[i][-1:]) < int(l_bubble[i - 1][-1:]):
            buf = l_bubble[i]
            l_bubble[i] = l_bubble[i - 1]
            l_bubble[i - 1] = buf
            flag = True
print(' '.join(l_bubble))
print('Stable')

l_selection = l_origin[:]
for j in range(num_inputs):
    mink = j
    for k in range(j, num_inputs):
        if int(l_selection[k][-1:]) < int(l_selection[mink][-1:]):
            mink = k
    if mink != j:
        buf = l_selection[j]
        l_selection[j] = l_selection[mink]
        l_selection[mink] = buf
print(' '.join(l_selection))

is_stable = True

for l in range(num_inputs):
    if l_bubble[l] == l_selection[l]:
        pass
    else:
        is_stable = False
        break

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

Solution (Python):
import sys
  
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, N):
            if C[j][1] < C[minj][1]:
                minj = j
  
        C[i], C[minj] = C[minj], C[i]
      
    return C
fin = sys.stdin
  
N = int(fin.readline())
A = fin.readline().split()
B = A[:]
  
A = bubble_sort(A, N)
B = selection_sort(B, N)
  
print(" ".join(A))
print("Stable")
  
print(" ".join(B))
if A == B:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
import copy
def bubbleSort(A, N):
    cnt = 0
    flag = 1
    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 = cnt + 1
    return cnt
 
 
def selectionSort(A, N):
    cnt = 0
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if A[j][1] < A[minj][1]:
                minj = j
        cnt = cnt + int(i != minj)
        A[i], A[minj] = A[minj], A[i]
    return cnt
 
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):
def bubblesort(a,n):
    flag=1
    while flag:
        flag=0
        for j in range(n-1,0,-1):
            if int(a[j][1])<int(a[j-1][1]):
                m=a[j]
                a[j]=a[j-1]
                a[j-1]=m
                flag=1
    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 i!=minj:
            m=a[i]
            a[i]=a[minj]
            a[minj]=m
    return a

n=int(input())
a=list(input().split( ))
b=[a[i] for i in range(n)]
a1=bubblesort(a,n)
print(" ".join(a1))
print("Stable")
a2=selectionsort(b,n)
print(" ".join(a2))
if a1==a2:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
import sys
 
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, N):
            if C[j][1] < C[minj][1]:
                minj = j
 
        C[i], C[minj] = C[minj], C[i]
     
    return C
fin = sys.stdin
 
N = int(fin.readline())
A = fin.readline().split()
B = A[:]
 
A = bubble_sort(A, N)
B = selection_sort(B, N)
 
print(" ".join(A))
print("Stable")
 
print(" ".join(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
        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
def bubbleSort(A, N):
    cnt = 0
    flag = 1
    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 = cnt + 1
    return cnt
 
 
def selectionSort(A, N):
    cnt = 0
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if A[j][1] < A[minj][1]:
                minj = j
        cnt = cnt + int(i != minj)
        A[i], A[minj] = A[minj], A[i]
    return cnt
 
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):
def bubble_sort(c, n):
  l = c[:]
  for i in range(n-1):
    for j in reversed(range(i+1, N)):
      if l[j][1] < l[j-1][1]:
        l[j], l[j-1] = l[j-1], l[j]
  return l

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

def is_stable(in_arr, out_arr, 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 in_arr[i][1] == in_arr[j][1] and in_arr[i] == out_arr[b] and in_arr[j] == out_arr[a]:
            return False
  return True


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

bubble_sorted_list = bubble_sort(C, N)
selection_sorted_list = selection_sort(C, N)

print(" ".join(map("".join, bubble_sorted_list)))
print("Stable" if is_stable(C, bubble_sorted_list, N) else "Not stable")
print(" ".join(map("".join, selection_sorted_list)))
print("Stable" if is_stable(C, selection_sorted_list, N) else "Not stable")

Solution (Python):
import copy

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

    def equals(self, card):
        if (card.suit == self.suit) and (card.number == self.number):
            return True
        else:
            return False

def bubble_sort(cards, n):
    for i in range(n):
        for j in range(n - 1, i, -1):
            if cards[j - 1].number > cards[j].number:
                cards[j - 1], cards[j] = cards[j], cards[j - 1]
    return cards

def selection_sort(cards, n):
    for i in range(n):
        min_j = i
        for j in range(i, n):
            if cards[j].number < cards[min_j].number:
                min_j = j
        if min_j != i:
            cards[i], cards[min_j] = cards[min_j], cards[i]
    return cards

def is_stable(cards1, cards2, n):
    result = True
    for i in range(n):
        if not(cards1[i].equals(cards2[i])):
            result = False
            break
    return result

def print_cards(cards, n):
    print(' '.join([c.suit + str(c.number) for c in cards]))

n = int(input())
cards = [Card(card[0], int(card[1])) for card in input().split()]
cards_bubble = bubble_sort(copy.deepcopy(cards), n)
cards_selection = selection_sort(copy.deepcopy(cards), n)

print_cards(cards_bubble, n)
print('Stable')
print_cards(cards_selection, n)
if is_stable(cards_bubble, cards_selection, n):
    print('Stable')
else:
    print('Not stable')

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

def selection_sort(C, key):
    n = len(C)
    for i in range(n):
        minj = i
        for j in range(i, n):
            if key(C[j]) < key(C[minj]):
                minj = j
        if i != minj:
            C[i], C[minj] = C[minj], C[i]

def chk_stable(org_arr, sorted_arr):
    n = len(org_arr)

    org_num_cnt = {}
    for i in range(n):
        num = org_arr[i][1]
        if num in org_num_cnt:
            org_num_cnt[num].append(i)
        else:
            org_num_cnt[num] = [i]

    is_stable = True
    _j = 0
    for i in range(1, n):
        if _j > 0:
            _j -= 1
            continue

        if sorted_arr[i-1][1] == sorted_arr[i][1]:
            idx_list = org_num_cnt[sorted_arr[i][1]]
            for j in range(len(idx_list)):
                if org_arr[idx_list[j]][0] != sorted_arr[i-1+j][0]:
                    is_stable = False
                    break
            _j = len(idx_list)-1
        if not is_stable:
            break

    return is_stable

n = int(input())

A = input().split()
C1 = A[:]
C2 = A[:]

bubble_sort(C1, lambda x: x[1])
print(*C1)
if chk_stable(A, C1) == True:
    print("Stable")
else:
    print("Not stable")

selection_sort(C2, lambda x: x[1])
print(*C2)
if chk_stable(A, C2) == True:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
n = int(input())
cardlist=list(map(str,input().split()))
def BubbleSort(C):
    for i in range(len(C)):
        for j in range(len(C)-1):
            if (C[j][-1:] >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 (C[j][-1:] < C[minj][-1:]):
                minj = j
        C[i],C[minj] = C[minj],C[i]
    return C
cardlist1 = cardlist.copy()
bubble = BubbleSort(cardlist)
print(*bubble)
print('Stable')
selection = SelectionSort(cardlist1)
print(*selection)
if(bubble == selection):
    print('Stable')
else:
    print('Not stable')

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

def b_sort(a):
	while True:
		for n in reversed(range(1, len(a))):
			if a[n][1] < a[n - 1][1]:
				a[n - 1], a[n] = a[n], a[n - 1]
				break
		else:
			return

def s_sort(a):
	for n in range(len(a)):
		min_n = n
		for m in range(n, len(a)):
			if a[m][1] < a[min_n][1]:
				min_n = m
		if n != min_n:
			a[n], a[min_n] = a[min_n], a[n]
	return

a_b = A.copy()
b_sort(a_b)
print(*a_b)
print("Stable")

a_s = A.copy()
s_sort(a_s)
print(*a_s)
print(["Stable", "Not stable"][not(a_b == a_s)])

Solution (Python):
n=int(input())
b=input().split()
s=b[:]
for i in range(n):
    for j in range(n-1,i,-1):
        if b[j][1]<b[j-1][1]:b[j],b[j-1]=b[j-1],b[j]
    m=i
    for j in range(i,n):
        if s[m][1]>s[j][1]:m=j
    s[m],s[i]=s[i],s[m]
print(*b)
print('Stable')
print(*s)
print(['Not s','S'][b==s]+'table')

Solution (Python):
import copy

def bubbleSort(C, M, N):
    for i in range(N):
        for j in reversed(range(i+1, N)):
            if C[j] < C[j-1]:
                out1 = C[j]
                C[j] = C[j-1]
                C[j-1] = out1
                out2 = M[j]
                M[j] = M[j-1]
                M[j-1] = out2
    print(' '.join(M))
    print('Stable')
    return M
    
def selectionSort(C, M, N):
    m = copy.deepcopy(M)
    for i in range(N):
        minj = i
        for j in range(i, N):
            if C[j] < C[minj]:
                minj = j
        out3 = C[i]
        C[i] = C[minj]
        C[minj] = out3
        out4 = M[i]
        M[i] = M[minj]
        M[minj] = out4
    print(' '.join(M))
    return M
    
def isStable(inn, out):
    for a, b in zip(inn, out):
        if a == b: continue
        else : return 'Not stable'
    return 'Stable'
    
if __name__ == '__main__':
    num1 = []
    N = int(input()) 
    M1 = list(input().split())
    for i in range(N):
        s = M1[i]
        num1.append(int(s[-1]))
    M2 = copy.deepcopy(M1)
    num2 = copy.deepcopy(num1)
    out1 = bubbleSort(num1, M1, N)
    out2 = selectionSort(num2, M2, N)
    print(isStable(out1, out2))

Solution (Python):
def bubble(N,C):
  for i in range(N):
    for j in range(i+1,N)[::-1]:
      if C[j][1] < C[j-1][1]:
        _=C[j]
        C[j]=C[j-1]
        C[j-1]=_
  print(*C)

def selection(N,C):
  for i in range(N):
    minj=i
    for j in range(i,N):
      if C[minj][1] > C[j][1]:
        minj=j
    _=C[minj]
    C[minj]=C[i]
    C[i]=_
  print(*C)

def stable(A,C):
  result='Stable'
  for i in range(1,10):
    a=[j for j in A if j[1]==str(i)]
    c=[k for k in C if k[1]==str(i)]
    if a!=c:
      result='Not stable'
  print(result)

N=int(input())
C=list(input().split())
A=C[:]
bubble(N,C)
stable(A,C)
C=A[:]
selection(N,C)
stable(A,C)

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

def bubble_sort(A):
    for i in range(len(A)):
        for j in range(len(A)-1, i, -1):
            if A[j]['value'] < A[j-1]['value']:
                tmp = A[j]
                A[j] = A[j-1]
                A[j-1] = tmp


def selection_sort(B):
    for i in range(len(B)):
        mini = i
        for j in range(i, len(B)):
            if B[j]['value'] < B[mini]['value']:
                mini = j
        tmp = B[i]
        B[i] = B[mini]
        B[mini] = tmp


def is_stable(A, B, n):
    for i in range(n):
        if A[i]['suit'] != B[i]['suit']:
            return False
    return True


def show_list(C):
    D = [i['suit'] + i['value'] for i in C]
    print(' '.join(D))
    
n = int(input())
A = [{'suit': i[0], 'value': i[-1]}for i in map(str, input().split())]
B = copy.deepcopy(A)

bubble_sort(A)
show_list(A)
print('Stable')

selection_sort(B)
show_list(B)
if is_stable(A, B, n):
    print('Stable')
else:
    print('Not stable')

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

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

N = int(input())
C = list(input().split())
C_dash = C.copy()

b = BubbleSort(C, N)
s = SelectionSort(C_dash, N)

print(" ".join(b))
print("Stable")
print(" ".join(s))
if b == s:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
from typing import List


def bubble_sort(elems: List[str]) -> List[str]:
    for i in range(0, len(elems)):
        for j in range(len(elems) - 1, i, -1):
            if int(elems[j][1]) < int(elems[j - 1][1]):
                elems[j], elems[j - 1] = elems[j - 1], elems[j]
    return elems


def selection_sort(elems: List[str]) -> List[str]:
    for i in range(0, len(elems)):
        mini = i
        for j in range(i + 1, len(elems)):
            if int(elems[j][1]) < int(elems[mini][1]):
                mini = j
        if i != mini:
            elems[i], elems[mini] = elems[mini], elems[i]
    return elems


def is_stable(input_elems: List[str], elems: List[str]) -> bool:
    for card1, card2 in zip(elems[:-1], elems[1:]):
        if (int(card1[1]) == int(card2[1])) and (
           input_elems.index(card1) > input_elems.index(card2)):
            return False
    return True


if __name__ == "__main__":
    elem_num = int(input())
    elems = list(input().split())

    elems_bubble_sort = elems.copy()
    elems_bubble_sort = bubble_sort(elems_bubble_sort)
    print(" ".join(elems_bubble_sort))
    if is_stable(elems, elems_bubble_sort):
        print("Stable")
    else:
        print("Not stable")

    elems_selection_sort = elems.copy()
    elems_selection_sort = selection_sort(elems_selection_sort)
    print(" ".join(elems_selection_sort))
    if is_stable(elems, elems_selection_sort):
        print("Stable")
    else:
        print("Not stable")

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

def bubble(S):
    sorted_l = []
    un_sorted_l = S[:]
    counter = 0
    while un_sorted_l:
        n = len(un_sorted_l)
        for i in reversed(range(1, n)):
            if un_sorted_l[i-1][1:] <= un_sorted_l[i][1:]:
                continue
            else:
                counter += 1
                un_sorted_l[i-1], un_sorted_l[i] = un_sorted_l[i], un_sorted_l[i-1]
        sorted_l.append(un_sorted_l[0])
        un_sorted_l = un_sorted_l[1:]

    return sorted_l
    
def select(S):
    selection_sort = S[:]
    counter = 0
    for i in range(len(selection_sort)):
        v = selection_sort[i]
        min_v = v
        min_i = i
        for j in range(i, len(selection_sort)):
            if min_v[1:] > selection_sort[j][1:]:
                min_v = selection_sort[j]
                min_i = j
        if v != min_v:
            counter += 1
            selection_sort[i], selection_sort[min_i] = selection_sort[min_i], selection_sort[i]
            
    return selection_sort

def check(X, S):
    d = {}
    for i, s in enumerate(S):
        d[s] = i
        
    for x, y in zip(X[:-1],X[1:]):
        if x[1:] == y[1:] and d[x] > d[y]:
            return 'Not stable'
    
    return 'Stable'
        
        

b = bubble(S)
print(' '.join(b))
print(check(b, S))

s = select(S)
print(' '.join(s))
print(check(s, S))