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

Solution (Python):

N = int(raw_input())
line = raw_input()

num_list1 = line.split()

num_list2 = line.split()


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

print " ".join(num_list1)
print "Stable"



for i in range(0,N,1):
   
    minj =i
    for j in range(i,N,1):
        if int(num_list2[j][1:]) < int(num_list2[minj][1:]):
            minj = j
            
    num_list2[i], num_list2[minj] = num_list2[minj], num_list2[i]
print " ".join(num_list2)


if num_list1 == num_list2: 
    print "Stable"
else:
    print "Not stable"

Solution (Python):
def str_selection_sort(a,n):
    m=0
    for i in range(0,n):
        minj=i
        for j in range(i,n):
            if(int(a[minj][1:]) > int(a[j][1:])):
                minj=j
        if(minj!=i):
            m+=1
            a[minj],a[i] = a[i],a[minj]
        
    print(" ".join(a))
    return a

def str_bubble_sort(a,n):
    m=0
    flag=True
    while(flag):
        flag=False
        for i in range(n-1,0,-1):
            if(a[i-1][1:] > a[i][1:]):
                tmp=a[i-1]
                a[i-1]=a[i]
                m+=1
                a[i]=tmp
                flag=True
                
    print(" ".join(a))
    return a

def is_stable(a,b,n):
    for i in range(1,n):
        if(b[i-1][1:]!=b[i][1:]):
            continue
        flag=False
        for j in a:
            if(j[:1]==b[i-1][:1] and (not flag)):
                flag=True
                continue
            if(j[:1]==b[i][:1]):
                if(not flag):
                    return False
                else:
                    return True
        
        if(flag):
            return False
    return True

a=[]
n=int(input())
s=input()
a=s.split()
b=str_bubble_sort(list(a),n)
print("Stable")
c=str_selection_sort(list(a),n)
if(b==c):
    print("Stable")
else:
    print("Not stable")

Solution (Python):
class card(object):
    def __init__(self, str):
        self.symbol = str[0]
        self.num = int(str[1:])
    
    def __lt__(self,obj):
        if(self.num < obj.num):
            return True
        else:
            return False
    def __gt__(self,obj):
        if(self.num > obj.num):
            return True
        else:
            return False

    def display_card(self):
        print("{0}{1}".format(self.symbol,self.num),end="")

n = int(input())
s = input()
org = list(map(card,s.split()))  

bub = list(org)
sel = list(org)


"""
Bubble sort(bub[])
""" '''
for i in range(0,len(bub)):
    for j in range(len(bub)-1,i-1,-1):
        if(bub[j] < bub[j-1]):
            tmp = bub[j]
            bub[j] = bub[j-1]
            bub[j-1] = tmp
'''
flag = True
while(flag==True):
    flag = False
    for i in range(1,len(bub)):
        if(bub[i]<bub[i-1]):
            bub[i],bub[i-1] = bub[i-1],bub[i]
            flag = True


"""
selection sort(sel[])
"""

for i in range(0,len(sel)-1):
    minj = i
    for j in range(i,len(sel)):
        if(sel[j] < sel[minj]):
            minj = j
    sel[i],sel[minj] = sel[minj],sel[i]
       
"""
comp org(org[])
"""




for i in range(0,len(bub)):
    bub[i].display_card()
    if (i==len(bub)-1):
        print("\n",end="")
    else :
        print(" ",end="")
print("Stable")

                
for i in range(0,len(sel)):
    sel[i].display_card()
    if (i==len(sel)-1):
        print("\n",end="")
    else :
        print(" ",end="")
if(bub == sel): 
    print("Stable")
else:
    print("Not stable")

Solution (Python):
n = int(input())

cards_b = input().split()
cards_s = list(cards_b)


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


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

print(" ".join(cards_b))
print("Stable")
print(" ".join(cards_s))

if cards_b == cards_s:
    print("Stable")
else:
    print("Not stable")

Solution (Python):




class Card(object):

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

    def __str__(self):
        return str(self.card)


