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 selection_sort(numbers, n, key=lambda x: x):
    """selection sort method

    Args:
        numbers: a list of numbers to be sorted
        n: len(numbers)
        key: sort key

    Returns:
        sorted numberd, number of swapped times
    """
    x = []
    for data in numbers:
        x.append(data)

    counter = 0

    for i in range(0, n):
        min_j = i
        for j in range(i, n):
            if key(x[j]) < key(x[min_j]):
                min_j = j
        if min_j != i:
            x[min_j], x[i] = x[i], x[min_j]
            counter += 1
    return x, counter


def bubble_sort(numbers, n, key=lambda x: x):
    """bubble sort method

    Args:
        numbers: a list of numbers to be sorted by bubble sort
        n: len(list)
        key: sort key

    Returns:
        sorted list
    """
    x = []
    for data in numbers:
        x.append(data)

    flag = True
    counter = 0
    while flag:
        flag = False
        for index in range(n - 1, 0, -1):
            if key(x[index]) < key(x[index - 1]):
                x[index], x[index - 1] = x[index - 1], x[index]
                flag = True
                counter += 1
    return x, counter


def insertion_sort(numbers, n, key=lambda x: x):
    """insertion sort method

    Args:
        numbers: a list of numbers to be sorted
        n: len(numbers)

    Returns:
        sorted list
    """
    for i in range(1, n):
        target = numbers[i]
        index = i - 1
        while index >= 0 and target < numbers[index]:
            numbers[index + 1] = numbers[index]
            index -= 1
        numbers[index + 1] = target

    return numbers


def is_stable(list1, list2):
    """check stablity of sorting method used in list2

    Args:
        list1: sorted list(bubble sort)
        list2: sorted list(some sort)

    Returns:
        bool
    """
    flag = True
    for index, data in enumerate(list1):
        if list2[index] != data:
            flag = False
            break

    return flag


length = int(raw_input())
cards = raw_input().split()
bubble_sorted_card, bubble_swapped = bubble_sort(numbers=cards, n=length, key=lambda x: int(x[1]))
selection_sorted_card, selection_swapped = selection_sort(numbers=cards, n=length, key=lambda x: int(x[1]))
print(" ".join(bubble_sorted_card))
print("Stable")
print(" ".join(selection_sorted_card))

if is_stable(bubble_sorted_card, selection_sorted_card):
    print("Stable")
else:
    print("Not stable")

Submission status: Accepted

Solution code:
def do_bubble_sort(data, n):
    """ ??°???data??????????????????????????????????????§???????????????????????????n?????°????????????
    ?????????????????????????????°??¨????????????????????????????????????
    """
    flag = True
    i = 0
    while flag is True:
        flag = False
        for j in range(n-1, i, -1):
            dj = int(data[j][1])
            dj_1 = int(data[j-1][1])
            #if data[j] < data[j-1]:
            if dj < dj_1:
                temp = data[j]
                data[j] = data[j-1]
                data[j-1] = temp
                flag = True
        i == 1
    return



def do_selection_sort(data, size):
    assert size == len(data), "data size error"
    for i in range(size):
        minj = i
        for j in range(i, size):
            dj = int(data[j][1])
            dmin = int(data[minj][1])
            if dj < dmin:
            #if data[j] < data[minj]:
                minj = j
        temp = data[i]
        data[i] = data[minj]
        data[minj] = temp
    return


def is_stable(bubble_d, selection_d):
    for b, s in zip(bubble_d, selection_d):
        if b != s:
            return False
    return True


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())
    cards = [x for x in input().split(' ')]
    #cards = ['H4', 'C9', 'S4', 'D2', 'C3']
    #cards = ['S1', 'H1']
    t = cards[:]  # ???????????????
    u = cards[:]

    # ???????????????????????????
    do_bubble_sort(t, len(t))
    do_selection_sort(u, len(u))
    result = is_stable(t, u)

    # ???????????????
    print('{0}'.format(' '.join(map(str, t))))
    print('Stable')
    print('{0}'.format(' '.join(map(str, u))))
    if result is True:
        print('Stable')
    else:
        print('Not stable')

