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:
import copy

def partition(A, p, r):
    x = A[r][1]
    i = p-1
    for j in range(p, r):
        if A[j][1] <= x:
            i = 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] + [("J", 1000000000) ]
    R = A[mid:right] + [("J", 1000000000)]
    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)
    
    
n = int(input())
A_Q = [input() for _ in range(n)]
A_Q = [(i.split()[0], int(i.split()[1])) for i in A_Q]
A_M = copy.deepcopy(A_Q)

quicksort(A_Q, 0, n-1)
mergesort(A_M, 0, n)

A_Q = [f"{str(i[0])} {str(i[1])}"for i in A_Q]
A_M = [f"{str(i[0])} {str(i[1])}"for i in A_M]
if A_Q == A_M:
    print("Stable")
else:
    print("Not stable")
print(*A_Q, sep="\n")

Submission status: Accepted

Solution code:
import sys
import copy

infty = 10**10

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

	eInfty = ['X',infty]
	L.append(eInfty)
	R.append(eInfty)

	i = 0
	j = 0
	cnt = 0

	for k in range(left,right):

		cnt += 1

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

	return cnt


def mergeSort(A,left,right):

	cnt = 0

	if left+1 < right:

		mid = (left + right) // 2
		cnt += mergeSort(A,left,mid)
		cnt += mergeSort(A,mid,right)
		cnt += merge(A,left,mid,right)

	return cnt


def Partition(A,p,r):

	# choose pivot
	#A[r],A[r//2] = A[r//2],A[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 isStable(M,Q):

	for i in range(len(M)):

		if M[i] != Q[i]:

			return False

	return True

def test():

	n = int(sys.stdin.readline())
	deck = []

	for i in range(n):

		inputs = list(sys.stdin.readline().split())
		inputs[1] = int(inputs[1])

		deck.append(inputs)

	original = copy.deepcopy(deck)
	result = mergeSort(original,0,n)

	Quicksort(deck,0,n-1)

	if isStable(original,deck) == True:
		print("Stable")
	else:
		print("Not stable")

	for i in range(n):
		print(f"{deck[i][0]} {deck[i][1]}")


if __name__ == "__main__":
	test()

Submission status: Accepted

Solution code:
import copy

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

for i in range(n):
    x, y = input().split()
    z = {'mark': x, 'num': int(y)}
    A.append(z)

B = copy.deepcopy(A)

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

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

quicksort(0, n-1)

def checkstable():
    for i in range(n-1):
        if A[i]['num'] == A[i+1]['num']:
            if B.index(A[i]) > B.index(A[i+1]):
                return 'Not stable'
                break
    return 'Stable'

print(checkstable())
for i in A:
    print(i['mark'], i['num'])

Submission status: Accepted

Solution code:
#クイックソート
import copy
 
INF = 10000000000
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

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

n = int(input())
A = [input().split() for _ in range(n)]
A = [(a[0], int(a[1])) for a in A]
B = [(a[0], int(a[1])) for a in A]

def quickSort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quickSort(A, p, q-1)
        quickSort(A, q+1, r)
        
quickSort(A, 0, n-1)
mergeSort(B, 0, n)
if A == B:
    print('Stable')
else:
    print("Not stable")
    
ans = [str(a[0])+" "+str(a[1]) for a in A]
ans = '\n'.join(ans)
print(ans)

Submission status: Accepted

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

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

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

num = int(input())
card_list = [input().split() for s in range(num)]
card_list = [(t[0], int(t[1])) for t in card_list]
cp_card_list = card_list[:]

quick_sort(card_list, 0, len(card_list) - 1)

is_stable = True
for i in range(len(card_list) - 1):
    if card_list[i][1] == card_list[i+1][1]:
        if cp_card_list.index(card_list[i]) > cp_card_list.index(card_list[i+1]):
            is_stable = False
            break

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

for t in card_list:
    print(t[0], t[1])

Submission status: Accepted

