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):
class Card:
    def __init__(self, label):
        suits = ['S', 'H', 'C', 'D']
        suit, value = list(label)
        assert(suit in suits and 0 < int(value) < 10)

        self.suit = suit
        self.value = int(value)

    def __eq__(self, other):
        """equal

        >>> Card('S1') == Card('D9')
        False
        >>> Card('D9') == Card('S1')
        False
        >>> Card('C5') == Card('C5')
        True
        """
        return self.value == other.value

    def __lt__(self, other):
        """less than

        >>> Card('S1') < Card('D9')
        True
        >>> Card('D9') < Card('S1')
        False
        """
        return self.value < other.value

    def __gt__(self, other):
        """greater than

        >>> Card('S1') > Card('D9')
        False
        >>> Card('D9') > Card('S1')
        True
        """
        return self.value > other.value

    def __hash__(self):
        return hash((self.suit, self.value))

    def __str__(self):
        return self.suit + str(self.value)


def bubble_sort(deck):
    """sort deck by bubble sort

    >>> deck = [Card('H4'), Card('C9'), Card('S4'), Card('D2'), Card('C3')]
    >>> print(" ".join([str(c) for c in bubble_sort(deck)]))
    D2 C3 H4 S4 C9
    """
    size = len(deck)
    for i in range(size):
        for j in reversed(range(i+1, size)):
            if deck[j] < deck[j-1]:
                deck[j-1], deck[j] = deck[j], deck[j-1]

    return deck


def selection_sort(deck):
    """sort deck by selection sort

    >>> deck = [Card('H4'), Card('C9'), Card('S4'), Card('D2'), Card('C3')]
    >>> print(" ".join([str(c) for c in selection_sort(deck)]))
    D2 C3 S4 H4 C9
    """
    size = len(deck)
    for i in range(size):
        mini = i
        for j in range(i, size):
            if deck[mini] > deck[j]:
                mini = j
        deck[i], deck[mini] = deck[mini], deck[i]

    return deck


def is_stable_sorted(org, deck):
    """check if deck is sorted by stable manner

    >>> c1 = Card('S1')
    >>> c2 = Card('D1')
    >>> is_stable_sorted([c1, c2], [c1, c2])
    True
    >>> is_stable_sorted([c1, c2], [c2, c1])
    False
    """
    idx = {c:i for (i, c) in enumerate(org)}
    return all([c1 < c2 or idx[c1] < idx[c2]
                for (c1, c2) in zip(deck[:-1], deck[1:])])


def check_stable(org, deck):
    if is_stable_sorted(org, deck):
        return "Stable"
    else:
        return "Not stable"


def run():
    _ = int(input()) 
    deck = []
    for lb in input().split():
        deck.append(Card(lb))

    db = bubble_sort(deck[:])
    print(" ".join([str(c) for c in db]))
    print(check_stable(deck, db))

    ds = selection_sort(deck[:])
    print(" ".join([str(c) for c in ds]))
    print(check_stable(deck, ds))


if __name__ == '__main__':
    run()

Solution (Python):
n = int(input())
*bLst, = input().split()
iLst = bLst[:]

for i in range(n):
    for j in range(n-1,i,-1):
        if bLst[j][1] < bLst[j-1][1]:
            bLst[j],bLst[j-1] = bLst[j-1],bLst[j]

print(*bLst)
print("Stable")

for i in range(n):
    min = i
    for j in range(i,n):
        if iLst[j][1] < iLst[min][1]:
            min = j
    iLst[i],iLst[min] = iLst[min],iLst[i]

print(*iLst)
if bLst == iLst:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
def bubble_sort(seq):
    for i in range(len(seq)):
        flag = 0
        for j in range(len(seq)-1,i,-1):
            if seq[j-1][1] > seq[j][1]:
                seq[j-1],seq[j] = seq[j],seq[j-1]
                flag = 1
        if flag == 0: break
    return seq


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



n = int(input())
*seq,= input().split()
seq2 = seq[:]