def print_array(a):
    print(" ".join(map(str, a)))


def bubblesort(cards, n):
    c = cards[::]
    for i in range(0, n):
        for j in range(n - 1, i, -1):
            if c[j].value < c[j - 1].value:
                (c[j], c[j - 1]) = (c[j - 1], c[j])
    return c


def selectionsort(cards, n):
    c = cards[::]
    for i in range(0, n):
        minj = i
        for j in range(i, n):
            if c[j].value < c[minj].value:
                minj = j
        (c[i], c[minj]) = (c[minj], c[i])
    return c


def main():
    n = int(input())
    cards = list(map(Card, input().split()))
    b = bubblesort(cards, n)
    print_array(b)
    print("Stable")
    s = selectionsort(cards, n)
    print_array(s)
    if b == s:
        print("Stable")
    else:
        print("Not stable")


if __name__ == "__main__":
    main()

Solution (Python):


def bubble_sort(A, N):
    C = list(A)
    for i in xrange(N):
        for j in reversed(xrange(i+1, N)):
            if C[j][1] < C[j-1][1]:
                C[j], C[j-1] = C[j-1], C[j]
    return C

def selection_sort(A, N):
    C = list(A)
    for i in xrange(N):
        minj = i
        for j in xrange(i, N):
            if C[j][1] < C[minj][1]:
                minj = j
        C[i], C[minj] = C[minj], C[i]
    return C

def is_stable(a, c, n):
    for i in xrange(n-1):
        if c[i][1] == c[i+1][1]:
            if a.index(c[i]) > a.index(c[i+1]):
                print "Not stable"
                return False
    print "Stable"
    return True

def print_c(c):
    print " ".join(map(lambda c:c[0] + str(c[1]), c))

def main():
    n = input()
    c = map(lambda c:(c[0], int(c[1:])), raw_input().split())
    bubble = bubble_sort(c, n)
    selection = selection_sort(c, n)
    print_c(bubble)
    is_stable(c, bubble, n)
    print_c(selection)
    is_stable(c, selection, n)

main()

Solution (Python):
def BubbleSort(lists, num):
  cards = lists[:]
  for i in xrange(num):
    for j in xrange(num - 1, i, -1):
      if cards[j].value < cards[j - 1].value:
        cards[j], cards[j - 1] = cards[j - 1], cards[j]
  return cards

def SelectionSort(lists, num):
  cards = lists[:]
  for i in xrange(num):
    minj = i
    for j in xrange(i, num):
      if cards[j].value < cards[minj].value:
        minj = j
    cards[i], cards[minj] = cards[minj], cards[i]
  return cards

class Card(object):
  """docstring for Card"""
  def __init__(self, arg):
    self.mark = arg[0]
    self.value = int(arg[1])

num = int(raw_input())
inputs = raw_input().split()
cards = [Card(inputs[x]) for x in xrange(num)]

bubble_ans = ""
bubble_cards = BubbleSort(cards, num)
for x in bubble_cards:
  bubble_ans += x.mark + str(x.value) + " "
print bubble_ans.rstrip()
print "Stable"

select_ans = ""
select_cards = SelectionSort(cards, num)
for x in select_cards:
  select_ans += x.mark + str(x.value) + " "
print select_ans.rstrip()
flag = True
for x in xrange(num):
  if bubble_cards[x].mark != select_cards[x].mark:
    flag = False
    break
print "Stable" if flag else "Not stable"

Solution (Python):
def comp(a,b):
    if a[1] > b[1]:
        return True
    else:
        return False

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

def selection_sort(a):
    for i in range(n):
        mini = i
        for j in range(i,n):
            if comp(a[mini],a[j]):
                mini=j
        a[mini],a[i]=a[i],a[mini]
    return a

def stable(original_a,sorted_a):
    for num in range(1,10):
        suite_ord = []
        for v in original_a:
            if v[1] == str(num):
                suite_ord.append(v[0])
        for v in sorted_a:
            if v[1] == str(num):
                if v[0]==suite_ord[0]:
                    del suite_ord[0]
                else:
                    return "Not stable"
    return "Stable"


