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):
from sys import stdin
def stdinput():
    return stdin.readline().strip()

class Card:
    def __init__(self, value):
        self.value = int(value[1:])
        self.value2 = value

def main():
    n = int(stdinput())
    A = list(map(Card, stdinput().split()))

    bubble_sorted = bubble_sort(A[:], len(A))
    selection_sorted = selection_sort(A[:], len(A))

    print(' '.join(map(lambda c: c.value2, bubble_sorted)))
    print('Stable' if is_stable(A, bubble_sorted) else 'Not stable')
    print(' '.join(map(lambda c: c.value2, selection_sorted)))
    print('Stable' if is_stable(A, selection_sorted) else 'Not stable')


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

def selection_sort(A, N):
    for i in range(N):
        min_idx = i
        for j in range(i+1, N):
            if A[j].value < A[min_idx].value:
                min_idx = j
        if min_idx != i:
            A[i], A[min_idx] = A[min_idx], A[i]
    return A

def is_stable(A, B):
    for i in range(1, 10):
        sub_A = list(filter(lambda c: c.value == i, A))
        sub_B = list(filter(lambda c: c.value == i, B))
        for a, b in zip(sub_A, sub_B):
            if a.value2 != b.value2:
                return False
    return True

if __name__ == '__main__':
    main()

Solution (Python):
import sys

class Card:

	def __init__(self, card):
		self.card = card
		self.mark = card[0]
		self.value = int(card[1])

	def __str__(self):
		return self.card

def print_arr(arr):
	for i in range(len(arr)):
		sys.stdout.write(str(arr[i]))
		if i != len(arr) - 1:
			sys.stdout.write(' ')
	print()

def swap(arr, i, j):
	temp = arr[i]
	arr[i] = arr[j]
	arr[j] = temp

def bubble_sort(arr, n):
	swap_count = 0
	for i in range(0, n):
		for j in range(n - 1, i, -1):
			if arr[j].value < arr[j - 1].value:
				swap(arr, j, j - 1)
				swap_count += 1
	return swap_count

def selection_sort(arr, n):
	stable = True
	for i in range(n):
		minj = i
		for j in range(i, n):
			if arr[j].value < arr[minj].value:
				minj = j
		if minj != i:
			for k in range(i + 1, minj):
				if arr[k].value == arr[i].value: stable = False
			swap(arr, i, minj)
	return stable

n = int(input())
arr = list(map(str, input().split()))
cards1 = [None] * n
cards2 = [None] * n
for i in range(n):
	cards1[i] = Card(arr[i])
	cards2[i] = Card(arr[i])

swap_count = bubble_sort(cards1, n)
stable = selection_sort(cards2, n)

print_arr(cards1)
print('Stable')
print_arr(cards2)
if stable == True:
	print('Stable')
else:
	print('Not stable')

Solution (Python):
import sys

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

	def __str__(self):
		return self.card

def swap(arr, i, j):
	temp = arr[i]
	arr[i] = arr[j]
	arr[j] = temp

def bubble_sort(arr):
	n = len(arr)
	for i in range(0, n):
		for j in range(n - 1, i, -1):
			if arr[j].value < arr[j - 1].value:
				swap(arr, j, j - 1)

def selection_sort(arr):
	n = len(arr)
	for i in range(n):
		minj = i
		for j in range(i, n):
			if arr[j].value < arr[minj].value:
				minj = j
		if minj != i:
			swap(arr, i, minj)

n = int(input())
arr = list(map(str, input().split()))
cards1 = [None] * n
cards2 = [None] * n
for i in range(n):
	cards1[i] = Card(arr[i])
	cards2[i] = Card(arr[i])

bubble_sort(cards1)
selection_sort(cards2)

for i in range(n):
	sys.stdout.write(cards1[i].card)
	if i != n - 1:
		sys.stdout.write(' ')
print()
print('Stable')

stable = True
for i in range(n):
	if cards1[i].card != cards2[i].card: stable = False
	sys.stdout.write(cards2[i].card)
	if i != n - 1:
		sys.stdout.write(' ')
print()
if stable == True:
	print('Stable')
else:
	print('Not stable')

Solution (Python):
import sys

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

	def __str__(self):
		return self.card