bl = bubble_sort(seq)
print(*bl)
print("Stable")
sl = selection_sort(seq2)
print(*sl)
if bl == sl:print("Stable")
else:print("Not stable")

Solution (Python):
def selection_sort(A):
    steps = 0
    N = len(A)
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if A[minj][0] > A[j][0]:
                minj = j
        if i != minj:
            steps += 1
        A[minj], A[i] = A[i], A[minj]

    
    
    return A


def bubbleSort(A):
    steps = 0
    flag = 1
    completed_idx = 0
    while flag:
        flag = 0
        for i in range(len(A) - 1, completed_idx, -1):
            if A[i - 1][0] > A[i][0]:
                A[i - 1], A[i] = A[i], A[i - 1]
                steps += 1
                flag = 1
        completed_idx += 1

    
    
    
    
    return A

d = dict()
N = int(input())
A = [(int(elem[1:]), elem[0]) for elem in input().split()]

for elem in A:
    if elem[0] not in d:
        d[elem[0]] = elem[1]
    else:
        d[elem[0]] += elem[1]

is_stable = True
A_bubble = bubbleSort(A[:])
st = A_bubble[0][1]
cur_val = A_bubble[1][0]
prev_val = A_bubble[0][0]
for e in A_bubble[1:]:
    cur_val = e[0]
    if cur_val != prev_val:
        if st != d[prev_val]:
            is_stable = False
            break
        st = ''
    st += e[1]
    prev_val = cur_val
[print(A_bubble[idx][1] + str(A_bubble[idx][0]), end=' ') if idx != len(A_bubble) - 1 else print(A_bubble[idx][1] + str(A_bubble[idx][0])) for idx in range(len(A_bubble))]
print('Stable' if is_stable else 'Not stable')

is_stable = True
A_slt = selection_sort(A[:])
st = A_slt[0][1]
cur_val = A_slt[1][0]
prev_val = A_slt[0][0]
for e in A_slt[1:]:
    cur_val = e[0]
    if cur_val != prev_val:
        if st != d[prev_val]:
            is_stable = False
            break
        st = ''
    st += e[1]
    prev_val = cur_val

[print(A_slt[idx][1] + str(A_slt[idx][0]), end=' ') if idx != len(A_slt) - 1 else print(A_slt[idx][1] + str(A_slt[idx][0])) for idx in range(len(A_slt))]
print('Stable' if is_stable else 'Not stable')

Solution (Python):
def bubbleSort(c):
    for i in range(0, len(c) - 1):
        for j in range(len(c)-1, i, -1):
            if c[j][1] < c[j-1][1]:
                c[j], c[j-1] = c[j-1], c[j]


def selectionSort(c):
    for i in range(0, 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]


def isStable(c1, c2):
    for i in range(0, len(c1)):
        if c1[i][0] != c2[i][0]:
            return False
    return True


import copy
n = int(input())
c1 = input().split()
c2 = copy.copy(c1)

bubbleSort(c1)
selectionSort(c2)
print(*c1)
print("Stable")
print(*c2)
print("Stable") if isStable(c1, c2) else print("Not stable")

Solution (Python):



import copy

def num_from_card(card):
    return int(card[1:])

def bubble_sort(A, N):
    A_ = copy.copy(A)
    flag = True
    while flag:
        flag = False
        for i in range(N-1, 0, -1):
            if num_from_card(A_[i]) < num_from_card(A_[i-1]):
                A_[i-1], A_[i] = A_[i], A_[i-1]
                flag = True
    return A_

def selection_sort(A, N):
    A_ = copy.copy(A)
    for i in range(N-1):
        minj = i
        for j in range(i, N):
            if num_from_card(A_[j]) < num_from_card(A_[minj]):
                minj = j
        if i != minj:
            A_[i], A_[minj] = A_[minj], A_[i]
    return A_

def is_stable(A, sorted_A, N):
    A_nums = [int(x[1:]) for x in A]
    same_num = [x for x in set(A_nums) if A_nums.count(x) > 1]
    A_symbols, sorted_A_symbols = [], []
    flag = 'Stable'
    for num in same_num:
        if [card[0] for card in A if int(card[1:]) == num] != [card[0] for card in sorted_A if int(card[1:]) == num]:
            flag = 'Not stable'
            break
    return flag

