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: Accepted

Solution code:
# coding: utf-8
# Your code here!
import copy

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



def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = []
    R = []
    for i in range(n1):
        L.append(A[left + i])
    for i in range(n2):
        R.append(A[mid + i])
    L.append(Card("", 2000000000))
    R.append(Card("", 2000000000))
    
    i = 0
    j = 0
    
    for k in range(left, right):
        if L[i].value <= R[j].value:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def mergeSort(A, left, right):
    if left + 1 < right:
        mid = int((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].value
    i = p - 1
    for j in range(p, r - 1):
        if A[j].value <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r -1] = A[r -1], A[i + 1]
    return i + 1
        
        
def quickSort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quickSort(A, p, q)
        quickSort(A, q + 1, r)
    return
    
    

n = int(input())
A = []
for i in range(n):
    tmp = list(input().split())
    A.append(Card(tmp[0], int(tmp[1])))

B = copy.copy(A)
flg = True

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

for i in range(n):
    if A[i].suit != B[i].suit:
        flg = False
if flg:
    print("Stable")
else:
    print("Not stable")
        
for i in range(n):
    print(A[i].suit, A[i].value)

Submission status: Accepted

Solution code:
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 quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q - 1)
        quicksort(A, q + 1, r)


n, *D = open(0).read().split()
n = int(n)
A = [(D[2 * i], int(D[2 * i + 1]), i) for i in range(n)]
quicksort(A, 0, n - 1)
stable = True
for i in range(n-1):
    if A[i][1] == A[i + 1][1] and A[i][2] > A[i + 1][2]:
        stable = False
print('Stable' if stable else 'Not stable')
A = [(a[0], a[1]) for a in A]
print('\n'.join(map(lambda x: ' '.join(map(str, x)), A)))

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
MOD = 1000000007
EPS = 0.000000001
#sys.setrecursionlimit(3**12)


class TRAMP:
    def __init__(self,arg_mark,arg_number,arg_input_index):
        self.mark = arg_mark
        self.number = arg_number
        self.input_index = arg_input_index

N = int(input())
table = []
for input_index in range(N):
    mark,number = map(str,input().split())
    table.append(TRAMP(mark,int(number),input_index))

def Partition(left,right):
    global table
    i = left-1
    pivot = table[right].number
    for start in range(left,right):
        if table[start].number <= pivot:
            i += 1
            table[i],table[start] = table[start],table[i]
    table[i+1],table[right] = table[right],table[i+1]
    return i+1

def quickSort(left,right):
        if left < right:
            q = Partition(left,right)
            quickSort(left,q-1)
            quickSort(q+1,right)

quickSort(0, N-1)
stable_FLG = True

for i in range(1,N):
    if table[i].number == table[i-1].number and table[i].input_index < table[i-1].input_index:
        stable_FLG = False
        break

if stable_FLG:
    print("Stable")
else:
    print("Not stable")

for i in range(N):
    print("%s %d"%(table[i].mark,table[i].number))

Submission status: Accepted

Solution code:
import copy
import sys

def partition(A, p, r):
    key = A[r][1]
    i = p
    for j in range(p, r):
        # 把小的放在左边
        if A[j][1] <= key:
            A[i], A[j] = A[j], A[i]
            i += 1
    # 最后交换key值
    A[r], A[i] = A[i], A[r]
    return i

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] + [(0, sys.maxsize)]
    R = A[mid: right] + [(0, sys.maxsize)]
    i = j = 0
    k = left
    while k < right:
        if L[i][1] <= R[j][1]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        k += 1

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


if __name__ == '__main__':
    n = int(input())
    numlist = []
    for _ in range(n):
        datas = input().split(' ')
        numlist.append((datas[0], int(datas[1])))
    list2 = copy.deepcopy(numlist)
    quick_sort(numlist, 0, n - 1)
    merge_sort(list2, 0, n)
    if list2 == numlist:
        print('Stable')
    else:
        print('Not stable')
    for c, num in numlist:
        print('%s %d' % (c, num))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

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

    if p < r:
        q = Partition(aa, p, r)
        QuickSort(aa, p, q - 1)
        QuickSort(aa, q + 1, r)

