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 bubble_sort(a):
    n = len(a)
    for j in range(n):
        m = n-1-j 
        for i in range(m):
            if a[i][1] > a[i+1][1]:
                a[i],a[i+1] = a[i+1],a[i]
    return a


def selection_sort(a):
    MAXINT = 10
    n = len(a)
    for j in range(n):
        minv = MAXINT
        minp = -1
        for i in range(j,n):
            if int(a[i][1]) < minv:
                minv = int(a[i][1])
                minp = i
        a[minp],a[j]=a[j],a[minp]
    return a

def stable(a,f):
    b = f(a[:])
    print ' '.join(b)
    p = 1
    while p < 10:
        c = []
        d = []
        for i in range(len(a)):
            if a[i][1] == str(p):
                c.append(a[i])
            if b[i][1] == str(p):
                d.append(b[i])
        for i in range(len(c)):
            if c[i] != d[i]:
                print "Not stable"
                return
        p += 1
    print "Stable"

n = int(raw_input())
cards = raw_input().split(' ')

stable(cards[:],bubble_sort)
stable(cards[:],selection_sort)

Solution (Python):
STABLE = 'Stable'
UNSTABLE = 'Not stable'


def main():
  card_num = int(input())
  cards = input().split()

  bubble_sorted = bubble_sort(cards, card_num)
  select_sorted = select_sort(cards, card_num)

  stability = True
  for i, c in enumerate(select_sorted):
    if c != bubble_sorted[i]:
      stability = False
      break
  stability = STABLE if stability else UNSTABLE

  print(' '.join(bubble_sorted))
  print(STABLE)

  print(' '.join(select_sorted))
  print(stability)

  return 0


def order(card_sym):
  order = int(card_sym[1])
  return order


def select_sort(elements, element_num):
  elements = list(elements)

  for i in range(0, element_num - 1):
    min_val = order(elements[i + 1])
    min_index = i + 1
    for j in range(i + 1, element_num):
      if order(elements[j]) < min_val:
        min_val = order(elements[j])
        min_index = j
    if order(elements[i]) > order(elements[min_index]):
      elements[i], elements[min_index] = elements[min_index], elements[i]

  return elements


def bubble_sort(elements, element_num):
  elements = list(elements)

  for i in range(1, element_num):
    for j in reversed(range(i, element_num)):
      if order(elements[j - 1]) > order(elements[j]):
        elements[j - 1], elements[j] = elements[j], elements[j - 1]

  return elements


if __name__ == '__main__':
  main()

Solution (Python):
N = int(input())
C1 = input().split()
C2 = C1[:]

def bubbleSort(C, N):
    for i in range(N):
        for j in range(N-1, i, -1):
            if int(C[j][1]) < int(C[j-1][1]):
                tmp = C[j]
                C[j] = C[j-1]
                C[j-1] = tmp
        i += 1
    return C

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 minj != i:
            tmp = C[minj]
            C[minj] = C[i]
            C[i] = tmp
        i += 1
    return C

bubbleSort_result = ' '.join(bubbleSort(C1, N))
selectionSort_result = ' '.join(selectionSort(C2, N))

print(bubbleSort_result)
print('Stable')
print(selectionSort_result)
if bubbleSort_result == selectionSort_result:
    print('Stable')
else:
    print('Not stable')

Solution (Python):
def selection_sort(array):
    count_swap = 0
    for i in range(len(array)):
        minj = i
        for j in range(i + 1,len(array)):
            if num(array[j]) < num(array[minj]):
                minj = j
        if num(array[minj]) is not num(array[i]):
            tmp = array[minj]
            array[minj] = array[i]
            array[i] = tmp
            count_swap += 1
    return count_swap

def bubble_sort(array):
    isEnd = False
    count_swap = 0
    while isEnd is False:
        isEnd = True
        for j in reversed(range(1,len(array))):
            if num(array[j - 1]) > num(array[j]):
                tmp = array[j - 1]
                array[j - 1] = array[j]
                array[j] = tmp
                count_swap += 1
                isEnd = False
    return count_swap

def print_array(array):
     print(str(array)[1:-1].replace(', ', ' ').replace('\'', ''))