N = int(input())
cards = [x for x in input().split(' ')]

bubble_sorted = bubble_sort(cards, N)
selection_sorted = selection_sort(cards, N)

print(' '.join(bubble_sorted))
print(is_stable(cards, bubble_sorted, N))
print(' '.join(selection_sorted))
print(is_stable(cards, selection_sorted, N))

Solution (Python):

"""
Created on Sat Apr 28 09:21:55 2018
ALDS-1-2c
@author: maezawa
"""

def selection(a, n):
    """
    Selection Sort of array a, n=len(a)
    
    配列aｆは参照渡しなのでa自身が変化する（ソートされる）
    """
    cnt = 0
    for i in range(n):
        flag = 0
        minj = i
        for j in range(i+1,n):
            if int(a[j][1]) < int(a[minj][1]):
                minj = j
                flag = 1
        if flag == 1:
            temp = a[minj]
            a[minj] = a[i]
            a[i] = temp
            cnt += 1
    return cnt

def bubble(a, n):
    cnt = 0
    for i in range(n):
        for j in reversed(range(i+1,n)):
            if int(a[j][1]) < int(a[j-1][1]):
                temp = a[j]
                a[j] = a[j-1]
                a[j-1] = temp
                cnt += 1
    return cnt

def print_array(a):
    ans = str(a[0])
    for i in range(1,n):
        ans += ' '+str(a[i])  
    print(ans)

def is_stable(a, b):
    for card1 in range(len(a)):
        for card2 in range(card1+1,len(a)):
            if a[card1][1] == a[card2][1]:
                if b.index(a[card1]) > b.index(a[card2]):
                    return 'Not stable'
    return 'Stable'

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

bub = a[:]
cnt = bubble(bub, n)   
print_array(bub)
print(is_stable(a, bub))

sel = a[:]
cnt = selection(sel, n)   
print_array(sel)
print(is_stable(a, sel))

Solution (Python):
n=int(input())
c=input().split();d=c[:]
for i in range(n-1):
 for j in range(n-i-1):
  if c[j][1]>c[j+1][1]:c[j:j+2]=c[j+1],c[j]
 m=i
 for j in range(i,n):
  if d[m][1]>d[j][1]:m=j
 d[i],d[m]=d[m],d[i]
print(*c);print("Stable")
print(*d);print(['Not s','S'][c==d]+'table')

Solution (Python):
n = int(input())
s = input()
a = s.split()

def value(a, i):
    return int(a[i][-1])

def isstable(s, a, n):
    for i in range(n - 1):
        if value(a, i) == value(a, i + 1):
            v1 = s.index(a[i])
            v2 = s.index(a[i + 1])
            if v1 > v2:
                return "Not stable"
    return "Stable"

for i in range(n - 1):
    for j in range(i + 1, n)[::-1]:
        if value(a, j) < value(a, j - 1):
            a[j], a[j - 1] = a[j - 1], a[j]
print(" ".join(a))
print(isstable(s.split(), a, n))

a = s.split()

for i in range(n - 1):
    minj = i
    for j in range(i + 1, n):
        if value(a, j) < value(a, minj):
            minj = j
    a[i], a[minj] = a[minj], a[i]
print(" ".join(a))
print(isstable(s.split(), a, n))

Solution (Python):
n = int(input())
deck = input().split()

bd = list(deck)
for i in range(n):
    for j in reversed(range(i + 1, n)):
        if bd[j][1] < bd[j - 1][1]:
            bd[j], bd[j - 1] = bd[j - 1], bd[j]
print(' '.join(bd))
print('Stable')

sd = list(deck)
for i in range(n):
    mi = i
    for j in range(i, n):
        if sd[j][1] < sd[mi][1]:
            mi = j
    sd[i], sd[mi] = sd[mi], sd[i]
print(' '.join(sd))

if (bd == sd):
    print('Stable')
else:
    print('Not stable')

