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


class Card :
        def __init__(self, char, num) :
                self.text = char
                self.value = num


def bubble_sort(Card, n) :
    for i in range(n) :
        for j in reversed(range(i+1, n)) :
            if Card[j].value < Card[j-1].value :
                Card[j], Card[j-1] = Card[j-1], Card[j]


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


def is_stable(lst_bubble, lst_sel) :
    for i in range(len(lst_bubble)) :
        if lst_bubble[i].text != lst_sel[i].text :
            return False
    return True


def print_result(lst, n) :
    for i in range(n-1) :
        print(lst[i].text + str(lst[i].value), end = "")
        print(" ", end = "")
    print(lst[-1].text + str(lst[-1].value))


def main() :
    n = int(input())
    lst1 = input().split()
    card_list1 = []
    for i in range(n) :
        card = Card(lst1[i][0], int(lst1[i][1]))
        card_list1.append(card)

    card_list2 = copy.deepcopy(card_list1)

    bubble_sort(card_list1, n)
    selection_sort(card_list2, n)

    print_result(card_list1, n)
    print("Stable")
    print_result(card_list2, n)
    if (is_stable(card_list1, card_list2)) :
        print("Stable")
    else :
        print("Not stable")


if __name__ == '__main__' :
        main()

Solution (Python):
import sys

ERROR_INPUT = 'input is invalid'


def main():
    n = get_length()
    arr = get_array(length=n)

    bubbleLi = bubbleSort(li=arr.copy(), length=n)
    selectionLi = selectionSort(li=arr.copy(), length=n)

    print(*list(map(lambda c: c.card, bubbleLi)))
    print(checkStable(inp=arr, out=bubbleLi))
    print(*list(map(lambda c: c.card, selectionLi)))
    print(checkStable(inp=arr, out=selectionLi))
    return 0


def get_length():
    n = int(input())
    if n < 1 or n > 36:
        print(ERROR_INPUT)
        sys.exit(1)
    else:
        return n


def get_array(length):
    nums = input().split(' ')
    return [Card(n) for n in nums]


def bubbleSort(li, length):
    for n in range(length):
        for n in range(1, length - n):
            if li[n].num < li[n - 1].num:
                li[n], li[n - 1] = li[n - 1], li[n]

    return li


def selectionSort(li, length):
    for i in range(0, length - 1):
        min_index = i
        for j in range(i, length):
            if li[j].num < li[min_index].num:
                min_index = j

        if i != min_index:
            li[i], li[min_index] = li[min_index], li[i]

    return li


def checkStable(inp, out):
    small_num = out[0].num

    for n in range(1, len(out)):
        if out[n].num == small_num:
            if inp.index(out[n]) < inp.index(out[n - 1]):
                return 'Not stable'
        elif small_num < out[n].num:
            small_num = out[n].num
            continue

    return 'Stable'


class Card:
    def __init__(self, disp):
        li = list(disp)
        self.card = disp
        self.chara = li[0]
        self.num = int(li[1])
        return


main()

Solution (Python):
import sys

ERROR_INPUT = 'input is invalid'


def main():
    n = get_length()
    arr = get_array(length=n)

    bubbleLi = bubbleSort(li=arr.copy(), length=n)
    selectionLi = selectionSort(li=arr.copy(), length=n)

    print(' '.join(list(map(lambda c: c.card, bubbleLi))))
    print(checkStable(inp=arr, out=bubbleLi))
    print(' '.join(list(map(lambda c: c.card, selectionLi))))
    print(checkStable(inp=arr, out=selectionLi))
    return 0


def get_length():
    n = int(input())
    if n < 1 or n > 36:
        print(ERROR_INPUT)
        sys.exit(1)
    else:
        return n


def get_array(length):
    nums = input().split(' ')
    return [Card(n) for n in nums]


def bubbleSort(li, length):
    for n in range(length):
        for n in range(1, length - n):
            if li[n].num < li[n - 1].num:
                li[n], li[n - 1] = li[n - 1], li[n]

    return li


