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

def bubble(N, A):
    for i in range(N - 1):
        for j in reversed(range(1, N)):
            if A[j - 1][1] > A[j][1]:
                tmp = A[j]
                A[j] = A[j - 1]
                A[j - 1] = tmp

def select(N, A):
    for i in range(N):
        min = i
        for j in range(i, N):
            if A[min][1] > A[j][1]:
                min = j
        tmp = A[i]
        A[i] = A[min]
        A[min] = tmp

def st(B, S):
    for i in range(N):
        if B[i] != S[i]:
            return False
    return True

N = int(input())

S = [i for i in input().split()]
B = copy.deepcopy(S)

bubble(N, B)
select(N, S)

print(" ".join(B))
print("Stable")
print(" ".join(S))
if st(B, S) == True:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
import copy

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]

def selection_sort(C, N):
    for i in range(N):
        minj = i
        for j in range(i+1, N):
            if C[j][1] < C[minj][1]:
                minj = j
        C[i], C[minj] = C[minj], C[i]

def is_stable(in0, out0):
    for m in '123456789':
        in1 = list(filter(lambda e:e[1]==m, in0))
        out1 = list(filter(lambda e:e[1]==m, out0))
        
        if in1 != out1:
            return 'Not stable'
    return 'Stable'

N = int(input())
C = list(input().split())
C1 = copy.deepcopy(C)
C2 = copy.deepcopy(C)
bubble_sort(C1, N)
selection_sort(C2, N)
print(*C1)
print(is_stable(C, C1))
print(*C2)
print(is_stable(C, C2))

Solution (Python):
n = int(input())
c = input().split()

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

cs = c[:]
for i in range(n):
	m = min(range(i,n), key=lambda j: cs[j][1])
	if i != m:
		cs[i],cs[m] = cs[m],cs[i]
print(*cs)
print('Stable' if cb == cs else 'Not stable')

Solution (Python):
import copy

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

def SelectionSort(arr):
	n=len(arr)
	for i in range(n):
		minp=i
		for j in range(i,n):
			if int(arr[j][1])<int(arr[minp][1]):
				minp=j
		arr[minp],arr[i]=arr[i],arr[minp]
	return arr
  
def IsStable(basearr,resultarr):
  checkarr1=[[] for _ in range(14)]
  checkarr2=[[] for _ in range(14)]
  for i in range(len(basearr)):
    checkarr1[int(basearr[i][1])].append(basearr[i][0])
    checkarr2[int(resultarr[i][1])].append(resultarr[i][0])
  if checkarr1==checkarr2:
    print('Stable')
  else:
    print('Not stable')
  

n=int(input())
arr=list(map(str,input().split()))
bubble=BubbleSort(copy.deepcopy(arr))
selection=SelectionSort(copy.deepcopy(arr))
print(' '.join(map(str,bubble)))
IsStable(arr,bubble)
print(' '.join(map(str,selection)))
IsStable(arr,selection)

Solution (Python):
def bubble_sort(a, n):
    for i in range(n-1):
        for j in range(n-1, i, -1):
            if a[j-1][1] > a[j][1]:
                a[j-1], a[j] = a[j], a[j-1]

    return a


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

    return a


if __name__ == "__main__":
    n = int(input())
    a = input().split()

    result1 = bubble_sort(a[:], n)
    result2 = selection_sort(a[:], n)
    print(*result1)
    print("Stable")
    print(*result2)
    print("Stable" if result1 == result2 else "Not stable")

Solution (Python):
num = int(input())
A = input().split(" ")
B = A.copy()


for i in range(num):
	for j in range(num-1,i,-1):
		
		m1 = int(A[j][1:])
		m2 = int(A[j-1][1:])
		if m1 < m2:
			A[j],A[j-1] = A[j-1],A[j]

print(*A)
print("Stable")


for i in range(num):
	minv = i
	for j in range(i+1,num):
		m1 = int(B[minv][1:])
		m2 = int(B[j][1:])
		if m1 > m2:
			minv = j
	B[i],B[minv] = B[minv],B[i]