def num(s):
    
    return int(s[1])

def main():
    N = int(input())
    array = [s for s in input().split(' ')]
    array2 = [i for i in array]
    
    bubble_sort(array)
    print_array(array)
    print('Stable')
    selection_sort(array2)
    print_array(array2)
    if array == array2:
        print('Stable')
    else:
        print('Not stable')

if __name__ == '__main__':
    main()

Solution (Python):
class Card():

    def __init__(self):
        self.suit = 0
        self.value = 0


def bubble_sort(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]


def selection_sort(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]


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


def print_result(c, n):
    r = []
    for i in range(n):
        r.append(c[i].suit + str(c[i].value))
    print(' '.join(r))


def main():
    n = int(input())
    c1 = [Card() for x in range(n)]
    c2 = [Card() for x in range(n)]
    ary = [x for x in input().split(' ')]

    for i in range(n):
        s, v = list(ary[i])
        c1[i].suit, c1[i].value = s, int(v)
        c2[i].suit, c2[i].value = s, int(v)

    bubble_sort(c1, n)
    selection_sort(c2, n)

    print_result(c1, n)
    print('Stable')
    print_result(c2, n)
    if is_stable(c1, c2, n):
        print('Stable')
    else:
        print('Not stable')


if __name__ == '__main__':
    main()

Solution (Python):


def BubbleSort(A, n):
    for i in range(n-1):
        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]
    return A


def SelectionSort(A, n):
    mini = 1
    for i in range(n):
        mini = i
        for j in range(i, n):
            if int(A[j][1]) < int(A[mini][1]):
                mini = j
        A[i], A[mini] = A[mini], A[i]
    return A

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

b_ans = BubbleSort(A[:], n)
s_ans = SelectionSort(A[:], n)

print(" ".join(b_ans))
print("Stable")
print(" ".join(s_ans))
if b_ans == s_ans:
    print("Stable")
else:
    print("Not stable")

Solution (Python):
length = int(input())
targ = [n for n in input().split(' ')]
selecttarg = targ[:]

for l in range(length):
    for init in range(l):
        if targ[l - init][1] < targ[l - init - 1][1]:
            disp = targ[l-init]
            targ[l-init] = targ[l-init-1]
            targ[l-init-1] = disp
print(' '.join([str(n) for n in targ]))

print("Stable")

selectflag = 0
for l in range(length):
    value = l
    samevalue = l
    for init in range(l+1,length):
        if selecttarg[value][1] > selecttarg[init][1]:
            value = init
        elif selectflag != 1 and selecttarg[l][1] == selecttarg[init][1]:
            samevalue = init
    if samevalue != l and value != l and value > samevalue:
        selectflag = 1
    disp = selecttarg[l]
    selecttarg[l] = selecttarg[value]
    selecttarg[value] = disp
print(' '.join([str(n) for n in selecttarg]))
if selectflag == 0:
    print("Stable")
else:
    print("Not stable")

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

def bubble_sort(A):
    for i in range(0, N):
        for j in range(i+1, N)[::-1]:
            if int(A[j][1]) < int(A[j-1][1]):
                A[j], A[j-1] = A[j-1], A[j]
    return A

def selection_sort(A):
    for i in range(0, N):
        min_i = i
        for j in range(i+1, N):
            if int(A[j][1]) < int(A[min_i][1]):
                min_i = j
        A[i], A[min_i] = A[min_i], A[i]
    return A

BA = bubble_sort(A[:])
SA = selection_sort(A[:])

print(' '.join([str(i) for i in BA]))
print('Stable')
print(' '.join([str(i) for i in SA]))
print('Stable' if SA == BA else 'Not stable')

Solution (Python):
import copy
N = int(input())
bscs = [(int(c[-1]), c) for c in input().split(" ")]
sscs = copy.copy(bscs)
for i in range(N):
    j = N - 1
    while j > i:
        if bscs[j][0] < bscs[j - 1][0]:
            tmp = bscs[j]
            bscs[j] = bscs[j - 1]
            bscs[j - 1] = tmp
        j -= 1