Solution (Python):
from typing import List, NamedTuple


class Card(NamedTuple):
    suit: str
    value: int


def bubble_sort(cards: List[Card]):
    for i in range(len(cards)):
        for j in range(len(cards) - 1, i, -1):
            if cards[j].value < cards[j - 1].value:
                cards[j], cards[j - 1] = cards[j - 1], cards[j]


def selection_sort(cards: List[Card]):
    for i in range(len(cards)):
        minj = i
        for j in range(i, len(cards)):
            if cards[j].value < cards[minj].value:
                minj = j
        cards[i], cards[minj] = cards[minj], cards[i]


def gen_numbet_card_pair(cards: List[Card]):
    return {n: [c for c in cards if c.value == n] for n in range(1, 10)}


def is_stable(in_cards: List[Card], out_cards: List[Card]):
    in_lists = gen_numbet_card_pair(in_cards)
    out_lists = gen_numbet_card_pair(out_cards)
    for n in range(10):
        if in_lists.get(n, []) != out_lists.get(n, []):
            return False
    return True


def printing(arr, f):
    b_arr = arr.copy()
    f(b_arr)
    print(" ".join([c.suit+str(c.value) for c in b_arr]))
    print("Stable" if is_stable(arr, b_arr) else "Not stable")


n = int(input())
cards: List[Card] = [Card(suit=x[0], value=int(x[1])) for x in input().split(" ")]
printing(cards, bubble_sort)
printing(cards, selection_sort)

Solution (Python):











def BubbleSort(C,N):
    flag = 1
    while flag:
        flag = 0
        for j in range(N-1,0,-1):
            if int(C[j][1:2]) < int(C[j-1][1:2]):
                tmp = C[j]
                C[j] = C[j-1]
                C[j-1] = tmp
                flag = 1
    print(' '.join(C))
    
    
                
                

def SelectionSort(C,N):
    for i in range(0,N,1):
        minj = i
        for j in range(i,N,1):
            if int(C[j][1:2]) < int(C[minj][1:2]):
                minj = j
        tmp = C[i]
        C[i] = C[minj]
        C[minj] = tmp
    print(' '.join(C))
        

def isStable(inp, out,N):
    for i in range(0,N):
        for j in range(i+1,N):
            for a in range(0,N):
                for b in range(a+1,N):

                    if int(inp[i][1]) == int(inp[j][1]) and inp[i] == out[b] and inp[j] == out[a]:
                        print('Not stable')
                        return
    print('Stable')



N = int(input())
A = list(input().split())
Bubble_A = A.copy()
Selection_A = A.copy()

BubbleSort(Bubble_A,N)
isStable(A,Bubble_A,N)
SelectionSort(Selection_A,N)
isStable(A,Selection_A,N)

Solution (Python):

def BubbleSort(C,N):
    for i in range (0,N,1):
        for j in range(N-1,i,-1):
            if int(C[j][1:2]) < int(C[j-1][1:2]):
                tmp = C[j]
                C[j] = C[j-1]
                C[j-1] = tmp
    print(' '.join(C))

    
                

def SelectionSort(C,N):
    for i in range(0,N,1):
        minj = i
        for j in range(i,N,1):
            if int(C[j][1:2]) < int(C[minj][1:2]):
                minj = j
        tmp = C[i]
        C[i] = C[minj]
        C[minj] = tmp
    print(' '.join(C))



N = int(input())
A = list(input().split())
Bubble_A = A.copy()
Selection_A = A.copy()

BubbleSort(Bubble_A,N)
print("Stable")
SelectionSort(Selection_A,N)
flag = True
for Bubble,Selection in zip(Bubble_A,Selection_A):
    if Bubble != Selection:
        flag = False
if flag :
    print("Stable")
else:
    print("Not stable")

Solution (Python):
def bubble(A):
    
    flag =True;
    n=len(A)
    i=0
    while flag:
        flag=False
        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]
               flag=True
        i+=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
        if i!=minj:
            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')

Solution (Python):
import copy

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