Solution code:
class Card:
    def __init__(self):
        self.suit = ''
        self.value = 0

def partition(A, p, r):
    x = A[r].value
    i = p
    for j in range(p, r):
        if A[j].value <= x:
            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)

def main():
    n = int(input())
    A = []
    for _ in range(n):
        card = Card()
        _input = input().split(" ")
        card.suit = _input[0]
        card.value = int(_input[1])
        A.append(card)
    
    ind = dict((e, i) for i, e in enumerate(A))
    quickSort(A, 0, n-1)
    
    for i in range(n - 1):
        if A[i].value == A[i + 1].value:
            if ind[A[i]] > ind[A[i + 1]]:
                print('Not stable')
                break
    else:
        print('Stable')
    
    for i in range(n):
        print(A[i].suit, A[i].value)
             
if __name__ == "__main__":
    main()

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())
S = []
for _ in range(n):
    a, b = map(str, input().split())
    S.append([a, int(b)])
copyS = copy.deepcopy(S)

quicksort(S, 0, n-1)

for i in range(n-1):
    if S[i][1] == S[i+1][1]:
        if copyS.index(S[i]) > copyS.index(S[i+1]):
            print("Not stable")
            break         
else:
    print("Stable")
    
for j in S:
    print(" ".join(str(a) for a in j))

Submission status: Accepted

Solution code:
import sys


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


SENTINEL_NUM = 10 ** 9 + 1
cnt = 0
sentinel = Card(None, SENTINEL_NUM)


def merge(A, left, mid, right):
    global cnt
    global sentinel
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid] + [sentinel]
    R = A[mid:right] + [sentinel]

    i, j = 0, 0
    for k in range(left, right):
        cnt += 1
        if L[i].value <= R[j].value:
            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)


def partition(A, 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, 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 = [[None] * 2 for _ in range(n)]
B = [[None] * 2 for _ in range(n)]
for i in range(n):
    suit, value = input().split()
    A[i] = B[i] = Card(suit, int(value))

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

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

Submission status: Accepted

Solution code:
from copy import copy


class Card:

    def __init__(self, s):
        splited = s.split(' ')
        self.suit = splited[0]
        self.number = int(splited[1])

    def __gt__(self, other):
        return self.number > other.number

    def __ge__(self, other):
        return self.number >= other.number

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

    def __lt__(self, other):
        return self.number < other.number

    def __repr__(self):
        return '{} {}'.format(self.suit, self.number)

    def __str__(self):
        return self.__repr__()

    def __eq__(self, other):
        return self.suit == other.suit and self.number == other.number


s = 'A 0'
SENTINEL = Card(s)
SENTINEL.number = float('inf')


def main():
    n = int(input())
    cs_1 = [Card(input()) for _ in range(n)]
    cs_2 = copy(cs_1)
    merge_sort(cs_1, n, 0, n)
    quick_sort(cs_2, 0, n-1)
    if all([c1 == c2 for c1, c2 in zip(cs_1, cs_2)]):
        print('Stable')
    else:
        print('Not stable')
    print('\n'.join([str(c) for c in cs_2]))


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 partition(A, p, r):
    x = A[r]
    i = p-1
    for j in range(p, r):
        if 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 merge_sort(A, n, left, right):
    if left+1 < right:
        mid = (left+right) // 2
        merge_sort(A, n, left, mid)
        merge_sort(A, n, mid, right)
        merge(A, n, left, mid, right)


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy

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

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

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)

n=int(input())
A=[input().split() for _ in range(n)]
B=copy.deepcopy(A)

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

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

Submission status: Accepted

Solution code:
class Card():
    def __init__(self, suit: chr, number: int):
        self.suit = suit
        self.number = number

def partition(a: list, left: int, right: int) :
    std = a[right].number
    j = left - 1
    for i, v in enumerate(a[left:right]):
        idx = i + left
        if a[idx].number <= std:
            j += 1
            a[j], a[idx] = a[idx], a[j]

    j += 1
    a[j], a[right] = a[right], a[j]
    return j