print(*B)
if A == B:
	print("Stable")
else:
	print("Not stable")

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

ab=a[:]
flg=True
i=0
while flg:
    flg=False
    for j in range(n-1,i,-1):
        if ab[j][1]<ab[j-1][1]:
            ab[j],ab[j-1]=ab[j-1],ab[j]
            flg=True
    i+=1
print(' '.join(map(str,ab)))
print('Stable')

ac=a[:]
for i in range(n):
    minj=i
    for j in range(i,n):
        if ac[j][1]<ac[minj][1]:
            j,minj=minj,j
    if i!=minj:
        ac[i],ac[minj]=ac[minj],ac[i]
print(' '.join(map(str,ac)))

if ab==ac:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
import time
import copy

def BubbleSort(A, N):
    flag = 1
    while flag:
        flag = 0
        for j in reversed(range(1, N)):
            if A[j]['value']<A[j-1]['value']:
                A[j], A[j-1] = A[j-1], A[j]
                flag = 1
    return A

def SelectionSort(A, N):
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if A[j]['value']<A[minj]['value']:
                minj = j
        if i!=minj:
            A[i], A[minj] = A[minj], A[i]
    return A

def IsStable(answer, target):
    N = len(answer)
    for i in range(N):
        if answer[i]['body'] != target[i]['body']:
            return False
    return True


def main():
    N = int(input())
    A = list(
        map(lambda x: {'body': x, 'value': int(x[1])}, input().split())
    )
    A_sortby_bubble = copy.deepcopy(A)
    A_sortby_select = copy.deepcopy(A)
    A_sortby_bubble = BubbleSort(A_sortby_bubble, N)
    A_sortby_select = SelectionSort(A_sortby_select, N)
    print(' '.join(map(lambda x: x['body'],A_sortby_bubble)))
    print('Stable')
    print(' '.join(map(lambda x: x['body'], A_sortby_select)))
    if IsStable(A_sortby_bubble, A_sortby_select):
        print('Stable')
    else:
        print('Not stable') 
    
main()

Solution (Python):
import copy

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

def bubble_sort(A):
    count = 0
    while True:
        swapped = False
        for i in range(len(A)-1):
            if A[i+1].number < A[i].number:
                A[i+1], A[i] = A[i], A[i+1]
                count += 1
                swapped = True
        if not swapped:
            return count

def selection_sort(A):
    count = 0
    for i in range(len(A)):
        min_value = A[i].number
        min_value_index = i
        
        for j in range(i, len(A)):
            
            
            if A[j].number < min_value:
                min_value = A[j].number
                min_value_index = j
        
        if i != min_value_index:
            count += 1
            A[i], A[min_value_index] = A[min_value_index], A[i]
            
        
    return count

n = int(input())
A = []
for row in input().split():
    suit, number = list(row)
    A.append(Card(suit, int(number)))

def is_stable(A, B):
    N = len(A)
    for i_A in range(N-1):
        for j_A in range(i_A+1, N):
            for i_B in range(N-1):
                for j_B in range(i_B+1, N):
                    if A[i_A].number == A[j_A].number and A[i_A].view == B[j_B].view and A[j_A].view == B[i_B].view:
                        return False

    return B

bubble_sort_A = copy.deepcopy(A)
selection_sort_A = copy.deepcopy(A)

bubble_sort(bubble_sort_A)
print(*[elem.view for elem in bubble_sort_A])
if is_stable(A, bubble_sort_A):
    print('Stable')
else:
    print('Not stable')

selection_sort(selection_sort_A)
print(*[elem.view for elem in selection_sort_A])

if is_stable(A, selection_sort_A):
    print('Stable')
else:
    print('Not stable')