print(" ".join([c[1] for c in bscs]))
print("Stable")
for i in range(N):
    minj = i
    for j in range(i, N):
        if sscs[j][0] < sscs[minj][0]:
            minj = j
    tmp = sscs[i]
    sscs[i] = sscs[minj]
    sscs[minj] = tmp
print(" ".join([c[1] for c in sscs]))
print("Stable" if bscs == sscs else "Not stable")

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

A = list(input().split())

def insertion_sort(l):
    for i in range(0, len(l) - 1):
        x = i + 1
        while x != 0 and int(l[x][1]) < int(l[x - 1][1]):
            temp = l[x]
            l[x] = l[x - 1]
            l[x - 1] = temp
            x -= 1
    return l


def babble_sort(l):
    for i in range(0, len(l)):
        for j in reversed(range(i+1, len(l))):
            b = int(l[j][1])
            a = int(l[j - 1][1])
            if b < a:
                t = l[j]
                l[j] = l[j-1]
                l[j-1] = t
    return l

def is_stable(a, l):
    for i in range(0, len(a)):
        if a[i] != l[i]:
            return False
    return True

def print_with_space(l):
    print(' '.join(str(x) for x in l))

B = insertion_sort(A[:])

babbled = babble_sort(A[:])
print_with_space(babbled)

if is_stable(B, babbled):
    print('Stable')
else:
    print('Not stable')

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

selected = selection_sort(A[:])
print_with_space(selected)

if is_stable(B, selected):
    print('Stable')
else:
    print('Not stable')

Solution (Python):
import sys

def is_stable(in_data, out_data):
    len_data = len(in_data)

    for i in range(len_data):
        for j in range(i+1, len_data):
            for a in range(len_data):
                for b in range(a+1, len_data):
                    if in_data[i][1] == in_data[j][1] and\
                       in_data[i] == out_data[b] and\
                       in_data[j] == out_data[a]:
                        return False

    return True

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

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

        data[i], data[minj] = data[minj], data[i]

def main():
    n = int(sys.stdin.readline().strip())
    card1 = sys.stdin.readline().strip().split(' ')

    card2 = card1[::]
    bubble_sort(card2, n)
    print(' '.join(card2))
    
    if is_stable(card1, card2):
        print('Stable')
    else:
        print('Not stable')

    card2 = card1[::]
    selection_sort(card2, n)
    print(' '.join(card2))
    
    if is_stable(card1, card2):
        print('Stable')
    else:
        print('Not stable')

if __name__ == '__main__':
    main()

Solution (Python):
import sys

def is_stable(bs_data, ss_data):
    
    
    len_data = len(bs_data)

    for i in range(len_data):
        if bs_data[i] != ss_data[i]:
            return False

    return True

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

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

        data[i], data[minj] = data[minj], data[i]

def main():
    n = int(sys.stdin.readline().strip())
    card1 = sys.stdin.readline().strip().split(' ')

    card2 = card1[::]
    bubble_sort(card2, n)
    print(' '.join(card2))
    
    print('Stable')

    card3 = card1[::]
    selection_sort(card3, n)
    print(' '.join(card3))
    
    if is_stable(card2, card3):
        print('Stable')
    else:
        print('Not stable')

if __name__ == '__main__':
    main()

Solution (Python):



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

input_num = int(input())
input_list = input().split()
bubble_list = bubble_sort(input_list)
selection_list = selection_sort(input_list)
for c in bubble_list:
    print(c, end='')
    if c != bubble_list[len(bubble_list)-1]:
        print(' ', end='')
print("\nStable")
stable_flg = True
for i in range(len(input_list)):
    if bubble_list[i] != selection_list[i]:
        stable_flg = False
    print(selection_list[i], end='')
    if i < len(input_list)-1:
        print(" ", end='')
if stable_flg:
    print("\nStable")
else:
    print("\nNot stable")

Solution (Python):
length = int(input())
eles = [l for l in input().split()]
is_stable = 'Stable'

import copy
_copy = copy.deepcopy(eles)

for i in range(length):
    for j in range(length-1, 0, -1):
        if _copy[j][1] < _copy[j-1][1]:
            _copy[j], _copy[j-1] = _copy[j-1], _copy[j]

print(*_copy)
print(is_stable)