def selectionSort(li, length):
    for i in range(0, length - 1):
        min_index = i
        for j in range(i, length):
            if li[j].num < li[min_index].num:
                min_index = j

        if i != min_index:
            li[i], li[min_index] = li[min_index], li[i]

    return li


def checkStable(inp, out):
    small_num = out[0].num

    for n in range(1, len(out)):
        if out[n].num == small_num:
            if inp.index(out[n]) < inp.index(out[n - 1]):
                return 'Not stable'
        elif small_num < out[n].num:
            small_num = out[n].num
            continue

    return 'Stable'


class Card:
    def __init__(self, disp):
        li = list(disp)
        self.card = disp
        self.chara = li[0]
        self.num = int(li[1])
        return


main()

Solution (Python):
import sys

ERROR_INPUT = 'input is invalid'


def main():
    n = get_length()
    arr = get_array(length=n)

    bubbleLi = bubbleSort(li=arr.copy(), length=n)
    selectionLi = selectionSort(li=arr.copy(), length=n)

    print(*list(map(lambda c: c.card, bubbleLi)))
    print(checkStable(inp=arr, out=bubbleLi))
    print(*list(map(lambda c: c.card, selectionLi)))
    print(checkStable(inp=arr, out=selectionLi))
    return 0


def get_length():
    n = int(input())
    if n < 1 or n > 36:
        print(ERROR_INPUT)
        sys.exit(1)
    else:
        return n


def get_array(length):
    nums = input().split(' ')
    return [Card(n) for n in nums]


def bubbleSort(li, length):
    for n in range(length):
        for n in range(1, length - n):
            if li[n].num < li[n - 1].num:
                li[n], li[n - 1] = li[n - 1], li[n]

    return li


def selectionSort(li, length):
    for i in range(0, length - 1):
        min_index = i
        for j in range(i, length):
            if li[j].num < li[min_index].num:
                min_index = j

        if i != min_index:
            li[i], li[min_index] = li[min_index], li[i]

    return li


def checkStable(inp, out):
    small_num = out[0].num

    for n in range(1, len(out)):
        if out[n].num == small_num:
            if inp.index(out[n]) < inp.index(out[n - 1]):
                return 'Not stable'
        elif small_num < out[n].num:
            small_num = out[n].num
            continue

    return 'Stable'


class Card:
    def __init__(self, disp):
        li = list(disp)
        self.card = disp
        self.chara = li[0]
        self.num = int(li[1])
        return


main()

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

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

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

b = a.copy()
c = a.copy()

bubble(b)
selection(c)

for d in [b, c]:
    print(" ".join(d))
    if d == b:
        print("Stable")
    else:
        print("Not stable")

Solution (Python):


import copy
class Algo:
  @staticmethod
  def bubbleSort(r, c, n):
    flag = 1
    while flag:
      flag = 0
      for j in range(n-1, 0, -1):
        if c[j] < c[j-1]:
          c[j], c[j-1] = c[j-1], c[j]
          r[j], r[j-1] = r[j-1], r[j]
          flag = 1
    return r

  def selectionSort(r, c, n):
    for i in range(0,n):
      minj = i
      for j in range(i,n):
        if c[j] < c[minj]:
          minj = j
      if c[i] != c[minj]:
        c[i], c[minj] = c[minj], c[i]
        r[i], r[minj] = r[minj], r[i]
    return r

  def createIntList(r, n):
    c = []
    for i in range(0,n):
      c.append(r[i][1])
    return c

  def printList(r, n):
    for i in range(0,n):
      if i == n-1:
        print(r[i])
      else:
        print(r[i], " ", sep="", end="")

n = int(input())
r = list(map(str,input().split()))
c = Algo.createIntList(r, n)
br = Algo.bubbleSort(copy.deepcopy(r), copy.deepcopy(c), n)
ir = Algo.selectionSort(copy.deepcopy(r), copy.deepcopy(c), n)
Algo.printList(br, n)
print("Stable")
Algo.printList(ir, n)
if br == ir:
  print("Stable")
