Problem:


Quick Sort

Let's arrange a deck of cards. Your task is to sort totally n cards. A card consists of a part of a suit (S, H, C or D) and an number. Write a program which sorts such cards based on the following pseudocode:

Partition(A, p, r)
1 x = A[r]
2 i = p-1
3 for j = p to r-1
4     do if A[j] n, the number of cards.

n cards are given in the following lines. Each card is given in a line and represented by a pair of a character and an integer separated by a single space.

Output

In the first line, print the stability ("Stable" or "Not stable") of this output.

In the following lines, print the arranged cards in the same manner of that of the input.

Constraints

1 ≤ n ≤ 100,000

1 ≤ the number of a card  ≤ 109

There are no identical card in the input

Sample Input 1

6
D 3
H 2
D 1
S 3
D 2
C 1

Sample Output 1

Not stable
D 1
C 1
D 2
H 2
D 3
S 3

Sample Input 2

2
S 1
H 1

Sample Output 2

Stable
S 1
H 1



Sample input:
6
D 3
H 2
D 1
S 3
D 2
C 1


Sample output:
Not stable
D 1
C 1
D 2
H 2
D 3
S 3

Submission status: Wrong Answer

Solution code:
def partition(hoge, p, r):
    x = int(hoge[r-1][1])
    i = p-1
    for j in range(p, r):
        if int(hoge[j][1]) <= x:
            i += 1
            tmp = hoge[i]
            hoge[i] = hoge[j]
            hoge[j] = tmp
    return i
    
def qSort(hoge, p, r):
    if p < r:
        q = partition(hoge, p, r)
        qSort(hoge, p, q-1)
        qSort(hoge, q+1, r)
    
def isStable(input_array, output_array):
    N = len(input_array)
    for i in range(1, N-1):
        for j in range(i+1, N):
            for a in range(1, N-1):
                for b in range(a+1, N):
                    if input_array[i][1] == output_array[j][1] and input_array[i] == output_array[b] and input_array[j] == output_array[a]:
                        return 'Not stable'
    return 'Stable'
    
if __name__ == '__main__':
    num = int(input())
    hoge = list()
    for _ in range(num):
        c, s = input().split()
        hoge.append(c+s)
    origin = hoge[:]
    qSort(hoge, 0, len(hoge))
    print(isStable(origin, hoge))
    print('\n'.join(['{0[0]} {0[1]}'.format(x) for x in hoge]))

Submission status: Wrong Answer

Solution code:
def partition(hoge, p, r):
    x = int(hoge[r-1][1])
    i = p-1
    for j in range(p, r):
        if int(hoge[j][1]) <= x:
            i += 1
            tmp = hoge[i]
            hoge[i] = hoge[j]
            hoge[j] = tmp
    return i+1
    
def qSort(hoge, p, r):
    #print(p, r)
    #print(' '.join(['{0[0]}: {0[1]}'.format(x) for x in hoge]))
    if p < r:
        q = partition(hoge, p, r)
        qSort(hoge, p, q-1)
        qSort(hoge, q+1, r)
    
def isStable(input_array, output_array):
    N = len(input_array)
    for i in range(1, N-1):
        for j in range(i+1, N):
            for a in range(1, N-1):
                for b in range(a+1, N):
                    if input_array[i][1] == output_array[j][1] and input_array[i] == output_array[b] and input_array[j] == output_array[a]:
                        return 'Not stable'
    return 'Stable'
    
if __name__ == '__main__':
    num = int(input())
    hoge = list()
    for _ in range(num):
        c, s = input().split()
        hoge.append((c,s))
    origin = hoge[:]
    qSort(hoge, 0, len(hoge))
    print(isStable(origin, hoge))
    print('\n'.join(['{0[0]} {0[1]}'.format(x) for x in hoge]))

Submission status: Wrong Answer