if __name__ == '__main__':
    n = int(input())
    B = input().split()
    C_bubble = bubble_sort(copy.deepcopy(B))
    print(*C_bubble)
    print('Stable')
    C_selection = selection_sort(copy.deepcopy(B))
    print(*C_selection)
    if C_bubble == C_selection:
        print('Stable')
    else:
        print('Not stable')

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

def selectionSort(c,n):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if(c[j][1] < c[minj][1]):
                minj = j
        c[i], c[minj] = c[minj], c[i]
    return c

def isStable(c1, c2, n):
    for i in range(n):
        if(c1[i] != c2[i]):
            return False
    return True

n = int(input())
c = input().split(' ')
trump = [list(i) for i in c]
bubble = ["".join(s) for s in bubbleSort(trump, n)]
trump = [list(i) for i in c]
selection = ["".join(s) for s in selectionSort(trump, n)]
str_bubble = " ".join(bubble)
str_selection = " ".join(selection)
print(str_bubble)
print('Stable')
print(str_selection)
if isStable(bubble, selection, n):
    print('Stable')
else:
    print('Not stable')

Solution (Python):



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


def SelectionSort(C, N):
    flag = 0

    for i in range(N):

        if N == 1:
            break

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

        if flag == 1:
            C[i], C[minj] = C[minj], C[i]

        flag = 0

    return C


def print_line(A):
    for i in range(len(A)):
        if i == len(A) - 1:
            print('{0}{1}'.format(A[i][0], A[i][1]))
        else:
            print('{0}{1} '.format(A[i][0], A[i][1]), end='')


def check_stable(Bubble_A, Select_A):
    for i in range(len(Select_A)):
        if Bubble_A[i][0] != Select_A[i][0]:
            print('Not stable')
            break
        elif i == len(Select_A) - 1:
            print('Stable')


N = int(input())
A = list(input())

A = [A[i:i+2] for i in range(0, len(A), 3)]

Bubble_A = BubbleSort(A[:], N)
Select_A = SelectionSort(A[:], N)

print_line(Bubble_A)
print('Stable')
print_line(Select_A)
check_stable(Bubble_A, Select_A)

Solution (Python):


import copy

def bubble_sort(bubble_N,bubble_A):
    
    flag = 1
    bi = 0
    
    while flag:
        flag = 0
        for bj in reversed(range(bi + 1, bubble_N)):
            if bubble_A[bj][1:2] < bubble_A[bj - 1][1:2]:
                tmp = bubble_A[bj - 1]
                bubble_A[bj - 1] = bubble_A[bj]
                bubble_A[bj] = tmp
            flag = 1
        bi += 1

def selection_sort(selection_N,selection_A):
    
    for si in range(selection_N):
        cnt_flg = 0
        minj = si
        for sj in range(si, selection_N):
            if selection_A[sj][1:2] < selection_A[minj][1:2]:
                minj = sj
                cnt_flg = 1
        tmp = selection_A[si]
        selection_A[si] = selection_A[minj]
        selection_A[minj] = tmp


N = int(input()) 
B_A = list(input().split()) 
S_A = copy.deepcopy(B_A) 

bubble_sort(N,B_A) 
selection_sort(N,S_A) 
ans_bubble = ' '.join(map(str,B_A)) 
ans_selection = ' '.join(map(str,S_A)) 


print(ans_bubble)
print("Stable")


print(ans_selection)
if ans_bubble == ans_selection:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
def bubble_sort(n, key=0):
    c = 0
    r = [x if isinstance(x, list) else [x] for x in n[:]]
    l = len(r) - 1
    for i in range(0, l):
        for j in range(l, i, -1):
            if r[j][key] < r[j-1][key]:
                r[j], r[j-1] = r[j-1], r[j]
                c += 1
    r = [x[0] if len(x) == 1 else x for x in r]
    return {'list': r, 'count': c}

def selection_sort(n, key=0):
    c = 0
    r = [x if isinstance(x, list) else [x] for x in n[:]]
    l = len(r)
    for i in range(0, l):
        mini = i
        for j in range(i, l):
            if (r[j][key] < r[mini][key]):
                mini = j
        if mini != i:
            r[i], r[mini] = r[mini], r[i]
            c += 1
    r = [x[0] if len(x) == 1 else x for x in r]
    return {'list': r, 'count': c}

