Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
class Card():
    def __init__(self, card):
        self.card = card
        self.mark = card[0]
        self.number = card[1]
        
    def __lt__(self, other):
        if not isinstance(other, Card):
            return NotImplemented
        return self.number < other.number
    
    def __eq__(self, other):
        if not isinstance(other, Card):
            return NotImplemented
        return self.mark == other.mark and self.number == other.number
        
    def __repr__(self):
        return '{}{}'.format(self.mark, self.number)


def BubbleSort(target):
    ls = target.copy()
    flag = 1
    while flag:
        flag = 0
        for i in range(len(ls)-1, 0, -1):
            if ls[i] < ls[i-1]:
                ls[i], ls[i-1] = ls[i-1], ls[i]
                flag = 1
    print(' '.join(map(str, ls)))
    return sorted(ls)


def SelectSort(target):
    ls = target.copy()
    for i in range(len(ls)):
        minj = i
        for j in range(i+1, len(ls)):
            if ls[j] < ls[minj]:
                minj = j
        if ls[i] != ls[minj]:
            ls[i], ls[minj] = ls[minj], ls[i]
    
    print(' '.join(map(str, ls)))
    return sorted(ls)

def judge(original, sorted_list):
    if original == sorted_list:
        print('Stable')
    else:
        print('Not stable')


_ = int(input())
l2 =  [Card(i) for i in input().split()]
l2_sort = sorted(l2)

bubble = BubbleSort(l2)
judge(l2_sort, bubble)

select = SelectSort(l2)
judge(l2_sort, select)



# Example run
# Input:
-1562
w(}A3%
# Output:
w(
Stable
w(
Stable
n = int(input())
*ls_a, = input().split()
ls_b = ls_a[:]
for i in range(n):
    for j in range(n-1, i, -1):
        if ls_a[j][1:] < ls_a[j-1][1:]:
            ls_a[j], ls_a[j-1] = ls_a[j-1], ls_a[j]

print(*ls_a)
print("Stable")

for i in range(n):
    minj = i
    for j in range(i, n):
        if ls_b[j][1:] < ls_b[minj][1:]:
            minj = j
    ls_b[i], ls_b[minj] = ls_b[minj], ls_b[i]
print(*ls_b)
if ls_a == ls_b:
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
0
B+]om;>PS
# Output:
B+]om;>PS
Stable
B+]om;>PS
Stable
def main(n):
	a = list(input().split())
	b = list(a)
	c = list(a)
	achk = [[] for _ in range(10)]
	bchk = [[] for _ in range(10)]
	cchk = [[] for _ in range(10)]
	for i in range(n):
		for j in range(n-1, i, -1):
			if int(b[j][1]) < int(b[j-1][1]):
				b[j], b[j-1] = b[j-1], b[j]
	print(" ".join(b))
	print("Stable")
	for i in range(n):
		minj = i
		for j in range(i, n):
			if int(c[j][1]) < int(c[minj][1]):
				minj = j
		c[i], c[minj] = c[minj], c[i]
	print(" ".join(c))
	if c == b:
		print("Stable")
	else:
		print("Not stable")

main(int(input()))


# Example run
# Input:
-20238871
+5I'S[L8#
# Output:
+5I'S[L8#
Stable
+5I'S[L8#
Stable
N = int(input())
cards = list(input().split())
cards_list = [list(i) for i in cards]

for i in range(N):
	for j in reversed(range(i+1,N)):
		if j<N:
			if int(cards_list[j][1])<int(cards_list[j-1][1]):
				cards_list[j],cards_list[j-1]=cards_list[j-1],cards_list[j]
cards_t =[0 for i in range(N)]
for i in range(N):
	cards_t[i] = "".join(cards_list[i])			
print(" ".join(cards_t))
print("Stable")

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

cards_t =[0 for i in range(N)]
for i in range(N):
	cards_t[i] = "".join(cards_list_1[i])			
print(" ".join(cards_t))
if cards_list == cards_list_1:
	print("Stable")
else:
	print("Not stable")


