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: Wrong Answer

Solution code:
n = int(input())
a = list(input().split())

A = []
A1 = []
A2 = []
for i in a:
    A.append(list(i))
    A1.append(list(i))
    A2.append(list(i))

# check stable or not
def is_stable(A3):
    for i in range( 1, n ):
        if int(A3[i-1][1]) == int(A3[i][1]):
            sm = i-1
            bg = i
            for j in range( n ):
                if ( A[j][0] == A3[sm][0]) & ( A[j][1] == A3[sm][1]):
                    t1 = j
                if ( A[j][0] == A3[bg][0]) & ( A[j][1] == A3[bg][1]):
                    t2 = j
            print(t1)
            print(t2)
            if t1 > t2:
                return "Not stable"
    return "Stable"

# bubble
for i in range( n ):
    for j in range( n-1, i, -1 ):
        if int(A1[j][1]) < int(A1[j-1][1]):
            t = A1[j-1]
            A1[j-1] = A1[j]
            A1[j] = t

s = is_stable(A1)
print(*A1)
print(s)


# selection
for i in range( n ):
    minj = i
    for j in range( i+1, n ):
        if int(A2[j][1]) < int(A2[minj][1]):
            minj = j
    if minj != i:
        t = A2[i]
        A2[i] = A2[minj]
        A2[minj] = t

s = is_stable(A2)
print(*A2)
print(s)

Submission status: Wrong Answer

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

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

N = int(input())
C = input().split()
B = BubbleSort(C, N)
S = SelectionSort(C, N)
mes = "Stable" if isStable(B, S, N) else "Not stable"
print(" ".join(list(map(str, B))))
print("Stable")
print(" ".join(list(map(str, S))))
print(mes)

Submission status: Wrong Answer

Solution code:

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

def output(c):
	for i in range(len(c)):
		if i != 0: print(" ", end="")
		print("{}{}".format(c[i][0], c[i][1]), end="")
	print()

def isstable(inp, outp, 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 (inp[i][1] == inp[j][1] and
						inp[i][0] == outp[b][0] and
						inp[j][0] == outp[a][0]):
						print("Not stable")
						return
	print("Stable")


def main():
	n = int(input())
	data = input().split()
	cards = []

	for c in data:
		cards.append((c[0],int(c[1])))
	cards1 = cards[:]
	cards2 = cards[:]

	bubblesort(cards1, n)
	output(cards1)
	isstable(cards, cards1, n)

	selectionsort(cards2, n)
	output(cards2)
	isstable(cards, cards2, n)

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
class Card(object):
    def __init__(self, card):
        self._suit = card[0]
        self._value = int(card[1])

    def __eq__(self, other):
        if other is None:
            return False
        return self.__dict__ == other.__dict__

    def getValue(self):
        return self._value

    def toString(self):
        return self._suit + str(self._value)


def card_bubbleSort(lst, n):
    for i in range(0, n):
        for j in range(n-1, i, -1):
            if lst[j].getValue() < lst[j-1].getValue():
                tmp = lst[j]
                lst[j] = lst[j-1]
                lst[j-1] = tmp

    return lst


def card_selectionSort(lst, n):
    for i in range(0, n):
        minj = i
        for j in range(i, n):
            if lst[j].getValue() < lst[minj].getValue():
                minj = j

        if i != minj:
            tmp = lst[i]
            lst[i] = lst[minj]
            lst[minj] = tmp

    return lst


def isStable(in_lst, out_lst, n):
    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 in_lst[i].getValue() == in_lst[j].getValue() \
                            and in_lst[i] == out_lst[b] \
                            and in_lst[j] == out_lst[a]:
                                return False
    return True


if __name__ == "__main__":
    n = int(input())
    lst = input().split()
    func_table = [card_bubbleSort, card_selectionSort]
    for func in func_table:
        cards = [Card(item) for item in lst]
        result = func(cards, n)
        cards = [Card(item) for item in lst]
        print(" ".join([card.toString() for card in result]))
        if isStable(cards, result, n):
            print("Stable")
        else:
            print("Not Stable")

Submission status: Wrong Answer

Solution code:
N = int(input())
C = list(input().split())
_C = C.copy()

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

for j in range(N):
    m = i
    for j in range(i, N):
        if (_C[j] < _C[j-1]):
            m = j
    _C[i], _C[m] = _C[m], _C[i]
print(*_C)
if(C ==_C):
    print("Stable")
else:
    print("Not stable")

Submission status: Wrong Answer

Solution code:
N = int(input())
C = input().split()
_C = C.copy()

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

for j in range(N):
    m = i
    for j in range(i, N):
        if (_C[j] < _C[j-1]):
            m = j
    _C[i], _C[m] = _C[m], _C[i]
print(*_C)
if(C ==_C):
    print("Stable")
else:
    print("Not stable")

Submission status: Wrong Answer

Solution code:
N = int(input())
C = list(input().split())
_C = C.copy()

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]
print(*C)
print("Stable")

