Problem:
Stable Sort Let's arrange a deck of cards. There are totally 36 cards of 4 suits(S, H, C, D) and 9 values (1, 2, ... 9). For example, 'eight of heart' is represented by H8 and 'one of diamonds' is represented by D1 . Your task is to write a program which sorts a given set of cards in ascending order by their values using the Bubble Sort algorithms and the Selection Sort algorithm respectively. These algorithms should be based on the following pseudocode: BubbleSort(C)
1 for i = 0 to C.length-1
2     for j = C.length-1 downto i+1
3         if C[j].value < C[j-1].value
4             swap C[j] and C[j-1] SelectionSort(C)
1 for i = 0 to C.length-1
2     mini = i
3     for j = i to C.length-1
4         if C[j].value < C[mini].value
5             mini = j
6     swap C[i] and C[mini] Note that, indices for array elements are based on 0-origin. Input The first line contains an integer N , the number of cards.  N cards are given in the following line. Each card is represented by two characters. Two consecutive cards are separated by a space character. Output In the first line, print the arranged cards provided by the Bubble Sort algorithm. Two consecutive cards should be separated by a space character. In the second line, print the stability (" Stable " or " Not stable ") of this output. In the third line, print the arranged cards provided by the Selection Sort algorithm. Two consecutive cards should be separated by a space character. In the fourth line, print the stability (" Stable " or " Not stable ") of this output. Constraints 1 ≤ N ≤ 36 Sample Input 1 5
H4 C9 S4 D2 C3 Sample Output 1 D2 C3 H4 S4 C9
Stable
D2 C3 S4 H4 C9
Not stable Sample Input 2 2
S1 H1 Sample Output 2 S1 H1
Stable
S1 H1
Stable

Solution (Python):
import copy

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

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

def SelectionSort(NUM_LIST):
    for i in range(len(NUM_LIST)):
        minj = i
        for j in range(i, len(NUM_LIST)):
            if NUM_LIST[minj][1] > NUM_LIST[j][1]:
                minj = j
        NUM_LIST[minj], NUM_LIST[i] = NUM_LIST[i], NUM_LIST[minj]

bubble_cards = copy.copy(cards)
selection_cards = copy.copy(cards)

BubbleSort(bubble_cards)
SelectionSort(selection_cards)


print(" ".join(bubble_cards))
print("Stable")

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

Solution (Python):
class Bubblesort():
    def __init__(self,x,n):
        self.C = x
        self.n = n
    def sorting(self):
        for i in range(self.n):
            for j in range(self.n - 1 , i , -1):
                if int(self.C[j][1]) < int(self.C[j - 1][1]):
                    self.C[j], self.C[j - 1] = self.C[j - 1], self.C[j]
        return self.C
    
    def check(self, xx):
        return CheckStable(self.C, xx)

class Selectionsort():
    def __init__(self, x, n):
        self.C = x
        self.n = n
    def sorting(self):
        for i in range(0, self.n):
            minj = i
            for j in range(i+1, self.n):
                if int(self.C[j][1])  < int(self.C[minj][1]):
                    minj = j
            self.C[i], self.C[minj] = self.C[minj], self.C[i]
        return self.C
    
    def check(self, xx):
        return CheckStable(self.C, xx)
    
def CheckStable(x1, xx2):
    ch1 = []
    for i in range(n - 1):
        if x1[i][1] == x1[i + 1][1]:
            ch1.append(x1[i])
            if i + 1 == n - 1:
                ch1.append(x1[i + 1])
        elif x1[i - 1][1] == x1[i][1]:
            ch1.append(x1[i])
    
    ch2 = []
    x2 = xx2
    for i in ch1:
        for j in range(len(x2)):
            if i[1] == x2[j][1]:
                ch2.append(x2[j])
                x2.pop(j)
                break

    if ch1 == ch2:
        return ('Stable')
    else:
        return ('Not stable')

n = int(input())
x = input().split()
xx =x[:]
y =x[:]
yy =x[:]

a = Bubblesort(x, n)
b = Selectionsort(y, n)
print(' '.join(a.sorting()))
print(a.check(xx))
print(' '.join(b.sorting()))
print(b.check(yy))

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