__copy = copy.deepcopy(eles)
for i in range(length-1):
    _min = i
    for l in range(i, length):
        if __copy[l][1] < __copy[_min][1]:
            _min = l
    if __copy[i][1] > __copy[_min][1]:
        __copy[i], __copy[_min] = __copy[_min], __copy[i]

print(*__copy)

for i in range(length -1):
    if _copy[i] != __copy[i]:
        is_stable = 'Not stable'

print(is_stable)

Solution (Python):
length = int(input())
eles = [l for l in input().split()]
is_stable = 'Stable'

_copy = eles[::]

for i in range(length):
    for j in range(length-1, 0, -1):
        if _copy[j][1] < _copy[j-1][1]:
            _copy[j], _copy[j-1] = _copy[j-1], _copy[j]

print(*_copy)
print(is_stable)

__copy = eles[::]
for i in range(length-1):
    _min = i
    for l in range(i, length):
        if __copy[l][1] < __copy[_min][1]:
            _min = l
    if __copy[i][1] > __copy[_min][1]:
        __copy[i], __copy[_min] = __copy[_min], __copy[i]

print(*__copy)

for i in range(length -1):
    if _copy[i] != __copy[i]:
        is_stable = 'Not stable'

print(is_stable)

Solution (Python):
class card:

    def __init__(self,cv):
        c = cv[0:1]
        v = int(cv[1:2])
        self.c = c
        self.v = v
    

    def self_str(self):
        q = str(str(self.c) + str(self.v))
        return q


n = int(input())
a = list(map(card, input().split()))


b = a[:]
c = a[:]

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

print(" ".join(x.self_str() for x in b))

coua = ["" for i in range(10)]
coub = ["" for i in range(10)]
conb = ""
for i in range(n):
    for j in range(n):
        if i != j:
            if a[i].v == a[j].v:
                coua[a[i].v] += a[i].c
            if b[i].v == b[j].v:
                coub[b[i].v] += b[i].c
if coua == coub:
     conb = "Stable"
else:
    conb = "Not stable"
print(conb)





for i in range(n):
    mini = i
    for j in range(i, n):
        if c[j].v < c[mini].v:
            mini = j
    c[mini], c[i] = c[i], c[mini]

print(" ".join(x.self_str() for x in c))

couc = ["" for i in range(10)]
conc = ""
for i in range(n):
    for j in range(n):
        if i != j:
            if c[i].v == c[j].v:
                couc[c[i].v] += c[i].c
if coua == couc:
     conc = "Stable"
else:
    conc = "Not stable"

print(conc)

Solution (Python):

def BS(N,A):
    for i in range(N):
        for j in reversed(range(i+1,N)):
            if int(A[j][1:])<int(A[j-1][1:]):
                swap=A[j]
                A[j]=A[j-1]
                A[j-1]=swap
    return A

def SS(N,A):
    for i in range(N):
        minj=i
        for j in range(i,N):
            if int(A[j][1:]) < int(A[minj][1:]):
                minj=j
        
        swap=A[i]
        A[i]=A[minj]
        A[minj]=swap
    return A

def Stable(A1,A2):
    ans="Stable"
    for i in range(len(A1)):
        if A1[i][1:]==A2[i][1:] and A1[i][:1]!=A2[i][:1]:
            ans="Not stable"
    return ans

def SS2(N,A,B):
    A1=BS(N,A)
    print(" ".join(A1))
    print("Stable")
    A2=SS(N,B)
    print(" ".join(A2))
    print(Stable(A1,A2))

if __name__=="__main__":
    N=int(input())
    a=input()
    A=a.split(" ")
    B=a.split(" ")
    SS2(N,A,B)

Solution (Python):
def BubbleSort(a, n):
    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]
    return a


def SelectionSort(a, n):
    for i in range(n):
        mini = i
        for j in range(i, n):
            if int(a[j][1]) < int(a[mini][1]):
                mini = j
        a[i], a[mini] = a[mini], a[i]
    return a


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


b = a[:]
a = BubbleSort(a, n)
b = SelectionSort(b, n)


print(*a)
print("Stable")
print(*b)

if a == b:
    print("Stable")
else:
    print("Not stable")

Solution (Python):



import copy


