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):
import copy
n = int(input())
a = input().split()
a_sr = []
a_sr_l = []
for i in range(n-1):
    if a[i][1] not in a_sr_l:
        for j in range(i+1, n):
            if a[i][1] == a[j][1]:
                if a[i][1] not in a_sr_l:
                    a_sr_l.append(a[i][1])
                if len(a_sr) == 0:
                    a_sr.append(a[i][0])
                a_sr.append(a[j][0])
a_b = copy.deepcopy(a)
a_s = copy.deepcopy(a)





neighbor = True
while neighbor:
    neighbor = False
    for i in range(n-1, 0, -1):
        if a_b[i][1] < a_b[i-1][1]:
            a_tmp = a_b[i]
            a_b[i] = a_b[i-1]
            a_b[i-1] = a_tmp
            neighbor = True
for i in range(n-1):
    print(a_b[i], end=" ")
print(a_b[n-1])
a_b_s = []
a_b_s_l = []
for _ in a_sr_l:
    for i in range(n):
        if a_b[i][1] == _ and _ not in a_b_s_l:
            for j in range(i+1, n):
                if a_b[i][1] == a_b[j][1]:
                    if a_b[i][1] not in a_b_s_l:
                        a_b_s_l.append(a_b[i][1])
                    if len(a_b_s) == 0:
                        a_b_s.append(a_b[i][0])
                    a_b_s.append(a_b[j][0])

if a_b_s != a_sr:
    print("Not stable")
else:
    print("Stable")


for i in range(n-1):
    tmp_index = i
    for j in range(i+1, n):
        
        
        if a_s[j][1] < a_s[tmp_index][1]:
            tmp_index = j
    if tmp_index != i:
        
        a_tmp = a_s[i]
        a_s[i] = a_s[tmp_index]
        a_s[tmp_index] = a_tmp
for i in range(n-1):
    print(a_s[i], end=" ")
print(a_s[n-1])
a_s_s = []
a_s_s_l = []
for _ in a_sr_l:
    for i in range(n):
        if a_s[i][1] == _ and _ not in a_s_s_l:
            for j in range(i+1, n):
                if a_s[i][1] == a_s[j][1]:
                    if a_s[i][1] not in a_s_s_l:
                        a_s_s_l.append(a_s[i][1])
                    if len(a_s_s) == 0:
                        a_s_s.append(a_s[i][0])
                    a_s_s.append(a_s[j][0])


if a_s_s != a_sr:
    print("Not stable")
else:
    print("Stable")

Solution (Python):
def bubble_sort(sequence):
    for i in range(len(sequence)):
        for j in range(len(sequence)-1, i, -1):
            if int(sequence[j-1][1]) > int(sequence[j][1]):
                sequence[j], sequence[j-1] \
                    = sequence[j-1], sequence[j]
    return sequence


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


def main():
    input()
    cards = input().split()
    bubble = bubble_sort(cards[:])
    selection = selection_sort(cards[:])
    stable = sorted(cards, key=lambda card: int(card[1]))
    print(' '.join(bubble))
    print('Stable' if bubble == stable else 'Not stable')
    print(' '.join(selection))
    print('Stable' if selection == stable else 'Not stable')


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
A = list(input().split())

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

def bubble_sort(A, N):
    x = A.copy()
    for i in range(N):
        for j in range(N-1, i, -1):
            if val(x[j]) < val(x[j-1]):
                x[j], x[j-1] = x[j-1], x[j]
    return x

def selection_sort(A, N):
    x = A.copy()
    for i in range(N):
        mini = i
        for j in range(i, N):
            if val(x[j]) < val(x[mini]):
                mini = j
        x[i], x[mini] = x[mini], x[i]
    return x
    
A_bubble = bubble_sort(A, N)
A_selection = selection_sort(A, N)

print(' '.join(map(str, A_bubble)))
print("Stable")
print(' '.join(map(str, A_selection)))
if A_bubble == A_selection:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
def SelectionSort(A):
    n = len(A)
    for i in range(n-1):
        mini = i
        for j in range(i+1, n):
            if int(A[j][1]) < int(A[mini][1]):
                mini = j
        if i != mini:
            A[i], A[mini] = A[mini], A[i]
    print(' '.join(A))
    return A