def main():
    n = int(input())
    #aa = list(map(int, input().split()))
    cc=[]
    ctoi={}
    for i in range(n):
        m,a=input().split()
        c=(int(a),m)
        ctoi[c]=i
        cc.append(c)
    QuickSort(cc,0,n-1)
    stable=True
    for c0,c1 in zip(cc,cc[1:]):
        if c0[0]==c1[0] and ctoi[c0]>ctoi[c1]:
            stable=False
            break
    print("Stable") if stable else print("Not stable")
    for c in cc:
        print(c[1],c[0])

main()

Submission status: Accepted

Solution code:

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

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


""" merge_sort """

def merge(A, n, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]

    L.append(Card('None', 2000000000))  # これをしないとマージするとき、最後の１回でリスト外アクセスでエラー。
    R.append(Card('None', 2000000000))

    # global count
    i, j = 0, 0

    # print('left, mid, right')
    # print(left, mid, right)

    for k in range(left, right, 1):
        # count += 1
        # print('i, j, k')
        # print(i, j, k)

        if L[i].value <= R[j].value:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

        # print('loop end')


def merge_sort(A, n, left, right):
    if right - left > 1:
        mid = (left + right) // 2
        merge_sort(A, n, left, mid)
        merge_sort(A, n, mid, right)
        merge(A, n, left, mid, right)


""" quick_sort """

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

    for j in range(p, r):
        if A[j].value <= 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, n, p, r):
    if p < r:
        q = partition(A, n, p, r)
        quick_sort(A, n, p, q-1)
        quick_sort(A, n, q+1, r)


N = int(input())
A = []
for i in range(N):
    suit, value = input().split()
    value = int(value)
    A.append(Card(suit, value))
B = list(A)

quick_sort(A, N, 0, N-1)
merge_sort(B, N, 0, N)

stable = True
for i in range(N):
    if A[i] != B[i]:
        stable = False

if stable is True:
    print('Stable')
else:
    print('Not stable')

for a in A:
    print(a)

# for b in B:
#     print(b)

Submission status: Accepted

Solution code:
import copy


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


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


n=int(input())
data=[]
for i in range(n):
    mark,num=map(str,input().split())
    data.append([mark,int(num)])

data_copy=copy.deepcopy(data)
data_copy=sorted(data_copy, key=lambda x:x[1])

quickSort(data,0,n-1)

print("Stable" if data==data_copy else "Not stable")

for mark,num in data:print(mark,num)

Submission status: Accepted

Solution code:
import copy

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

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

 
n=int(input())
a=[]
for i in range(n):
    a.append(input().split())
    
b=copy.deepcopy(a)
quicksort(b,1,n)
flag=True
for j in range(n-1):
    if int(b[j][1]) == int(b[j+1][1]): 
        if a.index(b[j]) > a.index(b[j+1]):flag=False ;break
if flag:print('Stable')
else:print('Not stable')

for i in b:
    print(*i)

Submission status: Accepted

Solution code:
n = int(input())
cL = []
for i in range(n):
    inputS = input()
    inputL = inputS.split()
    cL.append([inputS, int(inputL[1])])

def partition(A, l, r):
    pivot = A[r][1]
    minVI = l-1
    i = l
    while i < r:
        if A[i][1] <= pivot:
            minVI+=1
            A[i], A[minVI] = A[minVI], A[i]
        i+=1
    A[minVI+1], A[i] = A[i], A[minVI+1]
    return minVI+1

def quickSort(A, l, r):
    if l < r:
        pivotI = partition(A, l, r)
        quickSort(A, l, pivotI-1)
        quickSort(A, pivotI+1, r)

def merge(l, r):
    lI = 0
    rI = 0
    newL = []
    while lI < len(l) and rI < len(r):
        if l[lI][1] <= r[rI][1]:
            newL.append(l[lI])
            lI+=1
        else:
            newL.append(r[rI])
            rI+=1
    while lI < len(l):
        newL.append(l[lI])
        lI+=1
    while rI < len(r):
        newL.append(r[rI])
        rI+=1
    return newL

def mergeSort(curL):
    if len(curL) <= 1:
        return curL
    else:
        mid = len(curL)//2
        left = mergeSort(curL[:mid])
        right = mergeSort(curL[mid:])
        return merge(left, right)

mergeSorted = mergeSort(cL)
quickSort(cL, 0, len(cL)-1)
quickSorted = cL
if mergeSorted == quickSorted:
    print('Stable')
else:
    print('Not stable')
for v in quickSorted:
    print(v[0])

Submission status: Accepted