n = int(raw_input())
cards = raw_input().split(' ')

sorted_cards = bubble_sort(cards[:])
print ' '.join(sorted_cards)
print stable(cards,sorted_cards)
sorted_cards = selection_sort(cards[:])
print ' '.join(sorted_cards)
print stable(cards,sorted_cards)

Solution (Python):


def Selection_Sort(A,n):
    for i in range(n):
        mini = i
        for j in range(i,n): 
            if int(A[j][1]) < int(A[mini][1]):
                mini = j
        if A[i] != A[mini]:
            A[i], A[mini] = A[mini], A[i]
    return A
    
def Bubble_Sort(A, n):
    for i in range(n):
        for j in range(n-1,i,-1):
            if int(A[j][1]) < int(A[j-1][1]):
                A[j], A[j-1] = A[j-1], A[j]
    return A
    
n = int(input())
A = input().strip().split()

B = A[:]
A = Bubble_Sort(A,n)
print (' '.join(A))
print ("Stable")
B =Selection_Sort(B,n)
print (' '.join(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):
    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(A):
    N = len(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]
    return A


def selectionSort(A):
    N = len(A)
    for i in range(N):
        min_i = i
        for j in range(i, N):
            if A[j][1] < A[min_i][1]:
                min_i = j
        if min_i != i:
            A[i], A[min_i] = A[min_i], A[i]
    return A


def is_stable(A, B):
    for i in range(len(B) - 1):
        if B[i][1] == B[i + 1][1]:
            if A.index(B[i]) > A.index(B[i + 1]):
                return False
    return True


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

B = bubbleSort(A[:])
print(*B)
if is_stable(A, B):
    print('Stable')
else:
    print('Not stable')

S = selectionSort(A[:])
print(*S)
if is_stable(A, S):
    print('Stable')
else:
    print('Not stable')

Solution (Python):
n, a = int(input()), input().split()
ta = list((int(c[1]), i, c) for i, c in enumerate(a))
ca = sorted(ta)

ba = ta[:]
for i in range(n):
    for j in range(n - 1, i, -1):
        if ba[j][0] < ba[j - 1][0]:
            ba[j], ba[j - 1] = ba[j - 1], ba[j]

print(*[t[2] for t in ba])
print(('Not s' if ba != ca else 'S') + 'table')

sa = ta[:]
for i in range(n):
    minj = i
    for j in range(i, n):
        if sa[j][0] < sa[minj][0]:
            minj = j
    if minj != i:
        sa[i], sa[minj] = sa[minj], sa[i]

print(*[t[2] for t in sa])
print(('Not s' if sa != ca else 'S') + 'table')

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

def SelectionSort(C, N):
    for i in xrange(0,N):
        minj = i
        for j in xrange(i,N):
            if int(C[j][1]) < int(C[minj][1]):
                minj = j
        if minj != i:
            tmp = C[i]
            C[i] = C[minj]
            C[minj] = tmp
    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 = int(raw_input())
    A = raw_input().split()
    BA = BubbleSort(A[:], N)
    SA = SelectionSort(A[:], N)
    print ' '.join(BA)
    if isStable(A, BA,N):
        print "Stable"
    else:
        print "Not stable"
    print ' '.join(SA)
    if isStable(A, SA,N):
        print "Stable"
    else:
        print "Not stable"

    return 0

if __name__ == "__main__":
    main()

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

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

input()
cards = [x for x in input().split()]
cards_b = cards.copy()
cards_s = cards.copy()
bubble_sort(cards_b)
selection_sort(cards_s)
for data in [cards_b, cards_s]:
    print(' '.join(data))
    if data == cards_b:
        print("Stable")
    else:
        print("Not stable")

Solution (Python):
class card:
    def __init__(self, types, value):
        self.types = types
        self.value = value

def bubbleSort(A, N):
    for i in range(0, N):
        for j in range(N - 1, i, -1):
            if A[j].value < A[j - 1].value:
                exchange(A, j - 1, j)
    printCards(A)
    print "Stable"

def selectionSort(A, N):
    origin = A[:]
    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:
            exchange(A, i, minj)
    printCards(A)
    if checkStable(origin, A, N):
        print "Stable"
    else:
        print "Not stable"

def exchange(array, i, j):
    tmp = array[i]
    array[i] = array[j]
    array[j] = tmp

def printCards(cards):
    print " ".join(t.types + str(t.value) for t in cards)

def checkStable(origin, sorted, N):
    for i in range(0, N - 1):
        if sorted[i].value == sorted[i + 1].value:
            if origin.index(sorted[i]) > origin.index(sorted[i + 1]):
                return False
    return True

if __name__ == "__main__":
    N = input()
    A = [card(c[0], int(c[1])) for c in raw_input().split()]
    bubbleSort(A[:], N)
    selectionSort(A[:], N)

Solution (Python):


N = int(input())
A = input()

IN1 = [None] * N
IN2 = [None] * N
i=0


for a in A.split():
    tmp = int(a.lstrip("SHCD"))
    IN1[i] = [tmp, i, a]
    IN2[i] = [tmp, i, a]
    i+=1

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

def InsertionSort(A,N):
    for i in range(0,N):
        minj = i
        for j in range(i, N):
            if A[j][0] < A[minj][0]:
                 minj = j
        if i != minj:
            tmp = A[i]
            A[i] = A[minj]
            A[minj] = tmp

def StableCheck(A):
    tmp = [0,0]
    for t in A:
        if(tmp[1] > t[1]):
            if(tmp[0] == t[0]):
                return False
        tmp = t
    return True


BubbleSort(IN1,N)
InsertionSort(IN2,N)

for i in range(N - 1):
    print(IN1[i][2],end=' ')
print(IN1[N - 1][2])
if(StableCheck(IN1)):print("Stable")
else:print("Not stable")

for i in range(N - 1):
    print(IN2[i][2],end=' ')
print(IN2[N - 1][2])
if(StableCheck(IN2)):print("Stable")
else:print("Not stable")

Solution (Python):
def selectionSort(A, N):
	for i in range(N):
		minj = i
		for j in range(i, N):
			if A[j][1:] < A[minj][1:]:
				minj = j
		if i != minj:
			tmp = A[i]
			A[i] = A[minj]
			A[minj] = tmp

	return A

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

	return A

if __name__ == '__main__':
	n = int(input())
	R = list(map(str, input().split()))
	C = R[:]
	SR = selectionSort(R, n)
	BR = bubbleSort(C, n)

	fStable = SR == BR

	print(" ".join(map(str, BR)))
	print("Stable")
	print(" ".join(map(str, SR)))
	if (fStable == True):
		print("Stable")
	else:
		print("Not stable")

Solution (Python):


N = int(raw_input())
A = map(str, raw_input().split())
B = A[:]
for i in range(N):
    for j in range(N-1, i, -1):
        if int(A[j][1]) < int(A[j-1][1]):
            A[j], A[j-1] = A[j-1], A[j]
bubble = " ".join(A)
for i in range(N):
    minj = i
    for j in range(i, N):
        if int(B[j][1]) < int(B[minj][1]):
            minj = j
    B[i], B[minj] = B[minj], B[i]
select = " ".join(B)
print bubble
print "Stable"
print select
if bubble == select:
    print "Stable"
else:
    print "Not stable"

Solution (Python):
def isStable(lis1, lis2):
    ret = True
    for i in range(len(lis1)-1):
        if lis1[i][1] == lis1[i+1][1]:
           ret = (lis1[i+1] in lis2[(lis2.index(lis1[i])+1):]) and ret
    return ret
    
N = int(input())
cards = input().split()

B = list(cards)
for i in range(N):
    for j in range(N-1, i, -1):
        if B[j][1] < B[j-1][1]:
            temp = B[j]
            B[j] = B[j-1]
            B[j-1] = temp

print(' '.join(B))
print('Stable' if isStable(B, cards) else 'Not stable')

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

print(' '.join(S))
print('Stable' if isStable(S, cards) else 'Not stable')

Solution (Python):
from collections import namedtuple
from operator import itemgetter, attrgetter

def bubble_sort(a):
    a = a[:]
    n = len(a)

    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):
    a = a[:]
    n = len(a)

    for i in range(n):
        minj = i
        for j in range(i, n):
            if a[j].value < a[minj].value:
                minj = j
        a[i], a[minj] = a[minj], a[i]

    return a