Submission status: Accepted

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


def conv_input(arr):
    ret = []
    for e in arr:
        ret.append((e[0], int(e[1])))
    return ret


def conv_output(conv_arr):
    ret = []
    for e in conv_arr:
        ret.append(e[0] + str(e[1]))
    return ret


def is_stable(arr1, arr2):
    ret = 'Stable'
    for a1, a2 in zip(arr1, arr2):
        if a1 == a2:
            continue
        else:
            ret = 'Not stable'
            break
    return ret


def bubble_sort(n, arr):
    flag = True
    while flag:
        flag = False
        for i in reversed(range(n)):
            if i is 0:
                break
            if arr[i][1] < arr[i - 1][1]:
                tmp = arr[i]
                arr[i] = arr[i - 1]
                arr[i - 1] = tmp
                flag = True
    return arr


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

if __name__ == '__main__':
    n = int(input())
    arr1 = arr2 = [str(s) for s in input().split()]
    arr1 = conv_output(bubble_sort(n, conv_input(arr1)))
    print(' '.join(map(str, arr1)))
    print('Stable')
    arr2 = conv_output(selection_sort(n, conv_input(arr2)))
    print(' '.join(map(str, arr2)))
    print(is_stable(arr1, arr2))

Submission status: Accepted

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

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

def selection_sort(A):
  N = len(A)
  for i in range(N):
    mini = i
    for j in range(i + 1, N):
      if int(A[j][1]) < int(A[mini][1]):
        mini = j
    if mini != i:
      A[mini], A[i] = A[i], A[mini]
  return A

def is_stable(A, B):
  map_a = {}
  map_b = {}
  for i in range(len(A)):
    s_a = A[i][0]
    s_b = B[i][0]
    v_a = A[i][1]
    v_b = B[i][1]
    if v_a in map_a:
      map_a[v_a].append(s_a)
    else:
      map_a[v_a] = [s_a]
    if v_b in map_b:
      map_b[v_b].append(s_b)
    else:
      map_b[v_b] = [s_b]

  result = True
  for k in map_a:
    if len(map_a[k]) > 1:
      result = result and (map_a[k] == map_b[k])

  return result

A_sorted = bubble_sort(A[:])
print(" ".join(A_sorted))
print("Stable") if is_stable(A, A_sorted) else print("Not stable")

A_sorted = selection_sort(A[:])
print(" ".join(A_sorted))
print("Stable") if is_stable(A, A_sorted) else print("Not stable")

Submission status: Accepted

Solution code:
def buble_sort(seq):
    l = len(seq)
    res = seq[:]
    for i in range(l):
        for j in range(i+1, l)[::-1]:
            if res[j][-1] < res[j-1][-1]:
                res[j], res[j-1] = res[j-1], res[j]
    return res


def selection_sort(seq):
    l = len(seq)
    res = seq[:]
    for i in range(l):
        mi = i
        for j in range(i, l):
            if res[j][-1] < res[mi][-1]:
                mi = j
        if i is not mi:
            res[i], res[mi] = res[mi], res[i]
    return res


def is_stable(seq, sorted_seq):
    card_dic = {s[-1]: [] for s in set(seq)}
    for s in seq:
        key = s[-1]
        card_dic[key].append(s[0])

    for ss in sorted_seq:
        key = ss[-1]
        val = card_dic[key].pop(0)
        if not val == ss[0]:
            return False
    return True


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

b_sorted = buble_sort(C)
print(' '.join(b_sorted))
print('Stable' if is_stable(C, b_sorted) else 'Not stable')

s_sorted = selection_sort(C)
print(' '.join(s_sorted))
print('Stable' if is_stable(C, s_sorted) else 'Not stable')