Solution code:
class Card:
    def __init__(self, name, number):
        self.name = name
        self.number = number

    def __le__(self, other):
        return self.number <= other.number

    def __str__(self):
        return f'{self.name} {self.number}'


def partition(arr, p, r):
    x = arr[r]
    index = p - 1  # arr[p,index] <= x,arr[index+1,i)>x
    for i in range(p, r):
        if arr[i] <= x:
            arr[i], arr[index + 1] = arr[index + 1], arr[i]
            index += 1
    arr[index + 1], arr[r] = arr[r], arr[index + 1]
    return index + 1


def quick_sort(arr, l, r):
    if l >= r:
        return
    q = partition(arr, l, r)
    quick_sort(arr, l, q - 1)
    quick_sort(arr, q + 1, r)


if __name__ == '__main__':
    n = int(input())
    arr = []
    for _ in range(n):
        name, number = input().split()
        arr.append(Card(name, int(number)))
    sort_before_record = {}
    for ele in arr:
        if ele.number in sort_before_record:
            sort_before_record[ele.number].append(ele.name)
        else:
            sort_before_record[ele.number] = [ele.name]

    quick_sort(arr, 0, n - 1)

    sort_after_record = {}
    for ele in arr:
        if ele.number in sort_after_record:
            sort_after_record[ele.number].append(ele.name)
        else:
            sort_after_record[ele.number] = [ele.name]
    flag = True

    for key in sort_before_record:
        if sort_before_record[key] != sort_after_record[key]:
            flag = False
            break

    if flag:
        print('Stable')
    else:
        print('Not stable')
    for ele in arr:
        print(ele)

Submission status: Accepted

Solution code:
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
            m=A[i]
            A[i]=A[j]
            A[j]=m
    m=A[i+1]
    A[i+1]=A[r]
    A[r]=m
    return i+1
def quicksort(A,p,r):
    if p<r:
        q=partition(A,p,r)
        quicksort(A,p,q-1)
        quicksort(A,q+1,r)
n=int(input())
A=[]
for _ in range(n):
    card=input().split()
    A.append([card[0],int(card[1])])
Acopy=A.copy()
quicksort(A,0,n-1)
ans="Stable"
for i in range(n-1):
    if A[i][1]==A[i+1][1]:
        if Acopy.index(A[i+1])<Acopy.index(A[i]):
            ans="Not stable"
            break
print(ans)
for i in range(n):
    print(*A[i])

Submission status: Accepted

Solution code:
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
            temp=a[i]
            a[i]=a[j]
            a[j]=temp
    temp=a[i+1]
    a[i+1]=a[r]
    a[r]=temp
    return i+1

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


r=int(input())
a=[list(input().split()) for _ in range(r)]
for i in range(r):
    a[i][1]=int(a[i][1])
import copy
b=copy.deepcopy(a)
b.sort(key=lambda x:x[1])
quicksort(a,0,r-1)


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

for i in range(r):
    print(a[i][0],a[i][1])

Submission status: Accepted

Solution code:
n = int(input())
A = [input().split(" ") for _ in range(n)]
S = A.copy()