Solution code:
def partition(hoge, p, r):
    x = int(hoge[r][1])
    i = p-1
    for j in range(p, r):
        if int(hoge[j][1]) <= x:
            i += 1
            tmp = hoge[i]
            hoge[i] = hoge[j]
            hoge[j] = tmp
    tmp = hoge[i+1]
    hoge[i+1] = hoge[r]
    hoge[r] = tmp
    return i+1
    
def qSort(hoge, p, r):
    if p < r:
        q = partition(hoge, p, r)
        qSort(hoge, p, q-1)
        qSort(hoge, q+1, r)
    
def isStable(input_array, output_array):
    N = len(input_array)
    for i in range(1, N-1):
        for j in range(i+1, N):
            for a in range(1, N-1):
                for b in range(a+1, N):
                    if input_array[i][1] == output_array[j][1] and input_array[i] == output_array[b] and input_array[j] == output_array[a]:
                        return 'Not stable'
    return 'Stable'
    
if __name__ == '__main__':
    num = int(input())
    hoge = list()
    for _ in range(num):
        c, s = input().split()
        hoge.append((c,s))
    origin = hoge[:]
    qSort(hoge, 0, len(hoge)-1)
    print(isStable(origin, hoge))
    print('\n'.join(['{0[0]} {0[1]}'.format(x) for x in hoge]))

Submission status: Wrong Answer

Solution code:
# Quick Sort #
def partition(A, p, r):
    x = A[r][1]
    i = p-1
    for k in range(p, r):
        if A[k][1] <= x:
            i += 1
            A[i], A[k] = A[k], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

def quick_sort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quick_sort(A, p, q-1)
        quick_sort(A, q+1, r)

def is_stable(_in, out):
    n = len(_in)
    for i in range(n-1):
        for k in range(i+1, n):
            for a in range(n-1):
                for b in range(a+1, n):
                    if _in[i][1] == out[k][1] and _in[i] == out[b] and _in[k] == out[a]:
                        return False
    return True

n = int(input())
a = []
for i in range(n):
    mrk, num = input().split()
    num = int(num)
    a.append((mrk, num))
b = a[:]
quick_sort(b, 0, n-1)
if is_stable(a, b):
    print("Stable")
else:
    print("Not stable")
for i in b:
    print(*i)

Submission status: Wrong Answer

Solution code:
# Quick Sort #
def partition(A, p, r):
    x = A[r][1]
    i = p-1
    for k in range(p, r):
        if A[k][1] <= x:
            i += 1
            A[i], A[k] = A[k], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

def quick_sort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quick_sort(A, p, q-1)
        quick_sort(A, q+1, r)

def bubble_sort(c, n):
    x = c[:]
    for i in range(n):
        for k in range(n-1, i, -1):
            if x[k][1] < x[k-1][1]:
                x[k], x[k-1] = x[k-1], x[k]
    return x

def is_stable(_in, out):
    n = len(_in)
    for i in range(n):
        for k in range(i+1, n):
            for a in range(n):
                for b in range(a+1, n):
                    if _in[i][1] == _in[k][1] and _in[i] == out[b] and _in[k] == out[a]:
                        return False
    return True
n = int(input())
a = []
for i in range(n):
    mrk, num = input().split()
    num = int(num)
    a.append((mrk, num))
b = a[:]
quick_sort(b, 0, n-1)
c = bubble_sort(a[:], n)
if b == c:
    print("Stable")
else:
    print("Not Stable")
for i in b:
    print(*i)

Submission status: Wrong Answer

Solution code:
def partition(A, left, right):
    p = left
    r = right
    x = A[r][1]
    i = p - 1
    for j in range(p, r):
        if A[j][1] <= x:
            i += 1
            key = A[i]
            A[i] = A[j]
            A[j] = key
    key = A[i + 1]
    A[i + 1] = A[r]
    A[r] = key
    if i + 1 - left <= 1:
        if right - (i + 1) == 1:
            return i + 1, A[left:right + 1]
        else:
            return i + 1, A[left:i + 2]
    else:
        return i + 1, A[i + 1:i + 2]