for j in range(N):
    m = i
    for j in range(i, N):
        if (_C[j][1] < _C[j-1][1]):
            m = j
    _C[i], _C[m] = _C[m], _C[i]
print(*_C)
if(C ==_C):
    print("Stable")
else:
    print("Not stable")

Submission status: Wrong Answer

Solution code:
N = int(input())
C = input().split()
_C = C.copy()

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]
print(*C)
print("Stable")

for j in range(N):
    m = i
    for j in range(i, N):
        if (_C[j][1] < _C[j-1][1]):
            m = j
    _C[i], _C[m] = _C[m], _C[i]
print(*_C)
if(C ==_C):
    print("Stable")
else:
    print("Not stable")

Submission status: Wrong Answer

Solution code:
N = int(input())
C = input().split()
_C = C.copy()

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]
print(*C)
print("Stable")

for i in range(N):
    m = i
    for j in range(i, N):
        if (_C[j][1] < _C[j-1][1]):
            m = j
    _C[i], _C[m] = _C[m], _C[i]
print(*_C)
if(C ==_C):
    print("Stable")
else:
    print("Not stable")

Submission status: Wrong Answer

Solution code:
n = int(input())
a = input().split()
b = a[:]
frag = 1
while frag:
  frag = 0
  for i in range(n - 1):
    if a[i][1] > a[i + 1][1]:
      a[i], a[i + 1] = a[i + 1], a[i]
      frag = 1
print(*a)
print("Stable")

for i in range(n - 1):
  minj = i
  for j in range(i, n):
    if b[j][1] < b[minj][1]:
      minj = j
  b[i], b[minj] = b[minj], b[i]
print(*b)
if a == b:
  print("Stable")
else:
  print("Not Stable")

Submission status: Wrong Answer

Solution code:
def buble(n,x,count):
    for i in range(1,n + 1):
        for j in range(1,i):
            if int(x[i - j][1]) < int(x[i - j - 1][1]):
                x[i - j],x[i - j - 1] = x[i - j - 1],x[i - j]
                count += 1  
    print (" ".join(x))
    print ("Stable")
    
def delection(n,x,flag):
    
    for i in range(n - 1):
        minx = i
        for j in range(i + 1,n):
            if x[j][1] == x[i][1]:
                flag = 1
            if x[j][1] < x[minx][1]:
                minx = j
        
        if not i == minx:
            x[i],x[minx]=x[minx],x[i]
            
    print (" ".join(x))
    if flag == 1:
        print ("Stable")
    else:
        print ("Not stable")
    
n = int(input())
x = list(map(str,input().split()))
y = x
count = 0
flag = 0
buble(n,x,count)
delection(n,y,flag)

Submission status: Wrong Answer

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'



if __name__ == '__main__':

    N = int(input())

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

    A = bubbleSort(n1,N)

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

    B = selectionSort(n2,N)

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

Submission status: Wrong Answer

Solution code:
import sys

ERROR_INPUT = 'input is invalid'


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

    sortLi = bubbleSort(li=arr, length=n)

    print(*list(map(lambda c: c.card, sortLi)))
    print(checkStable(inp=arr, out=sortLi))
    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 checkStable(inp, out):
    if inp == out:
        return 'Stable'
    else:
        return 'Not 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: Wrong Answer

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):
    if inp == out:
        return 'Stable'
    else:
        return 'Not 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: Wrong Answer

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):
    if list(map(lambda c: c.card, inp)) == list(map(lambda c: c.card, out)):
        return 'Stable'
    else:
        return 'Not 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: Wrong Answer