Solution (Python):
class Sort():
	def __init__(self,n,cards):
		self.cards = cards
		self.n = n

	def bubble_sort(self):
		
		flag = 1
		while flag != 0:
			flag = 0
			rev = list(range(1,self.n))
			rev.reverse()
			for j in rev:
				if int(self.cards[j][1]) < int(self.cards[j-1][1]):
					self.cards[j],self.cards[j-1] = self.cards[j-1],self.cards[j]
					flag = 1

	def select_sort(self):
		for i in range(self.n):
			mini = i
			for j in range(i,self.n):
				if int(self.cards[j][1]) < int(self.cards[mini][1]):
					mini = j
			if i != mini:
				self.cards[i],self.cards[mini] = self.cards[mini],self.cards[i]

	def check_stable(self,origin):
		check_org = [["" for i in range(self.n)] for k in range(9)]
		check_sort = [["" for i in range(self.n)] for k in range(9)]
		for i in range(self.n):
			check_org[int(origin[i][1])-1][i] = origin[i][0]
			check_sort[int(self.cards[i][1])-1][i] = self.cards[i][0]
		flag = 0
		for i in range(9):
			if "".join(check_org[i]) != "".join(check_sort[i]):
				flag = 1
				break

		if flag == 0:
			print("Stable")
		else:
			print("Not stable")

	def print_card(self):
		for i in range(self.n):
			if i != self.n-1:
				print("%s" % (self.cards[i]),end=" ")
			else:
				print("%s" % (self.cards[i]))

if __name__ == '__main__':
	n = int(input())
	card = input().split()
	card2 = card.copy()
	card_origin = card.copy()
	
	bubble = Sort(n,card)
	bubble.bubble_sort()
	bubble.print_card()
	bubble.check_stable(card_origin)
	
	select = Sort(n,card2)
	select.select_sort()
	select.print_card()
	select.check_stable(card_origin)

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

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

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


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


def selection_sort(A):
    n = len(A)
    A = A[:]
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if A[j] < A[min_idx]:
                min_idx = j
        A[min_idx], A[i] = A[i], A[min_idx]
    return A


N = int(input())
A = [Card(s) for s in input().split()]
A_sorted_by_bsort = bubble_sort(A)
A_sorted_by_ssort = selection_sort(A)
print(*A_sorted_by_bsort)
print("Stable")
print(*A_sorted_by_ssort)
print("Stable" if A_sorted_by_ssort == A_sorted_by_bsort else "Not stable")

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

data1 = a[:]
data2 = a[:]

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

	return(data)

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

		data[i],data[minj] = data[minj],data[i]

	return(data)
data1 = bubble_sort(data1)
data2 = selection_sort(data2)
print(*data1)
print("Stable")
print(*data2)
print("Stable" if data1 == data2 else "Not stable")

Solution (Python):
import copy

N = int(input())

def hoge(arg):
    return [arg[0], int(arg[1])]

A = list(map(hoge, map(str, input().split())))
A1 = copy.deepcopy(A)
A2 = copy.deepcopy(A)

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

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

def judge(A, A1):
    for i in range(len(A) - 1):
        if A1[i][1] != A1[i+1][1]:
            continue
        a = A.index(A1[i])
        b = A.index(A1[i+1])
        if a > b:
            return 'Not stable'
    return 'Stable'

def toString(A):
    return A[0] + str(A[1])

bsort(A1, N)
print(' '.join(list(map(toString, A1))))
print(judge(A, A1))
ssort(A2, N)
print(' '.join(list(map(toString, A2))))
print(judge(A, A2))

Solution (Python):
import copy

N = int(input())

def hoge(arg):
    return [arg[0], int(arg[1])]

A = list(map(hoge, map(str, input().split())))
A1 = copy.deepcopy(A)
A2 = copy.deepcopy(A)

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

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

def judge(A, A1):
    for i in range(len(A) - 1):
        if A1[i][1] != A1[i+1][1]:
            continue
        a = A.index(A1[i])
        b = A.index(A1[i+1])
        if a > b:
            return 'Not stable'
    return 'Stable'

def toString(A):
    return A[0] + str(A[1])

