Problem:


Stable Sort

Let's arrange a deck of cards. There are totally 36 cards of 4 suits(S, H, C, D) and 9 values (1, 2, ... 9). For example, 'eight of heart' is represented by H8 and 'one of diamonds' is represented by D1.

Your task is to write a program which sorts a given set of cards in ascending order by their values using the Bubble Sort algorithms and the Selection Sort algorithm respectively. These algorithms should be based on the following pseudocode:

BubbleSort(C)
1 for i = 0 to C.length-1
2     for j = C.length-1 downto i+1
3         if C[j].value 

Input

The first line contains an integer N, the number of cards.

N cards are given in the following line. Each card is represented by two characters. Two consecutive cards are separated by a space character.

Output

In the first line, print the arranged cards provided by the Bubble Sort algorithm. Two consecutive cards should be separated by a space character.

In the second line, print the stability ("Stable" or "Not stable") of this output.

In the third line, print the arranged cards provided by the Selection Sort algorithm. Two consecutive cards should be separated by a space character.

In the fourth line, print the stability ("Stable" or "Not stable") of this output.

Constraints

1 ≤ N ≤ 36

Sample Input 1

5
H4 C9 S4 D2 C3

Sample Output 1

D2 C3 H4 S4 C9
Stable
D2 C3 S4 H4 C9
Not stable

Sample Input 2

2
S1 H1

Sample Output 2

S1 H1
Stable
S1 H1
Stable



Sample input:
5
H4 C9 S4 D2 C3


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

Submission status: Accepted

Solution code:
def bubblesort(a,n):
    flag=1
    while flag:
        flag=0
        for j in range(n-1,0,-1):
            if int(a[j][1])<int(a[j-1][1]):
                m=a[j]
                a[j]=a[j-1]
                a[j-1]=m
                flag=1
    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
        if i!=minj:
            m=a[i]
            a[i]=a[minj]
            a[minj]=m
    return a

n=int(input())
a=list(input().split( ))
b=[a[i] for i in range(n)]
a1=bubblesort(a,n)
print(" ".join(a1))
print("Stable")
a2=selectionsort(b,n)
print(" ".join(a2))
if a1==a2:
    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 = 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 bubble_sort(c, n):
  l = c[:]
  for i in range(n-1):
    for j in reversed(range(i+1, N)):
      if l[j][1] < l[j-1][1]:
        l[j], l[j-1] = l[j-1], l[j]
  return l

def selection_sort(c, n):
  l = c[:]
  for i in range(n):
    min_x = i
    for j in range(i, n):
      if l[j][1] < l[min_x][1]:
        min_x = j
    l[i], l[min_x] = l[min_x], l[i]
  return l