def quickSort(A, left, right):
    list = []
    if left < right:
        Q = partition(A, left, right)
        q = Q[0]
        list.extend(quickSort(A, left, q - 1))
        list.extend(Q[1])
        list.extend(quickSort(A, q + 1, right))
    return list

def bubleSort(a):
    for i in range(len(a)):
        for j in range(len(a)-1, i, -1):
            if a[j][1] < a[j-1][1]:
                a[j], a[j-1] = a[j-1], a[j]

    return a

n = int(input())
T = [('0', 0)]
for i in range(n):
    a, b = map(str, input().split())
    x = int(b)
    T.append((a, x))
T1 = T[1:]
T2 = quickSort(T, 1, n)

if T2 == bubleSort(T1):
    print('Stable')
else:
    print('Not Stable')

for i in range(n):
    a = str(T2[1])
    print(T2[i][0] + ' ' + str((T2[i][1])))

Submission status: Wrong Answer

Solution code:
import copy

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

def partition(A, p, r):
    x = num_from_card(A[r])
    i = p-1
    for j in range(p, r):
        if num_from_card(A[j]) <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

def quick_sort(A_i, p, r):
    A = copy.copy(A_i)
    if p < r:
        q = partition(A, p, r)
        quick_sort(A, p, q-1)
        quick_sort(A, q+1, r)
    return A

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

n = int(input())
cards = [input() for i in range(n)]

sorted_cards = quick_sort(cards, 0, n-1)
print(is_stable(cards, sorted_cards, n))
for c in sorted_cards:
    print(c)

Submission status: Wrong Answer

Solution code:
import copy

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

def partition(A, p, r):
    x = num_from_card(A[r])
    i = p-1
    for j in range(p, r):
        if num_from_card(A[j]) <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

def quick_sort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quick_sort(A, p, q-1)
        quick_sort(A, q+1, r)

def merge(A, left, mid, right):
    L = A[left: mid]
    R = A[mid: right]
    L.append('  ' + str(int(10e9 + 1)))
    R.append('  ' + str(int(10e9 + 1)))
    i, j = 0, 0
    for k in range(left, right):
        if num_from_card(L[i]) <= num_from_card(R[j]):
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def merge_sort(A, left, right):
    if left + 1 < right:
        mid = int((left + right)/2)
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)

n = int(input())
cards = [input() for i in range(n)]
merge_cards = copy.copy(cards)

quick_sort(cards, 0, n-1)
merge_sort(merge_cards, 0, n-1)

if merge_cards == cards:
    print('Stable')
else:
    print('Not stable')

for c in cards:
    print(c)

Submission status: Wrong Answer

Solution code:
class Num:
    a=0
    b=0
    origin=0

def partition(A, p, r):
    x=A[r].b
    i=p-1
    for j in range(p,r):
        if A[j].b <= x:
            i += 1
            A[i].b,A[j].b = A[j].b,A[i].b
            A[i].a,A[j].a = A[j].a,A[i].a
    A[i+1].b,A[r].b = A[r].b,A[i+1].b
    A[i+1].a,A[r].a = A[r].a,A[i+1].a
    return i+1
def quick_sort(A , p, r):
    if p < r:
        q = partition(A,p,r)
        quick_sort(A, p, q-1)
        quick_sort(A, q+1, r)
def isStable(A):
    n=len(A)
    for i in range(n-1):
        if A[i].b == A[i+1].b and A[i].origin < A[i+1].origin:
            return False
    return True

if __name__ == "__main__":
    
    n=int(input())
    A=[]
    for i in range(n):
        num =Num()
        a=input().split()
        num.a = a[0]
        num.b = int(a[1])
        num.origin=i
        A.append(num)
    quick_sort(A,0,n-1)
    for i in A:
        print("a={},b={},origin={}".format(i.a,i.b,i.origin))
    if isStable(A):
        print("Stable")
    else:
        print("Not stable")
    for i in A:
        print(i.a,end=" ")
        print(i.b)

Submission status: Wrong Answer