B = [int(x[1]) for x in A]
C = [x[0] for x in A]
D = [int(x[1]) for x in A]
E = [x[0] for x in A]
F = [int(x[1]) for x in A]
G = [x[0] for x in A]

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

def selectionSort(A, B, N):
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if A[j] < A[minj]: minj = j
        A[i], A[minj] = A[minj], A[i]
        B[i], B[minj] = B[minj], B[i]
    return 0

def showArray(A, B, N):
    for _ in range(N):
        if _ == N-1:
            print(A[_], sep='', end='')
            print(B[_], sep='', end='')
        else:
            print(A[_], sep='', end='')
            print(B[_], sep='', end=' ')
    print()
    return 0

def isStable(A, B, C, D, N):
    for _ in range(1, 10):
        if A.count(_) > 1:
            if [B[i] for i, x in enumerate(A) if x == _] == [D[i] for i, x in enumerate(C) if x == _]:
                continue
            else:
                return 'Not stable'
    return 'Stable'

if __name__ == '__main__':
    bubbleSort(B, C, N)
    selectionSort(D, E, N)
    
    showArray(C, B, N)
    print(isStable(B, C, F, G, N))
    showArray(E, D, N)
    print(isStable(D, E, F, G, N))

Solution (Python):
import copy

class Card:
    def __init__(self, mark_num):
        self.mark_num = mark_num
        self.mark = mark_num[0]
        self.num = int(mark_num[1:])

def bubble_sort(cards, n):
    flag = True
    while flag:
        flag = False
        for i in reversed(range(1, n)):
            if cards[i].num < cards[i-1].num:
                tmp = cards[i]
                cards[i] = cards[i-1]
                cards[i-1] = tmp
                flag = True
    
    
    

    mark_nums = []
    for c in cards:
        mark_nums.append(c.mark_num)

    print(" ".join(mark_nums))
    print("Stable")

    return cards

    
    
    

def selection_sort(cards, n):
    for i in range(n):
        minj = i
        flag = False
        for j in range(i, n-1):
            if cards[minj].num > cards[j+1].num:
                minj = j+1
                flag = True
        
        if flag:
            tmp = cards[i]
            cards[i] = cards[minj]
            cards[minj] = tmp

    mark_nums = []
    for c in cards:
        mark_nums.append(c.mark_num)

    print(" ".join(mark_nums))

    return cards

def is_stable(cards1, cards2, n):
    is_stable = True
    for i in range(n):
        if cards1[i].mark_num != cards2[i].mark_num:
            is_stable = False
            break

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




if __name__=="__main__":
    n = int(input())
    input_cards = list(input().split())
    card_list = []
    for input_card in input_cards:
        card = Card(input_card)
        card_list.append(card)

    cards_1 = bubble_sort(copy.deepcopy(card_list), n)
    cards_2 = selection_sort(copy.deepcopy(card_list), n)

    is_stable(cards_1, cards_2, n)

Solution (Python):
N = int(input())
A = list(map(str, input().split()))
unsorted_A = A[:]
bub_A = A[:]
sel_A = A[:]

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

    print(' '.join(bub_A))
    print('Stable')

def SelectionSort(sel_A):
    for i in range(N):
        min = i
        for j in range(i, N):
            if sel_A[j][1] < sel_A[min][1]:
                min = j
        if sel_A[i][1] > sel_A[min][1]:
            sel_A[i], sel_A[min] = sel_A[min], sel_A[i]

    print(' '.join(sel_A))
    if bub_A == sel_A:
        print('Stable')
    else:
        print('Not stable')

BubbleSort(bub_A)
SelectionSort(sel_A)

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

flag=1
while flag:
  flag=0
  for i in range(n-1,0,-1):
    if int(A[i-1][1])>int(A[i][1]):
      A[i-1],A[i]=A[i],A[i-1]
      flag=1
print(*A)
print("Stable")

for i in range(n-1):
  minj=i
  for j in range(i,n):
    if int(B[minj][1])>int(B[j][1]):
      minj=j
  if minj!=i:
    B[i],B[minj]=B[minj],B[i]