Submission status: Accepted

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

import copy

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

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

def is_stable(before_sort, after_sort):
    current_num = 0
    same_number_card = list()
    for num in after_sort:
        if current_num == int(num[1]):
            for same_card in same_number_card:
                if before_sort.index(same_card) > before_sort.index(num):
                    return False
            same_number_card.append(num)
        else:
            current_num = int(num[1])
            same_number_card = [num,]
    return True

def show_list(list):
    i = 0;
    while(i < len(list)-1):
        print(list[i], end=" ")
        i = i + 1
    print(list[i])

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

num = int(input())
input_card = [x for i, x in enumerate(input().split()) if i < num]
bubble_sort_card = bubble_sort(copy.deepcopy(input_card))
show_list(bubble_sort_card)
show_stable(is_stable(input_card, bubble_sort_card))
selection_sort_card = selection_sort(copy.deepcopy(input_card))
show_list(selection_sort_card)
show_stable(is_stable(input_card, selection_sort_card))

Submission status: Accepted

Solution code:
def bubble_sort(r, n):
    flag = True  # ??£??\????´?????????¨????????°
    while flag:
        flag = False
        for i in range(n - 1, 0, -1):
            if r[i - 1][1] > r[i][1]:
                r[i - 1], r[i] = r[i], r[i - 1]
                flag = True
    return r


def select_sort(r, n):
    for i in range(0, n):
        minj = i
        for j in range(i, n):
            if r[j][1] < r[minj][1]:
                minj = j
        if i != minj:
            r[i], r[minj] = r[minj], r[i]
    return r


def stable_sort(r, sort_r):
    for i in range(len(r)):
        for j in range(i + 1, len(r)):
            for a in range(len(sort_r)):
                for b in range(a + 1, len(sort_r)):
                    if r[i][1] == r[j][1] and r[i] == sort_r[b] and r[j] == sort_r[a]:
                         return "Not stable"

    return "Stable"


N = int(input())
R = list(input().split())
C = R[:]
BS_R = bubble_sort(R, N)
SS_R = select_sort(C, N)
print(*BS_R)
print(stable_sort(R, BS_R))
print(*SS_R)
print(stable_sort(R, SS_R))

Submission status: Accepted

Solution code:
class Card:
    def __init__(self, s, i):
        self.suit = s[0]
        self.value = s[1]
        self.iniorder = i

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]

    return C

def SelectionSort(C, N):
    for i in range(N):
        minj = i

        for j in range(i, N):
            if C[j].value < C[minj].value:
                minj = j

        C[i], C[minj] = C[minj], C[i]

    return C


n = int(input())
cards = [Card(c, i) for (i, c) in enumerate(input().split())]

res_bub = BubbleSort(cards[:], n)
res_sel = SelectionSort(cards[:], n)

print(*[c.suit + c.value for c in res_bub])

for i in range(n - 1):
    if res_bub[i].value == res_bub[i + 1].value:
        if res_bub[i].iniorder > res_bub[i + 1].iniorder:
            print("Not stable")
            break
else:
    print("Stable")

print(*[c.suit + c.value for c in res_sel])

for i in range(n - 1):
    if res_sel[i].value == res_sel[i + 1].value:
        if res_sel[i].iniorder > res_sel[i + 1].iniorder:
            print("Not stable")
            break
else:
    print("Stable")

Submission status: Accepted

Solution code:

class Card:
    def __init__(self, data, i):
        self.suit = data[0]
        self.value = data[1]
        self.initord = i

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

def SelectionSort(cards, N):
    for i in range(N):
        min_j = i

        for j in range(i + 1, N):
            if cards[j].value < cards[min_j].value:
                min_j = j

        cards[i], cards[min_j] = cards[min_j], cards[i]

N = int(input())
cards = [Card(data, i) for i, data in enumerate(input().split())]

cards1 = cards.copy()
cards2 = cards.copy()