# Example run
# Input:
-20131
0SbB[
# Output:

Stable

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


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

C1 = cards.copy()
bubble_sort(C1, N)
print(" ".join(C1))
print("Stable")

C2 = cards.copy()
selection_sort(C2, N)
print(" ".join(C2))
if C1 == C2:
    print("Stable")
else:
    print("Not stable")



# Example run
# Input:
-6
Xn6xMFrWF
# Output:
Xn6xMFrWF
Stable
Xn6xMFrWF
Stable
import copy
n=int(input())
num=input().split()
numa=copy.copy(num)
numb=copy.copy(num)

#buble
for i in range(0,n):
	a=0
	for j in range(n-1,i,-1):
		if numa[j][1:]<numa[j-1][1:]:
			a=numa[j]
			numa[j]=numa[j-1]
			numa[j-1]=a
print(' '.join(list(map(str,numa))))
print('Stable')

#select
for i in range(0,n):
	minj=i
	b=0
	for j in range(i,n):
		if numb[j][1:]<numb[minj][1:]:
			minj=j
	b=numb[minj]
	numb[minj]=numb[i]
	numb[i]=b
print(' '.join(list(map(str,numb))))
if numb==numa:
	print('Stable')
else:
	print('Not stable')
		



# Example run
# Input:
-227348
ShXn6xMF
# Output:
ShXn6xMF
Stable
ShXn6xMF
Stable
def str_selection_sort(a,n):
    m=0
    for i in range(0,n):
        minj=i
        for j in range(i,n):
            if(int(a[minj][1:]) > int(a[j][1:])):
                minj=j
        if(minj!=i):
            m+=1
            a[minj],a[i] = a[i],a[minj]
        
    print(" ".join(a))
    return a

def str_bubble_sort(a,n):
    m=0
    flag=True
    while(flag):
        flag=False
        for i in range(n-1,0,-1):
            if(a[i-1][1:] > a[i][1:]):
                tmp=a[i-1]
                a[i-1]=a[i]
                m+=1
                a[i]=tmp
                flag=True
                
    print(" ".join(a))
    return a

def is_stable(a,b,n):
    for i in range(1,n):
        if(b[i-1][1:]!=b[i][1:]):
            continue
        flag=False
        for j in a:
            if(j[:1]==b[i-1][:1] and (not flag)):
                flag=True
                continue
            if(j[:1]==b[i][:1]):
                if(not flag):
                    return False
                else:
                    return True
        
        if(flag):
            return False
    return True

a=[]
n=int(input())
s=input()
a=s.split()
b=str_bubble_sort(list(a),n)
print("Stable")
c=str_selection_sort(list(a),n)
if(b==c):
    print("Stable")
else:
    print("Not stable")

# Example run
# Input:
-4
="X+-V^+?
# Output:
="X+-V^+?
Stable
="X+-V^+?
Stable
N = int(input())
A = list(map(str, input().split()))
l_1 = []
l_2 = []
ans = []

for cha in A:
    l_1.append([cha[:1], int(cha[1:])])
    l_2.append([cha[:1], int(cha[1:])])

def BubbleSort(C, N):
  for i in range(N):
    nums = []
    for j in range(i+1, N):
      nums.append(j)
    nums.sort(reverse=True)
    for num in nums:
      if C[num][1] < C[num-1][1]:
        C[num], C[num-1] = C[num-1], C[num]
    a = []
    for cha in C:
      a.append(''.join(map(str, cha)))
  ans.append(' '.join(map(str, a)))
  print(ans[0])
  print('Stable')
  
BubbleSort(l_1, N)

def SelectionSort(D, N):
  for i in range(N):
    index = i
    for j in range(i, N):
      if D[j][1] < D[index][1]:
        index = j
    D[i], D[index] = D[index], D[i]
  b = []
  for cha in D:
    b.append(''.join(map(str, cha)))
  ans.append(' '.join(map(str, b)))
  if ans[0] == ans[1]:
    print(ans[1])
    print('Stable')
  else:
    print(ans[1])
    print('Not stable')

SelectionSort(l_2, N)


# Example run
# Input:
1
377
# Output:
377
Stable
377
Stable
class Card:
    def __init__(self, card):
        self.value = int(card[1])
        self.card = card


def selectionSort(A, N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if A[j].value < A[minj].value:
                minj = j
        if minj != i:
            tmp = A[i]
            A[i] = A[minj]
            A[minj] = tmp

    return A


def bubbleSort(A, N):
    flag = 1
    while flag:
        flag = 0
        for j in range(N-1, 0, -1):
            if A[j].value < A[j-1].value:
                tmp = A[j]
                A[j] = A[j-1]
                A[j-1] = tmp
                flag = 1

    return A


def check_stable(A, cards):
    for num in range(1, 10):
        As = []
        Cs = []
        for a in A:
            if a.value == num:
                As.append(a.card)
        for c in cards:
            if c.value == num:
                Cs.append(c.card)

        if As != Cs:
            print("Not stable")
            return
    else:
        print("Stable")
        return


def main():
    N = int(input())
    cards = [Card(i) for i in input().split()]
    bubble_cards = bubbleSort(cards.copy(), N)
    selection_cards = selectionSort(cards.copy(), N)

    print(*[bc.card for bc in bubble_cards])
    check_stable(bubble_cards, cards)
    print(*[sc.card for sc in selection_cards])
    check_stable(selection_cards, cards)


if __name__ == "__main__":
    main()


# Example run
# Input:
0
374
# Output:
374
Stable
374
Stable
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]
    return C
 
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]
    return C
 
