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

Solution (Python):
def bubble(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 bubble_sort(A, N):
	cnt = 0
	flag = 1
	while flag:
		flag = 0
		for i in range(N-1, 0, -1):
			if A[i][1:] < A[i-1][1:]:
				temp = A[i]
				A[i] = A[i-1]
				A[i-1] = temp
				flag = 1

	return A

def selection_sort(A, N):
	cnt = 0
	for i in range(N):
		minj = i
		for j in range(i, N):
			if A[j][1:] < A[minj][1:]:
				minj = j
		A[i], A[minj] = A[minj], A[i]

	return A

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

B = bubble_sort(copy.copy(A), N)
print(' '.join(B))
print('Stable')
C = selection_sort(copy.copy(A), N)
print(' '.join(C))
if B==C:
	print('Stable')
else:
	print('Not stable')

Solution (Python):
n = int(input())
cards = input().split()
cards_s, cards_b = cards[:], cards[:]
flag_s, flag_b = False, False
for i in range(n):
    
    mini = i
    for j in range(i, n):
        if cards_s[j][1] < cards_s[mini][1]:
            mini = j
    if mini != i:
        cards_s[i], cards_s[mini] = cards_s[mini], cards_s[i]
    
    for j in range(n-1, i, -1):
        if cards_b[j][1] < cards_b[j-1][1]:
            cards_b[j], cards_b[j-1] = cards_b[j-1], cards_b[j]
for i in range(n-1):
    for j in range(i+1,n):
        
        if cards_s[i][1] == cards_s[j][1]:
            flag_s = flag_s or (cards.index(cards_s[i]) > cards.index(cards_s[j]))
        
        if cards_b[i][1] == cards_b[j][1]:
            flag_b = flag_b or (cards.index(cards_b[i]) > cards.index(cards_b[j]))

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

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

Solution (Python):
def BubbleSort(A):
    loop = len(A)-1
    for i in range(loop):
        for j in range(loop-i):
            if A[j][1] > A[j+1][1]:
                A[j],A[j+1] = A[j+1],A[j]

    
def SelectionSort(A):
    loop = len(A)-1
    for i in range(loop):
        mini = i
        for j in range(i+1,loop+1):
            if A[j][1] < A[mini][1]:
                mini = j
        if i != mini:
            A[i],A[mini]=A[mini],A[i]            

    
N = int(input())
S = input().strip().split()
SS = S.copy()

BubbleSort(S)
for i in range(N):
    if i == N-1:
        print(S[i])
    else:
        print(S[i],end=' ')
print('Stable')

        
SelectionSort(SS)
for i in range(N):
    if i == N-1:
        print(SS[i])
    else:
        print(SS[i],end=' ')
if SS == S:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
def bubbleSort(A,N):
    flag = 1
    sortedIndex = 0
    i = 0
    while flag == 1:
        flag = 0
        for j in range(N-1,sortedIndex,-1):
            if int(A[j][1]) < int(A[j-1][1]):
                v = A[j]
                A[j] = A[j-1]
                A[j-1] = v
                flag = 1
                i += 1

def selectionSort(A,N):
    for i in range(N):
        minj = i
        for j in range(i+1,N):
            if int(A[j][1]) < int(A[minj][1]):
                minj = j
        v = A[i]
        A[i] = A[minj]
        A[minj] = v

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

def bubble_is_stable(A,N):
    bubble = A.copy()
    bubbleSort(bubble,N)
    bubble_is_stable = isStable(A,bubble,N)
    bubblestr = ''
    for i in range(N):
        bubblestr += "{} ".format(bubble[i])
    print(bubblestr[:len(bubblestr)-1])
    if bubble_is_stable:
        print('Stable')
    else:
        print('Not stable')

def selection_is_stable(A,N):
    selection = A.copy()
    selectionSort(selection,N)
    selection_is_stable = isStable(A,selection,N)
    selectionstr = ''
    for i in range(N):
        selectionstr += "{} ".format(selection[i])
    print(selectionstr[:len(selectionstr)-1])
    if selection_is_stable:
        print('Stable')
    else:
        print('Not stable')

if __name__ == '__main__':
    N = int(input())
    A = [ _ for _ in input().split()]
    bubble_is_stable(A,N)
    selection_is_stable(A,N)

Solution (Python):
n = int(input())
a = list(input().split())
b = a[:]
s = "Stable"
c, d = [[] for i in range(9)], [[] for i in range(9)]
for i in range(n):
    c[int(a[i][1])-1].append(a[i][0])
for _ in range(n):
    for i in range(n-1,0,-1):
        if int(b[i][1]) < int(b[i-1][1]):
            b[i], b[i-1] = b[i-1], b[i]
print(" ".join(map(str,b)))
print(s)
for i in range(n):
    min = a[n-1]
    ch = n - 1
    for j in range(n-2,i-1,-1):
        if int(a[j][1]) <= int(min[1]):
            min = a[j]
            ch = j
    a[i], a[ch] = a[ch], a[i]
for i in range(n):
    d[int(a[i][1])-1].append(a[i][0])
if c != d:
    s = "Not stable"
print(" ".join(map(str,a)))
print(s)

Solution (Python):


import re

N = int(input())

def val(stri):
    a = re.sub(r'\D', '', stri)
    a = int(a)
    return a

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

def selec_sort(N, A):
    for i in range(N):
        minj = i
        for j in range(i + 1, N):
            if val(A[j]) < val(A[minj]):
                minj = j
        A[i], A[minj] = A[minj], A[i]
    return A
    
def isStable(inp, out):
    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 val(inp[i]) == val(inp[j]) and inp[i] == out[b] and inp[j] == out[a]:
                        return False
    return True



def main():
    A = input().split()

    ST = ''
    for i in A:
        ST += i + ' '
    ST.rstrip(' ')

    bubble_sort(N, A)
    B = ST.split()

    print(*A)
    


    if isStable(A, B):
        print('Stable')
    else:
        print('Not stable')
    A = ST.split()
    selec_sort(N, A)
    B = ST.split()

    print(*A)
    

    if isStable(A, B):
        print('Stable')
    else:
        print('Not stable')

main()

Solution (Python):
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-1], C[j] = C[j], C[j-1]


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]


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