BubbleSort(cards1, N)
SelectionSort(cards2, N)

print(*[card.suit + card.value for card in cards1])

for i in range(N - 1):
    if cards1[i].value == cards1[i + 1].value:
        if cards1[i].initord > cards1[i + 1].initord:
            print("Not stable")
            break
else:
    print("Stable")

print(*[card.suit + card.value for card in cards2])

for i in range(N - 1):
    if cards2[i].value == cards2[i + 1].value:
        if cards2[i].initord > cards2[i + 1].initord:
            print("Not stable")
            break
else:
    print("Stable")

Submission status: Accepted

Solution code:
class Card:
    def __init__(self, name):
        self.name = name
        self.value = int(name[1])
    def __lt__(self, other):
        return self.value < other.value
    def __repr__(self):
        return self.name

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

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

n = int(input())
cards = [Card(s) for s in input().split()]

bubbled_cards = bubble_sort(cards[:], n)
selected_cards = selection_sort(cards[:], n)
print(' '.join(str(s) for s in bubbled_cards))
print('Stable')
print(' '.join(str(s) for s in selected_cards))
if bubbled_cards == selected_cards:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
n = int(input())
lst = input().split()
bub, sel = lst[:], lst[:]
def stable(sls):
    s, i = 1, n-1
    while s*i:
        if sls[i][1] == sls[i-1][1]:
            if lst.index(sls[i]) < lst.index(sls[i-1]) :
                s = 0
        i -= 1
    print('Stable' if s else 'Not stable')

for i in range(n):
    m = i
    for j in range(n-1,i,-1):
        if bub[j][1] < bub[j-1][1]:
            bub[j-1:j+1] = bub[j], bub[j-1]
    for k in range(i, n):
        if sel[k][1] < sel[m][1]:
            m = k
    if m != i:
        sel[i], sel[m] = sel[m], sel[i]

print(*bub)
stable(bub)
print(*sel)
stable(sel)

Submission status: Accepted

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


def bubble_sort(cards, num):
    flag = True
    while flag:
        flag = False
        for left in range(num-1, 0, -1):
            right = left - 1
            if cards[left][1] < cards[right][1]:
                cards[right], cards[left] = cards[left], cards[right]
                flag = True

    print(list_to_str(cards))


def selection_sort(cards, num):
    for head in range(num):
        min_i = head

        for target in range(head+1, num):
            if cards[target][1] < cards[min_i][1]:
                min_i = target
        cards[head], cards[min_i] = cards[min_i], cards[head]

    print(list_to_str(cards))


def is_stable(before, after, num):
    for i in range(num):
        for j in range(i+1, num):
            for a in range(num):
                for b in range(a+1, num):
                    if before[i][1] == before[j][1]\
                    and before[i] == after[b]\
                    and before[j] == after[a]:
                        return 'Not stable'
    return 'Stable'


def list_to_str(l, delimiter=' '):
    # The default delimiter is one space.
    return delimiter.join([str(v) for v in l])


if __name__ == '__main__':
    num = int(input())
    cards = input().split()
    cards_for_bubble = cards.copy()
    cards_for_selection = cards.copy()

    bubble_sort(cards_for_bubble, num)
    print(is_stable(cards, cards_for_bubble, num))

    selection_sort(cards_for_selection, num)
    print(is_stable(cards, cards_for_selection, num))

Submission status: Accepted

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


def bubble_sort(cards, num):
    for tail in range(num-1, 0, -1):
        for right in range(0, tail):
            left = right + 1
            if cards[left][1] < cards[right][1]:
                cards[right], cards[left] = cards[left], cards[right]

    print(list_to_str(cards))


def selection_sort(cards, num):
    for head in range(num):
        min_i = head

        for target in range(head+1, num):
            if cards[target][1] < cards[min_i][1]:
                min_i = target
        cards[head], cards[min_i] = cards[min_i], cards[head]

    print(list_to_str(cards))