print(*B)
if A==B:
  print("Stable")
else:
  print("Not stable")

Solution (Python):
import sys
import copy
input = sys.stdin.readline


def main():
    N = int(input())
    P = list(input().split())
    bubbleSortted = bubbleSort(N, copy.copy(P))
    print(' '.join(map(str, bubbleSortted)))
    print("Stable")
    selectionSorted = selectionSort(N, copy.copy(P))
    print(' '.join(map(str, selectionSorted)))
    print(isStable(bubbleSortted, selectionSorted))


def selectionSort(N, P):
    change_count = 0
    for i in range(0, N):
        minj = i

        
        

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

        if i != minj:
            tmp = P[i]
            P[i] = P[minj]
            P[minj] = tmp
            change_count += 1

        

    return P


def bubbleSort(N, P):
    change_count = 0
    i = 0
    while True:
        for j in range(N - 1, i, -1):
            if P[j][1] < P[j - 1][1]:
                tmp = P[j]
                P[j] = P[j - 1]
                P[j - 1] = tmp
                change_count += 1
        i += 1
        
        if i == N:
            break

    return P


def isStable(P1, P2):
    for i in range(len(P1)):
        
        if P1[i] != P2[i]:
            return "Not stable"
    return "Stable"


if __name__ == '__main__':
    main()

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

def bubble_sort(collection):
    collection = copy(collection)
    for i in range(len(collection)):
        for j in range(len(collection)-1, i, -1):
            if collection[j] < collection[j-1]:
                collection[j], collection[j-1] = collection[j-1], collection[j]
    return collection
    
def selection_sort(collection):
    collection = copy(collection)
    for i in range(len(collection)):
        mini = i
        for j in range(i, len(collection)):
            if collection[j] < collection[mini]:
                mini = j
        collection[i], collection[mini] = collection[mini], collection[i]
        
    return collection
    
def print_cards(cards):
    for card in cards[:-1]:
        print(card, end=' ')
    print(cards[-1])

def find_card_order(cards):
    duplicate_numbers = defaultdict(list)
    for card in cards:
        duplicate_numbers[card.number].append(card.suit)
    duplicate_numbers = {k: v for k, v in duplicate_numbers.items() if len(v) >= 2}
    return duplicate_numbers



class Card:
    def __init__(self, card):
        self._suit = card[0]
        self._number = int(card[1])
    
    def __str__(self):
        return self.card
    
    def __lt__(self, other):
        return self._number < other._number
        
    @property
    def card(self):
        return self._suit + str(self._number)
    
    @property
    def number(self):
        return self._number
    @property
    def suit(self):
        return self._suit
        
nums_card = int(input())
cards = list(map(Card, input().split()))
duplicate_cards =  find_card_order(cards)
bubble_sorted = bubble_sort(cards)
selection_sorted = selection_sort(cards)


print_cards(bubble_sorted)

stable = 'Stable'
for k, v in duplicate_cards.items():
    sorted_order = [card.suit for card in bubble_sorted if card.number == k]
    if duplicate_cards[k] != sorted_order:
        stable = 'Not stable'
print(stable)

print_cards(selection_sorted)
stable = 'Stable'
for k, v in duplicate_cards.items():
    sorted_order = [card.suit for card in selection_sorted if card.number == k]
    if duplicate_cards[k] != sorted_order:
        stable = 'Not stable'
print(stable)

Solution (Python):
from collections import namedtuple


Card = namedtuple('Card', 'suit value')
Card.__str__ = lambda self: self.suit + str(self.value)


def printcards(cards):
    print(' '.join([str(c) for c in cards]))


def bubblesort(it, key):
    it = list(it)
    for start_ind in range(len(it)):
        for target_ind in range(len(it)-1, start_ind, -1):
            target_val = key(it[target_ind])
            compare_val = key(it[target_ind-1])
            if target_val < compare_val:
                it[target_ind], it[target_ind-1] = it[target_ind-1], it[target_ind],
    return it