C1 = cards.copy()
bubble_sort(C1, N)
print(" ".join(C1))
print("Stable")

C2 = cards.copy()
selection_sort(C2, N)
print(" ".join(C2))
if C1 == C2:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
n = int(input())
a = [i for i in input().split()]
b = [a[i] for i in range(n)]
def bubbleSort(A):
    for i in range(n):
        for j in range(i+1,n)[::-1]:
            if int(A[j][1]) < int(A[j-1][1]):
                A[j], A[j-1] = A[j-1], A[j]
    return A

def selectionSort(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]
    return A

bubbleSort(a)
selectionSort(b)

print(' '.join(a))
print("Stable")
print(' '.join(b))
if a == b:
    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 C[j][1]<C[j-1][1]:
                C[j], C[j-1] = C[j-1], C[j]
    return C
 
def selectionSort(C, N):
    for i in range(0, 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
 
def check(C0, C1):
    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 C0[i][1] == C0[j][1] and C0[i] == C1[b] and C0[j] == C1[a]:
                        return False
    return True
 
def toStr(a):
    return str(a[0])+str(a[1])
 
N = int(input())
src = [(str(char[0]), int(char[1])) for char in input().split()]
 
out_1 = bubbleSort(src[:], N)
out_2 = selectionSort(src[:], N)


for out in [out_1, out_2]:
    ans = map(toStr, out)
    print(*ans)
    if check(src, out):
        print('Stable')
    else:
        print('Not stable')

Solution (Python):
def readInt():
  return int(input())


def bubleSort(l, n):
    for i in range(1, n):
        for j in range(n - i):
            if l[j][1] > l[j + 1][1]:
                l[j], l[j + 1] = l[j + 1], l[j]
    return l


def selectionSort(l, n):
    for i in range(n):
        mini = i
        for j in range(i, n):
            if l[j][1] < l[mini][1]:
                mini = j
        l[i], l[mini] = l[mini], l[i]
    return l

def readInts():
  return [int(i) for i in input().split()]
N = readInt()
AS = input().split()

import copy

stable = bubleSort(copy.deepcopy(AS), N)
notstable = selectionSort(AS, N)

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

Solution (Python):
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]
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]
n = int(input())
a = list(input().split())
b = [i for i in a]
bubblesort(a, n)
selectionsort(b, n)
print(' '.join(a))
print('Stable')
print(' '.join(b))
print('Stable' if a == b else 'Not stable')