bsort(A1, N)
print(' '.join(list(map(toString, A1))))
print(judge(A, A1))
ssort(A2, N)
print(' '.join(list(map(toString, A2))))
print(judge(A, A2))

Solution (Python):

def bubblesort(n, a):
    r = a[:]
    for i in range(n):
        for j in range(n-1, i, -1):
            if int(r[j][1]) < int(r[j-1][1]):
                r[j], r[j-1] = r[j-1], r[j]

    print(*r)
    print("Stable")


def selectionsort(n, a):
    r = a[:]
    ret = "Stable"
    for i in range(n):
        tmp = i
        for j in range(i, n):
            if int(r[j][1]) < int(r[tmp][1]):
                tmp = j
        r[i], r[tmp] = r[tmp], r[i]

    for i in range(n):
        for j in range(i+1, n):
            for k in range(n):
                for l in range(k+1, n):
                    if int(a[i][1]) == int(a[j][1]) and a[i] == r[l] and a[j] == r[k]:
                        ret = "Not stable"

    print(*r)
    print(ret)


def main():
    n = int(input())
    a = list(input().split())

    bubblesort(n, a)
    selectionsort(n, a)


if __name__ == '__main__':
    main()

Solution (Python):


def bubble(nums,N):
    for i in range(N-1): 
        j = N-1
        while j > i:
            if nums[j-1][1] > nums[j][1]:
                nums[j-1], nums[j] = nums[j], nums[j-1]
            j = j - 1 
    return nums

def selection(nums,N):
    for i in range(N-1):
        minj = i
        for j in range(i+1,N): 
            if nums[minj][1] > nums[j][1]:
                minj = j
        if minj != i:
            nums[minj], nums[i] = nums[i], nums[minj]
    return nums

N = int(input())
nums = input().split()
nums2 = nums.copy()



result1 = bubble(nums,N)
print(' '.join(map(str,result1)))
print("Stable")
result2 = selection(nums2,N)
print(' '.join(map(str,result2)))
print("Stable" if result1 == result2 else "Not stable")

Solution (Python):
n = input()
b = raw_input().split()
s = list(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]

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

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

Solution (Python):
N = input()
n = list(raw_input().split())
b = list(n)
for i in range(N-1):
	for j in range(N-i-1):
		if b[j][1] > b[j+1][1]:
			w = b[j]
			b[j] = b[j+1]
			b[j+1] = w
print " ".join(b[i] for i in range(N))
print "Stable"
for i in range(N-1):
	m = i
	for j in range(i+1,N):
		if n[m][1] > n[j][1]:
			m = j
	if m != i:
		w = n[i]
		n[i] = n[m]
		n[m] = w
print " ".join(n[i] for i in range(N))
if b == n:
	print "Stable"
else:
	print "Not stable"

Solution (Python):
def bubble(c):
	for i in range(len(c)):
		for j in range(len(c)-1,i,-1):
			if int(c[j][-1]) < int(c[j-1][-1]):
				c[j],c[j-1] = c[j-1],c[j]
	return c

def selection(c):
	for i in range(len(c)):
		mini = i
		for j in range(i,len(c)):
			if int(c[j][-1])<int(c[mini][-1]):
				mini = j
		c[i],c[mini]=c[mini],c[i]
	return c

n = int(input())
card = list(map(str,input().split()))
card1 = card[:]
bubble(card)
selection(card1)
print(" ".join(map(str,card)))
print("Stable")
print(" ".join(map(str,card1)))
print("Stable") if card==card1 else print("Not stable")

Solution (Python):
def compare_cards(a, b):
    return a[1] < b[1]

def bubble(C):
    for i in range(len(C)):
        for j in range(len(C) - 1, i, -1):
            if compare_cards(C[j], C[j - 1]):
                C[j], C[j - 1] = C[j -1], C[j]

def selection(C):
    for i in range(len(C)):
        mini = i
        for j in range(i, len(C)):
            if compare_cards(C[j], C[mini]):
                mini = j
        C[i], C[mini] = C[mini], C[i]