else:
  print("Not stable")

Solution (Python):
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]:
                A[j], A[j-1] = A[j-1], A[j]
                flag = 1
    print(*A)
    return A


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

    print(*A)
    return A


def isStable(input, output, 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 input[i][1] == input[j][1] and input[i] == output[b] and input[j] == output[a]:
                        print("Not stable")
                        return False
    print("Stable")
    return True

arr_length = int(input())
arr_num = [i for i in input().split(" ")]

isStable(arr_num, bubbleSort(list(arr_num), arr_length), arr_length)

isStable(arr_num, selectionSort(list(arr_num), arr_length), arr_length)

Solution (Python):
from copy import copy


def bubble_sort(org_A):
    A = copy(org_A)
    for i in range(len(A)):
        for j in range(len(A) - 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


def selection_sort(org_A):
    A = copy(org_A)
    n = len(A)
    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 mini != i:
            A[i], A[mini] = A[mini], A[i]
    return A

n = int(input())
A = input().split()
B = bubble_sort(A)
C = selection_sort(A)
print(' '.join(B))
print('Stable')
print(' '.join(C))
if B == C:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
def selection(l):
	lists = l[:]
	N = len(lists)

	for i in range(N):
		minj = i

		for j in range(i, N):
			if int(lists[j][1]) < int(lists[minj][1]):
				minj = j
		if i == minj:
			continue
		else:
			lists[i], lists[minj] = lists[minj], lists[i]

	return lists


def bubble(l):
	lists = l[:]
	N = len(lists)
	flag = 1

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

	return lists


def output(l):
	count = 0
	leng = len(l)
	for i in l:
		count += 1
		if count < leng:
			print(i, end =' ')
		else:
			print(i)




if __name__ == '__main__':
	n = int(input())
	l = input().split()
	l_1 = bubble(l)
	l_2 = selection(l)

	output(l_1)
	print("Stable")
	output(l_2)
	if l_1 == l_2:
		print("Stable")
	else:
		print("Not stable")

Solution (Python):



def bubbleSort(A, N):

    flag = True  
    i = 0  
    inv_num = 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
                inv_num += 1
        i += 1

    return A, inv_num


def selectionSort(A, N):
    count = 0

    for i in range(N):

        minj = i
        for j in range(i, N):
            if A[j][1] < A[minj][1]:
                minj = j
        if minj != i:
            count += 1

        A[i], A[minj] = A[minj], A[i]

    return A, count


if __name__ == '__main__':

    N = int(input())
    A = [(a[0], int(a[1])) for a in input().split(" ")]

    A_bubble, _ = bubbleSort(A.copy(), N)
    A_selection, _ = selectionSort(A.copy(), N)

    A_bubble = [a[0] + str(a[1]) for a in A_bubble]
    A_selection = [a[0] + str(a[1]) for a in A_selection]

    print(' '.join(A_bubble))
    print("Stable")
    print(" ".join(A_selection))
    if A_selection == A_bubble:
        print("Stable")
    else:
        print("Not stable")

Solution (Python):
def bubbleSort(c):
    for i in range(len(c)):
        for j in range(len(c) - 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):
    for i in range(len(c)):
        minj = i
        for j in range(i, len(c)):
            if c[j][1] < c[minj][1]:
                minj = j
        c[i], c[minj] = c[minj], c[i]
    return c


n = int(input())
b = input().split()
s = b[:]

b = bubbleSort(b)
s = selectionSort(s)

print(*b)
print('Stable')
print(*s)
print('Stable' if b == s else 'Not stable')

Solution (Python):
import copy

n=int(input())
s=input().split(' ')
s1=[]
s2=[]
s1=copy.deepcopy(s)
s2=copy.deepcopy(s)

def Bubble_Sort(n,s1):
	m=0
	flag=1
	while flag:
		flag=0
		for i in range(1,n):
			j=n-i
			if int(s1[j][1])<int(s1[j-1][1]):
				a=s1[j]
				s1[j]=s1[j-1]
				s1[j-1]=a
				m+=1
				flag=1
	b=s1
	return(b)

def Selection_Sort(n,s2):
	m=0
	for i in range(n):
		minj=i
		for j in range(i,n):
			if int(s2[j][1])<int(s2[minj][1]):
				minj=j
		if i!=minj:
			a=s2[minj]
			s2[minj]=s2[i]
			s2[i]=a
			m+=1
	b=s2
	return(b)

s1=Bubble_Sort(n,s1)
s2=Selection_Sort(n,s2)

print(' '.join(s1))
print('Stable')
print(' '.join(s2))
if s1==s2:
	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 C[j][1] < 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 + 1, N):
            if C[j][1] < C[minj][1]:
                minj = j
        if i != minj:
            C[i], C[minj] = C[minj], C[i]
N = int(input())
A = input().split()
B = A[:]
C = A[:]
BubbleSort(B, N)
print(*B)
print("Stable")
SelectionSort(C, N)
print(*C)
print("Stable" if B == C else "Not stable")

Solution (Python):
import copy


def SelectionSort(arr, n):
    for i in range(n):
        mini = i
        for j in range(i, n):
            if arr[j]['val'] < arr[mini]['val']:
                mini = j
        if mini != i:
            arr[i], arr[mini] = arr[mini], arr[i]
    return


def BubleSort(arr, n):
    for i in range(n):
        for j in range(n - 1, i, -1):
            if arr[j]['val'] < arr[j-1]['val']:
                arr[j], arr[j-1] = arr[j-1], arr[j]
    return


def isStable(inarr, comparr, n):
    i = 0
    while i < n:
        tmpVal = comparr[i]['val']
        for j in range(n):
            if inarr[j]['val'] == tmpVal:
                if inarr[j]['crd'] == comparr[i]['crd']:
                    if i != n - 1 and comparr[i+1]['val'] == tmpVal:
                        i += 1
                    else:
                        break
                else:
                    return 'Not stable'
        i += 1
    return 'Stable'


n = int(input())
arr = input().split()
tar = []

for s in arr:
    tar.append({'crd': s[0], 'val': s[1], 'str': s})

bub = copy.copy(tar)
BubleSort(bub, n)

prt = []
for s in bub:
    prt.append(s['str'])
print(*prt)
print(isStable(tar, bub, n))

bub = copy.copy(tar)
SelectionSort(bub, n)

prt = []
for s in bub:
    prt.append(s['str'])
print(*prt)
print(isStable(tar, bub, n))

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

Solution (Python):
n=int(input())
c=input().split();d=c[:]
for i in range(n-1):
 for j in range(0,n-i-1):
  if c[j][1]>c[j+1][1]:c[j],c[j+1]=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):