def print_arr(arr1, arr2):
	n = len(arr1)
	stable = True
	for i in range(n):
		if arr2 != None and arr1[i].card != arr2[i].card: stable = False
		sys.stdout.write(str(arr1[i]))
		if i != n - 1:
			sys.stdout.write(' ')
	print()
	return stable

def swap(arr, i, j):
	temp = arr[i]
	arr[i] = arr[j]
	arr[j] = temp

def bubble_sort(arr):
	n = len(arr)
	for i in range(0, n):
		for j in range(n - 1, i, -1):
			if arr[j].value < arr[j - 1].value:
				swap(arr, j, j - 1)

def selection_sort(arr):
	n = len(arr)
	for i in range(n):
		minj = i
		for j in range(i, n):
			if arr[j].value < arr[minj].value:
				minj = j
		if minj != i:
			swap(arr, i, minj)

n = int(input())
arr = list(map(str, input().split()))
cards1 = [None] * n
cards2 = [None] * n
for i in range(n):
	cards1[i] = Card(arr[i])
	cards2[i] = Card(arr[i])

bubble_sort(cards1)
selection_sort(cards2)

print_arr(cards1, None)
print('Stable')

stable = print_arr(cards2, cards1)
if stable == True:
	print('Stable')
else:
	print('Not stable')

Solution (Python):
import sys

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

	def __str__(self):
		return self.card

def print_cards(arr_print, arr_compare):
	n = len(arr_print)
	same = True
	for i in range(n):
		if arr_compare != None and arr_print[i].card != arr_compare[i].card: same = False
		sys.stdout.write(str(arr_print[i]))
		if i != n - 1:
			sys.stdout.write(' ')
	print()
	return same

def swap(arr, i, j):
	temp = arr[i]
	arr[i] = arr[j]
	arr[j] = temp

def bubble_sort(arr):
	n = len(arr)
	for i in range(0, n):
		for j in range(n - 1, i, -1):
			if arr[j].value < arr[j - 1].value:
				swap(arr, j, j - 1)

def selection_sort(arr):
	n = len(arr)
	for i in range(n):
		minj = i
		for j in range(i, n):
			if arr[j].value < arr[minj].value:
				minj = j
		if minj != i:
			swap(arr, i, minj)

n = int(input())
arr = list(map(str, input().split()))
cards1 = [None] * n
cards2 = [None] * n
for i in range(n):
	cards1[i] = Card(arr[i])
	cards2[i] = Card(arr[i])

bubble_sort(cards1)
selection_sort(cards2)

print_cards(cards1, None)
print('Stable')

stable = print_cards(cards2, cards1)
if stable == True:
	print('Stable')
else:
	print('Not stable')

Solution (Python):
import sys

class Card:
	def __init__(self, card):
		self.card = card
		self.symbol = card[0]
		self.value = int(card[1])

def print_cards(arr_print, arr_compare):
	n = len(arr_print)
	same = True
	for i in range(n):
		if arr_compare != None and arr_print[i].card != arr_compare[i].card: same = False
		sys.stdout.write(arr_print[i].card)
		if i != n - 1:
			sys.stdout.write(' ')
	print()
	return same

def swap(arr, i, j):
	temp = arr[i]
	arr[i] = arr[j]
	arr[j] = temp

def bubble_sort(arr):
	n = len(arr)
	for i in range(0, n):
		for j in range(n - 1, i, -1):
			if arr[j].value < arr[j - 1].value:
				swap(arr, j, j - 1)

def selection_sort(arr):
	n = len(arr)
	for i in range(n):
		minj = i
		for j in range(i, n):
			if arr[j].value < arr[minj].value:
				minj = j
		if minj != i:
			swap(arr, i, minj)

n = int(input())
arr = list(map(str, input().split()))
cards1 = [None] * n
cards2 = [None] * n
for i in range(n):
	cards1[i] = Card(arr[i])
	cards2[i] = Card(arr[i])

bubble_sort(cards1)
selection_sort(cards2)

print_cards(cards1, None)
print('Stable')

stable = print_cards(cards2, cards1)
if stable == True:
	print('Stable')
else:
	print('Not stable')

Solution (Python):
import sys