def check_stable(originC, sortedC):
    for i in range(len(originC) - 1):
        if not compare_cards(sortedC[i], sortedC[i + 1]):
            if originC.index(sortedC[i]) > originC.index(sortedC[i + 1]):
                return 'Not stable'
    return 'Stable'

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

bubbleC = list(C)
selectionC = list(C)

bubble(bubbleC)
selection(selectionC)

print(*bubbleC)
print(check_stable(C, bubbleC))
print(*selectionC)
print(check_stable(C, selectionC))

Solution (Python):
def BubbleSort(A):
    
    flag = 1
    N = len(A)
    
    while flag:
        flag = 0
        for j in xrange(N-1,0,-1):
            if A[j][1] < A[j-1][1]:
                A[j],A[j-1] = A[j-1],A[j]
                flag = 1
                
    return A 

def SelectionSort(A): 
    N = len(A)
    m = 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]
        if i != minj:
            m += 1
    return A

    
N = int(raw_input())
ls = raw_input().split()

tmp = BubbleSort(list(ls))
print ' '.join(map(str,tmp))
print 'Stable'

tmp2 = SelectionSort(list(ls))
print ' '.join(map(str,tmp2))
for k,j in zip(tmp,tmp2):
    if k != j:
        print 'Not stable'
        break
else:
    print 'Stable'

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

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

n = int(input())
l = []
for c in input().split():
    l.append((int(c[1]), c[0]))
    
bl = ' '.join([k + str(n) for n, k in bubbleSort(l[:], n)])
sl = ' '.join([k + str(n) for n, k in selectionSort(l[:], n)])
print(bl)
print('Stable')
print(sl)
print('Stable' if sl == bl else 'Not stable')

Solution (Python):







import sys

ary_len = int(sys.stdin.readline())
ary_str = sys.stdin.readline().rstrip().split(' ')
ary = map(lambda s: (int(s[1]), s), ary_str)


def bubble_sort(a):
    a_len = len(a)
    for i in range(0, a_len):
        for j in reversed(range(i + 1, a_len)):
            if a[j][0] < a[j - 1][0]:
                v = a[j]
                a[j] = a[j - 1]
                a[j - 1] = v


def selection_sort(a):
    a_len = len(a)
    for i in range(0, a_len):
        minj = i;
        for j in range(i, a_len):
            if a[j][0] < a[minj][0]:
                minj = j
        if minj != i:
            v = a[i]
            a[i] = a[minj]
            a[minj] = v

def print_ary(a):
    vals = map(lambda s: s[1], a)
    print ' '.join(vals)

def is_stable(before, after):
    length = len(before)
    for i in range(0, length):
        for j in range(i + 1, length):
            if before[i][0] == before[j][0]:
                v1 = before[i][1]
                v2 = before[j][1]
                for k in range(0, length):
                    if after[k][1] == v1:
                        v1_idx_after = k
                        break
                for k in range(0, length):
                    if after[k][1] == v2:
                        v2_idx_after = k
                        break
                if v1_idx_after > v2_idx_after:
                    return False
    return True

def run_sort(ary, sort_fn):
    ary1 = list(ary)
    sort_fn(ary1)
    print_ary(ary1)
    if is_stable(ary, ary1):
        print 'Stable'
    else:
        print 'Not stable'


run_sort(ary, bubble_sort)
run_sort(ary, selection_sort)

Solution (Python):
MARK = 0
NUMBER = 1


def bubble_sort(A):
    for i in range(len(A)-1):
        for j in reversed(range(i+1, len(A))):
            if A[j][NUMBER] < A[j - 1][NUMBER]:
                swap(A, j-1, j)


def selection_sort(A):
    for i in range(len(A)):
        mini = i
        for j in range(i, len(A)):
            if A[j][NUMBER] < A[mini][NUMBER]:
                mini = j
        if mini != i:
            swap(A, mini, i)


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