Solution code:
class Num:
    a=0
    b=0
    origin=0

def partition(A, p, r):
    x=A[r].b
    i=p-1
    for j in range(p,r):
        if A[j].b <= x:
            i += 1
            A[i].b,A[j].b = A[j].b,A[i].b
            A[i].a,A[j].a = A[j].a,A[i].a
    A[i+1].b,A[r].b = A[r].b,A[i+1].b
    A[i+1].a,A[r].a = A[r].a,A[i+1].a
    return i+1
def quick_sort(A , p, r):
    if p < r:
        q = partition(A,p,r)
        quick_sort(A, p, q-1)
        quick_sort(A, q+1, r)
def isStable(A):
    n=len(A)
    for i in range(n-1):
        if A[i].b == A[i+1].b and A[i].origin < A[i+1].origin:
            return False
    return True

if __name__ == "__main__":
    
    n=int(input())
    A=[]
    for i in range(n):
        num =Num()
        a=input().split()
        num.a = a[0]
        num.b = int(a[1])
        num.origin=i
        A.append(num)
    quick_sort(A,0,n-1)
    if isStable(A):
        print("Stable")
    else:
        print("Not stable")
    for i in A:
        print(i.a,end=" ")
        print(i.b)

Submission status: Wrong Answer

Solution code:
class Num:
    a=0
    b=0
    origin=0

def partition(A, p, r):
    x=A[r].b
    i=p-1
    for j in range(p,r):
        if A[j].b <= x:
            i += 1
            A[i].b,A[j].b = A[j].b,A[i].b
            A[i].a,A[j].a = A[j].a,A[i].a
    A[i+1].b,A[r].b = A[r].b,A[i+1].b
    A[i+1].a,A[r].a = A[r].a,A[i+1].a
    return i+1
def quick_sort(A , p, r):
    if p < r:
        q = partition(A,p,r)
        quick_sort(A, p, q-1)
        quick_sort(A, q+1, r)
def isStable(A):
    n=len(A)
    for i in range(n-1):
        if A[i].b == A[i+1].b and A[i].origin > A[i+1].origin:
            return False
    return True

if __name__ == "__main__":
    
    n=int(input())
    A=[]
    for i in range(n):
        num =Num()
        a=input().split()
        num.a = a[0]
        num.b = int(a[1])
        num.origin=i
        A.append(num)
    quick_sort(A,0,n-1)
    if isStable(A):
        print("Stable")
    else:
        print("Not stable")
    for i in A:
        print(i.a,end=" ")
        print(i.b)

Submission status: Wrong Answer

Solution code:
def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L, R = A[left: left + n1], A[mid: mid + n2]

    L.append([0,2000000000])
    R.append([0,2000000000])

    i, j = 0, 0
    for k in range(left, right):
        #print("k", k, "l", left, "m", mid, "r", right, "L", L, "R", R)
        if L[i][1] <= R[j][1]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1


def mergeSort(A, left, right):
    #print("l", left, "r", right)
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)


def partition(A, p, r):
    x = A[r][1]
    i = p - 1

    for j in range(p, r):
        if A[j][1] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]

    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1


def quick_sort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quick_sort(A, p, q - 1)
        quick_sort(A, q + 1, r)


n = int(input())
cards = []
merge_cards = []
for _ in range(n):
    tmp = input().split(' ')
    cards.append([tmp[0], int(tmp[1])])
    merge_cards.append([tmp[0], int(tmp[1])])

mergeSort(merge_cards, 0, n)

quick_sort(cards, 0, n - 1)

if merge_cards == cards:
    print("Stable")
else:
    print("Not Stable")

for card in cards:
    print(*card)

Submission status: Wrong Answer

Solution code:
def partition(num_list, start, end):
    split = start -1
    end -= 1
    x = num_list[end][1]
    for i in range(start, end):
        if num_list[i][1] <= x:
            split += 1
            num_list[split], num_list[i] = num_list[i], num_list[split]
    num_list[split+1], num_list[end] = num_list[end], num_list[split+1]
    num_list = [str(i) for i in num_list]
    return split+1