def selectsort(it, key):
    it = list(it)
    for start_ind in range(len(it)):
        min_ind = start_ind
        for target_ind in range(start_ind, len(it)):
            target_val = key(it[target_ind])
            min_val = key(it[min_ind])
            if target_val < min_val:
                min_ind = target_ind
        it[start_ind], it[min_ind] = it[min_ind], it[start_ind]
    return it


if __name__ == '__main__':
    n = int(input())
    cards = [Card(*suit_val) for suit_val in input().split()]
    cards_bub = bubblesort(cards, key=lambda x: x.value)
    cards_slc = selectsort(cards, key=lambda x: x.value)
    printcards(cards_bub)
    print('Stable')
    printcards(cards_slc)
    print('Stable') if cards_bub == cards_slc else print('Not stable')

Solution (Python):
import copy

def is_stable(ax,bx):
    num=[]
    for ix in ax:
        if ix[1] not in num:
            num.append(ix[1])
    for ix in num:
        cx=[]
        for jx in ax:
            if jx[1]==ix:
                cx.append(jx)
        dx=[]
        for jx in bx:
            if jx[1]==ix:
                dx.append(jx)
        if cx!=dx:
            return "Not stable"
    else:
        return "Stable"

def array_print(ar):
    s=""
    for i in range(len(ar)):
        s+=(ar[i][0]+str(ar[i][1]))
        if i!=n-1:
            s+=" "
    return s

n=int(input())
a=[[i[0],int(i[1])]for i in input().split()]
b1=copy.deepcopy(a)
b2=copy.deepcopy(a)


f=1
while f:
    f=0
    for i in range(n-1):
        if b1[n-i-1][1]<b1[n-i-2][1]:
            b1[n-i-1],b1[n-i-2]=b1[n-i-2],b1[n-i-1]
            f=1
print(array_print(b1))
print(is_stable(a,b1))


for i in range(n):
    min=i
    for j in range(i+1,n):
        if b2[min][1]>b2[j][1]:
            min=j
    b2[min],b2[i]=b2[i],b2[min]
print(array_print(b2))
print(is_stable(a,b2))

Solution (Python):


def printCards(C, N):
    for i in range(N):
        if i > 0:
            print(' ', end = '')
        print(C[i][0], end = '')
    print('')
    return True

n = int(input())
cards0 = map(str, input().split())
cards1 = list()
for i in cards0:
    cards1.append((i, int(i[1])))
cards2 = cards1[:]
del cards0


for i in range(n):
    for j in range(n-1, i, -1):
        if cards1[j][1] < cards1[j-1][1]:
            temp = cards1[j]
            cards1[j] = cards1[j-1]
            cards1[j-1] = temp
printCards(cards1, n)
print('Stable')


for i in range(n-1):
    minj = i
    for j in range(i+1, n):
        if cards2[j][1] < cards2[minj][1]:
            minj = j
    temp = cards2[i]
    cards2[i] = cards2[minj]
    cards2[minj] = temp
printCards(cards2, n)

for i in range(n):
    if cards1[i] != cards2[i]:
        print('Not stable')
        exit()
print('Stable')

Solution (Python):

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

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, N):
            if int(C[j][1]) < int(C[minj][1]):
                minj = j
        C[i], C[minj] = C[minj], C[i]
    return C

C1 = BubbleSort(A[:], N)
C2 = SelectionSort(A[:], N)
print(' '.join(map(str,C1)))
print('Stable')
print(' '.join(map(str,C2)))
if C1 == C2:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
def Bubble_Sort(l,n):
    count = 0
    dec = 0
    
    is_reverse = True
    while is_reverse:
        is_reverse = False
        
        for i in range(n-1-dec):
            if l[i][1] > l[i+1][1]:
                l[i] , l[i+1] = l[i+1], l[i]
                is_reverse = True
                count += 1
        
        dec += 1

def selectionSort(A,n):
    count = 0
    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]
        count = count + int( i != minj)
    return count

n = int(input())
A = input().split()
B = A.copy()
Bubble_Sort(B,n)
print(' '.join(B))
print('Stable')

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

Solution (Python):

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


c1 = c_ori[:]
for i in range(n):
    for j in range(n-1, i, -1):
        if c1[j][1] < c1[j-1][1]:
            c1[j-1], c1[j] = c1[j], c1[j-1]