def card_format(cards):
    return ' '.join([x[0] + str(x[1]) for x in cards])

if __name__ == '__main__':
    n = int(input())
    c = list(map(list, input().split(' ')))
    c = [[x[0], int(x[1])] for x in c]
    bsc = card_format(bubble_sort(c, 1)['list'])
    ssc = card_format(selection_sort(c, 1)['list'])
    print(bsc)
    print('Stable')
    print(ssc)
    print('Stable' if bsc == ssc else 'Not stable')

Solution (Python):
def BubbleSort(C, N):

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

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

def isStable(C1, C2, N):
    if C1 != C2:
        return "Not stable"
    return "Stable"

Num = int(input())
Cards = [x for x in input().split()]
card1 = BubbleSort(list(Cards), Num)
card2 = SelectionSort(list(Cards), Num)

print(" ".join(card1))
print(isStable(card1, card1, Num))
print(" ".join(card2))
print(isStable(card1, card2, Num))

Solution (Python):
def print_list(l):
    for i, n in enumerate(l):
        if i == N - 1:
            print(l[i])
        else:
            print(l[i], end=' ')

N = int(input())
A = input().split()
B = list(A)
for i in range(N):
    for j in range(N-1, i, -1):
        if int(A[j][1]) < int(A[j-1][1]):
            w = A[j]; A[j] = A[j-1]; A[j-1] = w
print_list(A)
print('Stable')

for i in range(N):
    min_j = i
    for j in range(i, N):
        if int(B[j][1]) < int(B[min_j][1]):
            min_j = j
    w = B[i]; B[i] = B[min_j]; B[min_j] = w
print_list(B)
if A == B:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
from copy import deepcopy

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


def bubble_sort(ary):
    for i in range(N):

        for j in range(N - 1, i, -1):
            if int(ary[j][1:]) < int(ary[j - 1][1:]):
                ary[j], ary[j - 1] = ary[j - 1], ary[j]


def selection_sort(ary):

    for i in range(0, N):
        minj = i

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

        ary[i], ary[minj] = ary[minj], ary[i]


def naive_check(oary, nary):
    for i in range(1, N - 1):
        for j in range(i + 1, N):
            for a in range(1, N - 1):
                for b in range(a + 1, N):

                    if int(oary[i][1:]) == int(nary[j][1:]):
                        if oary[i] == nary[b]:
                            if oary[j] == nary[a]:
                                return False

    return True


def is_stable(oary, nary):

    if naive_check(oary, nary):
        print('Stable')
    else:
        print('Not stable')


bary = deepcopy(oary)
bubble_sort(bary)
print(' '.join(bary))
print('Stable')


sary = deepcopy(oary)
selection_sort(sary)
print(' '.join(sary))
if bary == sary:
    print('Stable')
else:
    print('Not stable')

Solution (Python):


from math import sqrt, floor

class card:
    def __init__(self, _str):
        
        self.kind = _str  
        self.suit = _str[0]
        self.value = int(_str[1])

def cardinput():
    
    a = input().split()
    cards = []
    for i in range(len(a)):
        cards.append(card(a[i]))
    return cards

def show(a):
    
    _str = ""
    for i in range(len(a) - 1):
        _str += a[i].kind + " "
    _str += a[len(a) - 1].kind
    print(_str)

def bubble_sort(a):
    
    count = 0
    for i in range(1, len(a)):
        k = i - 1
        while k >= 0:
            
            if a[k].value > a[k + 1].value:
                a[k], a[k + 1] = a[k + 1], a[k]
                count += 1
            else: break
            k -= 1
    return count

def selection_sort(a):
    
    
    count = 0
    for i in range(len(a)):
        
        
        
        minj = i
        for j in range(i, len(a)):
            if a[j].value < a[minj].value: minj = j
        if a[i].value > a[minj].value: count += 1; a[i], a[minj] = a[minj], a[i]
    return count