class Solution:
    def stable_sort(self):
        
        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)

        
        if bubble_result == selection_result:
            print("Stable")
        else:
            print("Not stable")

    @staticmethod
    def selection_sort(s_array, array_length):
        
        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):
        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()

Solution (Python):



import copy


class Solution:
    def stable_sort(self):
        
        array_length = int(input())
        array = [str(x) for x in input().split()]
        array_2 = copy.deepcopy(array)

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

        
        if bubble_result == selection_result:
            print("Stable")
        else:
            print("Not stable")

    @staticmethod
    def selection_sort(array, array_length):
        
        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()

Solution (Python):



import copy


class Solution:
    def stable_sort(self):
        
        array_length = int(input())
        array = [str(x) for x in input().split()]
        array_2 = copy.deepcopy(array)

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

        
        if bubble_result == selection_result:
            print("Stable")
        else:
            print("Not stable")

    @staticmethod
    def selection_sort(array, array_length):
        
        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()

Solution (Python):


import re

def embedded_numbers(str):
	re_digits = re.compile(r'(\d+)')
	pieces = re_digits.split(str)
	pieces[1] = map(int, pieces[1])
	return pieces[1]

def selectionSort(Arry):
	for i in range(len(Arry)):
		minj = i
		for j in range(i,len(Arry)):
			if embedded_numbers(Arry[j]) < embedded_numbers(Arry[minj]):
				minj = j
		Arry[i],Arry[minj] = Arry[minj], Arry[i]

	return Arry

def bubbleSort(Arry):
	for i in range(len(Arry)):
		for j in range(len(Arry) - 1, i, -1):
			if embedded_numbers(Arry[j-1]) > embedded_numbers(Arry[j]):
				Arry[j-1], Arry[j] = Arry[j], Arry[j - 1]
	
	return Arry

def judge_satble(origin, sortedCards):
	if sorted(origin, key=embedded_numbers) == sortedCards:
		print "Stable"
	else:
		print "Not stable"

def main():
	
	N = int(raw_input())
	Cards = raw_input().split()
	s_cards = list(Cards)
	b_cards = list(Cards)
	
	bubble_sortedCards = bubbleSort(b_cards)
	print " ".join(bubble_sortedCards)
	judge_satble(Cards, bubble_sortedCards)

	select_sortedCards = selectionSort(s_cards)
	print " ".join(select_sortedCards)
	judge_satble(Cards, select_sortedCards)



	
		


	
if __name__ == '__main__':
	main()

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

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

Solution (Python):





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

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

Solution (Python):
def ssort(L, n):
    L = L[:]
    for i in range(n):
        minj = i
        for j in range(i, n):
            if L[j][1] < L[minj][1]:
                minj = j
        L[i], L[minj] = L[minj], L[i]
    return L

def bsort(L, n):
    L = L[:]
    for _ in L:
        for j in range(n-1, 0, -1):
            if L[j][1] < L[j-1][1]:
                L[j], L[j-1] = L[j-1], L[j]
    return L

def is_stable(L_in, L_out):
    in_pair_list= []
    out_pair_list= []
    for i, e1 in enumerate(L_in):
        for j, e2 in enumerate(L_in[i+1:]):
            if e1[1] == e2[1]:
                in_pair_list.append((e1, e2))
    for i, e1 in enumerate(L_out):
        for j, e2 in enumerate(L_out[i+1:]):
            if e1[1] == e2[1]:
                out_pair_list.append((e1, e2))
    return not bool(set(in_pair_list) - set(out_pair_list))

def print_stable(b):
    print('Stable' if b else 'Not stable')

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

b = bsort(L, n)
print(*b)
print_stable(is_stable(L, b))
s = ssort(L, n)
print(*s)
print_stable(is_stable(L, s))

Solution (Python):
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
    """
    x = []
    for data in numbers:
        x.append(data)

    counter = 0

    for i in range(0, n):
        min_j = i
        for j in range(i, n):
            if key(x[j]) < key(x[min_j]):
                min_j = j
        if min_j != i:
            x[min_j], x[i] = x[i], x[min_j]
            counter += 1
    return x, 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
    """
    x = []
    for data in numbers:
        x.append(data)

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