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:
import sys

class Card:
    def __init__(self, kind, num):
        self.kind = kind
        self.num = num
    def __eq__(self, other):
        return (self.kind == other.kind) and (self.num == other.num)
    def __ne__(self, other):
        return not ((self.kind == other.kind) and (self.num == other.num))
    def __str__(self):
        return self.kind + self.num

def list_to_string(array):
    s = ""
    for n in array:
        s += str(n) + " "
    return s.strip()
    
def swap(array, i, j):
    tmp = array[i]
    array[i] = array[j]
    array[j] = tmp

def is_stable(array1, array2):
    if reduce(lambda x, y: x and y, map(lambda x: x[0] == x[1], zip(array1, array2))):
        return "Stable"
    else:
        return "Not stable"

def bubble_sort(array):
    for i in range(0, len(array)):
        for j in reversed(range(i+1, len(array))):
            if array[j].num < array[j-1].num:
                swap(array, j, j-1)
    return array
        
def selection_sort(array):
    for i in range(0, len(array)):
        min_index = i
        for j in range(i, len(array)):
            if array[min_index].num > array[j].num:
                min_index = j
        swap(array, i, min_index)
    return array

def main():
    num = int(sys.stdin.readline().strip())
    array = map(lambda x: Card(x[0], x[1]), sys.stdin.readline().strip().split(" "))

    a = list(array)
    b = list(array)

    print list_to_string(bubble_sort(a))
    print "Stable"
    print list_to_string(selection_sort(b))
    print is_stable(a, b)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def print_list(array, N):
    for i in range(N):
        if i == N-1:
            print(array[i])
        else:
            print(array[i], end=" ")
            
def stable_sort(array_a, array, N):
    for i in range(N-1):
        stable = "yes"
        if array[i][1] == array[i+1][1]:
            index_1 = array.index(array[i])
            index_2 = array.index(array[i+1])
            index_a1 = array_a.index(array[i])
            index_a2 = array_a.index(array[i+1])
            #print(index_1, index_2, index_a1, index_a2)
            if not(index_1 < index_2\
            and index_a1 < index_a2):
                stable = "no"
                break
    if stable == "yes":
        print("Stable")
    else:
        print("Not stable")
            
N = int(input())
a = input().split()
b = [s for s in a]
for i in range(N-1):
    for j in range(N-1, i, -1):
        if b[j][1] < b[j-1][1]:
            t = b[j]
            b[j] = b[j-1]
            b[j-1] = t
print_list(b, N)
stable_sort(a, b, N)

c = [s for s in a]
for i in range(N-1):
    min_i = c[i][1]
    change = "no"
    for j in range(i+1, N):
        if min_i > c[j][1]:
            min_i = c[j][1]
            index = c.index(c[j])
            change = "ok"
    if change == "ok":
        t = c[i]
        c[i] = c[index]
        c[index] = t
print_list(c, N)
stable_sort(a, c, N)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
??????????????????
?????????????????????????????´?????????????????????
????????§?????????????????????(S, H, C, D)??¨???????????°???(1, 2, ..., 9)??????
?§??????????????¨? 36 ????????????????????¨????????????
????????°??????????????? 8 ???"H8"??????????????? 1 ???"D1"??¨??¨????????????

????????????????????????????????????????????¢?????´??????????????¨?????????
??????????????? N ????????????????????????????????°???????????????
???????????´?????????????????°????????????????????????????????????
??¢?????´??????????????????????????\????????????????????????????????????????????¨????????????
??°??????????´???? 0 ??????????????§?¨???°?????????????????????

1 BubbleSort(C, N)
2   for i = 0 to N-1
3     for j = N-1 downto i+1
4       if C[j].value < C[j-1].value
5         C[j] ??¨ C[j-1] ?????????
6
7 SelectionSort(C, N)
8   for i = 0 to N-1
9     minj = i
10    for j = i to N-1
11      if C[j].value < C[minj].value
12        minj = j
13    C[i] ??¨ C[minj] ?????????

??????????????¢?????´?????????????????????????????????????????\??????????????????????????????????????£??????????????±????????????????????????