def quickSort(num_list, start, end):
    if start < end:
        q = partition(num_list, start, end)
        quickSort(num_list, start, q-1)
        quickSort(num_list, q+1, end)

import sys, copy
n = int(input())
input_list = [i.rstrip().split() for i in sys.stdin.readlines()]
check_list = copy.deepcopy(input_list)
quickSort(input_list, 0, n)
for i in range(n-1):
    if input_list[i][1] == input_list[i+1][1]:
        if check_list.index(input_list[i]) > check_list.index(input_list[i+1]):
            print('Not Stable')
            break
else:
    print('Stable')
for i in input_list:
    print('{} {}'.format(i[0], i[1]))

Submission status: Wrong Answer

Solution code:
def partition(num_list, start, end):
    split = start -1
    end -= 1
    x = num_list[end][1]
    for i in range(start, end):
        if num_list[i][1] <= x:
            split += 1
            num_list[split], num_list[i] = num_list[i], num_list[split]
    num_list[split+1], num_list[end] = num_list[end], num_list[split+1]
    num_list = [str(i) for i in num_list]
    return split+1

def quickSort(num_list, start, end):
    if start < end:
        q = partition(num_list, start, end)
        quickSort(num_list, start, q-1)
        quickSort(num_list, q+1, end)

import sys, copy
n = int(input())
input_list = [sys.stdin.readline().rstrip().split() for i in range(n)]
check_list = copy.deepcopy(input_list)
quickSort(input_list, 0, n)
for i in range(n-1):
    if input_list[i][1] == input_list[i+1][1]:
        if check_list.index(input_list[i]) > check_list.index(input_list[i+1]):
            print('Not Stable')
            break
else:
    print('Stable')
for i in input_list:
    print('{} {}'.format(i[0], i[1]))

Submission status: Wrong Answer

Solution code:
def partition(num_list, start, end):
    split = start -1
    end -= 1
    x = num_list[end][1]
    for i in range(start, end):
        if num_list[i][1] <= x:
            split += 1
            num_list[split], num_list[i] = num_list[i], num_list[split]
    num_list[split+1], num_list[end] = num_list[end], num_list[split+1]
    num_list = [str(i) for i in num_list]
    return split+1

def quickSort(num_list, start, end):
    if start < end:
        q = partition(num_list, start, end)
        quickSort(num_list, start, q-1)
        quickSort(num_list, q+1, end)

import sys, copy
n = int(input())
input_list = [sys.stdin.readline().rstrip().split() for i in range(n)]
check_list = copy.deepcopy(input_list)
quickSort(input_list, 0, n)
for i in range(n-1):
    if input_list[i][1] == input_list[i+1][1]:
        if check_list.index(input_list[i]) > check_list.index(input_list[i+1]):
            print('Not stable')
            break
else:
    print('Stable')
for i in input_list:
    print('{} {}'.format(i[0], i[1]))

Submission status: Wrong Answer

Solution code:
#coding:utf-8
from copy import deepcopy
n = int(input())
A = []
for i in range(n):
    ch, num = input().split()
    A.append([ch, int(num)])

B = deepcopy(A)



def Merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    L.append(["S",20000000])
    R.append(["S",20000000])
    i,j = 0,0
    for k in range(left,right):
        if L[i][1] <= R[j][1]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def MergeSort(A, left, right):
    if left+1 < right:
        mid = (left + right)//2
        MergeSort(A, left, mid)
        MergeSort(A, mid, right)
        Merge(A, left, mid, right)

    

def partition(A, p, r):
    x = A[r-1][1]
    i = p-1
    for j in range(p, r):
        if A[j][1] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    return i


def quickSort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quickSort(A, p, q)
        quickSort(A, q+1, r)




        
quickSort(A, 0, n)
MergeSort(B, 0, n)

if A == B:
    print("stable")
else:
    print("Not stable")
    
for a in A:
    a = " ".join([a[0],str(a[1])])
    print(a)