class Card(namedtuple('Card', ['suit', 'value'])):
    def __str__(self):
        return '{0}{1}'.format(self.suit, self.value)

parser = lambda s: Card(s[0], int(s[1:]))

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

stable_sorted = sorted(a, key = attrgetter('value'))
bubble_sorted = bubble_sort(a)
selection_sorted = selection_sort(a)

print(' '.join(list(map(str, bubble_sorted))))
if stable_sorted == bubble_sorted:
    print('Stable')
else:
    print('Not stable')

print(' '.join(list(map(str, selection_sorted))))
if stable_sorted == selection_sorted:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
def isStable(before_sort, after_sort):
    num = len(before_sort)
    
    for i in range(0, num-1):
        for j in range(i+1, num):
            for a in range(0, num-1):
                for b in range(a+1, num):
                    if before_sort[i][1] == after_sort[j][1] and \
                       before_sort[i] == after_sort[b] and \
                       before_sort[j] == after_sort[a]:
                        return False
    return True

def isStable2(sorted_data, bubble_sort_data):
    for i in range(0, len(sorted_data)):
        if sorted_data[i] != bubble_sort_data[i]:
            return False
    return True
    
def BubbleSort(c, n):
    for i in range(0, n):
        for j in range(n-1, i, -1):
            if int(c[j][1]) < int(c[j-1][1]):
                c[j], c[j-1] = c[j-1], c[j]