"""
import math

def swap(A, x, y):
    """ ??????A???x????????¨y?????????????´??????\???????????? """
    t = A[x]
    A[x] = A[y]
    A[y] = t

def value(c):
    """ ??????????????°?????¨???????????? """
    return int(c[1:])

def suits(A):
    """ ????????????????????????????????¨???????????????????????? """
    s = ""
    for c in A:
        s = s + c[0]
    return s

def bSort(A, N):
    """ ?????????????????? """
    for i in range(0, N-1):
        for j in range(N-1, i, -1):
            if value(A[j]) < value(A[j-1]):
                swap(A,j,j-1)

def sSort(A, N):
    """ ?????????????????? """
    for i in range(0, N-1):
        minj = i
        for j in range(i,N):
            if value(A[j]) < value(A[minj]):
                minj = j
        if minj != i:
            swap(A,i,minj)

# ?????????
N = int(input().strip())
A = input().strip().split()
bA = A[:]
bSort(bA,N)
b1 = suits(bA)
print(" ".join(map(str,bA)))
print("Stable")

sA = A[:]
sSort(sA,N)
s1 = suits(sA)
print(" ".join(map(str,sA)))
if s1 == b1:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
import re


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


def selection_sort(C, N):
    for i in range(N):
        # i ?????????????????¨????????????
        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


def is_stable(C, sorted):
    # ????????°???????????????????¨???????????????????????´???????????????????
    c_container = []
    s_container = []
    for i in range(len(C)):
        # C ??§ i ????????\?????????????????§????????°????????????????????¢???
        for j in range(len(C)):
            # ????????°???????????????????????£?????´???
            if C[i][1] == C[j][1]:
                # C ????????????????¨?????????????
                c_container.append(C[j][0])
        # ????????°???????????????????????¨????????´???
        if len(c_container) >= 2:
            # C ??§ i ???????????????????????°?????¨????????°????????????????????¢???
            for k in range(len(sorted)):
                # ????±??????????????????°?????¨????????°???????¨?????????????????????????????????????????????????????´?
                if sorted[k][1] == C[i][1]:
                    s_container.append(sorted[k][0])
            # ??????????????´?????????????????£?????´???
            if c_container != s_container:
                # Not Stable
                return False
        # ?????????????????????
        c_container = []
        s_container = []

    return True


if __name__ == '__main__':
    N = int(input())
    # ??????????????????????????????????????¨?????¨??°?????¨?????????????????????????´?
    cards = input().split()
    C = [[] for i in range(N)]
    for i in range(N):
        # ??????????¨??????¨??°????????????
        symbol_and_num = re.findall(r'(\d+|\D+)', cards[i])
        C[i] = [symbol_and_num[0], int(symbol_and_num[1])]

    # ??????????????????????????????
    bubble_sorted = bubble_sort(C.copy(), N)
    # ?¨??????¨???????????????
    bubble_sorted_cards = [val[0] + str(val[1]) for val in bubble_sorted]
    # ?????????????????????
    print(' '.join(bubble_sorted_cards))
    # stable or not stable
    print('Stable' if is_stable(C, bubble_sorted) else 'Not stable')

    # ?????????????????????
    selection_sorted = selection_sort(C.copy(), N)
    # ?¨??????¨???????????????
    selection_sorted_cards = [val[0] + str(val[1]) for val in selection_sorted]
    # ?????????????????????
    print(' '.join(selection_sorted_cards))
    # stable or not stable
    print('Stable' if is_stable(C, selection_sorted) else 'Not stable')

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    CARD = tuple(input().split())

    sort_ = []
    for i in range(1, 10):
        for s in CARD:
            if str(i) in s:
                sort_.append(s)

    sort_ = tuple(sort_)
    bsort = tuple(bubbleSort(list(CARD), N))
    ssort = tuple(selectionSort(list(CARD), N))

    for s in (bsort, ssort):
        print(*s, sep=' ')
        if s == sort_:
            print('Stable')
        else:
            print('Not stable')

def bubbleSort(c, n):
    flag = 1
    while flag:
        flag = 0
        for i in range(1, n):
            if c[i][1] < c[i-1][1]:
                c[i], c[i-1] = c[i-1], c[i]
                flag = 1
    return c

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]
    return c

main()

Submission status: Accepted

Solution code:
def BubbleSort(C,n):
	for i in range(n):
		for j in range(i+1,n)[::-1]:
			if C[j][1] < 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 C[j][1] < C[minj][1]:
				minj = j
		C[i],C[minj] = C[minj],C[i]
	return C

def stable(C):
	new = []
	for i in range(1,10):
		Ci = [cc for cc in C if cc[1]==str(i)]
		new += Ci
	return new

n = int(input())
C = input().split()
x,y,z = C[:],C[:],C[:]
bubble = BubbleSort(x,n)
selection = SelectionSort(y,n)
sta = stable(z)

print(' '.join(bubble))
print({True:'Stable',False:'Not stable'}[sta==bubble])
print(' '.join(selection))
print({True:'Stable',False:'Not stable'}[sta==selection])

Submission status: Accepted

Solution code:
# bable sort
def bubbleSort(o_nums, n):
    nums=o_nums[:]
    for i in range(len(nums)-1):
        for j in range(len(nums)-1,i,-1):
            if nums[j][1]<nums[j-1][1]:
                nums[j],nums[j-1]=nums[j-1],nums[j]  
    return nums

# selection sort
def selectionSort(o_nums,n):
    nums=o_nums[:]
    for i in range(n):
        minj=i
        for j in range(i,n):
            if nums[j][1]<nums[minj][1]:
                minj=j
        if nums[i][1]!=nums[minj][1]:
            nums[i],nums[minj]=nums[minj],nums[i]
    return nums

n=int(input())
cards=list(input().split())

b=bubbleSort(cards, n)
s=selectionSort(cards,n)
print(*b)
print("Stable")
print(*s)
if bubbleSort(cards, n) == selectionSort(cards, n):
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
n = int(input())
*A, = input().split()
B = 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]
print(*A)
print("Stable")

for i in range(n):
    mj = i
    for j in range(i, n):
        if B[j][1] < B[mj][1]:
            mj = j
    B[i], B[mj] = B[mj], B[i]
print(*B)
if A == B:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
# coding: utf-8
# Here your code !
n=int(input())
cards=input().split()

def bubble_sort(cards_b,n):
    for i in range(n):
        for j in range(-1,-n,-1):
            a=int(cards_b[j][1])
            b=int(cards_b[j-1][1])
            if a<b:
                cards_b[j],cards_b[j-1]=cards_b[j-1],cards_b[j]
    return cards_b

def selection_sort(cards_s,n):
    for i in range(n):
        minv=i
        for j in range(i,n):
            a=int(cards_s[minv][1])
            b=int(cards_s[j][1])
            if a>b:
                minv=j
        cards_s[minv],cards_s[i]=cards_s[i],cards_s[minv]
    return cards_s


dummy=cards.copy()
ans_1=bubble_sort(cards,n)

ans_2=selection_sort(dummy,n)

print(*ans_1)
print("Stable")
print(*ans_2)
if ans_1!=ans_2:
    print("Not stable")
else:
    print("Stable")

Submission status: Accepted

Solution code:
import copy

def stable(origin, new):
    for i in range(n-1):
        if int(new[i][1]) == int(new[i+1][1]):
            if origin.index(new[i]) > origin.index(new[i+1]):
                return False
    return True

n = int(raw_input())
a_origin = raw_input().split()

a = copy.copy(a_origin)
b = copy.copy(a_origin)

# bubble sort
for i in range(n):
    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

for i in range(n):
    if i == n-1:
        print a[i]
    else:
        print a[i], 

if stable(a_origin, a):
    print 'Stable'
else:
    print 'Not stable'

# selection sort
for i in range(n):
    minj = i
    for j in range(i, n):
        if int(b[j][1]) < int(b[minj][1]):
            minj = j
    tmp = b[i]
    b[i] = b[minj]
    b[minj] = tmp

for i in range(n):
    if i == n-1:
        print b[i]
    else:
        print b[i],

if stable(a_origin, b):
    print 'Stable'
else:
    print 'Not stable'

Submission status: Accepted

Solution code:
N = int(input())
B = input().split()
S = B[:]

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]
    
    m = i
    for j in range(i, N):
        if S[m][1] > S[j][1]:
            m = j
    S[m], S[i] = S[i], S[m]

print(*B)
print('Stable')
print(*S)
print(['Not s', 'S'][B==S] + 'table')

Submission status: Accepted

Solution code:
# your code goes here
N=int(input())
Ci=[i for i in input().split()]
C=[]
for i in range(N):
   # print(C)
    C.append([])
    C[i].append(Ci[i][0])
  #  print(C)
    C[i].append(int(Ci[i][1]))
Cb=C
fl=1
#print(Cb)
while fl==1:
    fl=0
    for j in range(N-1):
   #     print(Cb)
        if Cb[N-1-j][1]<Cb[N-2-j][1]:
       #     print(Cb)
            t=Cb[N-1-j]
            Cb[N-1-j]=Cb[N-2-j]
            Cb[N-2-j]=t
            fl=1
        #    print(C)
for i in range(N):
    Cb[i][1]=str(Cb[i][1])
 #   print(Cb)
    Cb[i]="".join(Cb[i])
print(" ".join(Cb))
p="Stable"
print(p)
C=[]
for i in range(N):
 #   print(C)
    C.append([])
    C[i].append(Ci[i][0])
  #  print(C)
    C[i].append(int(Ci[i][1]))
Co=[]
for i in range(N):
    Co.append([])
  #  print(Co)
    Co[i].append(Ci[i][0])
    Co[i].append(int(Ci[i][1]))
for i in range(N-1):
    minj=i
    for j in range(i,N):
    #    print(C)
        if C[j][1]<C[minj][1]:
            minj=j
        elif C[j][1]==C[minj][1]:
            k=0
            while k<N and C[minj][1]!=Co[k][1]:
                k+=1
    #        print (j)
            if k<N and C[minj][0]!=Co[k][0]:
                p="Not stable"
    if i!=minj:
        t=C[i]
        C[i]=C[minj]
        C[minj]=t
   # print(minj)
for i in range(N):
    C[i][1]=str(C[i][1])
    C[i]="".join(C[i])
print(" ".join(C))
print(p)

Submission status: Accepted

Solution code:
# Aizu Problem ALDS_1_2_C: Stable Sort
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input2.txt", "rt")


def printA(A):
    print(' '.join([str(a) for a in A]))


def bubble_sort(A):
    for i in range(len(A) - 1):
        for j in range(len(A) - 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_sort(A):
    for i in range(len(A)):
        mini = i
        for j in range(i, len(A)):
            if A[j][1] < A[mini][1]:
                mini = j
        if mini != i:
            A[i], A[mini] = A[mini], A[i]
    return A

def is_stable(A, B):
    for val in range(1, 10):
        v = str(val)
        if [a[0] for a in A if a[1] == v] != [b[0] for b in B if b[1] == v]:
            return False
    return True
        
N = int(input())
A = list(input().split())
A_bubble = bubble_sort(A[:])
printA(A_bubble)
print("Stable" if is_stable(A, A_bubble) else "Not stable")
A_select = selection_sort(A[:])
printA(A_select)
print("Stable" if is_stable(A, A_select) else "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]
    print " ".join(map(str, C))
    print "Stable"

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]
    print " ".join(map(str, C))


N = int(raw_input())
L = raw_input().split()

t1 = list(L)
BubbleSort(t1, N)

t2 = list(L)
SelectionSort(t2, N)

if  t1 == t2:
    print "Stable"
else:
    print "Not stable"

Submission status: Accepted

Solution code:
def compare_cards(a, b):
    return a[1] < b[1]

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

def selection_sort(A):
    for i in range(len(A)):
        mini = i
        for j in range(i, len(A)):
            if compare_cards(A[j], A[mini]):
                mini = j
        A[i], A[mini] = A[mini], A[i]

def check_stable(originA, sortedA):
    for i in range(len(originA)-1):
        if not compare_cards(sortedA[i], sortedA[i+1]):
            if originA.index(sortedA[i]) > originA.index(sortedA[i+1]):
                return "Not stable"
    return "Stable"

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

bubbleA = list(A)
selectionA = list(A)

bubble_sort(bubbleA)
selection_sort(selectionA)

print(*bubbleA)
print(check_stable(A, bubbleA))

print(*selectionA)
print(check_stable(A, selectionA))

Submission status: Accepted

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())
B = input().split()
S = B[:]
B = BubbleSort(B, N)
S = SelectionSort(S, N)
mes = "Stable" if isStable(B, S, N) else "Not stable"
print(" ".join(B))
print("Stable")
print(" ".join(S))
print(mes)

Submission status: Accepted

Solution code:
def bubbleSort(A,N):
    for i in range(0,N):
        for j in range(N-1,i,-1):
            if A[j][1] < A[j-1][1]:
                v = A[j]
                A[j] = A[j-1]
                A[j-1] = v
    return A

def selectionSort(A,N):
    for i in range(0,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
    return A

if __name__ == '__main__':
    N = (int)(input())
    A1 = [[x[0],(int)(x[1])] for x in [list(x) for x in input().split()] ]
    A2 = A1.copy()

    resultA1 = bubbleSort(A1,N)
    resultA2 = selectionSort(A2,N)

    outputA1 = ' '.join( [x[0]+(str)(x[1]) for x in resultA1])
    outputA2 = ' '.join( [x[0]+(str)(x[1]) for x in resultA2])

    print(outputA1)
    print("Stable")
    print(outputA2)
    if outputA1 == outputA2 :
        print("Stable")
    else:
        print("Not stable")

Submission status: Accepted

Solution code:
import copy
def bs(array):
    for i in range(len(array)-1):
        for c in range(len(array)-1, i,-1):
            if array[c][1] < array[c-1][1]:
                swap = array[c]
                array[c] = array[c-1]
                array[c-1] = swap
    return array
def ss(array):
    for i in range(len(array)):
        minj = i
        for c in range(i+1,len(array)):
            if array[minj][1] > array[c][1]:
                minj = c
        swap = array[i]
        array[i] = array[minj]
        array[minj] = swap
    return array
def isStable(ar1,ar2):
    flag = 0
    for (x,y) in zip(ar1,ar2):
        if x != y:
            flag = 1
            break
    if flag == 0:
        print('Stable')
    else:
        print('Not stable')


n = input()
arr = [[i[0],int(i[1])] for i in input().split()]
arr1 = copy.deepcopy(arr)
arr2 = copy.deepcopy(arr)

bsarr = bs(arr2)
ssarr = ss(arr1)
print(' '.join([''.join([ x[0], str(x[1]) ]) for x in bsarr]))
print('Stable')
print(' '.join([''.join([ x[0], str(x[1]) ]) for x in ssarr]))
isStable(bsarr,ssarr)

Submission status: Accepted

Solution code:
n = int(input())
a = input().split()
b = a[:]
flag = 1
while flag:
    flag = 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]
            flag = 1
print(*a)
print("Stable")

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

Submission status: Accepted

Solution code:
import copy
def inputInline():
    N = int(input())
    cards = input().split(" ")
    return cards

def selectionSort(list):
    cards=copy.deepcopy(list)
    n = len(cards)
    count = 0
    for i in range(n):
        min_j = i
        for j in range(i + 1, n):
            if int(cards[j][1]) < int(cards[min_j][1]):
                min_j = j
        if min_j != i:
            temp = cards[i]
            cards[i] = cards[min_j]
            cards[min_j] = temp
            count += 1
    return (" ".join(cards), count)

def bubbleSort(list):
    cards=copy.deepcopy(list)
    N = len(cards)
    count = 0
    flag = True
    while flag:
        flag = False
        for i in range(N - 1):
            if int(cards[i][1]) > int(cards[i + 1][1]):
                temp = cards[i]
                cards[i] = cards[i + 1]
                cards[i + 1] = temp
                flag = True
                count += 1
    return (" ".join(cards), count)
cards=inputInline()
sortedbubble=bubbleSort(cards)[0]
sortedselection=selectionSort(cards)[0]
print(sortedbubble)
print("Stable")
print(sortedselection)
if sortedbubble==sortedselection:
    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, 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 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)
	print("Stable")

	selectionsort(cards2, n)
	output(cards2)
	if (cards1 == cards2):
		print("Stable")
	else:
		print("Not stable")

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from collections import namedtuple


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


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]


Card = namedtuple('Card', 'mark value')
n = int(input())
a = [Card(i[0], int(i[1])) for i in input().split()]
b = a[:]

BubbleSort(a, n)
SelectionSort(b, n)

print(" ".join([i.mark + str(i.value) for i in a]))
print("Stable")
print(" ".join([i.mark + str(i.value) for i in b]))
print("Stable" if a == b else "Not stable")

Submission status: Accepted

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

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

N, A= int(input()), input().split()
Ab = bubblesort(N, A)
print(*Ab)
print('Stable')
As = selectionSort(N, A)
print(*As)
if Ab != As:
    print('Not stable')
else:
    print('Stable')

Submission status: Accepted

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: Accepted

Solution code:
def bubbleSort(A,N):
    for i in range(N):
        for j in range(N-1,i,-1):
            if A[j][1:] < A[j-1][1:] :
                A[j] , A[j-1] = A[j-1] , A[j]
    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]
    return A

N =int(input())
cards = input().split()
bub , sel =cards[:] , cards[:]
X = bubbleSort(bub , N)
print(*X)
print("Stable")
Y = selectionSort(sel,N)
print(*Y)
print("Stable" if X == Y else "Not stable")

Submission status: Accepted

Solution code:
import copy

n = int(raw_input())
cards = raw_input().split()
cards1 = copy.deepcopy(cards)
cards2 = copy.deepcopy(cards)

def isbig(card1, card2):
	if int(card1[1]) > int(card2[1]):
		return 2
	elif int(card1[1]) == int(card2[1]):
		return 1
	else:
		return 0

def BubbleSort(c, n):
	temp = 0
	for i in range(n):
		for j in reversed(range(i+1,n)):
			if isbig(c[j], c[j-1]) == 0:
				temp = c[j]
				c[j] = c[j-1]
				c[j-1] = temp
	return c

def SelectionSort(c, n):
	temp = 0
	for i in range(n):
		minj = i
		for j in range(i,n):
			if isbig(c[j], c[minj]) == 0:
				minj = j
		temp = c[i]
		c[i] = c[minj]
		c[minj] = temp
		#print("*{:}".format(c))
	return c

def isstable(unsort, sort):
	for i in range(n):
		for j in range(i+1,n):
			for k in range(n):
				for l in range(k+1,n):
					if isbig(unsort[i], unsort[j]) == 1 and unsort[i] == sort[l] and unsort[j] == sort[k]:
						return 0
	return 1

for i in range(n):
	if i != n-1:
		print BubbleSort(cards1, n)[i],
	else:
		print BubbleSort(cards1, n)[i]

if isstable(cards, BubbleSort(cards1, n)) == 1:
	print("Stable")
else:
	print("Not stable")

for i in range(n):
	if i != n-1:
		print SelectionSort(cards2, n)[i],
	else:
		print SelectionSort(cards2, n)[i]

if isstable(cards, SelectionSort(cards2, n)) == 1:
	print("Stable")
else:
	print("Not stable")

Submission status: Accepted

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[m][1]):
            m = j
    _C[i], _C[m] = _C[m], _C[i]
print(*_C)
if(C ==_C):
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

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

Submission status: Accepted

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: Accepted

Solution code:
n=int(input())
a=[i for i in input().split(" ")]
b=a.copy()
flg=1

while flg:
    flg=0
    for j in range(n-1,0,-1):
        if a[j][1] < a[j-1][1]:
           a[j-1],a[j]=a[j],a[j-1]
           flg=1  

for i in range(n):
    mi=i
    for j in range(i,n):
        if b[j][1] < b[mi][1]:
            mi = j
    if i != mi:
        b[i],b[mi]=b[mi],b[i]

print(" ".join([str(i) for i in a]))
print("Stable")
print(" ".join([str(i) for i in b]))
if a==b:
    print("Stable")
else:
    print("Not stable")