def is_stable(in_arr, out_arr, 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 in_arr[i][1] == in_arr[j][1] and in_arr[i] == out_arr[b] and in_arr[j] == out_arr[a]:
            return False
  return True


N = int(input())
C = list(map(list, input().split()))

bubble_sorted_list = bubble_sort(C, N)
selection_sorted_list = selection_sort(C, N)

print(" ".join(map("".join, bubble_sorted_list)))
print("Stable" if is_stable(C, bubble_sorted_list, N) else "Not stable")
print(" ".join(map("".join, selection_sorted_list)))
print("Stable" if is_stable(C, selection_sorted_list, N) else "Not stable")

Submission status: Accepted

Solution code:
import copy

class Card:
    def __init__(self, suit, number):
        self.suit = suit
        self.number = number

    def equals(self, card):
        if (card.suit == self.suit) and (card.number == self.number):
            return True
        else:
            return False

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

def selection_sort(cards, n):
    for i in range(n):
        min_j = i
        for j in range(i, n):
            if cards[j].number < cards[min_j].number:
                min_j = j
        if min_j != i:
            cards[i], cards[min_j] = cards[min_j], cards[i]
    return cards

def is_stable(cards1, cards2, n):
    result = True
    for i in range(n):
        if not(cards1[i].equals(cards2[i])):
            result = False
            break
    return result

def print_cards(cards, n):
    print(' '.join([c.suit + str(c.number) for c in cards]))

n = int(input())
cards = [Card(card[0], int(card[1])) for card in input().split()]
cards_bubble = bubble_sort(copy.deepcopy(cards), n)
cards_selection = selection_sort(copy.deepcopy(cards), n)

print_cards(cards_bubble, n)
print('Stable')
print_cards(cards_selection, n)
if is_stable(cards_bubble, cards_selection, n):
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
def bubble_sort(C, key):
    n = len(C)
    flag = True
    i = 0
    while flag:
        flag = False
        for j in range(n - 1, i, -1):
            if key(C[j]) < key(C[j - 1]):
                C[j - 1], C[j] = C[j], C[j - 1]
                flag = True
        i += 1

def selection_sort(C, key):
    n = len(C)
    for i in range(n):
        minj = i
        for j in range(i, n):
            if key(C[j]) < key(C[minj]):
                minj = j
        if i != minj:
            C[i], C[minj] = C[minj], C[i]

def chk_stable(org_arr, sorted_arr):
    n = len(org_arr)

    org_num_cnt = {}
    for i in range(n):
        num = org_arr[i][1]
        if num in org_num_cnt:
            org_num_cnt[num].append(i)
        else:
            org_num_cnt[num] = [i]

    is_stable = True
    _j = 0
    for i in range(1, n):
        if _j > 0:
            _j -= 1
            continue

        if sorted_arr[i-1][1] == sorted_arr[i][1]:
            idx_list = org_num_cnt[sorted_arr[i][1]]
            for j in range(len(idx_list)):
                if org_arr[idx_list[j]][0] != sorted_arr[i-1+j][0]:
                    is_stable = False
                    break
            _j = len(idx_list)-1
        if not is_stable:
            break

    return is_stable

n = int(input())

A = input().split()
C1 = A[:]
C2 = A[:]

bubble_sort(C1, lambda x: x[1])
print(*C1)
if chk_stable(A, C1) == True:
    print("Stable")
else:
    print("Not stable")

selection_sort(C2, lambda x: x[1])
print(*C2)
if chk_stable(A, C2) == True:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
n = int(input())
cardlist=list(map(str,input().split()))
def BubbleSort(C):
    for i in range(len(C)):
        for j in range(len(C)-1):
            if (C[j][-1:] >C[j+1][-1:]):
                C[j],C[j+1] = C[j+1],C[j]
    return C

def SelectionSort(C):
    for i in range(len(C)):
        minj = i
        for j in range(i,len(C)):
            if (C[j][-1:] < C[minj][-1:]):
                minj = j
        C[i],C[minj] = C[minj],C[i]
    return C
cardlist1 = cardlist.copy()
bubble = BubbleSort(cardlist)
print(*bubble)
print('Stable')
selection = SelectionSort(cardlist1)
print(*selection)
if(bubble == selection):
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

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

def b_sort(a):
	while True:
		for n in reversed(range(1, len(a))):
			if a[n][1] < a[n - 1][1]:
				a[n - 1], a[n] = a[n], a[n - 1]
				break
		else:
			return

def s_sort(a):
	for n in range(len(a)):
		min_n = n
		for m in range(n, len(a)):
			if a[m][1] < a[min_n][1]:
				min_n = m
		if n != min_n:
			a[n], a[min_n] = a[min_n], a[n]
	return

a_b = A.copy()
b_sort(a_b)
print(*a_b)
print("Stable")

a_s = A.copy()
s_sort(a_s)
print(*a_s)
print(["Stable", "Not stable"][not(a_b == a_s)])

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

def bubbleSort(C, M, N):
    for i in range(N):
        for j in reversed(range(i+1, N)):
            if C[j] < C[j-1]:
                out1 = C[j]
                C[j] = C[j-1]
                C[j-1] = out1
                out2 = M[j]
                M[j] = M[j-1]
                M[j-1] = out2
    print(' '.join(M))
    print('Stable')
    return M
    
def selectionSort(C, M, N):
    m = copy.deepcopy(M)
    for i in range(N):
        minj = i
        for j in range(i, N):
            if C[j] < C[minj]:
                minj = j
        out3 = C[i]
        C[i] = C[minj]
        C[minj] = out3
        out4 = M[i]
        M[i] = M[minj]
        M[minj] = out4
    print(' '.join(M))
    return M
    
def isStable(inn, out):
    for a, b in zip(inn, out):
        if a == b: continue
        else : return 'Not stable'
    return 'Stable'
    
if __name__ == '__main__':
    num1 = []
    N = int(input()) #1行目のNを取得する
    M1 = list(input().split())
    for i in range(N):
        s = M1[i]
        num1.append(int(s[-1]))
    M2 = copy.deepcopy(M1)
    num2 = copy.deepcopy(num1)
    out1 = bubbleSort(num1, M1, N)
    out2 = selectionSort(num2, M2, N)
    print(isStable(out1, out2))

Submission status: Accepted

Solution code:
def bubble(N,C):
  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]=C[j-1]
        C[j-1]=_
  print(*C)

