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 

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



Sample input:
5
H4 C9 S4 D2 C3


Sample output:
D2 C3 H4 S4 C9
Stable
D2 C3 S4 H4 C9
Not stable

Submission status: Accepted

Solution code:
def bubbleSort(A,N):
    flag = 1 #????????????????????£??????????????????????????????????????¨??????
    i = 0

    while flag:
        flag = 0
        for j in range(N-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
        i += 1
    return A


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

def isStable(ori,sorted):
    for i in range(len(ori)-1):
        for j in range(i+1, len(ori)-1):
            for a in range(len(ori)):
                for b in range(a+1, len(ori)):
                    if ori[i][1] == ori[j][1] and ori[i] == sorted[b] and ori[j] == sorted[a]:
                        return 'Not stable'
    return 'Stable'

def output(A):
    for i in range(len(A)):  # output
        if i == len(A) - 1:
            print(A[i])
        else:
            print(A[i], end=' ')

if __name__ == '__main__':

    N = int(input())

    numbers = input().split(' ')
    n1 = numbers.copy()
    n2 = numbers.copy()

    A = bubbleSort(n1,N)

    output(A)
    print(isStable(numbers,A))

    B = selectionSort(n2,N)

    output(B)
    print(isStable(numbers, B))

Submission status: Accepted

Solution code:
import copy

def bubbleSort(cards):
    C = copy.copy(cards)
    for i in range(0, len(C)):
        for j in range(len(C) - 1, i, -1):
            if C[j][1] < C[j-1][1]:
                C[j-1], C[j] = C[j], C[j-1]
    return C

def selectionSort(cards):
    C = copy.copy(cards)
    for i in range(0, len(C)):
        min = i
        for j in range(i, len(C)):
            if C[j][1] < C[min][1]:
                min = j
        C[i], C[min] = C[min], C[i]
    return C


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

CB = bubbleSort(cards)
CS = selectionSort(cards)
print(' '.join(CB))
print('Stable')
print(' '.join(CS))
if CB == CS:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
#coding: UTF-8

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")

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


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")

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
count = int(input());
data = input().split(" ");

def bubble_sort(data):
    # print(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];
        # print(data);

def selection_sort(data):
    count = len(data);
    # print(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];
        # print(data);

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");

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
# coding: UTF-8

#共通関数と演算
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
  
#input
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)

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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'

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

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)
        # print(card, cur_pos)
        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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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]))) # tupleで渡す

b = bubble_sort(c, n)
print(" ".join(map(str, [i[0]+str(i[1]) for i in b])))
# bubble_sortは常に安定なソート
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")

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
# coding: utf-8
# Stable Sort 2018/3/12

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)