def quick_sort(a: list, left: int, right: int):
    if left < right:
        sep = partition(a, left, right)
        quick_sort(a, left, sep-1)
        quick_sort(a, sep+1, right)

def merge(a: list, left: int, mid: int, right: int):
    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])

    inf = 1 << 32
    L.append(Card("Z", inf))
    R.append(Card("Z", inf))

    i = 0
    j = 0
    for k in range(left, right, 1):
        if L[i].number <= R[j].number:
            a[k] = L[i]
            i += 1
        else:
            a[k] = R[j]
            j += 1

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

def is_stable(m, q):
    for i, j in zip(m, q):
        if i.number != j.number or i.suit != j.suit:
            return False
    return True

n = int(input())

cards = []
for i in range(n):
    card_info = input().split(" ")
    cards.append(Card(card_info[0], int(card_info[1])))

merge_sorted = cards.copy()
quick_sorted = cards.copy()

merge_sort(merge_sorted, 0, len(merge_sorted))
quick_sort(quick_sorted, 0, len(quick_sorted) - 1)
stable = is_stable(merge_sorted, quick_sorted)

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

for c in quick_sorted:
    print("{} {}".format(c.suit, c.number))

# print("##############")
# for c in merge_sorted:
#     print("{} {}".format(c.suit, c.number))

Submission status: Accepted

Solution code:
import copy
from typing import List, Tuple


def partition(elements: List[Tuple[str, int]], start_idx: int, pivot_idx: int) -> int:
    pivot = elements[pivot_idx][1]
    i = start_idx - 1

    for j in range(start_idx, pivot_idx):
        if elements[j][1] <= pivot:
            i += 1
            elements[i], elements[j] = elements[j], elements[i]
    elements[i + 1], elements[pivot_idx] = elements[pivot_idx], elements[i + 1]

    return i + 1


def quick_sort(elements: List[Tuple[str, int]], p: int, r: int) -> None:
    if p < r:
        q = partition(elements, p, r)
        quick_sort(elements, p, q - 1)
        quick_sort(elements, q + 1, r)


if __name__ == "__main__":
    n = int(input())
    elements = [("", 0)] * n
    for i in range(n):
        element = input().split()
        elements[i] = (element[0], int(element[1]))

    elements_copy = copy.deepcopy(elements)
    quick_sort(elements, 0, n - 1)

    for i in range(n - 1):
        if elements[i][1] == elements[i + 1][1]:
            if elements_copy.index(elements[i]) > elements_copy.index(elements[i + 1]):
                print("Not stable")
                break
    else:
        print("Stable")

    for elem in elements:
        print(f"{elem[0]} {elem[1]}")

Submission status: Accepted

Solution code:
class Card:
    suit = ''
    value = 0

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

    def __lt__(self, rhv):
        return self.value < rhv.value

    def __le__(self, rhv):
        return self.value <= rhv.value

    def __eq__(self, rhv):
        return self.suit == rhv.suit and self.value == rhv.value

    def __ne__(self, rhv):
        return not (self == rhv)

    def __str__(self):
        return '%s%d'%(self.suit, self.value)

def merge(arr, length, left, mid, right):
#  n1 = mid - left
#  n2 = right - mid

    L = arr[left : mid]
    R = arr[mid : right]

    L.append(Card([' ', 2000000000]))
    R.append(Card([' ', 2000000000]))

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

def merge_sort(arr, length, left, right):
    if (left + 1 < right):
        mid = (left + right)//2
        merge_sort(arr, length, left, mid)
        merge_sort(arr, length, mid, right)
        merge(arr, n, left, mid, right)

def partition(arr, left, right):
    x = arr[right]
    i = left - 1
    for j in range(left, right):
        if arr[j] <= x:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[right] = arr[right], arr[i + 1]
    return i + 1