class Card:
	def __init__(self, card):
		self.card = card
		self.mark = card[0]
		self.value = card[1]
	
	def equals(self, other):
		if self.mark != other.mark: return False
		if self.value != other.value: return False
		return True

	def __str__(self):
		return self.card

def print_cards(cards, cards_):
	n = len(cards)
	same = True
	for i in range(n):
		if cards_ != None and cards[i].equals(cards_[i]) == False:
			same = False
		sys.stdout.write(str(cards[i])) 
		if i != n - 1:
			sys.stdout.write(' ')
	print()
	return same	

def swap(cards, i, j):
	temp = cards[i]
	cards[i] = cards[j]
	cards[j] = temp

def bubble_sort(cards):
	n = len(cards)
	for i in range(n):
		for j in range(n - 1, i, -1):
			if cards[j].value < cards[j - 1].value:
				swap(cards, j, j - 1)

def selection_sort(cards):
	n = len(cards)
	for i in range(n):
		mini = i
		for j  in range(i, n):
			if cards[j].value < cards[mini].value:
				mini = j
		if mini != i:
			swap(cards, i, mini)
		
n = int(input())
input_list = list(map(str, input().split()))
cards1 = [None] * n
cards2 = [None] * n
for i in range(n):
	cards1[i] = Card(input_list[i])
	cards2[i] = Card(input_list[i])
	
bubble_sort(cards1)
selection_sort(cards2)

print_cards(cards1, None)
print('Stable')

stable = print_cards(cards2, cards1)
if stable == True:
	print('Stable')
else:
	print('Not stable')

Solution (Python):
def main():
    n = int(input())
    cards = list(map(str, input().split()))
    bubbleSortedCards = cards[:]
    selectionSortedCards = cards[:]


    bubbleSort(bubbleSortedCards, n)
    print(' '.join(map(str, bubbleSortedCards)))
    print('Stable')

    selectionSort(selectionSortedCards, n)
    print(' '.join(map(str, selectionSortedCards)))
    print(isStable(bubbleSortedCards, selectionSortedCards, n))


def bubbleSort(numbers, n):
    for i in range(n - 1, 0, -1):
        for j in range(i):
            if int(numbers[j][1]) > int(numbers[j + 1][1]):
                numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]

def selectionSort(numbers, n):
    minj = 0

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

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

def isStable(bubbleSortedCards, selectionSortedCards, n):
    for i in range(n):
        if bubbleSortedCards[i] != selectionSortedCards[i]:
            return 'Not stable'

    return 'Stable'

if __name__ == '__main__':
    main()

Solution (Python):
class Card:
    def __init__(self, mark, value):
        self.mark = mark
        self.value = value

    def __eq__(self, other):
        if not isinstance(other, Card):
            return NotImplemented
        return self.value == other.value and self.mark == other.mark

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

    def __str__(self):
        return self.mark + str(self.value)


def BubbleSort(arr):
    res = [Card(c.mark, c.value) for c in arr]
    swap_flg = True
    i = 0
    while swap_flg:
        swap_flg = False
        for j in range(len(res) - 1, i, -1):
            if (res[j] < res[j - 1]):
                res[j], res[j - 1] = res[j - 1], res[j]
                swap_flg = True
        i += 1
    return res


def SelectionSort(arr):
    res = [Card(c.mark, c.value) for c in arr]
    for i in range(0, len(res)):
        minj = i
        for j in range(i, N):
            if res[j] < res[minj]:
                minj = j
        if (i != minj):
            res[i], res[minj] = res[minj], res[i]
    return res


def isStable(in_arr, out_arr):
    stable_arr = BubbleSort(in_arr)
    return all(out_arr[i] == stable_arr[i] for i in range(0, len(out_arr)))


N = int(input())
arr = [Card(s[0], int(s[1])) for s in input().split()]
b_arr = BubbleSort(arr)
print(' '.join(map(str, b_arr)))
print('Stable' if isStable(arr, b_arr) else 'Not stable')
s_arr = SelectionSort(arr)
print(' '.join(map(str, s_arr)))
print('Stable' if isStable(arr, s_arr) else 'Not stable')

Solution (Python):
class Card:
    def __init__(self, mark, value):
        self.mark = mark
        self.value = value

    def __eq__(self, other):
        if not isinstance(other, Card):
            return NotImplemented
        return self.value == other.value and self.mark == other.mark

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

    def __str__(self):
        return self.mark + str(self.value)