def SelectionSort(c, n):
    for i in range(0, n):
        minj = i
        for j in range(i, n):
            if int(c[j][1]) < int(c[minj][1]):
                minj = j
        c[i], c[minj] = c[minj], c[i]
    
num = int(input())
data = input().split(' ')

copy_data = data.copy()
BubbleSort(copy_data, num)
print(' '.join(copy_data))
if isStable(copy_data, copy_data):
    print("Stable")
else:
    print("Not stable")

bubble_sort_data = data.copy()
SelectionSort(bubble_sort_data, num)
print(' '.join(bubble_sort_data))
if isStable(bubble_sort_data, copy_data):
    print("Stable")
else:
    print("Not stable")

Solution (Python):
def show_list(a):
    for x in a:
        print x,
    print

def stable_check(sorted_values,sorted_suits,default_values,default_suits,n):
    for i in xrange(1,10):
        check_ss = []
        check_ds = []
        if i in sorted_values:
            for x in xrange(n):
                if i == sorted_values[x]:
                    check_ss.append(sorted_suits[x])
                if i == default_values[x]:
                    check_ds.append(default_suits[x])
            for x in xrange(len(check_ss)):
                if check_ss[x]!=check_ds[x]:
                    return "Not stable"
    return "Stable"

def bubble_sort(values,suits,n):
    flag = True
    while flag:
        flag = False
        for j in reversed(xrange(1,n)):
            if values[j] < values[j-1]:
                tmp = values[j]
                values[j] = values[j-1]
                values[j-1] = tmp
                tmp = suits[j]
                suits[j] = suits[j-1]
                suits[j-1] = tmp
                flag = True
    show_list(marge_suits_values(values,suits,n))