count = int(input());
data = input().split(" ");

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

def selection_sort(data):
    count = len(data);
    
    for i in range(count - 1):
        minI = i;
        for j in range(i + 1, count):
            if data[j][1] < data[minI][1]:
                minI = j;
        if i != minI:
            data[i], data[minI] = data[minI], data[i];
        

def show(data):
    print(" ".join(data));

A = list(data);
bubble_sort(A);
show(A);
print("Stable");

B = list(data);
selection_sort(B);
show(B);
if A == B:
    print("Stable");
else:
    print("Not stable");

Solution (Python):
def bubbleSort(C1,N):
    for i in range(N):
        for j in range(N-1,i,-1):
            if C1[j][1] < C1[j-1][1]:
                C1[j],C1[j-1] = C1[j-1],C1[j]
    return C1[:]
    
def selectSort(C2,N):
    for i in range(0,N):
        minj = i
        for j in range(i,N):
            if C2[minj][1] > C2[j][1]:
                minj = j
        C2[i],C2[minj] = C2[minj],C2[i]
    return C2[:]

N = int(input())
C1 = input().split()
C2 = C1[:]

C1 = bubbleSort(C1,N)
C2 = selectSort(C2,N)

print(*C1)
print("Stable")
print(*C2)
if C1 == C2:
    print("Stable")