def main():
    N = int(input())
    cards = cardinput()
    
    
    
    _copy = [cards[i] for i in range(N)]

    bubble_sort(cards)
    selection_sort(_copy)

    show(cards)
    print("Stable")
    show(_copy)

    is_stable = True
    for i in range(N):
        for j in range(i + 1, N):
            if _copy[i].value != _copy[j].value: continue
            if _copy[i].suit != cards[i].suit: is_stable = False; break
    if is_stable: print("Stable")
    else: print("Not stable")

if __name__ == "__main__":
    main()

Solution (Python):

from copy import deepcopy

n = int(input())
A = list(input().split())
B = deepcopy(A)


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


def SelectionSort(A,N):
    for i in range(N):
        minj = i
        for j in range(i,N):
            if A[j][1] < A[minj][1]:
                minj = j
        A[i], A[minj] = A[minj], A[i]
        
                
BubbleSort(A,n)
SelectionSort(B,n)
A = " ".join([data for data in A])
B = " ".join([data for data in B])

print(A)
print("Stable")

print(B)
if A == B:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
def bubble_sort(a, n):
    for i in range(n):
        for j in range(n - 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(a, n):
    is_stable = True

    for i in range(n):
        minj = i
        samei = n
        for j in range(i+1, n, 1):
            if a[j]['value'] == a[i]['value']:
                samei = j
            if a[j]['value'] < a[minj]['value']:
                minj = j
                if samei < minj:
                    is_stable = False
        tmp = a[i]
        a[i] = a[minj]
        a[minj] = tmp

    return is_stable

def print_list_split_whitespace(a):
    for x in a[:-1]:
        print(x['design'] + str(x['value']), end=' ')
    print(a[-1]['design'] + str(a[-1]['value']))


n = int(input())

a = input().split()
for i in range(n):
    s = a[i]
    a[i] = {'design': s[0], 'value': int(s[1])}
b = a.copy()
c = a.copy()

bubble_sort(a, n)
print_list_split_whitespace(a)

print("Stable")

is_stable = selection_sort(b, n)
print_list_split_whitespace(b)

if is_stable:
    print("Stable")
else:
    print("Not stable")

Solution (Python):




def selection_sort(l):
    N = len(l)
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if int(l[j][1]) < int(l[minj][1]):
                minj = j
        if i != minj:
            l[i], l[minj] = l[minj], l[i]


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


if __name__ == '__main__':
    N = raw_input()
    l1 = raw_input().split()
    l2 = l1[:]
    bubble_sort(l1)
    print ' '.join(l1)
    print "Stable"
    selection_sort(l2)
    print ' '.join(l2)
    if l1 == l2:
        print "Stable"
    else:
        print "Not stable"

Solution (Python):
def print_list(array):
    for i,e in enumerate(array):
        if i == N - 1:
            print(e)
        else:
            print(e, end=" ")

def bubbleSort():
    for i in range(N-1):
        for j in range(N-1, i, -1):
            if int(A[j][1:]) < int(A[j-1][1:]):
                w = A[j]; A[j] = A[j-1]; A[j-1] = w

def selectionSort():
    for i in range(N):
        min_index = i
        for j in range(i, N):
            if int(B[min_index][1:]) > int(B[j][1:]):
                min_index = j
        if i != min_index:
            w = B[i]; B[i] = B[min_index]; B[min_index] = w

N = int(input())
A = input().split()
B = list(A)
bubbleSort()
print_list(A)
print("Stable")
selectionSort()
print_list(B)
if A == B:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
import copy

def BubbleSort(C, N):
    for i in range(0,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]
    ret = " ".join(C)
    print(ret)
    print("Stable")
    return ret

def SelectionSort(C, N):
    for i in range(0,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]
    ret = " ".join(C)
    print(ret)
    return ret

N = int(input())
C = input().split(" ")
ret_B = BubbleSort(copy.deepcopy(C),N)
ret_S = SelectionSort(copy.deepcopy(C),N)
if ret_B == ret_S:
    print("Stable")
else:
    print("Not stable")