Solution code:
#coding: UTF-8

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

  def selectionSort(r, c, n):
    print(r)
    print(c)
    tmp_r, tmp_c = r, c
    for i in range(0,n):
      minj = i
      for j in range(i,n):
        if tmp_c[j] < tmp_c[minj]:
          minj = j
      if tmp_c[i] != tmp_c[minj]:
        tmp_c[i], tmp_c[minj] = tmp_c[minj], tmp_c[i]
        tmp_r[j], tmp_r[minj] = tmp_r[minj], tmp_r[j]
    return tmp_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: Wrong Answer

Solution code:
#coding: UTF-8

import copy
class Algo:
  @staticmethod
  def bubbleSort(r, c, n):
    print(r)
    print(c)
    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):
    print(r)
    print(c)
    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: Wrong Answer

Solution code:
def bubble_sort(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(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(B)
print('Stable')
print(C)
if B == C:
    print('Stable')
else:
    print('Not stable')

Submission status: Wrong Answer

Solution code:
def bubble_sort(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(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: Wrong Answer

Solution code:
def selection(l):
	N = len(l)

	for i in range(N):
		minj = i

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

	return l


def bubble(l):
	N = len(l)
	flag = 1

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

	return l


def output(lists):
	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:
		prin("Not stable")

Submission status: Wrong Answer

Solution code:
def selection(l):
	N = len(l)

	for i in range(N):
		minj = i

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

	return l


def bubble(l):
	N = len(l)
	flag = 1

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

	return l


def output(lists):
	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: Wrong Answer

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(s1)
print('stable')
print(s2)
if s1==s2:
	print('Stable')
else:
	print('Not stable')

Submission status: Wrong Answer

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: Wrong Answer

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=d.index(min(d[i:]),i)
 if d[i][1]>=d[m][1]:d[i],d[m]=d[m],d[i]
print(*c);print("Stable")
print(*d)
b={i[1]for i in c}
print(["Stable","Not stable"][len(b)<len(c)])

Submission status: Wrong Answer

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(["Stable","Not stable"][len({i[1]for i in c})<len(c)])

Submission status: Wrong Answer

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: Wrong Answer

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]
    print(*C1)
    print("Stable")
    return C1[:]
    
def selectSort(C2,N):
    for i in range(0,N):
        minj = i
        for j in range(i,N-1):
            if C2[j][1] > C2[j+1][1]:
                minj = j+1
        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)

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

Submission status: Wrong Answer

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-1):
            if C2[j][1] > C2[j+1][1]:
                minj = j+1
        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: Wrong Answer

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-1):
            if C2[j][1] > C2[j+1][1]:
                minj = j+1
        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: Wrong Answer

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

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

def SelectionSort(c):
    for i in range(len(c)-1):
        m=i
        for j in range(i, len(c)-1):
            if int(c[j][-1]) < int(c[m][-1]):
                m=j
        c[j], c[m]=c[m],c[j]
    return c
l=r
a=BubbleSort(l)
#for i in range(10):
print(*a)
print('Stable')
b=SelectionSort(l)
#for i in range(0):
print(*b)
if a==b:
    print('Stable')
else:
    print('Not stable')

Submission status: Wrong Answer

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: Wrong Answer

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: Wrong Answer

Solution code:
n = input()
nums = input()
nums = nums.split()
print(' '.join(map(str, nums)))

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

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

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

bs = bubble_sort(nums, int(n))
print(' '.join(bs))
print('Stable')
ss = selection_sort(nums, int(n))
print(' '.join(ss))
print(is_stable(bs, ss))

Submission status: Wrong Answer

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 Cb
    print_stable(C, Cb)
    Cs = SelectionSort(list(C), N)
    print Cs
    print_stable(C, Cs)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = []
s = {}
for i in input().split():
  t = []
  for j, k in enumerate(i):
    if j == 0 and k not in s:
      s[k] = len(s.keys())
    t += [k]
  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 s[t[j-1][0]] > s[t[j][0]] else 0
print(*["{0}{1}".format(i[0], i[1]) for i in t])
print("Not stable" if f > 0 else "Stable")

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