def selection(N,C):
  for i in range(N):
    minj=i
    for j in range(i,N):
      if C[minj][1] > C[j][1]:
        minj=j
    _=C[minj]
    C[minj]=C[i]
    C[i]=_
  print(*C)

def stable(A,C):
  result='Stable'
  for i in range(1,10):
    a=[j for j in A if j[1]==str(i)]
    c=[k for k in C if k[1]==str(i)]
    if a!=c:
      result='Not stable'
  print(result)

N=int(input())
C=list(input().split())
A=C[:]
bubble(N,C)
stable(A,C)
C=A[:]
selection(N,C)
stable(A,C)

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

def bubble_sort(A):
    for i in range(len(A)):
        for j in range(len(A)-1, i, -1):
            if A[j]['value'] < A[j-1]['value']:
                tmp = A[j]
                A[j] = A[j-1]
                A[j-1] = tmp


def selection_sort(B):
    for i in range(len(B)):
        mini = i
        for j in range(i, len(B)):
            if B[j]['value'] < B[mini]['value']:
                mini = j
        tmp = B[i]
        B[i] = B[mini]
        B[mini] = tmp


def is_stable(A, B, n):
    for i in range(n):
        if A[i]['suit'] != B[i]['suit']:
            return False
    return True


def show_list(C):
    D = [i['suit'] + i['value'] for i in C]
    print(' '.join(D))
    
n = int(input())
A = [{'suit': i[0], 'value': i[-1]}for i in map(str, input().split())]
B = copy.deepcopy(A)

bubble_sort(A)
show_list(A)
print('Stable')

selection_sort(B)
show_list(B)
if is_stable(A, B, n):
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

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

N = int(input())
C = list(input().split())
C_dash = C.copy()

b = BubbleSort(C, N)
s = SelectionSort(C_dash, N)

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

Submission status: Accepted

Solution code:
from typing import List


def bubble_sort(elems: List[str]) -> List[str]:
    for i in range(0, len(elems)):
        for j in range(len(elems) - 1, i, -1):
            if int(elems[j][1]) < int(elems[j - 1][1]):
                elems[j], elems[j - 1] = elems[j - 1], elems[j]
    return elems


def selection_sort(elems: List[str]) -> List[str]:
    for i in range(0, len(elems)):
        mini = i
        for j in range(i + 1, len(elems)):
            if int(elems[j][1]) < int(elems[mini][1]):
                mini = j
        if i != mini:
            elems[i], elems[mini] = elems[mini], elems[i]
    return elems


def is_stable(input_elems: List[str], elems: List[str]) -> bool:
    for card1, card2 in zip(elems[:-1], elems[1:]):
        if (int(card1[1]) == int(card2[1])) and (
           input_elems.index(card1) > input_elems.index(card2)):
            return False
    return True