def quick_sort(arr, length, left, right):
    if (left < right):
        q = partition(arr, left, right)
        quick_sort(arr, length, left, q - 1)
        quick_sort(arr, length, q + 1, right)

if __name__ == '__main__':
    n = int(input())

    arr1 = []
    arr2 = []

    for i in range(n):
        temp = input().split(' ')
        arr1.append(Card(temp))
        arr2.append(Card(temp))
    
    stable = True

    merge_sort(arr1, n, 0, n)
    quick_sort(arr2, n, 0, n - 1)

    for i in range(n):
        if (arr1[i].suit != arr2[i].suit):
            stable = False
            break
    if stable:
        print('Stable')
    else:
        print('Not stable')

    for i in arr2:
        print('%s %d'%(i.suit, i.value))

Submission status: Accepted

Solution code:
from enum import Enum
from queue import Queue
import collections

import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

def partition(A,p,r):
    i = p-1
    for j in range(p,r):
        if A[j][1]<=A[r][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)

def isStable(A):
    for i in range(1,len(A)):
        if A[i-1][1] == A[i][1]:
            if A[i-1][2] > A[i][2]:
                return 'Not stable'
    return 'Stable'

n = int(input())
A = []
for i in range(n):
    suit,num = sys.stdin.readline().split()
    A += [[suit,int(num),i]]
QuickSort(A,0,n-1)
print(isStable(A))
for i in A:
    print(i[0],i[1])

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 = 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]+[["X",10000000000]]
    R=A[mid:right]+[["X",10000000000]]
    i = 0
    j = 0

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

def mergeSort(A, left, right):
    mid=0
    if left+1 < right:
        mid = int((left + right)/2)
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
import copy
n=int(input())
A=[]
for i in range(n):
    Astr=input().split( )
    A.append([Astr[0],int(Astr[1])])

B=A.copy()
#print(id(A))      # ID: 4315448960
#print(id(B))      # ID: 4315448960

quickSort(A,0,n-1)

mergeSort(B,0,n)
#print(*B)
flag=0
for i in range(n):
    if A[i]!=B[i]:
        flag=1
        break
    else:
        pass
if flag==1:
    print("Not stable")
else:
    print("Stable")

#print(*A)
#print(*B)
for i in range(n):
    print(*A[i])

Submission status: Accepted

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


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


n = int(input())
arr = [input().split() for _ in range(n)]
arr_s = sorted(arr, key=lambda x:x[1])
quicksort(arr, 0, n - 1)


print("Stable" if arr == arr_s else "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
            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 main():
    n = int(input())
    A = []
    for i in range(n):
        m, s = input().split()
        s = int(s)
        A.append([m, s])
    B = A[:]
    quicksort(B, 0, n-1)

    for i in range(n-1):
        if B[i][1] == B[i + 1][1]:
            if A.index(B[i]) > A.index(B[i + 1]):
                print("Not stable")
                break
    else:
        print("Stable")

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def partition(A,p,r):
  q = p
  for i in range(p,r):
    if A[i][1] <= A[r][1]:
      A[q],A[i] = A[i],A[q]
      q += 1

  A[q],A[r] = A[r],A[q]
  return q

def quicksort(A,left,right):
  if left < right:
    q = partition(A,left,right)
    quicksort(A,left,q-1)
    quicksort(A,q+1,right)

def check_stable(A):
  for i in range(1,len(A)):
    if A[i-1][1] == A[i][1]:
      if A[i-1][2] > A[i][2]:
        return "Not stable"
  return "Stable"

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

quicksort(data,0,len(data) -1)
print(check_stable(data))

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

Submission status: Accepted

Solution code:
def partition(A, p, r):
    COLUMN_SORT = 1

    global flag_stable

    x = A[r][COLUMN_SORT]
    i = p - 1

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

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

    for i in range(q + 1, r):
        if A[r] > A[i]:
            flag_stable = False

    return q


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


# INPUT
n = int(input())

list_card = []
for _ in range(n):
    suit, num = input().split()
    list_card.append([suit, int(num)])


# PROCESS
flag_stable = True

quicksort(list_card, 0, n-1)


# OUTPUT
if flag_stable:
    print("Stable")
else:
    print("Not stable")

for card in list_card:
    print(*card)

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):
    count = 0
    INF = 1000000000000000000000
    n1 = mid - left
    n2 = right - mid

    L = [A[left+i] for i in range(n1)]
    R = [A[mid+i] for i in range(n2)]
    L.append((INF, INF))
    R.append((INF, INF))

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