print(*c1)
print('Stable')


c2 = c_ori[:]
for i in range(n):
    minj = i
    for j in range(i, n):
        if c2[j][1] < c2[minj][1]:
            minj = j
    c2[minj], c2[i] = c2[i], c2[minj]
print(*c2)

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

Solution (Python):
def makedic(array):
    dic = {str(i): '' for i in range(10)}
    for v in array:
        dic[v[1]] += v[0]
    return dic


def main():
    n = int(input())
    origin = [v for v in input().split()]
    dic_origin = makedic(origin)

    a = origin[:]
    for i in range(n - 1):
        last = n - i - 1
        for j in range(last):
            if int(a[j][1]) > int(a[j + 1][1]):
                a[j], a[j + 1] = a[j + 1], a[j]

    print(' '.join(a))
    print('Stable' if makedic(a) == dic_origin else 'Not Stable')

    b = origin[:]
    for i in range(n):
        m = i
        for j in range(i + 1, n):
            if int(b[j][1]) < int(b[m][1]):
                m = j

        if not m == i:
            b[m], b[i] = b[i], b[m]

    print(' '.join(b))
    print('Stable' if makedic(b) == dic_origin else 'Not stable')


if __name__ == '__main__':
    main()

Solution (Python):
import copy


def bubbleSort(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]


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


n = int(input())
a = list(input().split())
b = copy.deepcopy(a)

bubbleSort(a, n)
print(*a)
print('Stable')

selectionSort(b, n)
print(*b)
print('Stable') if a == b else print('Not stable')

Solution (Python):
import copy
def bubble(box,n):
    for i in range(n):
        p=n-1
        while p!=i:
            if box[p][1]<box[p-1][1]:
                box[p],box[p-1]=box[p-1],box[p]
            p -=1
    return box

def selection(box,n):
    for i in range(n):
        mini=i
        for j in range(i,n):
            if box[j][1]<box[mini][1]:
                mini=j
        if box[i][1]>box[mini][1]:
            box[i],box[mini]=box[mini],box[i]
    return box

n=int(input())
A=list(input().split())
B=copy.deepcopy(A)

bubble=bubble(A,n)
print(*A)
print("Stable")
selection=selection(B,n)
print(*B)
print("Stable" if A==B else "Not stable")

Solution (Python):
N = int(input())
A = list(map(str, input().split()))

import copy
A1 = copy.copy(A)
A2 = copy.copy(A)

flag = 1
while flag:
    flag = 0
    for j in range(N-1, 0, -1):
        if int(A1[j][1]) < int(A1[j-1][1]):
            
            A1[j], A1[j-1] = A1[j-1], A1[j]
            flag = 1    
                        


for i in range(0, N):
    minj = i
    for j in range(i, N): 
        if int(A2[j][1]) < int(A2[minj][1]): 
            minj = j
    A2[i], A2[minj] = A2[minj], A2[i]

print(*A1)
print('Stable')
print(*A2)

if A1 == A2:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
def main(n):
	a = list(input().split())
	b = list(a)
	c = list(a)
	achk = [[] for _ in range(10)]
	bchk = [[] for _ in range(10)]
	cchk = [[] for _ in range(10)]
	for i in range(n):
		for j in range(n-1, i, -1):
			if int(b[j][1]) < int(b[j-1][1]):
				b[j], b[j-1] = b[j-1], b[j]
	print(" ".join(b))
	print("Stable")
	for i in range(n):
		minj = i
		for j in range(i, n):
			if int(c[j][1]) < int(c[minj][1]):
				minj = j
		c[i], c[minj] = c[minj], c[i]
	print(" ".join(c))
	if c == b:
		print("Stable")
	else:
		print("Not stable")

main(int(input()))

Solution (Python):




import copy

def BubbleSort(A, N):
    minj = 0
    tmp = 0
    flag = 1

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

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

def isStable(list1, list2, N):
    for i in range(0, N):
        if list1[i][0] != list2[i][0]:
            print("Not stable")
            return 0
    print("Stable")
    return 0

