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: Wrong Answer

Solution code:
#!/usr/bin/env python
# encoding: utf-8

import copy


class Solution:
    def stable_sort(self):
        # write your code here
        array_length = int(input())
        b_array = [str(x) for x in input().split()]
        s_array = copy.deepcopy(b_array)

        bubble_result = self.bubble_sort(b_array=b_array, array_length=array_length)
        selection_result = self.selection_sort(s_array=s_array, array_length=array_length)

        # check whether selection sort is stable
        if bubble_result == selection_result:
            print("Stable")
        else:
            print("Not Stable")

    @staticmethod
    def selection_sort(s_array, array_length):
        # selection sort
        print('in2', s_array)
        selection_count = 0
        for i in range(array_length):
            min_j = i
            for j in range(i, array_length):
                if s_array[j][1] < s_array[min_j][1]:
                    min_j = j
            s_array[i], s_array[min_j] = s_array[min_j], s_array[i]
            if i != min_j:
                selection_count += 1

        result = " ".join(map(str, s_array))
        print(result)
        return result

    @staticmethod
    def bubble_sort(b_array, array_length):
        print('in1', b_array)
        flag, bubble_count, cursor = 1, 0, 0
        while flag:
            flag = 0
            for j in range(array_length - 1, cursor, -1):
                if b_array[j][1] < b_array[j - 1][1]:
                    b_array[j], b_array[j - 1] = b_array[j - 1], b_array[j]
                    flag = 1
                    bubble_count += 1
        cursor += 1
        result = " ".join(map(str, b_array))
        print(result)
        print("Stable")
        return result


if __name__ == '__main__':
    solution = Solution()
    solution.stable_sort()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# encoding: utf-8

import copy


class Solution:
    def stable_sort(self):
        # write your code here
        array_length = int(input())
        b_array = [str(x) for x in input().split()]
        s_array = copy.deepcopy(b_array)

        bubble_result = self.bubble_sort(b_array=b_array, array_length=array_length)
        selection_result = self.selection_sort(s_array=s_array, array_length=array_length)

        # check whether selection sort is stable
        if bubble_result == selection_result:
            print("Stable")
        else:
            print("Not stable")

    @staticmethod
    def selection_sort(s_array, array_length):
        # selection sort
        print('in2', s_array)
        selection_count = 0
        for i in range(array_length):
            min_j = i
            for j in range(i, array_length):
                if s_array[j][1] < s_array[min_j][1]:
                    min_j = j
            s_array[i], s_array[min_j] = s_array[min_j], s_array[i]
            if i != min_j:
                selection_count += 1

        result = " ".join(map(str, s_array))
        print(result)
        return result

    @staticmethod
    def bubble_sort(b_array, array_length):
        print('in1', b_array)
        flag, bubble_count, cursor = 1, 0, 0
        while flag:
            flag = 0
            for j in range(array_length - 1, cursor, -1):
                if b_array[j][1] < b_array[j - 1][1]:
                    b_array[j], b_array[j - 1] = b_array[j - 1], b_array[j]
                    flag = 1
                    bubble_count += 1
        cursor += 1
        result = " ".join(map(str, b_array))
        print(result)
        print("Stable")
        return result


if __name__ == '__main__':
    solution = Solution()
    solution.stable_sort()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# encoding: utf-8

import copy


class Solution:
    def stable_sort(self):
        # write your code here
        array_length = int(input())
        array = [str(x) for x in input().split()]

        bubble_result = self.bubble_sort(array=array, array_length=array_length)
        selection_result = self.selection_sort(array=copy.deepcopy(array), array_length=array_length)

        # check whether selection sort is stable
        if bubble_result == selection_result:
            print("Stable")
        else:
            print("Not stable")

    @staticmethod
    def selection_sort(array, array_length):
        # selection sort
        selection_count = 0
        for i in range(array_length):
            min_j = i
            for j in range(i, array_length):
                if array[j][1] < array[min_j][1]:
                    min_j = j
            array[i], array[min_j] = array[min_j], array[i]
            if i != min_j:
                selection_count += 1

        result = " ".join(map(str, array))
        print(result)
        return result

    @staticmethod
    def bubble_sort(array, array_length):
        flag, bubble_count, cursor = 1, 0, 0
        while flag:
            flag = 0
            for j in range(array_length - 1, cursor, -1):
                if array[j][1] < array[j - 1][1]:
                    array[j], array[j - 1] = array[j - 1], array[j]
                    flag = 1
                    bubble_count += 1
        cursor += 1
        result = " ".join(map(str, array))
        print(result)
        print("Stable")
        return result


if __name__ == '__main__':
    solution = Solution()
    solution.stable_sort()

Submission status: Wrong Answer

Solution code:
N = input()
A = raw_input().split()
B = A[:]
for i in xrange(N):
    for j in xrange(N-1, i, -1):
        if B[j][1] < B[j-1][1]:
            B[j], B[j-1] = B[j-1], B[j]
print ' '.join(B)
print 'Stable'

s = True
for i in xrange(N):
    minj = i
    for j in xrange(i, N):
        if A[j][1] < A[minj][1]:
            minj = j
    if A[i][1] == A[j][1]:
        s = False
    A[i], A[minj] = A[minj], A[i]