else:
    print("Not stable")

Solution (Python):



def pprint(numlist):
  print(" ".join(map(str,numlist)))
def greater(s,t):
  if s[1] > t[1]:
    return True
  else:
    return False
def equal(s,t):
  if s[1] == t[1]:
    return True
  else:
    return False
def wasStable(Ans,Initial,N):
  I = Initial.copy()
  for i in range(N-1):
    if equal(Ans[i],Ans[i+1]):
      for x in I:
        if equal(Ans[i],x):
          if(Ans[i][0] != x[0]):
            return False
          else:
            I.remove(x)
            break
  return True
  

N = int(input())
A = input().split()
Initial = A.copy()
B = A.copy()


count = 0
flag = True
while flag:
  flag = False
  j = N - 1
  while j >= 1:
    if greater(A[j-1],A[j]):
      v = A[j]
      A[j] = A[j-1]
      A[j-1] = v
      flag = True
      count += 1
    j -= 1
pprint(A)
print("Stable")


count = 0
for i in range(N):
  j=i
  minj=i
  while j<= N-1:
    if greater(B[minj],B[j]):
      minj = j
    j += 1
  if i != minj:
    v=B[i]
    B[i]=B[minj]
    B[minj]=v
    count += 1
    
print(" ".join(map(str,B)))
if wasStable(B,Initial,N):
  ans = "Stable"
else:
  ans = "Not stable"
print(ans)

Solution (Python):
n, card = int(input()), input().split()
card1, card2 = card[:], card[:]

for i in range(n-1):
    for j in range(n-1, i, -1):
        if int(card1[j][1]) < int(card1[j-1][1]):
            card1[j], card1[j-1] = card1[j-1], card1[j]
print(" ".join(card1))
print("Stable")

for i in range(n-1):
    for j in range(i+1, n):
        if j == i+1:
            idx = j
        elif int(card2[idx][1]) > int(card2[j][1]):
            idx = j
    if int(card2[i][1]) > int(card2[idx][1]):
        card2[i], card2[idx] = card2[idx], card2[i]
print(" ".join(card2))
if card1 == card2:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
class Card:
    def __init__(self, inf):
        self.num = int(inf[1])
        self.inf = inf

n, card = int(input()), [Card(i) for i in input().split()]
card1 = card[:]

for i in range(n-1):
    for j in range(n-1, i, -1):
        if card[j].num < card[j-1].num:
             card[j], card[j-1] = card[j-1], card[j]
print(" ".join([i.inf for i in card]))
print("Stable")

for i in range(n-1):
    for j in range(i+1, n):
        if j == i+1:
            idx = j
        elif card1[idx].num > card1[j].num:
            idx = j
    if card1[i].num > card1[idx].num:
        card1[i], card1[idx] = card1[idx], card1[i]
print(" ".join([i.inf for i in card1]))
if card == card1:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
def bSort(A):
    flag = 1
    i = 0
    count = 0
    while flag:
        flag = 0
        for j in range(len(A)-1, i, -1):
            if int(A[j][1]) < int(A[j-1][1]):
                tmp = A[j]
                A[j] = A[j-1]
                A[j-1] = tmp
                flag = 1
                count += 1
        i += 1
    return A, count

def sSort(A):
    count = 0
    for i in range(len(A)):
        minj = i
        for j in range(i, len(A)):
            if int(A[j][1]) < int(A[minj][1]):
                minj = j
        if minj != i:
            count += 1
        tmp = A[i]
        A[i] = A[minj]
        A[minj] = tmp
    return A, count

def isStable(input_a, output_a):
    for v1, v2 in zip(input_a, output_a):
        if v1 != v2:
            return 'Not stable'
    return 'Stable'

if __name__ == '__main__':
    length = input()
    data = input().split()
    sort_s, _= sSort(list(data))
    sort_b, _= bSort(list(data))
    print (' '.join([str(x) for x in sort_b]))
    print (isStable(sort_b, sort_b))
    print (' '.join([str(x) for x in sort_s]))
    print (isStable(sort_b, sort_s))

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

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

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