if __name__ == "__main__":
    N=int(input()) 
    A=list(input().split()) 
    L1 = copy.deepcopy(A)
    L2 = copy.deepcopy(A)
    
    A1 = BubbleSort(L1, N)
    A2 = SelectionSort(L2, N)
    print(*A1)
    print("Stable")
    print(*A2)
    isStable(A1, A2, N)

Solution (Python):
import copy

def show(C):
    N=len(C)
    for i in range(N):
        if i<N-1:
            print(C[i][0]+str(C[i][1]),end=' ')
        else:
            print(C[i][0]+str(C[i][1]))
    
def BubbleSort(C,N):
    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 SelectionSort(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 C

def compare(C1,C2):
    for i in range(1,10):
        l1=[]
        for c in C1:
            if int(c[1])==i:
                l1.append(c)
        l2=[]
        for c in C2:
            if int(c[1])==i:
                l2.append(c)
        for j in range(min(len(l1),len(l2))):
            if l1[j][0]!=l2[j][0]:
                return False
    return True
   
N=int(input())
l=list(input().split())
deck=[]
for c in l:
    deck.append((c[0],c[1]))

deck1=copy.copy(deck)
deck2=copy.copy(deck)

deck1=BubbleSort(deck1,N)
deck2=SelectionSort(deck2,N)

show(deck1)
compare(deck,deck1)
print('Stable' if compare(deck,deck1) else 'Not stable')
show(deck2)
print('Stable' if compare(deck,deck2) else 'Not stable')

Solution (Python):


def returnInt(x):
    return int(x[-1])

def bubbleSort(A, N):
    flag = 1
    while flag:
        flag = 0
        for i in range(N - 1, 0, -1):
            if returnInt(A[i]) < returnInt(A[i - 1]):
                A[i], A[i - 1] = A[i - 1], A[i]
                flag = 1
    print(' '.join(A))
    return A

def selectionSort(A, N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if returnInt(A[j]) < returnInt(A[minj]):
                minj = j
        A[i], A[minj] = A[minj], A[i]
    print(' '.join(A))
    return A

if __name__ == "__main__":
    N = int(input())
    A = input().split()
    B = [i for i in A]

    A_bubble = bubbleSort(A, N)
    print('Stable')
    A_selection = selectionSort(B, N)
    if A_bubble == A_selection:
        print('Stable')
    else:
        print('Not stable')

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(" ".join([str(c) for c in 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)
is_stable = sorted_card_list1 == sorted_card_list2
print(" ".join([str(c) for c in sorted_card_list2]))
print("Stable" if is_stable else "Not stable")

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

BC = [0] * N
SC = [0] * N


for i in range(N):
    BC[i] = C[i]
    SC[i] = C[i]
for i in range(N):
    for j in range(N-1, i, -1):
        if int(BC[j][1]) < int(BC[j-1][1]):
            BC[j], BC[j-1] = BC[j-1], BC[j]

print(' '.join(list(map(str, BC))))
print("Stable")



for i in range(N):
    minj = i
    for j in range(i, N):
        if int(SC[j][1]) < int(SC[minj][1]):
            minj = j
    SC[minj], SC[i] = SC[i], SC[minj]
    
print(' '.join(list(map(str, SC))))
if SC == BC:
    print("Stable")
else:
    print("Not stable")

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


def SelectionSort(N, A):
    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]


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


N = int(input())
A = [str(i) for i in input().split()]


A1 = A.copy()

BubbleSort(N, A)
trace(A)
print('Stable')

SelectionSort(N, A1)
trace(A1)

same = True
for i in range(N):
    if A[i] != A1[i]:
        same = False
if same:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
import copy
def isStable(n,n_old):
  for i in range(len(n)-1):
    for j in range(i+1,len(n),+1):
      for a in range(len(n)-1):
        for b in range(a+1,len(n),+1):
          if n[i][1]==n[j][1]:
            if n[i]==n_old[b] and n[j]==n_old[a]:
              return 'Not stable'
  return 'Stable'
  
m=int(input())
n=list(map(str,input().split()))
n_old=copy.deepcopy(n)

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

print(' '.join(map(str, n)))
print(isStable(n,n_old))

n=copy.deepcopy(n_old)

for i in range(len(n)-1):
  minj=i
  cnt=0
  for j in range(i+1,len(n)):
    if n[j][1]<n[minj][1]:
      minj=j
      cnt=1
  if cnt==1:
    n[i],n[minj]=n[minj],n[i]

print(' '.join(map(str, n)))
print(isStable(n,n_old))

Solution (Python):

def main():
    N, *A = open(0).read().split()
    N = int(N)
    B = 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]
    print(*A)
    print("Stable")

    
    for i in range(N):
        mi = i
        for j in range(i, N):
            if B[j][1] < B[mi][1]:
                mi = j
        B[i], B[mi] = B[mi], B[i]
    print(*B)
    flg = B == A
    print("Stable" if flg else "Not stable")


if __name__ == "__main__":
    main()

Solution (Python):
def bubble(A0):
    A = A0.copy()
    N = len(A)
    flag = True
    while(flag):
        flag = False
        for i in range(N-1):
            if A[i][1] > A[i+1][1]:
                A[i], A[i+1] = A[i+1], A[i]
                flag = True
    return A

def select(A0):
    A = A0.copy()
    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]
    return A

if __name__ == '__main__':
    N = int(input())
    A = list(map(str, input().split()))
    A_sort = bubble(A)
    print(*A_sort)
    
    flag = True
    for i in range(N-1):
        if A_sort[i][1] == A_sort[i+1][1]:
            if A.index(A_sort[i]) > A.index(A_sort[i+1]):
                flag = False
                break
    if flag:
        print('Stable')
    else:
        print('Not stable')
    
    A_sort = select(A)
    print(*A_sort)
    flag = True
    for i in range(N-1):
        if A_sort[i][1] == A_sort[i+1][1]:
            if A.index(A_sort[i]) > A.index(A_sort[i+1]):
                flag = False
                break

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

Solution (Python):
N = int(input())
cards = list(input().split())
cards_list = [list(i) for i in cards]

for i in range(N):
	for j in reversed(range(i+1,N)):
		if j<N:
			if int(cards_list[j][1])<int(cards_list[j-1][1]):
				cards_list[j],cards_list[j-1]=cards_list[j-1],cards_list[j]
cards_t =[0 for i in range(N)]
for i in range(N):
	cards_t[i] = "".join(cards_list[i])			
print(" ".join(cards_t))
print("Stable")

cards_list_1 =[list(i) for i in cards]
for i in range(N):
	minj = i
	for j in range(i,N):
		if cards_list_1[j][1]<cards_list_1[minj][1]:
			minj = j
	cards_list_1[minj],cards_list_1[i] =cards_list_1[i],cards_list_1[minj]

cards_t =[0 for i in range(N)]
for i in range(N):
	cards_t[i] = "".join(cards_list_1[i])			
print(" ".join(cards_t))
if cards_list == cards_list_1:
	print("Stable")
else:
	print("Not stable")

Solution (Python):
import copy
num =int(input())

l = input().split()

def ccompare( p, q):
    return ord(p[1]) - ord(q[1])


def bsort(l):
    a = copy.copy(l)
    for i in range(len(a)):
        for j in reversed(range(i+1,len(a))):
            if ccompare(a[j],a[j-1]) < 0:
                tmp = a[j-1]
                a[j-1] = a[j]
                a[j] = tmp
    return a
def ssort(l):
    b = copy.copy(l)
    for i in range(len(b)):
        minj = i
        for j in range(i,len(b)):
            if ccompare(b[j], b[minj]) < 0:
                minj = j
        tmp = b[minj]
        b[minj] = b[i]
        b[i] = tmp
    return b
    
def show(lst):
    for i in range(len(lst)):
        print(lst[i], end="")
        if i < len(lst)-1:
            print(" ", end="")
        else:
            print()

def complist(s,t):
    for i in range(len(s)):
        if s[i] != t[i]:
            return False
    return True

bres = bsort(l)
sres = ssort(l)
show(bres)
print("Stable")
show(sres)
if complist(bres, sres):
    print("Stable")
else:
    print("Not stable")