print ' '.join(A)
print 'Stable' if s else 'Not stable'

Submission status: Wrong Answer

Solution code:
N = input()
A = raw_input().split()
B = A[:]
for i in xrange(N):
    for j in xrange(N-1, i, -1):
        if B[j][1] < B[j-1][1]:
            B[j], B[j-1] = B[j-1], B[j]
print ' '.join(B)
print 'Stable'

s = True
for i in xrange(N):
    minj = i
    for j in xrange(i, N):
        if A[j][1] < A[minj][1]:
            minj = j
    if i != minj and A[i][1] == A[minj][1]:
        s = False
    A[i], A[minj] = A[minj], A[i]
print ' '.join(A)
print 'Stable' if s else 'Not stable'

Submission status: Wrong Answer

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_C&lang=jp
#??????????????????
#??????????????????????°???????????????£?????´???????????´?????¨??\?????????????????????????????????????????´????????????
#??????????????????????????????????°????????????????????????´???????????????????????????????????????????????¨??????

def bubble_sort(origin_list):
    list_length = len(origin_list)
    target_list = [i for i in origin_list]#??°????????????????????????
    flag = True
    change_count = 0
    top_index = 1
    while flag:
        flag = False
        for i in range(top_index, list_length)[::-1]:
            if target_list[i][1] < target_list[i - 1][1]:
                tmp = target_list[i]
                target_list[i] = target_list[i - 1]
                target_list[i - 1] = tmp
                change_count += 1
                flag = True
        top_index += 1       
    return target_list

def selection_sort(origin_list):
    list_length = len(origin_list)
    target_list = [i for i in origin_list]#??°????????????????????????
    change_count = 0
    for i in range(list_length):
        min_index = i
        for j in range(i, list_length):
            if target_list[j][1] < target_list[min_index][1]:
                min_index = j
        else:
            if not i == min_index:
                tmp = target_list[i]
                target_list[i] = target_list[min_index]
                target_list[min_index] = tmp
                change_count += 1
    return target_list

def check_stable(origin_list, target_list):
    for i, origin_v in enumerate(origin_list):
        for origin_v2 in origin_list[i+1:]:
            if origin_v[1] == origin_v2[1]:
                for j, target_v in enumerate(target_list):
                    for target_v2 in target_list[j+1:]:
                        if origin_v == target_v2 and origin_v2 == target_v:
                            return False
    return True

def stable_sort(target_list):
    print(*bubble_sort(target_list))
    print(check_stable(target_list, bubble_sort(target_list)))
    print(*selection_sort(target_list))
    print(check_stable(target_list, selection_sort(target_list)))
    
def main():
    n_list = int(input())
    target_list = [a for a in input().split()]
    stable_sort(target_list)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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
    """
    counter = 0
    for i in range(0, n):
        min_j = i
        for j in range(i, n):
            if key(numbers[j]) < key(numbers[min_j]):
                min_j = j
        if min_j != i:
            numbers[min_j], numbers[i] = numbers[i], numbers[min_j]
            counter += 1
    return numbers, 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
    """
    flag = True
    counter = 0
    while flag:
        flag = False
        for index in range(n - 1, 0, -1):
            if key(numbers[index]) < key(numbers[index - 1]):
                numbers[index], numbers[index - 1] = numbers[index - 1], numbers[index]
                flag = True
                counter += 1
    return numbers, 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: Wrong Answer

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: Wrong Answer

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: Wrong Answer

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

for i in range(n):
    m = i
    li = lst[i][0]
    if not li in sts:
        sts.append(li)
    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: Wrong Answer

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


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

    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]:
                        print('Not stable')
    print('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)
    is_stable(cards, cards_for_bubble, num)

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

Submission status: Wrong Answer

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


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

    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: Wrong Answer

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):
    for i in range(0, N-1):
        if B[i][1] == B[i+1][1]:
            for j in range(0, N):
                if B[i][1] == A[j][1]:
                    if B[i][0] != A[j][0]:
                        return "Not stable"
                    else:
                        break
    return "Stable"
    
bubbleSort(Card2, N)
print " ".join(Card2)
print stableJudge(Card, Card2)
selectionSort(Card3, N)
print " ".join(Card3)
print stableJudge(Card, Card3)

Submission status: Wrong Answer

Solution code:
def BubbleSort(C,N):
    count = 0
    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
                count += 1
            j -= 1
    return C,count

def SelectionSort(D,N):
    count = 0
    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
                count += 1
        tmp = D[i]
        D[i] = D[minj]
        D[minj] = tmp
    return D,count

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

Submission status: Wrong Answer

Solution code:
def BubbleSort(C,N):
    count = 0
    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
                count += 1
            j -= 1
    return C,count

def SelectionSort(D,N):
    count = 0
    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
                count += 1
        tmp = D[i]
        D[i] = D[minj]
        D[minj] = tmp
    return D,count

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

Submission status: Wrong Answer

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


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

number2 = number
mark2 = mark

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

Submission status: Wrong Answer

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


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

number2 = number
mark2 = mark

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

Submission status: Wrong Answer

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


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: Wrong Answer

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]


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: Wrong Answer

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("Stable")
    return print("Not stable")


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

Submission status: Wrong Answer

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
                print(A)
    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
        C[j],C[minj] = C[minj],C[j]
    return C

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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