def check(C0, C1):
    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 C0[i][1] == C0[j][1] and C0[i] == C1[b] and C0[j] == C1[a]:
                        return False
    return True
 
def toStr(a):
    return str(a[0])+str(a[1])
 
N = int(input())
src = [(str(char[0]), int(char[1])) for char in input().split()]
 
out_1 = bubbleSort(src[:], N)
out_2 = selectionSort(src[:], N)
# &は2進数
# リストは参照渡し
for out in [out_1, out_2]:
    ans = map(toStr, out)
    print(*ans)
    if check(src, out):
        print('Stable')
    else:
        print('Not stable')


# Example run
# Input:
-54544899
-74270783
# Output:
-7
Stable
-7
Stable
class Card:
    def __init__(self, suit, value):
        self.suit = suit
        self.value = value
    
def selection(ls):
    for i in range(len(ls)):
        minj = i
        
        for j in range(i, len(ls)):
            if ls[j].value < ls[minj].value:
                minj = j
        ls[i], ls[minj] = ls[minj], ls[i]

def bubblesort(ls):
    for i in range(1, len(ls)):
        for j in reversed(range(i, len(ls))):
            if ls[j].value < ls[j-1].value:
                ls[j], ls[j-1] = ls[j-1], ls[j]

def isStable(ls1, ls2):
    if ls1 == ls2:
        print("Stable")
    else:
        print("Not stable")

def printcards(cards):
    for x in range(len(cards)):
        if x == len(cards) - 1:
            print(cards[x].suit + cards[x].value)
        else:
            print(cards[x].suit + cards[x].value, ' ', sep='', end='')

def main():
    N = int(input().rstrip())

    cards = []
    for card in list(input().split(' ')):
        cards.append(Card(card[0], card[1]))

    a = [x for x in cards]
    b = [x for x in cards]
    

    bubblesort(a)
    selection(b)
    
    printcards(a)
    print("Stable")

    printcards(b)
    isStable(a,b)
    
if __name__ == '__main__':
    main()

