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 is_stable(oline, line):
    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 (oline[i][1] == oline[j][1]) & (oline[i] == line[b]) & (oline[j] == line[a]):
                        return False
    return True

N = int(input())
line = input().split()
oline = line.copy()
#BubbleSort
for i in range(N):
    for j in range(N-1, i, -1):
        if int(line[j][1]) < int(line[j-1][1]):
            tmp = line[j]
            line[j] = line[j-1]
            line[j-1] = tmp
print(' '.join(line))
print(('Not stable', 'Stable')[is_stable(oline, line)])

#SelectionSort
line = oline.copy()
for i in range(N):
    minj = i
    for j in range(i+1, N):
        if int(line[minj][1]) > int(line[j][1]):
            minj = j
    tmp = line[i]
    line[i] = line[minj]
    line[minj] = tmp
print(' '.join(line))

print(('Not stable', 'Stable')[is_stable(oline, line)])

Submission status: Accepted

Solution code:
def is_stable(output_str, same_num_str):
    if len(same_num_str)>0:
        for i in range(len(same_num_str)):
            if output_str.find(same_num_str[i]) == -1:
                return "Not stable"
    return "Stable"
    
data_num = int(input())
cards = input().split(" ")
cards2 = cards[:]
cnt = 0
num_1 = 0
num_2 = 0
same_num_str = []
output_str = ""
judge_stbl = ""
for i in range(data_num):
    
    for j in range(data_num-1, i,-1):
        if int(cards[j][1:]) < int(cards[j-1][1:]):
            cards[j], cards[j-1] = cards[j-1], cards[j]
        elif int(cards[j][1:]) == int(cards[j-1][1:]):
            same_num_str.append(cards[j-1]+" "+cards[j])    
            
output_str = " ".join(cards) 
judge_stbl = is_stable(output_str, same_num_str)

print(output_str + "\n" + judge_stbl)

same_num_str = []
output_str = ""
judge_stbl = ""

for i in range(data_num):
    min_idx = i
    for j in range(i, data_num):
        if int(cards2[j][1:]) < int(cards2[min_idx][1:]):
            min_idx = j
        elif int(cards2[j][1:]) == int(cards2[min_idx][1:]) and j != min_idx:
            same_num_str.append(cards2[min_idx]+" "+cards2[j])    

    if i != min_idx:
        cards2[i], cards2[min_idx] = cards2[min_idx], cards2[i]

output_str = " ".join(cards2) 
judge_stbl = is_stable(output_str, same_num_str)

print(output_str + "\n" + judge_stbl)

Submission status: Accepted

Solution code:
def BubbleSort(C,N):
    for i in range(N):
        for j in range(i+1, N)[::-1]:
            if int(C[j][1]) < int(C[j - 1][1]):
                C[j],C[j-1] = C[j-1],C[j]

def SelectionSort(C,N):
    for i in range(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]

N = int(input())
C = (input()).split()
ORG = C[:]
BubbleSort(C,N)
print (" ".join(C))
print ("Stable")
C2=ORG
SelectionSort(C2,N)
print(" ".join(C2))
if C == C2:
    print ("Stable")
else:
    print ("Not stable")

Submission status: Accepted

Solution code:
import sys

def bubble_sort(C, N):
	for i in range(N):
		for j in range(N - 1, i, -1):
			if C[j][1] < C[j - 1][1]:
				C[j], C[j - 1] = C[j - 1], C[j]
				
	return C

def	selection_sort(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]
	
	return C

#fin = open("test.txt", "r")
fin = sys.stdin

N = int(fin.readline())
A = fin.readline().split()
B = A[:]

A = bubble_sort(A, N)
B = selection_sort(B, N)

print(" ".join(A))
print("Stable")

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

Submission status: Accepted

Solution code:
def isStable(inlist, outlist):
	flag = True
	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 int(inlist[i][1:]) == int(inlist[j][1:]) and inlist[i] == outlist[b] and inlist[j] == outlist[a]:
						flag = False
						break
				else:
					continue
				break
			else:
				continue
			break
		else:
			continue
		break

	return(flag)
