import collections

def chk_before_tranp_bigger(now, before):
    return int(before[1]) > int(now[1])


def is_stable(inputs: list, sort_: list) -> str:
    """
conditions
・ Cards with the same number
・ Same as the order in which they appear in the input

Once, group the list of input data using numbers as keys
Example)
        {
            '4': ['H4', 'S4'],
            '9': ['C9'],
            '3': ['C3']
        }
    """
    judge = 'Not stable'
    loop = True
    set_num = collections.defaultdict(list)
    for input_ in inputs:
        set_num[input_[1]].append(input_)

    for g, dl in set_num.items():
        if len(dl) <= 1:
            continue
        min_index = -1
        for d in dl:
            if min_index > sort_.index(d):
                loop = False
                break
            min_index = sort_.index(d)
        if not loop:
            break
    else:
        judge = 'Stable'

    return judge


def bubble_sort(n: int, a: list) -> (list, str):
    dl = a.copy()
    for i in range(n):
        for j in range(n-1, i, -1):
            if chk_before_tranp_bigger(dl[j], dl[j-1]):
                dl[j], dl[j-1] = dl[j-1], dl[j]
    return dl, is_stable(a,  dl)


def selected_sort(n: int, a: list) -> (list, str):
    dl = a.copy()
    for i in range(n):
        mini = i
        for j in range(i, n):
            if chk_before_tranp_bigger(dl[j], dl[mini]):
                mini = j
        if mini != i:
            dl[i], dl[mini] = dl[mini], dl[i]

    return dl, is_stable(a, dl)


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

sort_, judge = bubble_sort(n, a)
print(*sort_)
print(judge)

sort_, judge = selected_sort(n, a)
print(*sort_)
print(judge)

Recommended Posts