def BubbleSort(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], A[j-1] = A[j-1], A[j]
    print(' '.join(A))
    return A

_ = input()
lines = input().split()
a = BubbleSort(lines.copy())
print('Stable')
b = SelectionSort(lines.copy())
ans = 'Stable' if a == b else 'Not stable'
print(ans)

Solution (Python):
def b_sort(alist):
    for i in range(len(alist)):
        for j in range(len(alist)-1, i, -1):
            if alist[j][1] < alist[j-1][1]:
                alist[j], alist[j-1] = alist[j-1], alist[j]
        alist[i] = alist[i][0] + alist[i][1]
    return ' '.join(alist)


def s_sort(alist):
    for x in range(len(alist)):
        currentmin = x
        for y in range(x+1, len(alist)):
            if alist[y][1] < alist[currentmin][1]:
                currentmin = y
        if x != currentmin:
            alist[x], alist[currentmin] = alist[currentmin], alist[x]
        alist[x] = alist[x][0] + alist[x][1]
    return ' '.join(alist)


if __name__ == '__main__':
    N = int(input())
    alist = [list(x) for x in list(input().split())]
    clist = alist.copy()
    ans_b = b_sort(alist)
    ans_s = s_sort(clist)
    print(ans_b)
    print('Stable')
    print(ans_s)
    print('Stable' if ans_b == ans_s else "Not stable")

Solution (Python):
def bubble_sort(cards, n):
    for i in range(n):
        for j in range(n-1, i, -1):
            if cards[j][1] < cards[j-1][1]:
                cards[j], cards[j-1] = cards[j-1], cards[j]

    return cards

def selection_sort(cards, n):
    for i in range(n):
        minj = i

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

        if i != minj:
            cards[i], cards[minj] = cards[minj], cards[i]

    return cards

def is_stable(cards, sorted_cards):
    hashed = {}

    for m, v in cards:
        if v not in hashed:
            hashed[v] = []

        hashed[v].append((m, v))

    for sm, sv in sorted_cards:
        if hashed[sv][0] != (sm, sv):
            return False

        hashed[sv] = hashed[sv][1:]

    return True

def print_cards(cards, sorted_cards):
    print(' '.join([card[0]+str(card[1]) for card in sorted_cards]))

    if is_stable(cards, sorted_cards):
        print('Stable')
    else:
        print('Not stable')

def main():
    n = int(input())
    cards = [(card[0], int(card[1])) for card in input().split()]

    sorted_cards = bubble_sort(cards[:], n)
    print_cards(cards, sorted_cards)

    sorted_cards = selection_sort(cards[:], n)
    print_cards(cards, sorted_cards)

if __name__ == '__main__':
    main()

Solution (Python):
import copy
def BubbleSort(A):
    C = copy.deepcopy(A)
    N = len(A)
    for i in range(N):
        for j in range(N-1, i, -1):
            if int(C[j][1]) < int(C[j -1][1]):
                C[j], C[j - 1] = C[j - 1], C[j]
    return C

def SelectionSort(A):
    C = copy.deepcopy(A)
    N = len(A)
    for i in range(N):
        min_temp = i
        for j in range(i, N, 1):
            if int(C[j][1]) < int(C[min_temp][1]):
                min_temp = j
        C[min_temp], C[i] = C[i], C[min_temp]
    return C

def isStable(A, B):
    N = len(A)
    M = len(B)
    for i in range(N):
        for j in range(i+1, N, 1):
            for x in range(M):
                for y in range(x+1, M, 1):
                    if A[i][1] == A[j][1] and A[i] == B[y] and A[j] == B[x]:
                        return 'Not stable'
    else:
        return 'Stable'

N = int(input())
cards = input().split()
result1 = ' '.join(BubbleSort(cards))
result2 = ' '.join(SelectionSort(cards))
print(result1)
print(isStable(cards, BubbleSort(cards)))
print(result2)
print(isStable(cards, SelectionSort(cards)))

Solution (Python):
import copy
N = int(input())
Cards1 = list(map(str, input().split()))


Cards2 = copy.deepcopy(Cards1)