def BubbleSort(arr):
    res = [Card(c.mark, c.value) for c in arr]
    swap_flg = True
    i = 0
    while swap_flg:
        swap_flg = False
        for j in range(len(res) - 1, i, -1):
            if (res[j] < res[j - 1]):
                res[j], res[j - 1] = res[j - 1], res[j]
                swap_flg = True
        i += 1
    return res


def SelectionSort(arr):
    res = [Card(c.mark, c.value) for c in arr]
    for i in range(0, len(res)):
        minj = i
        for j in range(i, N):
            if res[j] < res[minj]:
                minj = j
        if (i != minj):
            res[i], res[minj] = res[minj], res[i]
    return res


def isStable(in_arr, out_arr):
    stable_arr = BubbleSort(in_arr)
    return all(out_arr[i] == stable_arr[i] for i in range(0, len(out_arr)))


N = int(input())
arr = [Card(s[0], int(s[1])) for s in input().split()]
b_arr = BubbleSort(arr)
print(' '.join(map(str, b_arr)))
print('Stable' if isStable(arr, b_arr) else 'Not stable')
s_arr = SelectionSort(arr)
print(' '.join(map(str, s_arr)))
print('Stable' if isStable(arr, s_arr) else 'Not stable')

Solution (Python):
class Card:
    def __init__(self, mark, value):
        self.mark = mark
        self.value = value

    def __eq__(self, other):
        if not isinstance(other, Card):
            return NotImplemented
        return self.value == other.value and self.mark == other.mark

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

    def __str__(self):
        return self.mark + str(self.value)


def BubbleSort(arr):
    res = [Card(c.mark, c.value) for c in arr]
    swap_flg = True
    i = 0
    while swap_flg:
        swap_flg = False
        for j in range(len(res) - 1, i, -1):
            if (res[j] < res[j - 1]):
                res[j], res[j - 1] = res[j - 1], res[j]
                swap_flg = True
        i += 1
    return res


def SelectionSort(arr):
    res = [Card(c.mark, c.value) for c in arr]
    for i in range(0, len(res)):
        minj = i
        for j in range(i, N):
            if res[j] < res[minj]:
                minj = j
        if (i != minj):
            res[i], res[minj] = res[minj], res[i]
    return res


def isStable(in_arr, out_arr):
    stable_arr = BubbleSort(in_arr)
    return all(out_arr[i] == stable_arr[i] for i in range(0, len(out_arr)))


N = int(input())
arr = [Card(s[0], int(s[1])) for s in input().split()]
b_arr = BubbleSort(arr)
print(' '.join(map(str, b_arr)))
print('Stable' if isStable(arr, b_arr) else 'Not stable')
s_arr = SelectionSort(arr)
print(' '.join(map(str, s_arr)))
print('Stable' if isStable(arr, s_arr) else 'Not stable')

Solution (Python):
import copy
N = int(input())
A = input().split()
B = copy.copy(A)
boo = 1
while boo:
    boo = 0
    for i in range(N-1):
        if A[i][1] > A[i+1][1]:
            A[i], A[i+1] = A[i+1], A[i]
            boo = 1
print(*A)
print("Stable")
for i in range(N):
    mi = i
    for j in range(i,N):
        if B[mi][1] > B[j][1]:
            mi = j
    B[i], B[mi] = B[mi], B[i]
if A==B:
    print(*B)
    print("Stable")
else:
    print(*B)
    print("Not stable")

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

