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 < C[j-1].value
4             swap C[j] and C[j-1] SelectionSort(C)
1 for i = 0 to C.length-1
2     mini = i
3     for j = i to C.length-1
4         if C[j].value < C[mini].value
5             mini = j
6     swap C[i] and C[mini] Note that, indices for array elements are based on 0-origin. 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

Solution (Python):
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 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:
            
                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(' ')]
    
    
    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')

Solution (Python):



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))

Solution (Python):
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")

Solution (Python):
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')

Solution (Python):


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))

Solution (Python):
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))

Solution (Python):
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")

Solution (Python):

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")

Solution (Python):
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')

Solution (Python):
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)

Solution (Python):



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=' '):
    
    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))

Solution (Python):



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=' '):
    
    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))

Solution (Python):
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)

Solution (Python):
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')

Solution (Python):
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()

Solution (Python):
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])

Solution (Python):
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')

Solution (Python):
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"  )

Solution (Python):
N = int(input())

C = input().split()

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


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


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")

Solution (Python):
N = int(input())

C = input().split()

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


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


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")

Solution (Python):
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)

Solution (Python):
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")

Solution (Python):



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(data))
    print("Stable")
    selection = SelectionSort(selection, n)
    print(" ".join(selection))
    if data == selection:
        print("Stable")
    else:
        print("Not stable")

Solution (Python):
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")

Solution (Python):
def is_stable(oline, line):
    for i in range(N):
        for j in range(i+1, N):
            for a in range(N):
                for b in range(a+1, N):
                    if (oline[i][1] == oline[j][1]) & (oline[i] == line[b]) & (oline[j] == line[a]):
                        return False
    return True

N = int(input())
line = input().split()
oline = line.copy()

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


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

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

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

print(output_str + "\n" + judge_stbl)

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

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

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

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

print(output_str + "\n" + judge_stbl)

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

def SelectionSort(C,N):
    for i in range(N):
        minj = i
        for j in range(i,N):
            if int(C[j][1]) < int(C[minj][1]):
                minj = j
        C[i],C[minj] = C[minj],C[i]

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

Solution (Python):
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")