def merge_sort(A, left, right):
    if left+1 < right:
        mid = (left + right) // 2
        count_left = merge_sort(A, left, mid)
        count_right = merge_sort(A, mid, right)
        count = merge(A, left, mid, right)
        return count + count_right + count_left
    return 0


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)


def main():
    import copy
    n = int(input())
    A = []
    for _ in range(n):
        a, b = input().split()
        A.append((a, int(b)))

    B = copy.deepcopy(A)

    merge_sort(B, 0, len(B))
    quick_sort(A, 0, n-1)

    # print(A, B)

    if A == B:
        print("Stable")
    else:
        print("Not stable")

    for a in A:
        print(f"{a[0]} {a[1]}")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())

A = []
B = []

for i in range(n):
    arr = input().split()
    A.append(arr)
    B.append(arr)

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = [['x', 0]] * (n1 + 1)
    R = [['x', 0]] * (n2 + 1)

    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
    L[n1][1] = 1.0e+9 + 1
    R[n2][1] = 1.0e+9 + 1
    i = 0
    j = 0
    for k in range(left, right):
        if int(L[i][1]) <= int(R[j][1]):
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            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 = int(A[r][1])
    i = p - 1
    for j in range(p, r):
        if int(A[j][1]) <= x:
            i = 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)


quicksort(A, 0, n-1)
mergeSort(B, 0, n)

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

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

for i in range(n):
    print("{} {}".format(A[i][0], A[i][1]))

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    MAX = 100000
    SENTINEL = 2000000000

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

    def merge(A, n ,left, mid, right):
        n1 = mid - left
        n2 = right - mid
        L = [Card(None, None) for _ in range(n1+1)]
        R = [Card(None, None) 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].value = SENTINEL
        R[n2].value = SENTINEL
        i, j = 0, 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, n, left, right):
        if left+1 < right:
            mid = (left + right)//2
            mergeSort(A, n, left, mid)
            mergeSort(A, n, mid, right)
            merge(A, n, left, mid, right)


    def swap(a, i, j):
        # list aのi番目の要素とj番目の要素を交換する関数
        k = a[j]
        a[j] = a[i]
        a[i] = k

    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
                swap(A, i, j)
        swap(A, i+1, r)
        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 = [Card(None, None) for _ in range(n)]
    B = [Card(None, None) for _ in range(n)]

    for i in range(n):
        suit, value = input().split()
        A[i].suit = suit
        B[i].suit = suit
        A[i].value = int(value)
        B[i].value = int(value)

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

    for i in range(n):
        if A[i].suit != B[i].suit:
            print('Not stable')
            break
    else:
        print('Stable')

    for b in B:
        print(b.suit, b.value)

Submission status: Accepted

Solution code:
import copy
n = int(input())
A = []
for ni in range(n):
    A.append(input().split())
B = copy.deepcopy(A)
B.sort(key = lambda x: int(x[1]))

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

def QuickSort(A, p, r):
    if p >= r:
        return None
    else:
        q, A = Partition(A, p, r)
        QuickSort(A, p, q-1)
        QuickSort(A, q+1, r)
        return A

QuickSort(A, 0, n-1)
if A == B:
    print("Stable")
else:
    print("Not stable")
for ni in range(n):
    print(*A[ni], sep=" ")