def selectionSort(cards,N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if cards.numbers[j] < cards.numbers[minj]:
                minj = j
        if minj != i:
            cards.swap(i, minj)
    return cards

class Cards(object):
    
    def __init__(self, cards):
        self.cards = cards
        self.numbers = [int(card[1]) for card in cards]

    def filter_by_number(self, number):
        return [card for card in self.cards if card.endswith(str(number))]

    def swap(self, i, j):
        self.cards[i], self.cards[j] = self.cards[j], self.cards[i]
        self.numbers = [int(card[1]) for card in self.cards]

    def show(self):
        print(' '.join(self.cards))

    def is_stable(self, cards):
        for n in range(1,10):
            suits_x = self.filter_by_number(str(n))
            suits_y = cards.filter_by_number(str(n))
            if suits_x != suits_y:
                return False
        return True

    def copy(self):
        return Cards([card for card in self.cards])

def run():
    n = int(input())
    cards = Cards(input().split())
    cards_sorted = bubbleSort(cards.copy(),n)
    cards_sorted.show()
    if cards.is_stable(cards_sorted):
        print('Stable')
    else:
        print('Not stable')

    cards_sorted = selectionSort(cards.copy(),n)
    cards_sorted.show()
    if cards.is_stable(cards_sorted):
        print('Stable')
    else:
        print('Not stable')

if __name__ == '__main__':
    run()

Solution (Python):
import copy

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

def is_stable(sorted_list):
    for i in range(len(sorted_list)-1):
        if sorted_list[i][1] == sorted_list[i+1][1]:
            for j in range(len(A)):
                if A[j] == sorted_list[i]:
                    smaller_idx = j
                if A[j] == sorted_list[i+1]:
                    larger_idx = j
            if smaller_idx > larger_idx:
                return False
    return True

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

def bubble_sort(A1):
    flg = True
    while flg:
        for i in range(N):
            flg = False
            for j in range(N-1, i, -1):
                if int(A1[j-1][1]) > int(A1[j][1]):
                    A1[j-1], A1[j] = A1[j], A1[j-1]
                    flg = True
    print(" ".join(A1))
    print_stable_or_not(is_stable(A1))

def insertion_sort(A2):
    for i in range(N-1):
        min_idx = i
        for j in range(i+1, N):
            if int(A2[min_idx][1]) > int(A2[j][1]):
                min_idx = j
        if min_idx != i:
            A2[i], A2[min_idx] = A2[min_idx], A2[i]
    print(" ".join(A2))
    print_stable_or_not(is_stable(A2))

if __name__ == '__main__':
    A1 = copy.deepcopy(A)
    A2 = copy.deepcopy(A)
    bubble_sort(A1)
    insertion_sort(A2)

Solution (Python):
import copy

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

def is_stable(sorted_list):
    for i in range(len(sorted_list)-1):
        if sorted_list[i][1] == sorted_list[i+1][1]:
            for j in range(len(A)):
                if A[j] == sorted_list[i]:
                    smaller_idx = j
                if A[j] == sorted_list[i+1]:
                    larger_idx = j
            if smaller_idx > larger_idx:
                return False
    return True

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

def bubble_sort(A1):
    flg = True
    while flg:
        for i in range(N):
            flg = False
            for j in range(N-1, i, -1):
                if int(A1[j-1][1]) > int(A1[j][1]):
                    A1[j-1], A1[j] = A1[j], A1[j-1]
                    flg = True
    print(" ".join(A1))
    print_stable_or_not(is_stable(A1))

def insertion_sort(A2):
    for i in range(N-1):
        min_idx = i
        for j in range(i+1, N):
            if int(A2[min_idx][1]) > int(A2[j][1]):
                min_idx = j
        if min_idx != i:
            A2[i], A2[min_idx] = A2[min_idx], A2[i]
    print(" ".join(A2))
    print_stable_or_not(is_stable(A2))

if __name__ == '__main__':
    A1 = copy.deepcopy(A)
    A2 = copy.deepcopy(A)
    bubble_sort(A1)
    insertion_sort(A2)

Solution (Python):
def bubbleSort(cards):
    n = len(cards)
    for i in range(n):
        for j in range(n-1, i, -1):
            if cards[j][1] < cards[j-1][1]:
                cards[j], cards[j-1] = cards[j-1], cards[j]
    
    return cards


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


def isStableSort(initialArray, resultArray):
    n = len(initialArray)
    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 initialArray[i][1] == initialArray[j][1]:
                        if initialArray[i] == resultArray[b]:
                            if initialArray[j] == resultArray[a]:
                                return False
    
    return True


n = int(input())
array = [x for x in input().split()]
cards = [[a[0], a[1]] for a in array]
cardsForBubble = cards[:]
cardsForSelection = cards[:]

bSort = bubbleSort(cardsForBubble)
sSort = selectionSort(cardsForSelection)

resultForBubble = []
resultForSelection = []

for b in bSort:
    resultForBubble.append(''.join(b))
for s in sSort:
    resultForSelection.append(''.join(s))

print(*resultForBubble)
if isStableSort(array, resultForBubble):
    print("Stable")
else:
    print("Not stable")

print(*resultForSelection)
if isStableSort(array, resultForSelection):
    print("Stable")
else:
    print("Not stable")

Solution (Python):
N = int(input())
l = input().split()
l2 = l[:]
for j in range(N):
    for i in range(N-1):
        if l[i][1] > l[i+1][1]:
            l[i], l[i+1] = l[i+1], l[i]
for i in range(0,len(l)-1):
    print(l[i],end=' ')
print(l[N-1])
print("Stable")

for j in range(0,len(l2)-1):
    min = l2[j][1]
    a = j
    for i in range(j,len(l2)):
        if min > l2[i][1]:
            min = l2[i][1]
            a = i
    l2[j],l2[a] = l2[a],l2[j]
for i in range(0,len(l2)-1):
    print(l2[i],end=' ')
print(l2[N-1])
if l==l2:
    print("Stable")
else:
    print("Not stable")

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

def BubbleSort(C, n):
    for i in range(n-1):
        for w in range(i+1, n):
            j = n-w+i
            if (C[j][1] < C[j-1][1]):
                a = C[j]
                C[j] = C[j-1]
                C[j-1] = a
def SelectionSort(C, n):
    for i in range(n):
        mini = i
        for j in range(i+1,n):
            if (C[j][1] < C[mini][1]):
                mini = j
        if(mini != i):
            a = C[i]
            C[i] = C[mini]
            C[mini] = a

def stable(A,B):
    count = [0 for i in range(9)]
    for l in A:
        count[int(l[1]) - 1] += 1
    ilist = [] 
    for i in range(1,10):
        if (count[i-1] > 1):
            awlist = []
            for l in A:
                if(int(l[1]) == i):
                    awlist.append(l[0])
            bwlist = []
            for l in B:
                if(int(l[1]) == i):
                    bwlist.append(l[0])
            if (awlist == bwlist):
                ilist.append(i)
            
        else:
            ilist.append(i)
    if (len(ilist) == 9):
        print('Stable',end = '')
    else:
        print('Not stable', end = '')
                  

Blist = list(clist)
BubbleSort(Blist, n)
for i in range(n):
    if (i == n-1):
        print('{}{}'.format(Blist[i][0],Blist[i][1]), end = '')
    else : 
        print('{}{}'.format(Blist[i][0],Blist[i][1]), end = ' ')
print()
stable(clist, Blist)
print()

Slist = list(clist)
SelectionSort(Slist, n)
for i in range(n):
    if(i == n-1):
        print('{}{}'.format(Slist[i][0],Slist[i][1]), end = '')
    else:
        print('{}{}'.format(Slist[i][0],Slist[i][1]), end = ' ')
print()
stable(clist, Slist)
print()

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

def BubbleSort(C, n):
    for i in range(n-1):
        for w in range(i+1, n):
            j = n-w+i
            if (C[j][1] < C[j-1][1]):
                a = C[j]
                C[j] = C[j-1]
                C[j-1] = a
def SelectionSort(C, n):
    for i in range(n):
        mini = i
        for j in range(i+1,n):
            if (C[j][1] < C[mini][1]):
                mini = j
        if(mini != i):
            a = C[i]
            C[i] = C[mini]
            C[mini] = a

def stable(A,B):
    count = [0 for i in range(9)]
    for l in A:
        count[int(l[1]) - 1] += 1
    ilist = [] 
    for i in range(1,10):
        if (count[i-1] > 1):
            awlist = []
            for l in A:
                if(int(l[1]) == i):
                    awlist.append(l[0])
            bwlist = []
            for l in B:
                if(int(l[1]) == i):
                    bwlist.append(l[0])
            if (awlist == bwlist):
                ilist.append(i)
            
        else:
            ilist.append(i)
    if (len(ilist) == 9):
        print('Stable',end = '')
    else:
        print('Not stable', end = '')
                  

Blist = list(clist)
BubbleSort(Blist, n)
for i in range(n):
    if (i == n-1):
        print('{}{}'.format(Blist[i][0],Blist[i][1]), end = '')
    else : 
        print('{}{}'.format(Blist[i][0],Blist[i][1]), end = ' ')
print()
stable(clist, Blist)
print()

Slist = list(clist)
SelectionSort(Slist, n)
for i in range(n):
    if(i == n-1):
        print('{}{}'.format(Slist[i][0],Slist[i][1]), end = '')
    else:
        print('{}{}'.format(Slist[i][0],Slist[i][1]), end = ' ')
print()
stable(clist, Slist)
print()

Solution (Python):


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

    def __str__(self):
        return self.suit + str(self.value)

def swap(A, i, j):
    tmp  = A[i]
    A[i] = A[j]
    A[j] = tmp

def BubbleSort(C, N):
    for i in range(N):
        for j in range(N-1, i, -1):
            if C[j].value < C[j-1].value:
                swap(C, j, j-1)  

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
        swap(C, i, minj)  

def isStable(A, B):
    for i in range(1, len(B)):
        if B[i-1].value == B[i].value:
            for j in range(len(A)):
                if A[j] == B[i-1]: break
                if A[j] == B[i]:   return False
    return True

N = int(input())
A = [Card(t) for t in input().split()]
if len(A) != N: raise

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

Solution (Python):
n = int(input())
*A, = input().split()
B = A[:]
for i in range(n):
    for j in range(n-1, i, -1):
        if A[j][1] < A[j-1][1]:
            A[j], A[j-1] = A[j-1], A[j]
print(*A)
print("Stable")
 
for i in range(n):
    minj = i
    for j in range(i, n):
        if B[j][1] < B[minj][1]:
            minj = j
    B[i], B[minj] = B[minj], B[i]
print(*B)
if A == B:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
from copy import copy

def bubbleSort(arr):
    cp_arr = copy(arr)
    indices = list(range(len(cp_arr)))
    
    finished_flag = False
    while not finished_flag:
        finished_flag = True

        for i in range(len(cp_arr)-1):
            if cp_arr[i] > cp_arr[i+1]:
                finished_flag = False

                t = cp_arr[i]
                cp_arr[i] = cp_arr[i+1]
                cp_arr[i+1] = t

                t = indices[i]
                indices[i] = indices[i+1]
                indices[i+1] = t
    return indices

def selectionSort(arr):
    cp_arr = copy(arr)
    indices = list(range(len(cp_arr)))

    for i in range(len(cp_arr)):
        min = i
        for j in range(i+1, len(cp_arr)):
            if cp_arr[j] < cp_arr[min]:
                min = j

        t = cp_arr[i]
        cp_arr[i] = cp_arr[min]
        cp_arr[min] = t

        t = indices[i]
        indices[i] = indices[min]
        indices[min] = t

    return indices

if __name__ == "__main__":
    input()
    cards = input().split()
    values = list(map(lambda x: int(x[1]), cards))
    bubbleSorted_indices = bubbleSort(values)
    selectionSorted_indices = selectionSort(values)
    bubble_stable = True
    selection_stable = True
    for i in range(len(values)-1):
        if values[bubbleSorted_indices[i]] == values[bubbleSorted_indices[i+1]] and bubbleSorted_indices[i] > bubbleSorted_indices[i+1]:
            bubble_stable = False
        if values[selectionSorted_indices[i]] == values[selectionSorted_indices[i+1]] and selectionSorted_indices[i] > selectionSorted_indices[i+1]:
            selection_stable = False
    bubble_sorted = [cards[i] for i in bubbleSorted_indices]
    selection_sorted = [cards[i] for i in selectionSorted_indices]
    print(" ".join(bubble_sorted))
    print("Stable" if bubble_stable else "Not stable") 
    print(" ".join(selection_sorted))
    print("Stable" if selection_stable else "Not stable")

Solution (Python):
input_line = int(input())
out_selection = input().split()
out_bubble = out_selection[:]


for i in range(input_line):
    for j in range(input_line-1, i, -1):
        if out_bubble[j][1] < out_bubble[j-1][1]:
            out_bubble[j], out_bubble[j-1] = out_bubble[j-1],out_bubble[j]
print(*out_bubble)
print("Stable")


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

print(*out_selection)
print("Stable" if out_bubble == out_selection else "Not stable")