amount = int(input())
cards = input().split()  
isStable_selection = True


for i in range(amount):
    cards[i] = tuple([cards[i][MARK], int(cards[i][NUMBER])])

cards_bubble = list(cards)
cards_selection = list(cards)

bubble_sort(cards_bubble)
selection_sort(cards_selection)


if cards_bubble == cards_selection:
    isStable_selection = True
else:
    isStable_selection = False

print(*[cards_bubble[i][MARK] + str(cards_bubble[i][NUMBER])
        for i in range(amount)])
print("Stable")

print(*[cards_selection[i][MARK] + str(cards_selection[i][NUMBER])
        for i in range(amount)])
if isStable_selection:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
def bubbleSort( cards ):
    n = len( cards )
    for i in range( 0, 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]
 
    print( " ".join( map( str, cards ) ) )
 
def selectionSort( cards ):
	n = len( cards )
	for i in range( 0, n ):
		mini = i
		for j in range( i , n ):
			if int( cards[j][1] ) < int( cards[ mini ][1] ):
				mini = j
		if mini != i:
			cards[i], cards[ mini ] = cards[ mini ], cards[i]

	print( " ".join( map( str, cards ) ) )


n = int( raw_input( ) )
cards = raw_input( ).split( " " )
cards2 = list( cards )
bubbleSort( cards )
print( "Stable" )
selectionSort( cards2 )
if " ".join( map( str, cards2 ) ) == " ".join( map( str, cards ) ):
	print( "Stable" )
else:
	print( "Not stable" )

Solution (Python):
def bubbleSort( cards ):
    n = len( cards )
    for i in range( 0, 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]
 
    print( " ".join( map( str, cards ) ) )
 
def selectionSort( cards ):
	n = len( cards )
	for i in range( 0, n ):
		mini = i
		for j in range( i , n ):
			if int( cards[j][1] ) < int( cards[ mini ][1] ):
				mini = j
		if mini != i:
			cards[i], cards[ mini ] = cards[ mini ], cards[i]

	print( " ".join( map( str, cards ) ) )


n = int( input( ) )
cards = input( ).split( " " )
cards2 = list( cards )
bubbleSort( cards )
print( "Stable" )
selectionSort( cards2 )
if " ".join( map( str, cards2 ) ) == " ".join( map( str, cards ) ):
	print( "Stable" )
else:
	print( "Not stable" )

Solution (Python):
def bubbleSort( cards ):
    n = len( cards )
    for i in range( 0, 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]
 
    print( " ".join( map( str, cards ) ) )
 
def selectionSort( cards ):
	n = len( cards )
	for i in range( 0, n ):
		mini = i
		for j in range( i , n ):
			if int( cards[j][1] ) < int( cards[ mini ][1] ):
				mini = j
		if mini != i:
			cards[i], cards[ mini ] = cards[ mini ], cards[i]

	print( " ".join( map( str, cards ) ) )


n = int( raw_input( ) )
cards = raw_input( ).split( " " )
cards2 = list( cards )
bubbleSort( cards )
print( "Stable" )
selectionSort( cards2 )
if cards2 == cards:
	print( "Stable" )
else:
	print( "Not stable" )

Solution (Python):
import collections

Card = collections.namedtuple('Card', ['suit', 'value'])


def bubble_sort(array):
    a = array[::]
    for i in range(len(a)):
        for j in reversed(range(i + 1, len(a))):
            if a[j].value < a[j - 1].value:
                a[j], a[j - 1] = a[j - 1], a[j]
    return a


def selection_sort(array):
    a = array[::]
    for i in range(len(a)):
        min_j = i
        for j in range(i, len(a)):
            if a[j].value < a[min_j].value:
                min_j = j
        a[i], a[min_j] = a[min_j], a[i]
    return a