Submission status: Wrong Answer

Solution code:
def quicksort(A, p, r):
    if p < r:
        q = patation(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)

def patation(A, p, r):
    x = int(A[r][1])
    i = p - 1
    for j in range(p, r):
        if int(A[j][1]) <= x:
            i += 1
            tmp = A[i]; A[i] = A[j]; A[j] = tmp
            if int(A[j][1]) == x:
                global stable; stable = False

    tmp = A[i+1]; A[i+1] = A[r]; A[r] = tmp
    return i+1

def print_list(A):
    if stable == False:
        print("Not stable")
    else:
        print("Stable")

    for line in A:
        print(line[0], line[1])

A = []
n = int(input())
for i in range(n):
    A.append(input().split())
p = 0; r = n - 1
quicksort(A, p, r)
print_list(A)

Submission status: Wrong Answer

Solution code:
def quicksort(A, p, r):
    if p < r:
        q = patation(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)

def patation(A, p, r):
    x = int(A[r][1])
    i = p - 1
    for j in range(p, r):
        if int(A[j][1]) <= x:
            i += 1
            tmp = A[i]; A[i] = A[j]; A[j] = tmp
            if int(A[j][1]) == x and i != j:
                global stable; stable = False

    tmp = A[i+1]; A[i+1] = A[r]; A[r] = tmp
    return i+1

def print_list(A):
    if stable == False:
        print("Not stable")
    else:
        print("Stable")

    for line in A:
        print(line[0], line[1])

A = []
n = int(input())
for i in range(n):
    A.append(input().split())
p = 0; r = n - 1
stable = True
quicksort(A, p, r)
print_list(A)

Submission status: Wrong Answer

Solution code:
def main() :
    n = int(input())
    cards = [Card(*input().split()) for i in range(n)]
    stableCards = sorted(cards[:], key=lambda c: (c.number, c.prefix))
    quickSort(cards, 0, n - 1)
    print(isStable(cards, stableCards, n))
    list(map(lambda i : i.print_card(), cards))

def quickSort(cards, p, r) :
    if p < r:
        q = partion(cards, p, r)
        quickSort(cards, p, q - 1)
        quickSort(cards, q + 1, r)

def partion(cards, p, r) :
    x = cards[r]
    i = p
    for j in range(p, r + 1) :
        if cards[j].number <= x.number :
            cards[i], cards[j] = cards[j], cards[i]
            i += 1
    return i - 1

def isStable(a, b, n):
    for i in range(n):
        if a[i].prefix != b[i].prefix:
            return 'Not stable'

    return 'Stable'

class Card():
    def __init__(self, prefix, number):
        self.prefix = prefix
        self.number = number

    def print_card(self):
        print(self.prefix, self.number)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main() :
    n = int(input())
    cards = [Card(*input().split()) for i in range(n)]
    stableCards = sorted(cards[:], key=lambda c: c.number)
    quickSort(cards, 0, n - 1)
    print(isStable(cards, stableCards, n))
    list(map(lambda i : i.print_card(), cards))

def quickSort(cards, p, r) :
    if p < r:
        q = partion(cards, p, r)
        quickSort(cards, p, q - 1)
        quickSort(cards, q + 1, r)

def partion(cards, p, r) :
    x = cards[r]
    i = p
    for j in range(p, r + 1) :
        if cards[j].number <= x.number :
            cards[i], cards[j] = cards[j], cards[i]
            i += 1
    return i - 1

def isStable(a, b, n):
    for i in range(n):
        if a[i].prefix != b[i].prefix:
            return 'Not stable'

    return 'Stable'

class Card():
    def __init__(self, prefix, number):
        self.prefix = prefix
        self.number = number

    def print_card(self):
        print(self.prefix, self.number)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def partition(A, p, r):
    x = A[r]/10
    i = p-1
    for j in range(p, r):
        if A[j]/10 <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    i += 1
    A[i], A[r] = A[r], A[i]
    return i