if __name__ == "__main__":
    elem_num = int(input())
    elems = list(input().split())

    elems_bubble_sort = elems.copy()
    elems_bubble_sort = bubble_sort(elems_bubble_sort)
    print(" ".join(elems_bubble_sort))
    if is_stable(elems, elems_bubble_sort):
        print("Stable")
    else:
        print("Not stable")

    elems_selection_sort = elems.copy()
    elems_selection_sort = selection_sort(elems_selection_sort)
    print(" ".join(elems_selection_sort))
    if is_stable(elems, elems_selection_sort):
        print("Stable")
    else:
        print("Not stable")

Submission status: Accepted

Solution code:
N = int(input())
S = list(input().split())

def bubble(S):
    sorted_l = []
    un_sorted_l = S[:]
    counter = 0
    while un_sorted_l:
        n = len(un_sorted_l)
        for i in reversed(range(1, n)):
            if un_sorted_l[i-1][1:] <= un_sorted_l[i][1:]:
                continue
            else:
                counter += 1
                un_sorted_l[i-1], un_sorted_l[i] = un_sorted_l[i], un_sorted_l[i-1]
        sorted_l.append(un_sorted_l[0])
        un_sorted_l = un_sorted_l[1:]

    return sorted_l
    
def select(S):
    selection_sort = S[:]
    counter = 0
    for i in range(len(selection_sort)):
        v = selection_sort[i]
        min_v = v
        min_i = i
        for j in range(i, len(selection_sort)):
            if min_v[1:] > selection_sort[j][1:]:
                min_v = selection_sort[j]
                min_i = j
        if v != min_v:
            counter += 1
            selection_sort[i], selection_sort[min_i] = selection_sort[min_i], selection_sort[i]
            
    return selection_sort

def check(X, S):
    d = {}
    for i, s in enumerate(S):
        d[s] = i
        
    for x, y in zip(X[:-1],X[1:]):
        if x[1:] == y[1:] and d[x] > d[y]:
            return 'Not stable'
    
    return 'Stable'
        
        

b = bubble(S)
print(' '.join(b))
print(check(b, S))

s = select(S)
print(' '.join(s))
print(check(s, S))

Submission status: Accepted

Solution code:
# 比较冒泡排序和选择排序

def bubble_sort(arr):
    no_swap = True
    #swap_cnt = 0
    for i in range(len(arr), 0, -1):
        if not no_swap:
            break
        for j in range(0, i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                #swap_cnt += 1
            no_swap = True
    #return swap_cnt

def selection_sort(arr):
    #swap_cnt = 0
    for i in range(0, len(arr)):
        min_index = i
        for j in range(i + 1, len(arr)):
            if arr[min_index] > arr[j]:
                min_index = j
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]
            #swap_cnt += 1
    #return swap_cnt

# n^4 method
def is_stable(raw, sort_):
    N = len(raw)
    for i in range(N):
        for j in range(i + 1, N):
            for m in range(N):
                for n in range(m + 1, N):
                    if (raw[i].value == raw[j].value) and (raw[i] == sort_[n]) and (raw[j] == sort_[m]):
                        return 'Not stable'
    return 'Stable'

class Card:
    suit = ''
    value = 0

    def __init__(self, val):
        self.suit = val[0]
        self.value = int(val[1])

    def __lt__(self, rhv):
        return self.value < rhv.value

    def __eq__(self, rhv):
        return self.suit == rhv.suit and self.value == rhv.value

    def __ne__(self, rhv):
        return not (self == rhv)

    def __str__(self):
        return '%s%d'%(self.suit, self.value)

if __name__ == '__main__':
    N = int(input())
    raw = list(map(Card, input().split()))
    arr1 = []
    arr2 = []
    for i in raw:
        arr1.append(i)
        arr2.append(i)
    bubble_sort(arr1)
    result = is_stable(raw, arr1)
    print(' '.join(map(str, arr1)))
    # print('Stable')
    print(result)
    selection_sort(arr2)
    print(' '.join(map(str, arr2)))
    result = is_stable(raw, arr2)
    print(result)
    # for i in range(len(arr1)):
    #     if arr1[i] != arr2[i]:
    #         print('Not stable')
    #         break
    #     if i == len(arr1) - 1:
    #         print('Stable')