Solution (Python):
def bubble_sort(A,N,M):
    flag = 1
    while flag:
        flag = 0
        for i in range(N-1,0,-1):
            if A[i] < A[i-1]:
                tmp = A[i]
                tmp2 = M[i]
                A[i] = A[i-1]
                M[i] = M[i-1]
                A[i-1] = tmp
                M[i-1] = tmp2
                flag = 1
    return M

def choice_sort(A,N,M):
    for i in range(N):
        top = A[i]
        tp = M[i]
        mini = min(A[i:])
        if top > mini:
            tmp = top
            tmpIndex = A[i:].index(mini) + i
            A[i] = mini
            A[tmpIndex] = tmp
            M[i] = M[tmpIndex]
            M[tmpIndex] = tp
    return M

time = int(input())
nums = list(input().split(" "))
numnum = []
for i in nums:
    numnum.append(list(i)[1])
numnum2 = numnum.copy()
memo = []
for i in range(time):
    memo.append(i)
memo2 = memo.copy()

bubble_order = bubble_sort(numnum,time,memo)
answer = ""
for i in bubble_order:
    answer += str(nums[i])
    answer += ' '
print(answer[:-1])
print("Stable")

choice_order = choice_sort(numnum2,time,memo2)
answer2 = ""
for i in choice_order:
    answer2 += str(nums[i])
    answer2 += ' '
print(answer2[:-1])


if answer[:-1] == answer2[:-1]:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
class Card:
    def __init__(self, suit='', num=''):
        self.suit = suit
        self.num = num
    def __str__(self):
        return "" + self.suit + self.num

def bubble_sort(list):
    for i in range(n):
        for j in range(n - 1, i, -1):
            if list[j].num < list[j - 1].num:
                tmp = list[j]
                list[j] = list[j - 1]
                list[j - 1] = tmp

def selection_sort(list):
    for i in range(n):
        mini = i
        for j in range(i+1, n):
            if list[j].num < list[mini].num:
                mini = j
        tmp = list[mini]
        list[mini] = list[i]
        list[i] = tmp

n = int(input())
inputs = [string for string in input().split(" ")]

cards = []
for i in range(n):
    cards.append(Card(inputs[i][0], inputs[i][1]))

selection_cards = cards.copy()

bubble_sort(cards)
selection_sort(selection_cards)

bubble_result = str(cards[0])
for i in range(1, n):
    bubble_result += " " + str(cards[i]);
print(bubble_result)
print("Stable")

selection_result = str(selection_cards[0])
stable_flag = (cards[0] == selection_cards[0])
for i in range(1, n):
    if cards[i] != selection_cards[i]:
        stable_flag = False
    selection_result += " " + str(selection_cards[i])
print(selection_result)
if stable_flag:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
import copy as c
n,*a=open(0).read().split()
n=int(n)
b=c.deepcopy(a)
for i in range(n):
    for j in range(n-1,0,-1):
        if int(b[j][1])<int(b[j-1][1]):
            b[j],b[j-1]=b[j-1],b[j]
print(*b)
print("Stable")

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]
print(*a)
if a!=b:
    print("Not stable")
else:
    print("Stable")

Solution (Python):
import copy


def bubble(_v):
    v = copy.copy(_v)
    n = len(v)
    for i in range(n):
        for j in range(n-1, i, -1):
            if v[j][1] < v[j-1][1]:
                v[j], v[j-1] = v[j-1], v[j]
    return v


def selection(_v):
    v = copy.copy(_v)
    n = len(v)
    for i in range(n):
        mi = i
        for j in range(i, n):
            if v[j][1] < v[mi][1]:
                mi = j
        v[i], v[mi] = v[mi], v[i]
    return v


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

b = bubble(v)
s = selection(v)
print(" ".join(b))
print("Stable")
print(" ".join(s))
print("Stable" if b == s else "Not stable")