def quicksort(A, p, r):
    if p<r:
        q = partition(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)
    return

def order(A):
    x = [0 for i in range(len(A))]
    xp = 0
    for i in range(9):
        for e in A:
            if e/10 == i:
                x[xp] = e
                xp += 1
    return x

n = int(input())
x = [[] for i in range(n)]
for i in range(n):
    a, b = raw_input().split()
    x[i] = int(b)*10 + 'SHDC'.index(a)

x1 = x + []
quicksort(x1, 0, n-1)
if order(x) == order(x1):
    print 'Stable'
else:
    print 'Not stable'
for e in x1:
    print 'SHDC'[e % 10], e/10

Submission status: Wrong Answer

Solution code:
def partition(A, p, r):
    x = A[r]/10
    i = p-1
    for j in range(p, r):
        if A[j]/10 <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    i += 1
    A[i], A[r] = A[r], A[i]
    return i

def quicksort(A, p, r):
    if p<r:
        q = partition(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)
    return

def suits(A):
    x = [0 for i in range(len(A))]
    xp = 0
    for i, e in enumerate(A):
        x[xp] = e % 10
        xp += 1
    return x

n = int(input())
x = [[] for i in range(n)]
for i in range(n):
    a, b = raw_input().split()
    x[i] = int(b)*10 + 'SHDC'.index(a)

x1 = x + []
quicksort(x1, 0, n-1)
if suits(x) == suits(x1):
    print 'Stable'
else:
    print 'Not stable'
for e in x1:
    print 'SHDC'[e % 10], e/10

Submission status: Wrong Answer

Solution code:
def partition(A, p, r):
    x = A[r]/10
    i = p-1
    for j in range(p, r):
        if A[j]/10 <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    i += 1
    A[i], A[r] = A[r], A[i]
    print A,i,r
    return i

def quicksort(A, p, r):
    if p<r:
        q = partition(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)
    return

def bubblesort(A):
    for i in range(len(A)):
        for j in range(i+1,len(A))[::-1]:
            if A[j] < A[j-1]:
                A[j],A[j-1] = A[j-1], A[j]
    return

n = int(input())
x = [[] for i in range(n)]
for i in range(n):
    a, b = raw_input().split()
    x[i] = int(b)*10 + 'SHDC'.index(a)

x1 = x + []
quicksort(x1, 0, n-1)
x2 = x + []
bubblesort(x2)

if x1 == x2:
    print 'Stable'
else:
    print 'Not stable'
for e in x1:
    print 'SHDC'[e % 10], e/10

Submission status: Wrong Answer

Solution code:
def partition(A, p, r):
    x = A[r]/10
    i = p-1
    for j in range(p, r):
        if A[j]/10 <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    i += 1
    A[i], A[r] = A[r], A[i]
    return i

def quicksort(A, p, r):
    if p<r:
        q = partition(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)
    return

def bubblesort(A):
    for i in range(len(A)):
        for j in range(i+1,len(A))[::-1]:
            if A[j] < A[j-1]:
                A[j],A[j-1] = A[j-1], A[j]
    return

n = int(input())
x = [[] for i in range(n)]
for i in range(n):
    a, b = raw_input().split()
    x[i] = int(b)*10 + 'SHDC'.index(a)

x1 = x + []
quicksort(x1, 0, n-1)
x2 = x + []
bubblesort(x2)

if x1 == x2:
    print 'Stable'
else:
    print 'Not stable'
for e in x1:
    print 'SHDC'[e % 10], e/10

Submission status: Wrong Answer

Solution code:
def partition(A, p, r):
    x = A[r]
    i = p-1
    for j in range(p, r):
        if A[j][0] <= x[0]:
            i += 1
            A[i], A[j] = A[j], A[i]
    i += 1
    A[i], A[r] = A[r], A[i]
    return i

def quicksort(A, p, r):
    if p<r:
        q = partition(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)
    return

def order(A):
    return sorted(A, key = lambda e: e[0])