Submission status: Accepted

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
cards = [list(c) for c in stdin.readline().rstrip().split()]
c_cards = cards.copy()

def bubble_sort(a, n):
    for i in range(0, 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 select_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]
    return a

bubbled = [''.join(c) for c in bubble_sort(cards, N)]
selected = [''.join(c) for c in select_sort(c_cards, N)]
print(*bubbled)
print('Stable')
print(*selected)
if selected == bubbled:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
class Card:
    def __init__(self, s):
        self.color = s[0]
        self.val = int(s[1])

    def __str__(self):
        return "%s%d" % (self.color, self.val)


if __name__ == '__main__':
    n = int(raw_input())
    A = map(Card, raw_input().split())
    B = A[:]

    # bubble sort
    for i in range(0, n):
        for j in range(n - 1, i, -1):
            if A[j].val < A[j - 1].val:
                A[j], A[j - 1] = A[j - 1], A[j]

    # select sort
    for i in range(0, n):
        minj = i
        for j in range(i, n):
            if B[j].val < B[minj].val:
                minj = j
        if minj != i:
            B[minj], B[i] = B[i], B[minj]

    for c in A:
        print c,
    print
    print "Stable"
    for c in B:
        print c,
    print
    flag = True
    for i in range(n):
        if A[i] != B[i]:
            flag = False
            break
    print "Stable" if flag else "Not stable"

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

def bubble_sort(A):
    for i in range(len(A)):
        flag = 1
        while flag:
            flag = 0
            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]
                    flag = 1
    return A

def sentaku_sort(A):
    for i in range(len(A)):
        min_n = i
        for j in range(i+1, len(A)):
            if A[j][1] < A[min_n][1]:
                min_n = j
        if min_n != i:
            A[i], A[min_n] = A[min_n], A[i]
    return A

def isStable(A, B):
    for i in range(len(A)):
        for j in range(i+1, len(A)):
            for a in range(len(A)):
                for b in range(a+1, len(A)):
                    if A[i][1] == A[j][1] and A[i] == B[b] and A[j] == B[a]:
                        return False
    return True
    

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


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

B = bubble_sort(A[:])
hyoji(B)
if isStable(A, B):print('Stable')
else:print('Not stable')

C = sentaku_sort(A[:])
hyoji(C)
if isStable(A, C):print('Stable')
else:print('Not stable')

Submission status: Accepted

Solution code:
"""
# 標準入力取得
## 文字列
 = sys.stdin.readline().rstrip()
 = list(sys.stdin.readline().rstrip())

## 数値
 = int(sys.stdin.readline())
 = map(int, sys.stdin.readline().split())
 = list(map(int, sys.stdin.readline().split()))
 = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]
"""

import math
import sys
import itertools
import queue
from fractions import gcd


mod = 1000000007

if __name__ == "__main__":
    n = int(sys.stdin.readline())
    l = list(sys.stdin.readline().split())

    #リストを使い回すのは危険。ソートなど意図しない変更がかかっているかも。
    b = l[:]#リスト丸々コピー
    s = l[:]

    def BubbleSort(l,n):
        for i in range(n):
            for j in range(1,n):
                if l[j][1] < l[j-1][1]:
                    temp=l[j-1]
                    l[j-1]=l[j]
                    l[j]=temp

    def SelectionSort(l,n):
        for i in range(n):
            minj=i
            for j in range(i,n):
                if l[j][1] < l[minj][1]:
                    minj = j
            if i!=minj:
                temp=l[minj]
                l[minj]=l[i]
                l[i]=temp

    BubbleSort(b,n)
    print(*b)
    print('Stable')
    SelectionSort(s,n)
    print(*s)
    #真ならば前、偽ならば後ろ
    print("Stable" if b==s else "Not stable")

Submission status: Accepted

Solution code:
def bubble(n,c):
    for i in range(n):
        ch=True
        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]
                ch=False
        if ch:
            break
    return c

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