def partition(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
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

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

SENTINEL = 9999999999999

def merge(S, n, left, mid, right):
    global SENTINEL
    n1 = mid - left
    n2 = right - mid
    L = S[left:mid] + [[" ", SENTINEL]]
    R = S[mid:right] + [[" ", SENTINEL]]
    i = j = 0
    for k in range(left, right):
        if int(L[i][1]) <= int(R[j][1]):
            S[k] = L[i]
            i += 1
        else:
            S[k] = R[j]
            j += 1

def mergeSort(S, n, left, right):
    if left + 1 < right:
        mid = int((left + right) / 2)
        mergeSort(S, n, left, mid)
        mergeSort(S, n, mid, right)
        merge(S, n, left, mid, right)

quickSort(A, 0, n-1)
mergeSort(S, n, 0, n)

def Judge():
    for _ in range(n):
        if A[_] != S[_]:
            return "Not stable"
    return "Stable"
    
print(Judge())
for _ in range(n):
    print(*A[_])

Submission status: Accepted

Solution code:
def merge(A, l, m, r):
  L = A[l:m]
  L.append((1e10, None))
  R = A[m:r]
  R.append((1e10, None))
  i, j = 0, 0
  for k in range(l, r):
    if L[i][0] <= R[j][0]:
      A[k] = L[i]
      i += 1
    else:
      A[k] = R[j]
      j += 1

def msort(A, l, r):
  if r-l > 1:
    m = (l+r)//2
    msort(A, l, m)
    msort(A, m, r)
    merge(A, l, m, r)

def partition(A, l, r):
    v = A[r-1]
    i = l - 1
    for j in range(l, r-1):
        if A[j][0] <= v[0]:
            i += 1
            t = A[i]
            A[i] = A[j]
            A[j] = t
    q = i+1
    A[r-1] = A[q]
    A[q] = v
    return q

def qsort(A, l, r):
    if r-l > 1:
        q = partition(A, l, r)
        qsort(A, l, q)
        qsort(A, q+1, r)

N = int(input())
A, B = [], []
for _ in range(N):
    c, n = input().split()
    n = int(n)
    A.append((n, c))
    B.append((n, c))
qsort(A, 0, N)
msort(B, 0, N)
print('Stable' if A == B else 'Not stable')
for n, c in A:
    print(c, n)

Submission status: Accepted

Solution code:
import sys
import copy
input = sys.stdin.readline

n = int(input())
# カードの番号だけintにcastしながら受け取る
A = [None for _ in range(n)]
M = [None for _ in range(n)]
for i in range(n):
    tmp = list(input().split())
    A[i] = [tmp[0], int(tmp[1])]
    M[i] = [tmp[0], int(tmp[1])]

# mergeSortで使う
SENTINEL = 1000000005
merge_count = 0


def main():
    # print("before sort:{}".format(A))
    quickSort(A, 1, len(A) - 1)
    # print("quickSort Result:{}".format(A))
    mergeSort(M, 0, len(M))
    # print("mergeSort Result:{}".format(M))

    print(isStable(A, M))
    for a in A:
        print(a[0] + ' ' + str(a[1]))


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


def partition(A, p, r):
    last = A[r][1]
    i = p - 1
    # print("last:{}".format(last))
    # print("i:{}".format(i))
    for j in range(i, r, 1):
        # print("A[j]:{}".format(A[j]))
        if A[j][1] <= last:
            # print("change")
            tmp = A[i]
            A[i] = A[j]
            A[j] = tmp
            i += 1

        # print(A)
    tmp = A[i]
    A[i] = A[r]
    A[r] = tmp

    return i


def merge(M, left, mid, right):
    # print("---merge start---")
    # print("M is {}".format(M))
    # print("left:{0}, mid:{1}, right{2}".format(left, mid, right))
    global merge_count

    L = M[left:mid] + [["SENTINEL", SENTINEL]]
    R = M[mid:right] + [["SENTINEL", SENTINEL]]

    # print("L:{}".format(L))
    # print("R:{}".format(R))

    i, j = 0, 0
    for k in range(left, right, 1):
        merge_count += 1
        # print("k:{0}".format(k))
        if L[i][1] <= R[j][1]:
            M[k] = L[i]
            i += 1
        else:
            M[k] = R[j]
            j += 1

    # print("M is {}".format(M))
    # print("----merge end----")


def mergeSort(M, left, right):
    # print("------mergeSort start--------")
    # print("left:{0}, right:{1}".format(left, right))

    if left + 1 < right:
        mid = (left + right) // 2
        # print("left:{0}, mid:{1}, right:{2}".format(left, mid, right))
        mergeSort(M, left, mid)
        mergeSort(M, mid, right)
        merge(M, left, mid, right)


def isStable(A, M):
    for i in range(len(A)):
        if A[i] != M[i]:
            return "Not stable"
    return "Stable"


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
クイックソート

6
D 3
H 2
D 1
S 3
D 2
C 1
"""
import copy

MAX = 500000
L = [None] * int(MAX / 2 + 2) 
R = [None] * int(MAX / 2 + 2) 
# 番兵
SENTINEL = "2000000000000"
from pprint import pprint

def quick_sort(A, n, p, r):
    if p < r:
        q = partition(A, n, p, r)
        # pprint(A)
        # z = []
        # for a in A:
        #     z.append(a.mark_num)
        # print(z)
        quick_sort(A, n, p, q-1)
        quick_sort(A, n, q+1, r)

def partition(A, n, p, r):
    # print(n, p, r)
    x = A[r].num
    i = p
    # print(p)
    for k in range(p, r+1):
        if A[k].num <= x:
            tmp = A[i]
            A[i] = A[k]
            A[k] = tmp
            i += 1
            # print(i)
    return i-1

def merge(B, n, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    for i in range(n1):
        L[i] = B[left + i]
    for i in range(n2):
        R[i] = B[mid + i]
    L[n1] = Card("dummy {}".format(SENTINEL))
    R[n2] = Card("dummy {}".format(SENTINEL))
    i = 0
    j = 0
    k = left
    while  k < right:
        if L[i].num <= R[j].num:
            B[k] = L[i]
            i += 1
        elif L[i].num > R[j].num:
            B[k] = R[j]
            j += 1
        k += 1


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

            

class Card:
    def __init__(self, mark_num):
        self.mark_num = mark_num
        self.num = int(mark_num.split()[1])


if __name__=="__main__":
    n = int(input())
    A = []
    for i in range(n):
        row = input()
        A.append(Card(row))

    B = copy.deepcopy(A)

    quick_sort(A, n, 0, n-1)
    # for a in A:
    #     print(a.mark_num)
    
    # print("======")
    merge_sort(B, n, 0, n)
    # for b in B:
    #     print(b.mark_num)
    # print(" ".join(A_str))

    for i in range(n):
        if A[i].mark_num != B[i].mark_num:
            print("Not stable")
            break
    else:
        print("Stable")
        # print(A[i].mark_num, B[i].mark_num)

    for a in A:
        print(a.mark_num)

Submission status: Accepted

Solution code:
INF = 1000000000

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

	def __repr__(self):
		return self.suit + ' ' + str(self.value)


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



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


def merge(A, left, mid, right):
	L = A[left:mid]
	R = A[mid:right]
	L.append(Card("INF", INF))
	R.append(Card("INF", INF))
	i = 0
	j = 0
	for k in range(left, right):
		if L[i].value <= R[j].value:
			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)


if __name__ == "__main__":
	n = int(input())
	A = []
	for _ in range(n):
		suit, value = input().split()
		A.append(Card(suit, int(value)))

	B = A.copy()
	quickSort(A, 0, n - 1)
	mergeSort(B, 0, n)
	if A == B:
		print("Stable")
	else:
		print("Not stable")
	for card in A:
		print(card)

Submission status: Accepted

Solution code:
def merge(A, left, mid , right):
  L = A[left:mid]
  R = A[mid:right]
  L.append(('J', 1000000001))
  R.append(('J', 1000000001))
  i = 0
  j = 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 merge_sort(A, p ,r):
  if p + 1 < r:
    m = (p + r) // 2
    merge_sort(A, p, m)
    merge_sort(A, m, r)
    merge(A, p, m, r)

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 = []

for i in range(n):
  card, rank = input().split(" ")
  cards.append((card, int(rank)))
copy_cards = cards[:]

quick_sort(cards, 0, len(cards) - 1)
merge_sort(copy_cards, 0, len(cards))

stable = True
for x, y in zip(cards, copy_cards):
  if x != y:
    stable = False
    print('Not stable')
    break

if stable:
  print('Stable')

for card in cards:
  print("{} {}".format(card[0], card[1]))

Submission status: Accepted

Solution code:
def partition(A, p, r):
    x = A[r][1]
    i = p - 1
    for j in range(p, r + 1):
        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 - 1)
        quicksort(A, q + 1, r)


def makedic(A, n):
    d = {}
    for i in range(n):
        key = A[i][1]
        value = A[i][0]
        if key in d:
            d[key] += value
        else:
            d[key] = value
    return d

def main():
    N = int(input())
    A = []
    for i in range(N):
        a, v = input().split()
        v = int(v)
        A.append((a, v))

    sd = makedic(A, N)
    quicksort(A, 0, N - 1)
    ed = makedic(A, N)

    print('Stable' if sd == ed else 'Not stable')

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy

class Cards:
    def __init__(self, letter, value):
        self.letter = letter
        self.value = value

def Partition(NUM_LIST, left, right):
    v = NUM_LIST[right-1].value
    border = left
    for foot in range(left, right-1):
        if NUM_LIST[foot].value <= v:
            NUM_LIST[foot], NUM_LIST[border] = NUM_LIST[border], NUM_LIST[foot]
            border += 1
    NUM_LIST[right-1], NUM_LIST[border] = NUM_LIST[border], NUM_LIST[right-1]
    return border
    
def QuickSort(NUM_LIST, left, right):
    if left+1 < right:
        q = Partition(NUM_LIST, left, right)
        QuickSort(NUM_LIST, left, q)
        QuickSort(NUM_LIST, q+1, right)

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

def Merge(NUM_LIST, left, mid, right):
    L = NUM_LIST[left:mid]
    inf = Cards("inf", 1000000001)
    L.append(inf)
    R = NUM_LIST[mid:right]
    R.append(inf)
    i=0
    j=0
    for k in range(left, right):
        if L[i].value > R[j].value:
            NUM_LIST[k] = R[j]
            j += 1
        else:
            NUM_LIST[k] = L[i]
            i += 1

n = int(input())
CARD_LIST = []

for i in range(n):
    c, v = input().split()
    v = int(v)
    tmp = Cards(c, v)
    CARD_LIST.append(tmp)

QUICK_LIST = copy.copy(CARD_LIST)
MERGE_LIST = copy.copy(CARD_LIST)

QuickSort(QUICK_LIST, 0, len(QUICK_LIST))
MergeSort(MERGE_LIST, 0, len(MERGE_LIST))


if QUICK_LIST == MERGE_LIST:
    print("Stable")
else:
    print("Not stable")
    
for i in range(len(MERGE_LIST)):
    print("%s %d"%(QUICK_LIST[i].letter, QUICK_LIST[i].value))

Submission status: Accepted

Solution code:
import copy
INF = 10000000000
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]
            flag = 1
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

def Qsort(A,p,r):
    if p < r:
        q = Partition(A,p,r)
        Qsort(A,p,q-1)
        Qsort(A,q+1,r)

def merge(A, left, mid, right):
    count = 0
    L = A[left:mid] + [(INF,INF)]
    R = A[mid:right] + [(INF,INF)]

    i, j = 0, 0
    for k in range(left, right):
        count = count + 1
        if L[i][1] <= R[j][1]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
    return count

def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        countL = mergeSort(A, left, mid)
        countR = mergeSort(A, mid, right)
        return merge(A, left, mid, right) + countL + countR
    return 0

N = int(input())
C = []
for i in range(N):
    C.append(input().split())
    C[i][1] = int(C[i][1])

D = copy.deepcopy(C)
Qsort(C,0,N-1)
mergeSort(D,0,N)

if C==D:
    print("Stable")
else:
    print("Not stable")
for i in range(N):
    print(C[i][0]+" "+str(C[i][1]))

Submission status: Accepted

Solution code:
#ALDS1_6_C Quick Sort
import sys
# sys.setrecursionlimit(10000)
def partition(A, p, r):
    q = A[r][1]
    j = p
    for i in range(p, r):
        if A[i][1] <= q:
            A[i], A[j] = A[j], A[i]
            j += 1
    A[j], A[r] = A[r], A[j]
    return j


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([None, float('inf')])
    r.append([None, float('inf')])

    i = 0
    j = 0

    for k in range(left, right, 1):
        if l[i][1] <= r[j][1]:
            A[k] = l[i]
            i += 1
        else:
            A[k] = r[j]
            j += 1


def merge_sort(A, 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)


n = int(input())
A = []
for i in range(n):
    suit, num = input().split()
    A.append([suit, int(num)])
A1 = A.copy()

quick_sort(A, 0, n-1)
merge_sort(A1, 0, n)

if A != A1:
    print('Not stable')
else:
    print('Stable')

for i in range(n):
    print(' '.join(map(str, A[i])))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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 quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)

def marge(A, left, right, mid):
    n1 = mid - left
    n2 = right - mid
    L = [[] for _ in range(n1+1)]
    R = [[] for _ in range(n2+1)]
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
    L[n1] = ('Z', 10 ** 9 + 1)
    R[n2] = ('Z', 10 ** 9 + 1)
    i = 0
    j = 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
    return

def margesort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        margesort(A, left, mid)
        margesort(A, mid, right)
        marge(A, left, right, mid)
        return
    return


def main():
    n = int(input())
    A = [[] for _ in range(n)]
    B = [[] for _ in range(n)]
    for i in range(n):
        a, b = input().split()
        b = int(b)
        A[i] = (a, b)
        B[i] = (a, b)
    margesort(A, 0, n)
    quicksort(B, 0, n-1)
    if A == B:
        print("Stable")
    else:
        print("Not stable")
    for a in B:
        print(a[0], a[1])

if __name__ == '__main__': main()