N = int(input())
A = input().split()
B = A[:]
C = A[:]

flag = 1
counter = 0
while flag:
    flag = 0
    for i in reversed(range(1,N)):
        if int(C[i][1:]) < int(C[i-1][1:]):
            C[i], C[i-1] = C[i-1], C[i]
            counter += 1
            flag = 1
print(" ".join(map(str, C)))

if(isStable(A, C)):
	print("Stable")
else:
	print("Not stable")

counter=0
for i in range(N):
	Br = B[i:]
	Brr = [int(Br[j][1:]) for j in range(N-i)]
	num = Brr.index(min(Brr)) 
	if num != 0:
		B[i], B[(i+num)] = B[(i+num)], B[i]
		counter += 1
print(" ".join(map(str,B)))
if(isStable(A, B)):
	print("Stable")
else:
	print("Not stable")

Submission status: Accepted

Solution code:
def SelectionSort(A, N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if A[j][1:] < A[minj][1:]:
                minj = j
        #if i != minj:
            #times += 1
        A[i], A[minj] = A[minj], A[i]
        #print(*A)
    return A

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

    return A

N= int(input())
A = [str(x) for x in input().split()]
B = [0 for i in range(N)]
for i in range(N):
    B[i] = A[i]
bubble = BubbleSort(A, N)
selection = SelectionSort(B, N)
#print(A, B)
#print(*A)
print(*bubble)
print('Stable')
print(*selection)
if bubble == selection:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
# coding: utf-8
# Here your code !
A = int(input())
N = tuple(input().split())
bs=[]
ss=[]
def isStable(a,b):
    leng = int(len(a))
    for i in range(leng):
        for j in range(i+1,leng):
            for x in range(leng):
                for y in range(x+1,leng):
                    if a[i][1]==a[j][1] and a[i]==b[y] and a[j]==b[x]:
                        return "Not stable"
    return "Stable"
    
def bSort(n,a):
    n = list(n)
    for i in range(a):
        for j in range(a-1,i,-1):
            if int(n[j][1]) < int(n[j-1][1]):
                n[j],n[j-1]=n[j-1],n[j]
    return n
    #print(" ".join(n))

    
def seleSort(n,a):
    n = list(n)
    for i in range(a):
        minj = i
        for j in range(i+1,a):
            if n[j][1]<n[minj][1]:
                minj = j
                
        n[i],n[minj]=n[minj],n[i]
    return n
    #print(" ".join(n))

bs = bSort(N,A)
ss = seleSort(N,A)
print(" ".join(bs))
print(isStable(bs,bs))
print(" ".join(ss))
print(isStable(bs,ss))

Submission status: Accepted

Solution code:
N = int(input())
A = [ x for x in input().split(" ")]
orig_A = A[:]

#bubblesort
for i in range(0, N):
    for j in range(N-1, i, -1):
        if int(A[j][1]) < int(A[j-1][1]):
            A[j], A[j-1] = A[j-1], A[j]

print(*A)
print("Stable")


#selectionsort
for i in range(0, N):
    minj = i
    for j in range(i, N):
        if int(orig_A[j][1]) < int(orig_A[minj][1]):
            minj = j
    orig_A[i], orig_A[minj] = orig_A[minj], orig_A[i]


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

Submission status: Accepted

Solution code:
N, C = int(input()), [temp for temp in input().split()]
D    = list(C)

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

for i in range(N) :
    minj = i
    for j in range(i, N) :
        if int(D[j][1 :]) < int(D[minj][1 :]) :
            minj = j
    D[i], D[minj] = D[minj], D[i]
print(*D)

cou = 0
for che in range(N) :
    if C[che] != D[che] :
        cou = 1
if cou == 0 : print('Stable')
else        : print('Not stable')

Submission status: Accepted

Solution code:
N = input()
A = map(str,raw_input().split())
Ab = A[:]
As = A[:]

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

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
        v = A[i]
        A[i] = A[minj]
        A[minj] = v

def Output(A):
    for i in range(N-1):
        print A[i],
    print A[-1]

def Stable(AA):
    n = []
    for i in range(N-1):
        if AA[i][1] == AA[i+1][1] and AA[i][1] not in n:
            n.append(AA[i][1])
    l = []
    m = []
    for item in n:
        for i in range(N):
            if AA[i][1] == item:
                l.append(AA[i])
            if A[i][1] == item:
                m.append(A[i])
    if l == m:
        msg = "Stable"
    else:
        msg = "Not stable"
    print msg

SelectionSort(As,N)
BubbleSort(Ab,N)

Output(Ab)
Stable(Ab)
Output(As)
Stable(As)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import copy

def bubble_sort(card, N):
    for i in range(0, N):
        for j in range(N-1, i, -1):
            if value(card[j]) < value(card[j-1]):
                card[j], card[j-1] = card[j-1], card[j]
    return " ".join(map(str, card))


def selection_sort(card, N):
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if value(card[j]) < value(card[minj]):
                minj = j
        card[i], card[minj] = card[minj], card[i]
    return " ".join(map(str, card))


# check method
# insertion sort is a stable sort.
def insertion_sort(card, N):
    for i in range(1, N):
        v = card[i]
        j = i - 1
        while j >= 0 and value(card[j]) > value(v):
            card[j+1] = card[j]
            j -= 1
        card[j+1] = v
    return " ".join(map(str, card))


def value(elem):
    return elem[1]


def main():
    size = int(input())
    line = input().split()
    gold_standard = insertion_sort(copy.deepcopy(line), copy.deepcopy(size))

    bubble_ans = bubble_sort(copy.deepcopy(line), copy.deepcopy(size))
    print(bubble_ans)
    if bubble_ans == gold_standard:
        print('Stable')
    else:
        print('Not stable')

    selection_ans = selection_sort(copy.deepcopy(line), copy.deepcopy(size))
    print(selection_ans)
    if selection_ans == gold_standard:
        print('Stable')
    else:
        print('Not stable')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class Card:
    def __init__(self, suit, value):
        self.suit = suit
        self.value = value
    
def selection(ls):
    for i in range(len(ls)):
        minj = i
        
        for j in range(i, len(ls)):
            if ls[j].value < ls[minj].value:
                minj = j
        ls[i], ls[minj] = ls[minj], ls[i]

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

def isStable(ls1, ls2):
    if ls1 == ls2:
        print("Stable")
    else:
        print("Not stable")

def printcards(cards):
    for x in range(len(cards)):
        if x == len(cards) - 1:
            print(cards[x].suit + cards[x].value)
        else:
            print(cards[x].suit + cards[x].value, ' ', sep='', end='')

def main():
    N = int(input().rstrip())

    cards = []
    for card in list(input().split(' ')):
        cards.append(Card(card[0], card[1]))

    a = [x for x in cards]
    b = [x for x in cards]
    

    bubblesort(a)
    selection(b)
    
    printcards(a)
    print("Stable")

    printcards(b)
    isStable(a,b)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def bubble_sort(num_list):
    list_b = num_list[:]
    for i in range(len(list_b)-1):
        for j in range(len(list_b)-1,i,-1):
            if list_b[j][1] < list_b[j-1][1]:
                list_b[j],list_b[j-1] = list_b[j-1],list_b[j]
    return list_b

def selection_sort(num_list):
    list_s = num_list[:]
    for i in range(len(list_s)):
        minj = i
        for j in range(i,len(list_s)):
            if list_s[minj][1] > list_s[j][1]:
                minj = j
        list_s[i],list_s[minj] = list_s[minj],list_s[i]
    return list_s

def isStable(list_x, list_y):
    leng = int(len(list_x))
    for i in range(leng-1):
        for j in range(i+1, leng):
            for x in range(leng-1):
                for y in range(x+1, leng):
                    if list_x[i][1]==list_x[j][1] and list_x[i]==list_y[y] and list_x[j] == list_y[x]:
                        return "Not stable"
    return "Stable"


qnt = int(input())
num_list = input().split()

bs = bubble_sort(num_list)
ss = selection_sort(num_list)
print(" ".join(bs))
print(isStable(num_list,bs))
print(" ".join(ss))
print(isStable(num_list,ss))

Submission status: Accepted

Solution code:
def bubble_sort(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]):
				A[j], A[j-1] = A[j-1], A[j]
				flag = 1

		i += 1
	
	return A

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

		if i != minj:
			A[i], A[minj] = A[minj], A[i]

	return A