n=int(input())
c=list(input().split())
c2=c[:]
ba=bubble(n,c2)
print(*ba)
print("Stable")
sa=selection(n,c)
print(*sa)
print("Stable" if sa==ba else "Not stable")

Submission status: Accepted

Solution code:
import copy
def p(a):
    for i in a[:-1]:
        print(i,end=' ')
    print(a[-1])


def selection_sort(a):
    cnt = 0
    for i in range(len(a)-1):
        fl = 0
        min = i
        for j in range(i+1,len(a)):
            if a[j][1]<a[min][1]:
                fl=1
                min = j
        cnt+=fl
        tmp = a[min]
        a[min] = a[i]
        a[i] = tmp


def bubble_sort(a):
    for i in range(len(a)-1):
        for j in range(i+1,len(a))[::-1]:
            if a[j-1][1]>a[j][1]:
                tmp = a[j]
                a[j] = a[j-1]
                a[j-1] = tmp


n = int(input())
l = list(input().split())
a = copy.copy(l)
bubble_sort(l)
selection_sort(a)
p(l)
print('Stable')
p(a)
if a==l:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
def bubble(A):
    flag = 1
    n = len(A)
    cnt = 0
    while flag:
        flag = 0
        for j in range(n-1, 0, -1):
          if A[j][1] < A[j-1][1]:
            A[j], A[j-1] = A[j-1], A[j]
            flag = 1
        cnt += 1
  
   
            
def selection(A):
    n = len(A)
    
    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]
    
  
    
  
n = int(input())
ss = [x for x in input().split()]
ss2 = ss.copy()

bubble(ss)
for i in range(len(ss)-1):
  print(ss[i], end=" ")
print(ss[-1])
print('Stable')

selection(ss2)
for i in range(len(ss2) - 1):
  print(ss2[i], end=" ")
print(ss2[-1])
if ss == ss2:
  print('Stable')
else:
  print('Not stable')

Submission status: Accepted

Solution code:
def BubbleSortChar(c,n):
    num = [int(s[1]) for s in c]
    for i in range(n):
        # n-1からiまでさかのぼっていく
        for j in range(n-1,i,-1):
            # 順番を入れ替える条件
            if num[j-1] > num[j]:
                # 数字のみの入れ替え
                tmp = num[j-1]
                num[j-1] = num[j]
                num[j] = tmp
                # 本物の入れ替え
                tmp = c[j-1]
                c[j-1] = c[j]
                c[j] = tmp
    return " ".join(c)

def SelectionSortChar(c,n):
    num = [int(s[1]) for s in c]
    for i in range(n):
        # print(c)
        minj = i
        for j in range(i,n):
            if num[j] < num[minj]:
                minj = j
        # origin
        tmp = c[minj]
        c[minj] = c[i]
        c[i] = tmp
        #num
        tmp = num[minj]
        num[minj] = num[i]
        num[i] = tmp

    return " ".join(c)




# バブルソートは常に安定ソート
# バブルソートと違う -> Not Stable
N = int(input())
S1 = input().split(" ")
S2 = [s for s in S1]
# Bubble Sort
C1 = BubbleSortChar(S1,N)
print(C1)
print("Stable")

# Selection Sort
C2 = SelectionSortChar(S2,N)
print(C2)
if C1==C2:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

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

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

N = int(input())
C = input().split()
C1 = C.copy()
C2 = C.copy()

BSC = BubbleSort(C1)
print(" ".join(BSC))
print("Stable")
SSC = SelectionSort(C2)
print(" ".join(SSC))
if BSC == SSC:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
import copy

array_to_str = lambda A: ' '.join([str(a) for a in A])
input_number = lambda: int(input())
input_num_array = lambda: [int(a) for a in input().split()]
input_array = lambda: input().split()

def bubble_sort(C, A, N):
  flag = 1
  while flag:
    flag = 0
    for j in range(N)[:0:-1]:
      if A[j] < A[j-1]:
        A[j],A[j-1] = A[j-1], A[j]
        C[j],C[j-1] = C[j-1], C[j]
        flag = 1
  print(' '.join(C))
  print('Stable')