for i in range(0, N):
    for j in reversed(range(i+1, N)):
        if int(Cards1[j][1:]) < int(Cards1[j-1][1:]):
            Cards1[j], Cards1[j-1] = Cards1[j-1], Cards1[j]


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

print(*Cards1)
print('Stable')
print(*Cards2)
if Cards1 != Cards2:
    print('Not stable')
else:
    print('Stable')

Solution (Python):
def bubble_sort(lis, l):
    flag = 1
    while flag:
        flag = 0
        for i in range(l - 1, 0, -1):
            if int(lis[i][1:]) < int(lis[i - 1][1:]):
                ele = lis[i]
                lis[i] = lis[i - 1]
                lis[i - 1] = ele
                flag = 1
    return 'Stable'


def selection_sort(lis, l):
    for i in range(0, l - 1):
        minj = i
        for j in range(i, l):
            if int(lis[j][1:]) < int(lis[minj][1:]):
                minj = j
        ele = lis[i]
        lis[i] = lis[minj]
        lis[minj] = ele

inputs = []
while True:
    try:
        inputs.append(input())
    except(EOFError):
        break

ln = int(inputs[0])
li_1 = list(inputs[1].split())
li_2 = li_1.copy()

stab_1 = bubble_sort(li_1, ln)
stab_2 = selection_sort(li_2, ln)

sortComp = 'Stable' if (li_1 == li_2) else 'Not stable'

print(*li_1)
print(stab_1)
print(*li_2)
print(sortComp)

Solution (Python):
def bubble_sort(c, n):
    is_swapped = True
    i = 0
    while is_swapped:
        is_swapped = False
        for j in range(n-1, i, -1):
            if c[j][1] < c[j-1][1]:
                tmp = c[j]
                c[j] = c[j-1]
                c[j-1] = tmp
                is_swapped = True
        i += 1


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
        if i != minj:
            tmp = c[i]
            c[i] = c[minj]
            c[minj] = tmp


def make_dict(l):
    result = {}
    for v in l:
        num = v[1]
        if num in result:
            result[num].append(v)
        else:
            result[num] = [v]
    result = {k: v for k, v in result.items() if len(v) >= 2}

    return result


def print_is_stable(before, after):
    is_stable = True
    before_dict = make_dict(before)
    after_dict = make_dict(after)
    for k in before_dict:
        if before_dict[k] != after_dict[k]:
            is_stable = False
            break

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


n = int(input())
a = [i for i in input().split()]
c = a[:]

bubble_sort(c, n)
print(' '.join([str(i) for i in c]))
print_is_stable(a, c)

c = a[:]
selection_sort(c, n)
print(' '.join([str(i) for i in c]))
print_is_stable(a, c)

Solution (Python):
n = int(input())
c = list(input().split())
c1, c2 = c[:], c[:]

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

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

bubbleSort()
selectionSort()
print(" ".join(map(str, c1)))
print("Stable")
print(" ".join(map(str, c2)))
if c1==c2:
  print("Stable")
else:
  print("Not stable")

Solution (Python):

class Card:
    def __init__(self, c):
        self.suit = c[0]
        self.value = int(c[1])
def toi(c):
    return c.value
def toStr(c):
    return c.suit + str(c.value)
def bubble_sort(C,N):
    for i in range(0, N):
        for j in range(N-1,i,-1):
            if C[j].value < C[j-1].value:
                tmp = C[j]
                C[j] = C[j-1]
                C[j-1] = tmp
    return (C,True)
def selection_sort(C,N):
    st = True
    for i in range(0,N):
        minj = i
        for j in range(i,N):
            
            if C[j].value < C[minj].value:
                minj = j
        if not i == minj:
            if (list(map(toi, C[i:]))).count(C[i].value) > 1: st = False
            tmp = C[i]
            C[i] = C[minj]
            C[minj] = tmp
    return (C, st)
N = int(input())
C = [Card(i) for i in input().split(' ')]
C1, isstable1 = bubble_sort(C[:],N)
print(' '.join(list(map(toStr, C1))))
if isstable1: print('Stable')
else: print('Not stable')
C2, isstable2 = selection_sort(C[:],N)
print(' '.join(list(map(toStr, C2))))
if isstable2: print('Stable')
else: print('Not stable')