def selection_sort(values,suits,n):
    for i in xrange(n):
        minj = i
        for j in xrange(i,n):
            if values[j]<values[minj]:
                minj = j
        if minj!=i:
            tmp = values[i]
            values[i]=values[minj]
            values[minj]=tmp
            tmp = suits[i]
            suits[i]=suits[minj]
            suits[minj]=tmp
    show_list(marge_suits_values(values,suits,n))
def marge_suits_values(values,suits,n):
    ans = []
    for x in xrange(n):
        ans.append(suits[x]+str(values[x]))
    return ans

def main():
    n = input()
    a = raw_input().split()
    suits1 = []
    values1 =[]
    for x in xrange(n):
        suits1.append(a[x][0])
        values1.append(int(a[x][1]))
    suits2 = list(suits1)
    values2 = list(values1)
    bubble_sort(values1,suits1,n)
    print stable_check(values1,suits1,values2,suits2,n)

    values1 = list(values2)
    suits1 = list(suits2)
    selection_sort(values2,suits2,n)
    print stable_check(values2,suits2,values1,suits1,n)

if __name__ == '__main__':
    main()

Solution (Python):
def BubbleSort(C, N):
    for i in xrange(0, N):
        for j in reversed(xrange(i+1, N)):
            if C[j][1] < C[j-1][1]:
                C[j], C[j-1] = C[j-1], C[j]

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

def isStable(C, N):
    flag = 0
    for i in xrange(1, 14):
        Ct = [C[j] for j in xrange(N) if C[j][1] == str(i)]
        if len(Ct) > 1:
            for k in xrange( len(Ct)-1 ):
                if Ct[k][2] > Ct[k+1][2]:
                    flag = 1
    if flag == 0: print "Stable"
    else:         print "Not stable"


N = input()
C = []
Ct = map(str, raw_input().split())
for i in xrange(N):
    C.append([Ct[i][0], Ct[i][1::], i])

Ct = list(C)
BubbleSort(Ct, N)
print " ".join([Ct[i][0]+Ct[i][1] for i in xrange(N)])
isStable(Ct, N)

Ct = list(C)
SelectionSort(Ct, N)
print " ".join([Ct[i][0]+Ct[i][1] for i in xrange(N)])
isStable(Ct, N)

Solution (Python):
from collections import namedtuple
Card = namedtuple('Card', 'suit value')

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

def SelectionSort(C):
    for i in range(len(C)):
        mini = i
        for j in range(i,len(C)):
            if C[j].value < C[mini].value:
                mini = j
        C[i],C[mini] = C[mini],C[i]

def checkStable(C0, C1):
    result = True
    for i in range(1,10):
        f0 = [x.suit for x in list(filter(lambda c: c.value==i,C0))]
        f1 = [x.suit for x in list(filter(lambda c: c.value==i,C1))]
        if f0!=f1:
            result = False
    return result

if __name__=='__main__':
    N = int(input()) 
    Co = list(map(lambda X: Card(X[0],int(X[1])), map(list, input().split())))
    Cb,Cs = [Co[:] for _ in range(2)]
    for C, Sort in zip([Cb,Cs], [BubbleSort, SelectionSort]):
        Sort(C)
        print(*["".join([X.suit,str(X.value)]) for X in C])
        print("Stable" if checkStable(Co,C) else "Not stable")

Solution (Python):
N = input()
A = map(str, raw_input().split())
B = A[:]
for i in range(N):
    for j in range(N-1, i, -1):
        if int(A[j][1]) < int(A[j-1][1]):
            A[j], A[j-1] = A[j-1], A[j]
bubble = " ".join(A)
for i in range(N):
    minj = i
    for j in range(i, N):
        if int(B[j][1]) < int(B[minj][1]):
            minj = j
    B[i], B[minj] = B[minj], B[i]
select = " ".join(B)
print bubble
print "Stable"
print select
if bubble == select:
    print "Stable"
else:
    print "Not stable"

Solution (Python):