def selection_sort(C, A, N):
  stability = True
  for i in range(N):
    minj = i
    for j in range(i,N):
      if A[j] < A[minj]:
        minj = j

    # if i > minj and A[minj] == A[i]:
    #   stability = not stability

    C[i], C[minj] = C[minj], C[i]
    A[i], A[minj] = A[minj], A[i]
        
  print(' '.join(C))
  # print('Stable' if stability else 'Not stable')

N = input_number()
C = input_array()
A = [int(c[1]) for c in C]
A_copy = copy.copy(A)
C_copy = copy.copy(C)
bubble_sort(C_copy, A_copy, N)
selection_sort(C, A, N)
print('Stable' if C == C_copy else 'Not stable')

Submission status: Accepted

Solution code:
def bubble_sort(arr):
    n = len(arr)
    flag = True
    i = 0
    while flag:
        flag = False
        for j in range(n - 1, 0, -1):
            if int(arr[j][1]) < int(arr[j - 1][1]):
                arr[j], arr[j - 1] = arr[j - 1], arr[j]
                flag = True
        i += 1
    return arr


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


def is_stable(arr, arr_sorted):
    print("Stable" if arr_sorted == sorted(arr, key=lambda x:int(x[1])) else "Not stable")


n = int(input())
arr = input().split()
arr_b = bubble_sort(arr[:])
arr_s = selection_sort(arr[:])

print(*arr_b)
is_stable(arr, arr_b)
print(*arr_s)
is_stable(arr, arr_s)

Submission status: Accepted

Solution code:
n=int(input())
bubble=input().split()
select=bubble[:]
for i in range(n):
    for j in range(n-1,i,-1):
        if int(bubble[j][1])<int(bubble[j-1][1]):
            bubble[j],bubble[j-1]=bubble[j-1],bubble[j]

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

for i in range(n-1):
    print(bubble[i],end=" ")
print(bubble[n-1])
print("Stable")
for i in range(n-1):
    print(select[i],end=" ")
print(select[n-1])
if bubble==select:
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
def bubble_sort(a_list):
    n = len(a_list)
    for i in range(0, n):
        for j in reversed(range(i + 1, n)):
            if a_list[j - 1][1] > a_list[j][1]:
                a_list[j - 1], a_list[j] = a_list[j], a_list[j - 1]
    return a_list


def selection_sort(a_list):
    n = len(a_list)
    for i in range(0, n):
        mini = i
        for j in range(i, n):
            if a_list[j][1] < a_list[mini][1]:
                mini = j
        if i != mini:
            a_list[i], a_list[mini] = a_list[mini], a_list[i]
    return a_list


n = int(input())
a_list = input().split()

bubble_sorted = bubble_sort(a_list[:])
print(' '.join(map(str, bubble_sorted)))
print('Stable')
selection_sorted = selection_sort(a_list[:])
print(' '.join(map(str, selection_sorted)))
if bubble_sorted == selection_sorted:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
import sys

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

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

def bubble_sort(n, A):

    for i in range(n):
        for j in range(n-1, i, -1):
            if A[j-1][1:] > A[j][1:]:
                A[j], A[j-1] = A[j-1], A[j]
    return A

def is_stable(in_data, out_data):
    len_data = len(in_data)

    for i in range(len_data):
        for j in range(i+1, len_data):
            for a in range(len_data):
                for b in range(a+1, len_data):
                    if in_data[i][1] == in_data[j][1] and\
                       in_data[i] == out_data[b] and\
                       in_data[j] == out_data[a]:
                        return False

    return True

n = int(sys.stdin.readline().strip())
card = sys.stdin.readline().strip().split(' ')

raw = card[:]
bs = bubble_sort(n, raw)
raw = card[:]
ss = selection_sort(n, raw)

print(' '.join(bs))

if is_stable(card, bs):
    print('Stable')
else:
    print('Not stable')

print(' '.join(ss))

if is_stable(card, ss):
    print('Stable')
else:
    print('Not stable')