l=list(r)
a=BubbleSort(l, n)
print(*a)
print('Stable')
l=list(r)
b=SelectionSort(l, n)
print(*b)
if a==b:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
n=int(raw_input())
r=raw_input().split()

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

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

l=list(r)
a=BubbleSort(l, n)
print ' '.join(a)
print 'Stable'
l=list(r)
b=SelectionSort(l, n)
print ' '.join(b)
if a==b:
    print 'Stable'
else:
    print 'Not stable'

Solution (Python):



import sys

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

def selection_sort(A):
    for i in range(len(A)):
        min_val = A[i][1]
        for x in range(i, len(A)):
            if A[x][1] < min_val:
                min_val = A[x][1]
                min_index = x
        if min_val < A[i][1]:
            A[min_index], A[i] = A[i], A[min_index]

def check_stable(srt_list, org_list):
    prev_val = None
    prev_pos = -1
    for card in srt_list:
        cur_pos = org_list.index(card)
        
        if card[1] == prev_val:
            if cur_pos < prev_pos:
                print('Not stable')
                return
        prev_val = card[1]
        prev_pos = cur_pos

    print('Stable')


n = int(sys.stdin.readline())
org_list = sys.stdin.readline().split()
_list1 = org_list[:]
_list2 = org_list[:]

bubble_sort(_list1)
selection_sort(_list2)

print(' '.join(_list1))
check_stable(_list1, org_list)
print(' '.join(_list2))
check_stable(_list2, org_list)

Solution (Python):
def BubbleTrump(C, N):
    i = 0
    while i < N:
        j = N - 1
        while j > i:
            if int(C[j][1]) < int(C[j-1][1]):
                c = C[j]
                C[j] = C[j - 1]
                C[j - 1] = c
            j -= 1
        i += 1
    return C

def SelectionTrump(C, N):
    i = 0
    while i < N:
        minj = i
        j = i
        while j < N:
            if int(C[j][1]) < int(C[minj][1]):
                minj = j
            j += 1
        if minj != i:
            c = C[i]
            C[i] = C[minj]
            C[minj] = c
        i += 1
    return C

n = int(input())
C = list(map(str, input().split(' ')))
ans = ''
Cb = BubbleTrump(C.copy(), n)
ans += ' '.join(map(str, Cb)) + '\nStable\n'
Cs = SelectionTrump(C.copy(), n)
q = 0
f = 1
while q < n:
    if Cb[q] != Cs[q]:
        f = 0
    q += 1
ans += ' '.join(map(str, Cs)) + '\n'
if f == 0:
    ans += 'Not stable'
else:
    ans += 'Stable'
print(ans)

Solution (Python):
def bubble_sort(c, n):
    x = c[:]
    for i in range(n):
        for k in range(n-1, i, -1):
            if x[k][1] < x[k-1][1]:
                x[k], x[k-1] = x[k-1], x[k]
    return x

def selection_sort(c, n):
    x = c[:]
    for i in range(n):
        mink = i
        for k in range(i, n):
            if x[k][1] < x[mink][1]:
                mink = k
        x[i], x[mink] = x[mink], x[i]
    return x

n = int(input())
c = []
for i in list(input().split()):
    c.append((i[0], int(i[1]))) 

b = bubble_sort(c, n)
print(" ".join(map(str, [i[0]+str(i[1]) for i in b])))

stable = True
print("Stable")

s = selection_sort(c, n)
print(" ".join(map(str, [i[0]+str(i[1]) for i in s])))
if b != s:
    stable = False
if stable:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
class Card(object):
    def __init__(self, card):
        self.suit = card[:1]
        self.value = int(card[1:])
    
    def __str__(self):
        return self.suit + str(self.value)

def is_stable(bs, ss):
    if bs == ss:
        return 'Stable'
    else:
        return 'Not stable'

def bubble_sort(c, n):
    c = c.split()
    c = [Card(card) for card in c]
    for i in range(n-1):
        for j in range(n-1):
            if c[j].value > c[j+1].value:
                c[j], c[j+1] = c[j+1], c[j]
    return c