sample_input = list(range(3))
sample_input[0] = '''5
H4 C9 S4 D2 C3'''
sample_input[1] = '''2
S1 H1'''
sample_input[2] = '''5
H4 C9 S4 D2 C3'''
give_sample_input = None
if give_sample_input is not None:
    sample_input_list = sample_input[give_sample_input].split('\n')
    def input():
        return sample_input_list.pop(0)
        

import copy

def swap_list_item(lst, i, j):
    tmp = lst[i]
    lst[i] = lst[j]
    lst[j] = tmp
    
class Card:
    number = None
    mark = None
    def __init__(self, str_card):
        self.number = int(str_card[1])
        self.mark = str_card[0]
        pass
    def __eq__(self, other):
        return self.number == other.number
    def __lt__(self, other):
        return self.number < other.number
    def to_str(self):
        return self.mark + str(self.number)

def selection_sort(list_of_data):
    num_of_data = len(list_of_data)
    for i in range(num_of_data):
        minj = i
        for j in range(i, num_of_data):
            if list_of_data[minj] > list_of_data[j]:
                minj = j
        if not minj == i:
            swap_list_item(list_of_data, i, minj)
            
def bubble_sort(list_of_data):
    flag = True
    while flag:
        flag = False
        n = num_of_data - 1
        while n >= 1:
            if list_of_data[n] < list_of_data[n-1]:
                swap_list_item(list_of_data, n, n-1)
                flag = True
            n -= 1
        
def get_mark_order_info(card_list, number):
    result = ''
    for card in card_list:
        if card.number == number:
            result += card.mark
    return result

def print_card_list(card_list):
    output = ''
    for card in card_list:
        output += card.to_str() + ' '
    output = output.rstrip()
    print(output)

num_of_data = int(input())
data_list_str = input().split()
data_cards = [Card(str) for str in data_list_str]
data_cards_bubble = copy.copy(data_cards)
data_cards_selection = copy.copy(data_cards)

mark_order_info = []
for number in [n+1 for n in range(13)]:
    mark_order_info.append(get_mark_order_info(data_cards, number))
    
bubble_sort(data_cards_bubble)
selection_sort(data_cards_selection)

mark_order_info_bubble = []
for number in [n+1 for n in range(13)]:
    mark_order_info_bubble.append(get_mark_order_info(data_cards_bubble, number))

mark_order_info_selection = []
for number in [n+1 for n in range(13)]:
    mark_order_info_selection.append(get_mark_order_info(data_cards_selection, number))
    
print_card_list(data_cards_bubble)
if (mark_order_info == mark_order_info_bubble):
    print('Stable')
else:
    print('Not stable')
    
print_card_list(data_cards_selection)
if (mark_order_info == mark_order_info_selection):
    print('Stable')
else:
    print('Not stable')

Solution (Python):
def select(S):
    for i in range(0, 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])
    return S

def bubble(B):
    flag = True
    while flag:
        flag = False
        for j in reversed(range(1, n)):
            if int(B[j][1]) < int(B[j-1][1]):
                (B[j-1], B[j]) = (B[j], B[j-1])
                flag = True
    return B

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

B = bubble(A[:])
print(" ".join(B[:]))
print("Stable")
S = select(A)
print(" ".join(S))
print("Stable" if " ".join(B) == " ".join(S) else "Not stable")

Solution (Python):
def select(S):
    for i in range(0, 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])
    return S

def bubble(B):
    flag = True
    while flag:
        flag = False
        for j in reversed(range(1, n)):
            if int(B[j][1]) < int(B[j-1][1]):
                (B[j-1], B[j]) = (B[j], B[j-1])
                flag = True
    return B

def isStable(inA, out):
    for i in range(0, n):
        for j in range(i+1, n):
            for a in range(0, n):
                for b in range(a+1, n):
                    if inA[i][1] == inA[j][1] and inA[i] == out[b] and inA[j] == out[a]:
                        return "Not stable"
    return "Stable"



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

B = bubble(A[:])
print(" ".join(B))
print(isStable(A, B))
S = select(A[:])
print(" ".join(S))
print(isStable(A, S))