def is_stable(A, B, 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 int(A[i][1]) == int(A[j][1]) and A[i] == B[b] and A[j] == B[a]:
						return False

	return True

def print_stable(flag):
	if flag:
		print('Stable')
	else:
		print('Not stable')

if __name__ == '__main__':
	n = int(input())
	A = list(input().split())
	A2 = A[:]

	B = bubble_sort(A, n)
	print(' '.join(B))
	print_stable(is_stable(A, B, n))

	B = selection_sort(A2, n)
	print(' '.join(B))
	print_stable(is_stable(A, B, n))

Submission status: Accepted

Solution code:
def bubble_sort(A, n):
	for i in range(n):
		for j in range(n-1, i, -1):
			if A[j][1] < A[j-1][1]:
				A[j], A[j-1] = A[j-1], A[j]

	print(' '.join(A))

def selection_sort(A, n):
	for i in range(n):
		minj = i
		for j in range(i, n):
			if A[j][1] < A[minj][1]:
				minj = j
		if i != minj:
			A[i], A[minj] = A[minj], A[i]

	print(' '.join(A))

if __name__ == '__main__':
	n = int(input())
	A = list(input().split())
	B = A[:]

	bubble_sort(A, n)
	print('Stable')

	selection_sort(B, n)
	print('Stable' if A == B else 'Not stable')

Submission status: Accepted

Solution code:
def bubble_sort(A, n):
	for i in range(n):
		for j in range(n-1, i, -1):
			if A[j][1] < A[j-1][1]:
				A[j], A[j-1] = A[j-1], A[j]

	print(' '.join(A))

def selection_sort(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(' '.join(A))

if __name__ == '__main__':
	n = int(input())
	A = list(input().split())
	B = A[:]

	bubble_sort(A, n)
	print('Stable')

	selection_sort(B, n)
	print('Stable' if A == B else 'Not stable')

Submission status: Accepted

Solution code:
#ALDS1_2-C Sort 1 - Stable Sort
def selectionSort(A,N):
    c=0
    for i in range(N):
        minj = i
        j=i
        while j<N:
            if(int(A[j][1])<int(A[minj][1])):
                minj = j
            j+=1
        if(i!=minj):
            A[i],A[minj]=A[minj],A[i]
            c+=1
    return c

def bubbleSort(A,N):
    c=0
    flag=1
    while flag:
        flag=0
        j=N-1
        while j>0:
            if(int(A[j][1])<int(A[j-1][1])):
                c+=1
                A[j],A[j-1]=A[j-1],A[j]
                flag=1
            j-=1
    return c

N=int(input())
A=input().split()
checkA=[""]*9
for i in range(N):
    checkA[int(A[i][1])-1]+=A[i][0]

B=[]+A
C=[]+A

bubbleSort(B,N)
checkB=[""]*9
for i in range(N):
    checkB[int(B[i][1])-1]+=B[i][0]
S=""
for i in range(N-1):
    S+=B[i]+" "
S+=str(B[-1])
print(S)
if(checkB==checkA):
    print("Stable")
else:
    print("Not stable")
    
selectionSort(C,N)
checkC=[""]*9
for i in range(N):
    checkC[int(C[i][1])-1]+=C[i][0]
S=""
for i in range(N-1):
    S+=C[i]+" "
S+=str(C[-1])
print(S)
if(checkC==checkA):
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
N = int(input())
A1 = list(map(str,input().split()))
A2 = A1[:]

def bubbleSort(A, N):
 flag = 0
 i = 0
 while flag == 0:
  flag = 1
  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 = 0
  i += 1
 return A

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

def stable(Ab, As, N):
 for i in range(N):
  if Ab[i] != As[i]:
   return False
 return True

bubbleSort(A1, N)
selectSort(A2, N)
print(" ".join(map(str, A1)))
print("Stable")
print(" ".join(map(str, A2)))
if stable(A1, A2, N):
 print("Stable")
else:
 print("Not stable")

Submission status: Accepted

Solution code:
n = int(input())
a = input().strip().split()
#Bubble sort
b = a[:]
for i in range(n):
    for j in range(n-1,i,-1):
        if b[j][1] < b[j-1][1]:
            b[j],b[j-1] = b[j-1],b[j]
print(' '.join(b))
print('Stable')
#Selection sort
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(' '.join(a))
print('Stable' if b == a else 'Not stable')

Submission status: Accepted

Solution code:
# coding=utf-8

def print_list(X):
    first_flag = True
    for val in X:
        if first_flag:
            print_line = str(val)
            first_flag = False
        else:
            print_line = print_line + ' ' + str(val)
    print(print_line)

def combine_list(A_suit, A_rank, N):
    A_after = []
    for i in range(N):
        A_after.append(A_suit[i] + str(A_rank[i]))
    return A_after


def bubble_sort(A, index_list, N):
    #print_list(A)
    #flag: ???????????????????????????True???????´?
    flag = True
    i = 0
    while flag:
        flag = False
        for j in range(N-1, i, -1):
            if A[j] < A[j-1]:
                A[j-1], A[j] = A[j], A[j-1]
                index_list[j-1], index_list[j] = index_list[j], index_list[j-1]
                flag = True
        i += 1
    return A, index_list

def selection_sort(A, index_list, N):
    for i in range(N):
        min_j = i
        for j in range(i, N):
            if A[j] < A[min_j]:
                min_j = j
        if i != min_j:
            A[i], A[min_j] = A[min_j], A[i]
            index_list[i], index_list[min_j] = index_list[min_j], index_list[i]
    return A, index_list

def main():
    N = int(input())
    A = list(input().split())
    A_suit = []
    A_rank = []
    index_list = [x for x in range(N)]
    A_after_bubble = []
    A_after_selection = []

    for element in A:
        val = list(element)
        val_suit = val[0]
        val_rank = int(val[1])
        A_suit.append(val_suit)
        A_rank.append(val_rank)
    A_suit_after_bubble = [0 for x in range(N)]
    A_suit_after_selection = [0 for x in range(N)]

    A_rank_after_bubble, index_list_after_bubble = bubble_sort(A_rank.copy(), index_list.copy(), N)
    A_rank_after_selection, index_list_after_selection = selection_sort(A_rank.copy(), index_list.copy(), N)

    for index_before, index_after in enumerate(index_list_after_bubble):
        A_suit_after_bubble[index_before] = A_suit[index_after]

    for index_before, index_after in enumerate(index_list_after_selection):
        A_suit_after_selection[index_before] = A_suit[index_after]

    A_after_bubble = combine_list(A_suit_after_bubble, A_rank_after_bubble, N)
    A_after_selection = combine_list(A_suit_after_selection, A_rank_after_selection, N)

    print_list(A_after_bubble)
    print("Stable")
    print_list(A_after_selection)
    if A_after_selection == A_after_bubble:
        print("Stable")
    else:
        print("Not stable")



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from operator import lt

def main():
    N = int(input())
    A = list(input().split(' '))

    Ab = bubbleSort(A[:], N, lambda a, b: int(a[1]) < int(b[1]))
    As = selectionSort(A[:], N, lambda a, b: int(a[1]) < int(b[1]))

    print(' '.join([str(a) for a in Ab]))
    print('Stable')

    print(' '.join([str(a) for a in As]))
    print('Stable' if Ab == As else 'Not stable')

def bubbleSort(A, N, comp=lt):
    flag = True

    while flag:
        flag = False

        for j in range(N-1, 0, -1):
            if comp(A[j], A[j-1]):
                A[j], A[j-1] = A[j-1], A[j]
                flag = True

    return A

def selectionSort(A, N, comp=lt):
    for i in range(0, N-1):
        minj = i

        for j in range(i, N):
            if comp(A[j], A[minj]):
                minj = j

        if i != minj:
            A[i], A[minj] = A[minj], A[i]

    return A

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def rls(): return list(map(str, input().split()))
def pl(a): print(" ".join(list(map(str, a))))


N = ri()
a = rls()
bubble = a[:]

flag = True
while(flag):
    flag = False
    for i in range(1, N):
        if(bubble[-i][1] < bubble[-i-1][1]):
            hold = bubble[-i]
            bubble[-i] = bubble[-i-1]
            bubble[-i-1] = hold
            flag = True
pl(bubble)
print("Stable")  # ?????????Stable

selection = a[:]
for i in range(N):
    minj = i
    for j in range(i, N):
        if(selection[j][1] < selection[minj][1]):
            minj = j
    hold = selection[i]
    selection[i] = selection[minj]
    selection[minj] = hold

pl(selection)
print("Stable" if bubble == selection else "Not stable")

Submission status: Accepted

Solution code:
def buble(lst):

    src_list = list(lst)
    flag=True
    while flag:
        flag = False
        for idx in range(len(lst)-1, 0, -1):
            if int(lst[idx][1]) < int(lst[idx-1][1]):
                tmp=lst[idx]
                lst[idx]=lst[idx-1]
                lst[idx-1]=tmp
                flag=True

    flag_stable = True
    for num in range(0, 9):
        tmp1 = []
        tmp2 = []
        for i in range(0, len(lst)):
            if int(lst[i][1]) == num:
                tmp1.append(lst[i])
            if int(src_list[i][1]) == num:
                tmp2.append(src_list[i])

        if tmp1 != tmp2:
           flag_stable = False
           break
    print " ".join(lst)

    if flag_stable:
        print "Stable"
    else:
        print "Not stable"

def selection(lst):

    src_list = list(lst)
    for i in range(len(lst)):
        m = i
        for j in range(i,len(lst)):
            if int(lst[m][1]) > int(lst[j][1]):
                m=j
        tmp=lst[i]
        lst[i]=lst[m]
        lst[m]=tmp

    flag_stable = True
    for num in range(0, 9):
        tmp1 = []
        tmp2 = []
        for i in range(0, len(lst)):
            if int(lst[i][1]) == num:
                tmp1.append(lst[i])
            if int(src_list[i][1]) == num:
                tmp2.append(src_list[i])

        if tmp1 != tmp2:
           flag_stable = False
           break

    print " ".join(lst)
    if flag_stable:
        print "Stable"
    else:
        print "Not stable"


n=raw_input()
lst1 = raw_input().split()
lst2 = list(lst1)

buble(lst1)
selection(lst2)

Submission status: Accepted

Solution code:
class Cards:
    def __init__(self,shape,value):
        self.shape = shape
        self.value = value

n = int(input())
s = input().split(" ")
cards1 = []
for i in range(n):
    cards1.append(Cards(s[i][0],int(s[i][1])))
cards2 = list(cards1)
for i in range(n):
    for j in range(n-1,i,-1):
        if cards1[j].value < cards1[j-1].value:
            w = cards1[j]
            cards1[j] = cards1[j-1]
            cards1[j-1] = w
for i in range(n):
    if i == n-1:
        print("{0}{1}".format(cards1[i].shape,cards1[i].value))
    else:
        print("{0}{1}".format(cards1[i].shape,cards1[i].value),end=" ")
print("Stable")

for i in range(n):
    minj = i
    for j in range(i+1,n):
        if cards2[j].value < cards2[minj].value:
            minj = j
    w = cards2[i]
    cards2[i] = cards2[minj]
    cards2[minj] = w
for i in range(n):
    if i == n-1:
        print("{0}{1}".format(cards2[i].shape,cards2[i].value))
    else:
        print("{0}{1}".format(cards2[i].shape,cards2[i].value),end=" ")
for i in range(n):
    if cards1[i].shape != cards2[i].shape:
        print("Not stable")
        break
    if i == n-1:
        print("Stable")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 18 10:01:05 2017

@author: syaga
"""

if __name__ == "__main__":
    N = int(input())
    C = list(input().split())
    D = C[:]

    # Bunbble Sort
    for i in range(0, N):
        for j in range(N-1, i, -1):
            if int(C[j][1]) < int(C[j-1][1]):
                temp = C[j]
                C[j] = C[j-1]
                C[j-1] = temp
    print(" ".join(C))
    print("Stable")

    # Selection Sort
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if int(D[j][1]) < int(D[minj][1]):
                minj = j
        temp = D[i]
        D[i] = D[minj]
        D[minj] = temp
    print(" ".join(D))
    flag = 0
    for (i, j) in zip(C, D):
        if i != j:
            flag = 1
            break
    if flag == 1:
        print("Not stable")
    else:
        print("Stable")

Submission status: Accepted

Solution code:
N = int(input())
a = [(s[0], int(s[1])) for s in input().split()]

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

def selection(a):
    n = len(a)
    for i in range(n):
        minj = i
        for j in range(i+1, n):
            if a[j][1] < a[minj][1]:
                minj = j
        a[i], a[minj] = a[minj], a[i]

    return a

b_a = bubble(a[:])
s_a = selection(a[:])

print(" ".join([p[0]+str(p[1]) for p in b_a]))
print("Stable")
print(" ".join([p[0]+str(p[1]) for p in s_a]))
print("Stable" if b_a==s_a else "Not stable")

Submission status: Accepted

Solution code:
import copy

n = int(input())
a = input().split()
b = copy.deepcopy(a)

for i in range(n):
    for j in range(n - 1 - i):
        if int(a[j][1]) > int(a[j + 1][1]):
            tmp = a[j]
            a[j] = a[j + 1]
            a[j + 1] = tmp

ra = " ".join(a)

print(ra)
print("Stable")

for i in range(n - 1):
    minj = i
    for j in range(i + 1, n):
        if int(b[j][1]) < int(b[minj][1]):
            minj = j
    if minj != i:
        tmp = b[i]
        b[i] = b[minj]
        b[minj] = tmp

rb = " ".join(b)
print(rb)

if ra == rb:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
def bubble(A, N):
    flag = True
    while flag:
        flag = False
        for j in range(N-1, 0, -1):
            if int(A[j][-1]) < int(A[j-1][-1]):
                A[j], A[j-1] = A[j-1], A[j]
                flag = True
    return A

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

if __name__ == "__main__":
    N = int(input())
    A = input().split()

    A_bubble = bubble(A[:], N)
    print (*A_bubble)
    print ("Stable")

    A_selection = selection(A[:], N)
    print (*A_selection)
    if A_bubble == A_selection:
        print ("Stable")
    else:
        print ("Not stable")

Submission status: Accepted

Solution code:

def BubbleSort(N, C):
    C = [] + C
    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]
    return C

def SelectionSort(N, C):
    C = [] + C
    for i in range(N):
        minj = i
        for j in range(i, N):
            if C[minj][1] > C[j][1]:
                minj = j
        C[i], C[minj] = C[minj], C[i]
    return C

def CompareSuit(L1, L2):
    suit1, suit2 = "", ""
    for i in range(len(L1)):
        suit1 = suit1 + L1[i]
        suit2 = suit2 + L2[i]
    if suit1 == suit2:
        return "Stable"
    else:
        return "Not stable"

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

C1 = BubbleSort(N, C)
C2 = SelectionSort(N, C)

print(" ".join(C1))
print(CompareSuit(C1, C1))
print(" ".join(C2))
print(CompareSuit(C1, C2))

Submission status: Accepted

Solution code:
N=int(input())
A=input().split()

B=A[:]
S=A[:]

def BubbleSort(A, N):
    count = 0
    flag = True
    while flag:
        flag = False
        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]
                count += 1
                flag = True
                
    return A

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
        A[i], A[minj] = A[minj], A[i] 
        count += 1
    return A

b = BubbleSort(B, N)
s = SelectionSort(S, N)
print(*b)
print("Stable")
print(*s)

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