# Example run
# Input:
103303
8\G<E[
# Output:
8\
Stable
8\
Stable
n=int(input())
c=list(map(str, input().split()))

def bubble(c:list, n:int) -> str:
    if not isinstance(c, list):
        return None

    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 " ".join(c)

def selection(c:list, n:int) -> str:
    if not isinstance(c, list):
        return None

    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 " ".join(c)
d = c[:]
bub=bubble(c, n)
print(bub)
print("Stable")
sel=selection(d, n)
print(sel)
if sel == bub:
    print("Stable")
else :
    print("Not stable")


# Example run
# Input:
-64378103
^C{`
# Output:
^C{`
Stable
^C{`
Stable
N=int(input())
A=input().split()

B=A[:]
S=A[:]

def BubbleSort(A, N):
    count = 0
    flag = True
    while flag:
        flag = False
        for j in range(N-1, 0, -1):
            if A[j][1] < A[j-1][1]:
                A[j], A[j-1] = A[j-1], A[j]
                count += 1
                flag = True
                
    return A

def SelectionSort(A, N):
    count = 0
    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] 
        count += 1
    return A

b = BubbleSort(B, N)
s = SelectionSort(S, N)
print(*b)
print("Stable")
print(*s)

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

# Example run
# Input:
-172907376
p2<j
# Output:
p2<j
Stable
p2<j
Stable
def bubble_sort(arr):
    n = len(arr)
    flag = True
    i = 0
    while flag:
        flag = False
        for j in range(n - 1, 0, -1):
            if int(arr[j][1]) < int(arr[j - 1][1]):
                arr[j], arr[j - 1] = arr[j - 1], arr[j]
                flag = True
        i += 1
    return arr


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


def is_stable(arr, arr_sorted):
    print("Stable" if arr_sorted == sorted(arr, key=lambda x:int(x[1])) else "Not stable")


n = int(input())
arr = input().split()
arr_b = bubble_sort(arr[:])
arr_s = selection_sort(arr[:])

print(*arr_b)
is_stable(arr, arr_b)
print(*arr_s)
is_stable(arr, arr_s)



# Example run
# Input:
-241292
-2147483648
# Output:
-2147483648
Stable
-2147483648
Stable
N = int(input())
A = list(input().split())
B = A[:]

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]

print(*A, sep=' ')
print('Stable')

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

print(*B, sep=' ')
if A == B:
    print('Stable')
else:
    print('Not stable')


# Example run
# Input:
0
Y&J
# Output:
Y&J
Stable
Y&J
Stable
import copy

def bubbleSort(C, M, N):
    for i in range(N):
        for j in reversed(range(i+1, N)):
            if C[j] < C[j-1]:
                out1 = C[j]
                C[j] = C[j-1]
                C[j-1] = out1
                out2 = M[j]
                M[j] = M[j-1]
                M[j-1] = out2
    print(' '.join(M))
    print('Stable')
    return M
    
def selectionSort(C, M, N):
    m = copy.deepcopy(M)
    for i in range(N):
        minj = i
        for j in range(i, N):
            if C[j] < C[minj]:
                minj = j
        out3 = C[i]
        C[i] = C[minj]
        C[minj] = out3
        out4 = M[i]
        M[i] = M[minj]
        M[minj] = out4
    print(' '.join(M))
    return M
    
def isStable(inn, out):
    for a, b in zip(inn, out):
        if a == b: continue
        else : return 'Not stable'
    return 'Stable'
    
if __name__ == '__main__':
    num1 = []
    N = int(input()) #1行目のNを取得する
    M1 = list(input().split())
    for i in range(N):
        s = M1[i]
        num1.append(int(s[-1]))
    M2 = copy.deepcopy(M1)
    num2 = copy.deepcopy(num1)
    out1 = bubbleSort(num1, M1, N)
    out2 = selectionSort(num2, M2, N)
    print(isStable(out1, out2))


# Example run
# Input:
-1
[dhxe
# Output:
[dhxe
Stable
[dhxe
Stable
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')

# Example run
# Input:
-507526654
YQocc[TJS
# Output:
YQocc[TJS
Stable
YQocc[TJS
Stable
import copy


class Card:
    def __init__(self, pair):
        self.suit = pair[0]
        self.value = int(pair[1])

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


def bubble_sort(a, n):
    for i in range(0, n):
        for j in range(n-1, i, -1):
            if a[j].value < a[j-1].value:
                a[j], a[j-1] = a[j-1], a[j]


def selection_sort(a, n):
    for i in range(0, n):
        min_j = i
        for j in range(i, n):
            if a[j].value < a[min_j].value:
                min_j = j
        a[i], a[min_j] = a[min_j], a[i]


def equals(cards1, cards2):
    for card1, card2 in zip(cards1, cards2):
        if card1.suit != card2.suit:
            return False
    return True


def main():
    # input
    n = int(input())
    cards1 = list(map(Card, input().split(' ')))
    cards2 = copy.deepcopy(cards1)

    # sort
    bubble_sort(cards1, n)
    selection_sort(cards2, n)

    # output
    print(' '.join(map(str, cards1)))
    print('Stable')
    print(' '.join(map(str, cards2)))
    if equals(cards1, cards2):
        print('Stable')
    else:
        print('Not stable')


if __name__ == "__main__":
    main()



# Example run
# Input:
-84521052
-2
# Output:
-2
Stable
-2
Stable
import copy

class card:
    def __init__(self, s):
        self.value = int(s[1:])
        self.mark = s[0]
        self.s = s
    
    def __repr__(self):
        return self.s
        
def isstable(Cin, Cout, n):
    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 Cin[i].value==Cin[j].value and Cout[a].s==Cin[j].s and Cout[b].s == Cin[i].s:
                        return False
    return True
    
def BubbleSort(C, N):
    Cin = copy.copy(C)
    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]
    print(*C)

    if isstable(Cin, C, N):
        print('Stable')
    else:
        print('Not stable')

def SelectionSort(C,N):
    Cin = copy.copy(C)
    for i in range(N):
        minj = i
        for j in range(i, N):
            if C[j].value < C[minj].value:
                minj = j
        if minj!=i:
            C[i], C[minj] = C[minj], C[i]

    print(*C)
    if isstable(Cin, C, N):
        print('Stable')
    else:
        print('Not stable')

N = int(input())
C = list(map(card, input().split()))

#N = 5
#C = list(map(card, ['H4', 'C9', 'S4', 'D2', 'C3']))
BubbleSort(copy.copy(C), N)
SelectionSort(copy.copy(C), N)




# Example run
# Input:
-23909
-68
# Output:
-68
Stable
-68
Stable
def bubbleSort(A):
  global N
  for i in range(N):
    for j in  range(N-1,i,-1):
      jn = int(A[j][1:])
      jm =  int(A[j-1][1:])
      if jn < jm:
        x = A[j]
        A[j] = A[j-1]
        A[j-1] = x

def selectionSort(A):
  global N
  for i in range(N):
    minj = i
    for j in range(i,N):
      jn = int(A[j][1:])
      jm =  int(A[minj][1:])
      if jn < jm:
        minj = j
    if minj != i :
      x = A[minj]
      A[minj] = A[i]
      A[i] = x

def stableDict(A):
  S = dict()
  for e in A:
    i = e[1:]
    if i in S:
      S[i] = e + S[i]
    else:
      S[i] = e
  return S

def ckStable(org,dst):
  dictOrg = stableDict(org)
  dictDst = stableDict(dst)
  stableFlg = True
  for a in dictOrg.keys():
    if dictOrg[a] != dictDst[a]:
      stableFlg = False
  if stableFlg :
    print("Stable")
  else:
    print("Not stable")

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

A1 = list(A)
A2 = list(A)

bubbleSort(A1)
print(" ".join(A1))
ckStable(A,A1)
  
selectionSort(A2)
print(" ".join(A2))
ckStable(A,A2)


# Example run
# Input:
-35795037
[y[[Kd
# Output:
[y[[Kd
Stable
[y[[Kd
Stable
import copy

def bubble_sort(array):
    N = len(array)
    unsorted_num_exist = True
    for i in range(N):
        unsorted_num_exist = False
        for j in reversed(range(i, N - 1)):
            if array[j][1] > array[j + 1][1]:
                unsorted_num_exist = True
                array[j], array[j + 1] = array[j + 1], array[j]
        if not unsorted_num_exist:
            break

def selection_sort(array):
    N = len(array)
    for i in range(N):
        min_index = i
        for j in range(i, N):
            if array[j][1] < array[min_index][1]:
                min_index = j
        array[i], array[min_index] = array[min_index], array[i]
 

def putsarray(array):
    for i in range(len(array) - 1):
        print(array[i][0] + str(array[i][1]), end=' ')
    print(array[-1][0] + str(array[-1][1]))

def check_stable(origin, sorted):
    dict_origin = {}
    for e in origin:
        num = e[1]
        if num in dict_origin.keys():
            dict_origin[num].append(e[0])
        else:
            dict_origin[num] = [e[0]]
    dict_sorted = {}
    for e in sorted:
        num = e[1]
        if num in dict_sorted.keys():
            dict_sorted[num].append(e[0])
        else:
            dict_sorted[num] = [e[0]]
    
    return all(dict_origin[key] == dict_sorted[key] for key in dict_origin.keys())

if __name__ == "__main__":
    N = int(input())
    array = input().split()
    array = [[s[0], int(s[1])] for s in array]
    array2 = copy.deepcopy(array)
    array3 = copy.deepcopy(array)
    bubble_sort(array2)
    putsarray(array2)
    print("Stable" if check_stable(array, array2) else "Not stable")
    selection_sort(array3)
    putsarray(array3)
    print("Stable" if check_stable(array, array3) else "Not stable")


# Example run
# Input:
2
3579
# Output:
35
Stable
35
Stable