Solution (Python):
import copy

def bublesort(array, n):
    flag = 1
    while(flag):
        i=0
        flag=0
        for j in range(len(array)-1, i, -1):
            if array[j][1] < array[j-1][1]:
                array[j],array[j-1] = array[j-1],array[j]
                flag = 1
        i += 1

def selectionsort(array,n):
    for i in range(len(array)):
        minj = i
        for j in range(i,len(array)):
            if array[j][1] < array[minj][1]:
                minj = j
        array[minj],array[i] = array[i],array[minj]

factor = int(input())
numbers = input().split()
numbers_select = copy.deepcopy(numbers)


bublesort(numbers,factor)
selectionsort(numbers_select,factor)

print(" ".join(list(map(str, numbers))))
print("Stable")

print(" ".join(list(map(str, numbers_select))))
print("Stable") if numbers == numbers_select else print("Not stable")

Solution (Python):
N = int(input())
A = input()
B = A.split()
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")

C = A.split()
for i in range(N) :
    mini = i
    for j in range(i, N) :
        if int(C[j][1]) < int(C[mini][1]) :
            mini = j
    C[i], C[mini] = C[mini], C[i]
print(" ".join(C))
if B == C :
    print("Stable")
else :
    print("Not stable")

Solution (Python):
def swap(a, i, j):
    
    k = a[j]
    a[j] = a[i]
    a[i] = k


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


def bubbleSort(a, n):
    flag = 1
    while flag:
        flag = 0
        for j in range(n-1,0,-1):
            if a[j][1] < a[j-1][1]:
                swap(a, j-1, j)
                flag = 1


n = int(input())
a = list(input().split())
b = a[:]
bubbleSort(a, n)
print(' '.join(a))
print('Stable')
selectionSort(b, n)
print(' '.join(b))
if a == b:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
n = int(input())
a1 = input().split()
a2 = a1[:]
i = 0
flag = 1
while flag:
    flag = 0
    for j in range(n - 1, i, -1):
        if int(a1[j][1]) < int(a1[j - 1][1]):
            flag = 1
            a1[j], a1[j - 1] = a1[j - 1], a1[j]
    i += 1
print(" ".join(a1))
print("Stable")


for i in range(n):
    minj = i
    for j in range(i, n):
        if int(a2[j][1]) < int(a2[minj][1]):
            minj = j
    if minj != i:
        a2[i], a2[minj] = a2[minj], a2[i]
print(" ".join(a2))
if a1 == a2:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
n = int(input())
cards = list(input().split())
cards1 = cards.copy()
















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

    return cards


def SelectionSort(cards):
    cnt = 0
    for i in range(n):
        minj = i
        for j in range(i,n):
            if int(cards[minj][1]) > int(cards[j][1]):
                minj = j
        if i != minj:
            cnt += 1
        cards[i], cards[minj] = cards[minj], cards[i]

    return cards

a = BubbleSort(cards)
b = SelectionSort(cards1)

print(*a)
print("Stable")
print(*b)
if a == b:
    print("Stable")
else:
    print("Not stable")

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

Solution (Python):
def judegStable(A, B):
    num_dict_input = dict(zip(map(lambda x: str(x), range(1, 10)), [[]] * 9))
    num_dict_output = dict(zip(map(lambda x: str(x), range(1, 10)), [[]] * 9))

    for i in range(0, N):
        num_dict_input[A[i][1]] = num_dict_input[A[i][1]] + [A[i]]
        num_dict_output[B[i][1]] = num_dict_output[B[i][1]] + [B[i]]
    for key, val in num_dict_input.items():
        for i in range(len(val)):
            if val[i] != num_dict_output[key][i]:
                print "Not stable"
                return False
    print "Stable"
    return True


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

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

N = input()
line_ = raw_input()
line = line_.strip().split()
line2 = line_.strip().split()
line3 = line_.strip().split()

output_bubble = bubbleSort(line, N)
print(' '.join(output_bubble))
judegStable(line2, output_bubble)

output_select = selectionSort(line2, N)
print(' ' .join(output_select))
judegStable(line3, output_select)