n = int(input())
x = [[] for i in range(n)]
for i in range(n):
    a, b = raw_input().split()
    x[i] = (int(b), 'SHDC'.index(a))

x1 = x + []
quicksort(x1, 0, n-1)
x2 = x + []
order(x2)
if x1 == x2:
    print 'Stable'
else:
    print 'Not stable'
for e in x1:
    print 'SHDC'[e[1]], e[0]

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def patition(a, p, r):
    x = a[r][0]
    i = p - 1
    for j in range(p, r):
        if a[j][0] <= x:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i+1], a[r] = a[r], a[i+1]
    return i + 1


def quick_sort(a, p, r):
    if p < r:
        q = patition(a, p, r)
        quick_sort(a, p, q-1)
        quick_sort(a, q+1, r)


n = int(stdin.readline())
data = []
s = set()
for i in range(n):
    c, num = stdin.readline().split()
    data.append((int(num), c))
    s.add(int(num))
output = data[:]
quick_sort(output, 0, n-1)
for i in s:
    if [d for d in data if d[0] == i] != [d for d in output if d[0] == i]:
        print('Not stable')
        break
else:
    print('Stable')
for num, c in data:
    print(c, num)

Submission status: Time Limit Exceeded

Solution code:
a = []
n = int(input())
for _ in range(n):
    s, i = input().split()
    a += [(s, int(i))]
b = a[:]

def partition(a, left, right):
    standard = a[right][1]
    cnt = left
    for i in range(left, right+1):
        if i == right:
            if a[i][1] <= standard:
                a[i],a[cnt] = a[cnt], a[i] 
        elif a[i][1] <= standard:
            a[cnt],a[i] = a[i], a[cnt]
            cnt += 1
    return cnt

def quickSort(a, left = 0, right = len(a) - 1):
    if 1 <= right - left:
        cnt_ = partition(a, left, right)
        quickSort(a,left, cnt_ - 1)
        quickSort(a,cnt_ + 1, right)

quickSort(a, 0 , len(a)-1)

#bubble sort


for i in range(n-1):
    for j in range(n-1-i):
        if b[j][1] > b[j+1][1]:
            b[j], b[j+1] = b[j+1], b[j]
        

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

for i in range(n):
    print(*a[i])

Submission status: Time Limit Exceeded

Solution code:
import copy

def merge(A, left, mid, right):
    SENTINEL = 10 ** 9
    L = A[left:mid] + [Card('D', SENTINEL)]
    R = A[mid:right] + [Card('D', SENTINEL)]
    # print('L', L)
    # print('R', R)

    i = 0
    j = 0
    for k in range(left, right):
        # print(vars(L[i]))
        # print(vars(R[i]))
        if L[i].number <= R[j].number:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    # print('l', left, 'm', mid, 'r', right, A, count)

def merge_sort(A, left, right):
    # print('merge_sort', left, right)
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)
def partition(A, p, r):
    x = A[r].number
    i = p - 1
    for j in range(p, r):
        if A[j].number <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i + 1

class Card:
    def __init__(self, suit, number):
        self.suit = suit
        self.number = number

def quick_sort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quick_sort(A, p, q-1)
        quick_sort(A, q+1, r)

n = int(input())
A = []
for i in range(n):
    suit, number = input().split()
    A.append(Card(suit, int(number)))
# print(A)

merge_sorted_A = copy.deepcopy(A)

merge_sort(merge_sorted_A, 0, len(merge_sorted_A))
# print('merge_sort')
# for card in merge_sorted_A:
#     print(card.suit, card.number)

# print('quick_sort')
quick_sorted_A = copy.deepcopy(A)
quick_sort(quick_sorted_A, 0, len(quick_sorted_A)-1)

# for card in quick_sorted_A:
#     print(card.suit, card.number)

is_stable = True
for i in range(len(A)):
    if not (quick_sorted_A[i].suit == merge_sorted_A[i].suit):
        is_stable = False
        break

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

for card in quick_sorted_A:
    print(card.suit, card.number)