def is_stable(before, after, num):
    for i in range(num):
        for j in range(i+1, num):
            for a in range(num):
                for b in range(a+1, num):
                    if before[i][1] == before[j][1]\
                    and before[i] == after[b]\
                    and before[j] == after[a]:
                        return 'Not stable'
    return 'Stable'


def list_to_str(l, delimiter=' '):
    # The default delimiter is one space.
    return delimiter.join([str(v) for v in l])


if __name__ == '__main__':
    num = int(input())
    cards = input().split()
    cards_for_bubble = cards.copy()
    cards_for_selection = cards.copy()

    bubble_sort(cards_for_bubble, num)
    print(is_stable(cards, cards_for_bubble, num))

    selection_sort(cards_for_selection, num)
    print(is_stable(cards, cards_for_selection, num))

Submission status: Accepted

Solution code:
N = int(raw_input())
Card = map(str, raw_input().split())
Card2 = Card[:]
Card3 = Card[:]

def bubbleSort(A, N):
    flag = 1
    while flag:
        flag = 0
        for i in range(N-1, 0, -1):
            if int(A[i][1]) < int(A[i-1][1]):
                temp = A[i]
                A[i] = A[i-1]
                A[i-1] = temp
                flag = 1
                
def selectionSort(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:
            temp = A[i]
            A[i] = A[minj]
            A[minj] = temp

def stableJudge(A, B):
    i = 0
    while(1):
        if i >= N-1:
            return "Stable"
        strB = []
        strB += B[i][0]
        strA = []
        for j in range(i+1, N):
            if B[i][1] == B[j][1] and j != N-1:
                strB += B[j][0]
            else:
                if B[i][1] == B[j][1] and j == N-1:
                    strB += B[j][0]
                if len(strB) != 1:
                    for k in range(0, N):
                        if A[k][1] == B[i][1]:
                            strA += A[k][0]
                    if strA != strB:
                        return "Not stable"
                    else:
                        i += len(strB)
                        break
                else:
                    i += len(strB)
                    break

bubbleSort(Card2, N)
print " ".join(Card2)
print stableJudge(Card, Card2)
selectionSort(Card3, N)
print " ".join(Card3)
print stableJudge(Card, Card3)

Submission status: Accepted

Solution code:
def BubbleSort(C,N):
    for i in range(N):
        j = N-1
        while True:
            if j == 0:
                break
            a,b = list(C[j]),list(C[j-1])
            if a[1] < b[1]:
                tmp = C[j-1]
                C[j-1] = C[j]
                C[j] = tmp
            j -= 1
    return C

def SelectionSort(D,N):
    for i in range(N):
        minj = i
        for j in range(i,N):
            a,b = list(D[j]),list(D[minj])
            if a[1] < b[1]:
                minj = j
        tmp = D[i]
        D[i] = D[minj]
        D[minj] = tmp
    return D

n = int(input())
d = input().split()
d2 = list(d)
d = BubbleSort(d,n)
for i in range(len(d)-1):
    print(d[i],end = ' ')
print(d[-1])
print('Stable')
d2 = SelectionSort(d2,n)
for i in range(len(d2)-1):
    print(d2[i],end = ' ')
print(d2[-1])
if d2 == d:
    print('Stable')
else:
    print('Not stable')

Submission status: Accepted

Solution code:
class Card():

    def bubble_sort(self):
        bubble_card = [i for i in self]
        for i in range(len(bubble_card)):
            for j in range(len(self)-1, i, -1):
                if bubble_card[j].strip('SHCD') < bubble_card[j-1].strip('SHCD'):
                    bubble_card[j], bubble_card[j-1] = bubble_card[j-1], bubble_card[j]
        return bubble_card


    def selection_sort(self):
        select_card = [i for i in self]
        for i in range(len(select_card)):
            minj = i
            change = False
            for j in range(i + 1, len(select_card)):
                if select_card[minj].strip('SHCD') > select_card[j].strip('SHCD'):
                    minj = j
                    change = True
            if change:
                select_card[i], select_card[minj] = select_card[minj], select_card[i]
        return select_card


    def stable_sort(self):
        sort_card = [i for i in self]
        sort = []
        for i in range(len(sort_card)-1):
            min = i
            for j in range(i+1, len(sort_card)):
                if int(sort_card[min].strip('SHCD')) > int(sort_card[j].strip('SHCD')):
                    min = j
            min_card = sort_card[min]
            sort_card.pop(min)
            sort_card.insert(i,min_card)
        sort = sort_card
        return sort





def main():
    n = int(input())
    cards = [i for i in input().split()]
    bubble = Card.bubble_sort(cards)
    select = Card.selection_sort(cards)
    stable = Card.stable_sort(cards)

    for i in range(len(bubble)):
        print(bubble[i]) if i == len(bubble)-1 else print(str(bubble[i])+' ',end='')
    print('Stable') if bubble == stable else print('Not stable')

    for i in range(len(select)):
        print(select[i]) if i == len(select)-1 else print(str(select[i])+' ',end='')
    print('Stable') if select == stable else print('Not stable')


if __name__ == '__main__':
    main()

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 stable','Stable'][b==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:
def selectionSort(a,b):
    for i in range(len(a)):
        mini = i
        for j in range(i,len(a)):
            if a[j] < a[mini]:
                mini = j
        if i != mini:
            ret = a[i]
            a[i] = a[mini]
            a[mini] = ret
            ret = b[i]
            b[i] =b[mini]
            b[mini] = ret
    
    output = []           
    for i in range(len(a)):
        output.append(str(b[i])+str(a[i]))
    print(" ".join(output))
    return output
    
    
def bubblesort(a,b):
    swap = True
    while swap:
        swap = False
        for j in range(1,len(a))[::-1]:
            if a[j] < a[j-1]:
                ret = a[j]
                a[j] = a[j-1]
                a[j-1] = ret
                ret = b[j]
                b[j] = b[j-1]
                b[j-1] = ret
                swap = True
    output = []           
    for i in range(len(a)):
        output.append(str(b[i])+str(a[i]))
    print(" ".join(output))
    return output


n = int(input())
card = input().split()
number = []
mark = []
number2 = []
mark2 = []
for i in range(n):
    number.append(int(list(card[i])[1]))
    mark.append(list(card[i])[0])
    number2.append(int(list(card[i])[1]))
    mark2.append(list(card[i])[0])

output1 = bubblesort(number,mark)
print("Stable")
output2 = selectionSort(number2, mark2)
print("Stable" if output1 == output2 else "Not stable"  )

Submission status: Accepted

Solution code:
N = int(input())

C = input().split()

B = C[:]
S = C[:]

# bubble sort
flag = 1
while(flag):
    flag = 0
    for x in range(1, N):
        if B[x][1:] < B[x-1][1:]:
            B[x], B[x-1] = B[x-1], B[x]
            flag = 1

# sectionSot
for x in range(0,N):
    minj = x
    for j in range(x,N):
        if S[j][1:] < S[minj][1:]:
            minj = j
    if minj != x:
        S[x], S[minj] = S[minj], S[x]

for i in range(1, N):
    v = C[i]
    j = i - 1
    while(j >=0 and C[j][1:] > v[1:]):
        C[j+1] = C[j]
        j -= 1
    C[j+1] = v

if(C == B):
    print(" ".join(b for b in B))
    print("Stable")
else:
    print(" ".join(b for b in B))
    print("Not stable")


if(C == S):
    print(" ".join(b for b in S))
    print("Stable")
else:
    print(" ".join(b for b in S))
    print("Not stable")

Submission status: Accepted

Solution code:
N = int(input())

C = input().split()

B = C[:]
S = C[:]

# bubble sort
flag = 1
while(flag):
    flag = 0
    for x in range(1, N):
        if B[x][1:] < B[x-1][1:]:
            B[x], B[x-1] = B[x-1], B[x]
            flag = 1

# sectionSot
for x in range(0,N):
    minj = x
    for j in range(x,N):
        if S[j][1:] < S[minj][1:]:
            minj = j
    if minj != x:
        S[x], S[minj] = S[minj], S[x]



print(" ".join(b for b in B))
print("Stable")


if(B == S):
    print(" ".join(b for b in S))
    print("Stable")
else:
    print(" ".join(b for b in S))
    print("Not stable")

Submission status: Accepted

Solution code:
def selectionSort(n, A):
    cnt = 0
    for i in range(n):
        minj = i
        for j in range(i, n):
            if A[minj][1] > A[j][1]:
                minj = j
        if i != minj:
            A[i], A[minj] = A[minj], A[i]
            cnt += 1
    return A


def bubbleSort(n, A):
    flag = True
    cnt = 0
    while flag:
        flag = False
        for j in range(n - 1, 0, -1):
            if A[j - 1][1] > A[j][1]:
                A[j - 1], A[j] = A[j], A[j - 1]
                cnt += 1
                flag = True
    return A


def stableSort(input, output):
    n = len(input)
    for i in range(n):
        for j in range(i + 1, n):
            for a in range(n):
                for b in range(a + 1, n):
                    if input[i][1] == input[j][1] and input[i] == output[b] and input[j] == output[a]:
                        return print("Not stable")
    return print("Stable")


if __name__ == '__main__':
    n = int(input())
    R = list(map(str, input().split()))
    C = R[:]
    D = R[:]  #????????¨?????????
    SR = selectionSort(n, R)
    BR = bubbleSort(n, C)
    print(*BR)
    stableSort(D,BR)
    print(*SR)
    stableSort(D,SR)

Submission status: Accepted

Solution code:
l, r=len, range
N= int(input())
c1= input().split()
c2=c1[:]
for i in r(l(c1)):
    for j in r(i+1, l(c1))[::-1]:
        if c1[j][1]< c1[j-1][1]:
            c1[j], c1[j-1]= c1[j-1], c1[j]

    m= i
    for j in r(i, l(c2)):
        if c2[j][1] < c2[m][1]: m= j
    c2[i], c2[m]= c2[m], c2[i]
print(*c1)
print("Stable")
print(*c2)
print("Stable" if c1==c2 else "Not stable")

Submission status: Accepted

Solution code:
# coding: utf-8
# Here your code !

def BubbleSort(A, N):
    count = 0
    flag = 1
    while flag:
        flag = 0
        for i in range(1, N):
            if int(A[N - i][1]) < int(A[N - i - 1][1]):
                A[N - i], A[N - i - 1] = A[N - i - 1], A[N - i]
                flag = 1
    return A


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
        if i != minj:
            C[i], C[minj] = C[minj], C[i]
    return C


if __name__ == '__main__':
    n = int(input())
    data = input().split()
    selection = data[:]
    data = BubbleSort(data, n)
#    print(" ".join(BubbleSort(data, n)))
    print(" ".join(data))
    print("Stable")
    selection = SelectionSort(selection, n)
    print(" ".join(selection))
    if data == selection:
        print("Stable")
    else:
        print("Not stable")

Submission status: Accepted

Solution code:
N = int(input())
l = [list(i) for i in input().split()]

a = l.copy()
frag = 1
i = 0
while frag:
    frag = 0
    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]
        frag = 1
    i += 1 
bubble_a = ["".join(a[i]) for i in range(N)]
print(" ".join(bubble_a))
print("Stable")

a = l.copy()
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]
selection_a = ["".join(a[i]) for i in range(N)]
print(" ".join(selection_a))

if bubble_a == selection_a:
    print("Stable")
else:
    print("Not stable")