def selection_sort(c, n):
    c = c.split()
    c = [Card(card) for card in c]
    for i in range(n):
        mink = i
        for v in range(i, n):
            if c[v].value < c[mink].value:
                mink = v
        if mink != i:
            c[i], c[mink] = c[mink], c[i]
    return c

n = input()
nums = input()

bs = bubble_sort(nums, int(n))
bs_str = [str(card) for card in bs]
print(' '.join(bs_str))
print('Stable')

ss = selection_sort(nums, int(n))
ss_str = [str(card) for card in ss]
print(' '.join(ss_str))
print(is_stable(bs_str, ss_str))

Solution (Python):



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

    def __repr__(self):
        return self.card


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


def SelectionSort(C, N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if C[j].value < C[minj].value:
                minj = j
        C[i], C[minj] = C[minj], C[i]
    return C


def isStable(inl, out):
    n = len(inl)
    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 inl[i].value == inl[j].value and inl[i] == out[b] and inl[j] == out[a]:
                        return False
    return True


def print_stable(inl, out):
    if isStable(inl, out):
        print "Stable"
    else:
        print "Not stable"


if __name__ == "__main__":
    N = int(raw_input())
    inputs = raw_input().split()
    C = []
    for i in inputs:
        C.append(Card(i))
    Cb = BubbleSort(list(C), N)
    print " ".join([i.card for i in Cb])
    print_stable(C, Cb)
    Cs = SelectionSort(list(C), N)
    print " ".join([i.card for i in Cs])
    print_stable(C, Cs)

Solution (Python):
import re
import copy
pattern = r'([0-9])'
repatter = re.compile(pattern)

n = int(input())
text = input()

*lists, = text.split(" ")
lists2 = copy.copy(lists)
lists3 = copy.copy(lists)



def bubble_sort(a):
    flag = 1
    i = 0
    while flag:
        flag = 0
        for j in range(n-1, i, -1):
            x = repatter.findall(a[j])
            y = repatter.findall(a[j-1])
            if x < y:
                a[j], a[j-1] = a[j-1], a[j]
                flag = 1
        i += 1
    print(*a)
    print("Stable")



def select_sort(a):
    for i in range(n):
        min_j = i
        for j in range(i+1, n):
            x = repatter.findall(a[j])
            y = repatter.findall(a[min_j])
            if x < y:
                min_j = j
        a[i], a[min_j] = a[min_j], a[i]
    print(*a)


def isStable(before, after):
    flag = True
    for i in range(n):
        for j in range(i+1, n):
            for a in range(n):
                for b in range(a+1, n):
                    x = repatter.findall(before[i])
                    y = repatter.findall(before[j])
                    if x == y and before[i] == after[b] and before[j] == after[a]:
                        flag = False
    if flag is True:
        print("Stable")
    else:
        print("Not stable")


bubble_sort(lists)
select_sort(lists2)
isStable(lists3, lists2)

Solution (Python):
n = int(input())
l = []
for i in input().split():
  t = []
  for j in i: t += [j]
  l += [t]

t = l[:]
f = 0
for i in range(n):
  for j in range(n-1, 0, -1):
    if t[j][1] < t[j-1][1]:
      t[j], t[j-1] = t[j-1], t[j]
    elif t[j][1] == t[j-1][1]:
      f += 1 if l.index(t[j-1]) > l.index(t[j]) else 0
print(*["{0}{1}".format(i[0], i[1]) for i in t])
print("Not stable" if f > 0 else "Stable")

x = l[:]
f = 0
for i in range(n):
  m = i
  for j in range(i, n):
    if x[j][1] < x[m][1]:
      m = j
    elif x[j][1] == x[m][1]:
      f += 1 if l.index(x[m]) > l.index(x[j]) else 0
  x[i], x[m] = x[m], x[i]
print(*["{0}{1}".format(i[0], i[1]) for i in x])
print("Not stable" if f > 0 else "Stable")