if __name__ == '__main__':
    n = int(input())
    cards = [Card(suit, int(value)) for suit, value in input().split()]
    stable = sorted(cards, key=lambda a: a.value)

    bubble = bubble_sort(cards)
    print(' '.join(''.join(map(str, card)) for card in bubble))
    print('Stable' if bubble == stable else 'Not stable')

    selection = selection_sort(cards)
    print(' '.join(''.join(map(str, card)) for card in selection))
    print('Stable' if selection == stable else 'Not stable')

Solution (Python):
n = int(input())
c = input().split()
d = c[:]


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


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]

print(*c)
print("Stable" if c == d else "Not stable")

Solution (Python):


def bubbleSort(C, N):
    for i in xrange(N):
        for j in xrange(N-1, i, -1):
            if C[j-1][1] > C[j][1]:
                C[j], C[j-1] = C[j-1], C[j]
    return C

def selectionSort(C, N):
    for i in xrange(N):
        minj = i
        for j in xrange(i, N):
            if C[minj][1] > C[j][1]:
                minj = j
        C[i], C[minj] = C[minj], C[i]
    return C

def isStable(in_, out_, N):
    for i in xrange(N):
        for j in xrange(i + 1, N):
            for a in xrange(N):
                for b in xrange(a + 1, N):
                    if in_[i][1] == in_[j][1] and in_[i] == out_[b] and in_[j] == out_[a]:
                        return False
    return True

def main():
    N = input()
    cards = raw_input().split()
    bubble = bubbleSort(cards[:], N)
    selection = selectionSort(cards[:], N)
    print ' '.join(bubble)
    print 'Stable' if isStable(cards, bubble, N) else 'Not stable'
    print ' '.join(selection)
    print 'Stable' if isStable(cards, selection, N) else 'Not stable'



if __name__ == '__main__':
    main()

Solution (Python):
def compare(s1, s2):
    if s1[1] > s2[1]:
        return 1
    elif s1[1] < s2[1]:
        return -1

    return 0

def bubbleSort(N, A):
    flag = True
    while flag:
        flag = False
        for i in xrange(N-1, 0, -1):
            if compare(A[i-1], A[i]) > 0:
                A[i-1], A[i] = A[i], A[i-1]
                flag = True

def selectSort(N, A):
    for i in xrange(N):
        minj = i
        for j in xrange(i, N):
            if compare(A[j], A[minj]) < 0:
                minj = j
        if minj != i:
            A[i], A[minj] = A[minj], A[i]

N = int(raw_input())
A = raw_input().split()
B = list(A)
bubbleSort(N, A)
print ' '.join(A)
print 'Stable'
selectSort(N, B)
print ' '.join(B)
if A == B:
    print 'Stable'
else:
    print 'Not stable'

Solution (Python):



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

n = int(input())
cardsR = input().split()
cardsS = cardsR[:]

print(' '.join(BubbleSort(cardsR, n)))
print("Stable")
print(*SelectionSort(cardsS, n))
print("Stable" if cardsR == cardsS else "Not stable")

Solution (Python):



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

n = int(input())
cards = input().split()
copy = list(cards)

print(*BubbleSort(cards, n))
print("Stable")
print(*SelectionSort(copy, n))
print("Stable" if cards == copy else "Not stable")

Solution (Python):
N = int(raw_input())
line = raw_input()
A = line.strip().split(" ")
A2 = line.strip().split(" ")
for i in range(0, N):
    min_j = i
    for j in range(i, N):
        if int(A2[j][1:]) < int(A2[min_j][1:]):
            min_j = j
    A2[i], A2[min_j] = A2[min_j], A2[i]
select = " ".join(A2)
flag = True
while flag:
    flag = False
    for j in range(N-1, 0, -1):
        if int(A[j][1:]) < int(A[j-1][1:]):
            A[j], A[j-1] = A[j-1], A[j]
            flag = True
bubble = " ".join(A)
print bubble
print "Stable"
print select
if bubble == select:
    print "Stable"
else:
    print "Not stable"

Solution (Python):

numbers = []
n = int(raw_input())

S = raw_input()

b = S.split(" ")
s = S.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"

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

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