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:
from collections import defaultdict


def key(pair):
    _, n = pair
    return n


def partitionize(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if key(A[j]) <= key(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 = partitionize(A, p, r)
        quick_sort(A, p, q - 1)
        quick_sort(A, q + 1, r)


def is_stable(ordered, original):
    scanned_ordered = defaultdict(list)
    scanned_original = defaultdict(list)
    for a, b in zip(ordered, original):
        s, n = a
        scanned_ordered[n].append(s)
        t, m = b
        scanned_original[m].append(t)
    for k in scanned_ordered:
        if scanned_ordered.get(k, "__NaN_1__") != scanned_original.get(k, "__NaN_2__"):
            return False
    return True


N = int(input())
A = []
for _ in range(N):
    s, n = input().split()
    A.append((s, int(n)))
sorted_A = A.copy()
quick_sort(sorted_A, 0, N - 1)
print("Stable" if is_stable(sorted_A, A) else "Not stable")
for s, n in sorted_A:
    print(s, n)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
INF = 10**10

def merge(A, l, mid, r):
    a1 = A[l:mid] + [[None, INF]]
    a2 = A[mid:r] + [[None, INF]]
    i = j = 0
    for k in range(l, r):
        if a1[i][1] <= a2[j][1]:
            A[k] = a1[i]
            i += 1
        else:
            A[k] = a2[j]
            j += 1

def merge_sort(A, l, r):
    if l + 1 >= r:
        return
    mid = (l + r) // 2
    
    merge_sort(A, l, mid)
    merge_sort(A, mid, r)
    
    merge(A, l, mid, r)
    
    
def quick_sort(A, l, r):
    if l < r:
        #mid = (l + r) // 2
        mid = r
        pivot = A[mid][1]
        A[mid], A[r] = A[r], A[mid]
        i = 0
        for j in range(l, r):
            if A[j][1] <= pivot:
                A[l+i], A[j] = A[j], A[l+i]
                i += 1
        A[l+i], A[r] = A[r], A[l+i]
        
        quick_sort(A, l, l+i-1)
        quick_sort(A, l+i+1, r)

n = int(input())
cards = [input().split() for _ in range(n)]

for card in cards:
    card[1] = int(card[1])

confirm_cards  = cards[:]

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

if cards == confirm_cards:
    print('Stable')
else:
    print('Not stable')
    
for card in cards:
    print(*card)

#print('-----')
#for card in confirm_cards:
#    print(*card)

Submission status: Accepted

Solution code:
from operator import attrgetter
class Card:
    def __init__(self, suit, number):
        self.suit = suit
        self.number = number

def partition(A, p, r):
    x = A[r]
    i = p-1
    for j in range(p, r):
        if A[j].number <= x.number:
            i = i + 1
            tp = A[j]
            A[j] = A[i]
            A[i] = tp
        else:
            continue
    A[r] = A[i+1]
    A[i+1] = x
    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 _ in range(n):
        suit, num = map(str, input().split())
        A.append(Card(suit, int(num))) 
    comp = sorted(A, key=attrgetter('number'))
    quickSort(A, 0, n-1)
    if A == comp:
        print('Stable')
    else:
        print('Not stable')
    for p in A:
        print(p.suit, p.number)
main()

Submission status: Accepted

Solution code:
n = int(input())
a = [0]*n


class card:
    def __init__(self, s, input_idx):
        self.m = s.split()[0]
        self.num = int(s.split()[1])
        self.t = s
        self.input_idx = input_idx
 
for i in range(n):
    a[i] = card(input(), i)
    
def partition(A, p, r):
    x = A[r].num
    i = p-1
    for j in range(p,r):
        if A[j].num <= 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)

stable = True
for i in range(1, n):
    if a[i].num==a[i-1].num and a[i].input_idx<a[i-1].input_idx:
        stable = False
        
if stable:
    print('Stable')
else:
    print('Not stable')
    
for item in a:
    print(item.t)

Submission status: Accepted

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

    for j in range(p, r):
        if A[j][2] <= 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(A):
    for index, a in enumerate(A):
        for i in range(index, len(A)):
            if (a[2] == A[i][2]) and (a[0] > A[i][0]):
                return "Not stable"

    return "Stable"



n = int(input())
A = []
for i in range(n):
    a, b = input().split()
    A.append([i, a, int(b)])

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

print(IsStable(A))
[print("{} {}".format(A[i][1], A[i][2])) for i in range(len(A))]

Submission status: Accepted

Solution code:
class Card:
    def __init__(self, mark, numebr):
        super().__init__()
        self.mark = mark
        self.number = number

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


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


if __name__ == "__main__":
    n = int(input())
    Cards = []
    Cards2 = []
    for _ in range(n):
        mark, number = input().split()
        Cards.append(Card(mark, int(number)))
        Cards2.append(Card(mark, int(number)))

    quickSort(Cards, 0, n-1)
    Cards2 = sorted(Cards2)

    stable = True
    for i in range(n):
        if not (Cards[i].mark == Cards2[i].mark and Cards[i].number == Cards2[i].number):
            stable = False

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

    for card in Cards:
        print('{} {}'.format(card.mark, card.number))

Submission status: Accepted

Solution code:
def partition(A, l, r):
    """ partition A[l:r] using q(A[r]) and return q's index
    """
    q = A[r][1]
    sep_i = l # left elements of seq <= q < right ones
    for j in range(l, r):
        if A[j][1] <= q:
            # A[j] is left element
            
            # add A[j] to last of left, and replace first of right to last
            A[sep_i], A[j] = A[j],  A[sep_i]
            sep_i += 1 # update separator
        else:
            # A[j] is right element
            pass

    A[sep_i], A[r] = A[r], A[sep_i]
    
    return sep_i

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

def is_stable(A, B):
    cA = list(A)
    for x in B:
        i = cA.index(x)
        if i == 0:
            pass
        elif cA[i - 1][1] == x[1]:
            return False
        del cA[i]
    return True

A = []
r = int(input())
for _ in range(r):
    mark, num = input().split()
    A.append([mark, int(num)])

B = list(A)
quick_sort(A, 0, r)

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

for x in A:
    print(*x)

Submission status: Accepted

Solution code:
import 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)

def show(l):
    for i in range(len(l)):
        print(l[i][0], l[i][1], sep = ' ')
    

n = int(input())
l_1 = []
for _ in range(n):
    a = input().split()
    l_1.append(a)
l_2 = copy.deepcopy(l_1)

quickSort(l_1, 0, n-1)

for i in range(n-1):
    if int(l_1[i][1]) == int(l_1[i+1][1]):
        if l_2.index(l_1[i]) > l_2.index(l_1[i+1]):
            print('Not stable')
            break
else:  
    print('Stable')

show(l_1)

Submission status: Accepted

Solution code:
import math
import string
import itertools
import fractions
import heapq
import collections
import re
import array
import bisect
import sys
import random
import time
inf = 10**9


def partition(a, p, r):
    # xがピボット
    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 main():
    n = int(input())
    cards = []
    for i in range(n):
        c = input().split()
        cards.append((c[0], int(c[1])))

    stable_sorted_cards = sorted(cards, key=lambda x: x[1])
    quicksort(cards, 0, n-1)

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

    for card in cards:
        print(card[0], card[1])


if __name__ == '__main__':
    main()

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

n = int(input())
#A = [None for i in range(n)]
A = []
for i in range(n):
    a, b = input().split()
    A.append([a, int(b)])

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

ans = [str(x[0]) +" "+str(x[1]) for x in A]
ans = '\n'.join(ans)
print(ans)

Submission status: Accepted

Solution code:
import copy

def partition(A,p,r):
    x = A[r][1]
    i = p-1
    # iは必ず1ずつ増える、jでx以下の要素を検出し、iの位置に持って行く
    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 = int(input())
card = [input().split() for i in range(N)]
for i in range(N):
    card[i][1] = int(card[i][1])

card2 = copy.deepcopy(card)
card2.sort(key=lambda x: x[1])

quickSort(card,0,N-1)
#print(card)
#print(card2)

ans = 'Stable'
for i in range(N):
    if card[i][0] != card2[i][0]:
        ans = 'Not stable'
        break
print(ans)
for i in range(N):
    print(' '.join(map(str,card[i])))

Submission status: Accepted

Solution code:
## Quick Sort

import copy

N = int(input())
lst1 = [list(input().split()) for i in range(N)]
lst2 = copy.copy(lst1)
INF = 10**9 + 1

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]
    L.append(("", INF))  # 番兵
    R = A[mid:right]
    R.append(("", INF))  # 番兵
    i, j = 0, 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

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

quick_sort(lst1, 0, N-1)
merge_sort(lst2, 0, N)
ans = 'Stable'
if (lst1 != lst2):
    ans = 'Not stable'
print(ans)
for i in lst1:
    print(*i)

Submission status: Accepted

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

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

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

def is_stable(original_list, sorted_list):
    for key, val in sorted_list:
        for original_key, original_val in original_list[:]:
            if val == original_val:
                if key != original_key:
                    print("Not stable")
                    return
                original_list.remove([original_key, original_val])
                break
    print("Stable")
    return
    
if __name__ == "__main__":
    n = int(input())
    A = [input().split() for _ in range(n)]
    A_original = deepcopy(A)
    quick_sort(0, n-1)
    is_stable(A_original, A)
    for key, val in A:
        print("{} {}".format(key, val))

Submission status: Accepted

Solution code:
class card:
    def __init__(self,suit,num,input_index):
        self.suit = suit
        self.num = num
        self.input_index = input_index

def partition(p,r):
    c_pivot=cards[r]
    i=p-1
    for j in range(p,r):
        if(cards[j].num<=c_pivot.num):
            i+=1
            cards[i],cards[j]=cards[j],cards[i]
    cards[i+1],cards[r]=cards[r],cards[i+1]
    return i+1

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

n=int(input())
cards=[]
for i in range(n):
    suit,num=input().split()
    cards.append(card(suit,int(num),i))

quicksort(0,n-1)

stableflag=True
for i in range(1,n):
    if(cards[i-1].num == cards[i].num and cards[i-1].input_index > cards[i].input_index):
        stableflag=False
        break
if(stableflag):
    print("Stable")
else:
    print("Not stable")

for ci in cards:
    print(ci.suit,ci.num)

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
            tmp = A[i]
            A[i] = A[j]
            A[j] = tmp
    tmp = A[i+1]
    A[i+1] = A[r]
    A[r] = tmp
    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 check_stable(C1, C2):
    C_order_table = {}
    sorted_C_order_table = {}
    for i in range(len(C1)):
        if C_order_table.get(C1[i][1]):
            C_order_table[C1[i][1]] += C1[i][0]
        else:
            C_order_table[C1[i][1]] = C1[i][0]
        
        if sorted_C_order_table.get(C2[i][1]):
            sorted_C_order_table[C2[i][1]] += C2[i][0]
        else:
            sorted_C_order_table[C2[i][1]] = C2[i][0]
    
    is_stable = True
    for key in C_order_table.keys():
        if C_order_table.get(key) != sorted_C_order_table.get(key):
            is_stable = False
            break
    
    if is_stable:
        print('Stable')
    else:
        print('Not stable')
n = int(input())
A = []
for i in range(n):
    c_and_num = input().split(' ')
    c = c_and_num[0]
    num = int(c_and_num[1])
    A.append((c, num))
original_A = A.copy()
quick_sort(A, 0, n-1)
check_stable(original_A, A)
for c, num in A:
    print(c, num)

Submission status: Accepted

Solution code:
import copy

n = int(input())

Card1 = []

for i in range(n):
  Card1.append(input())

def partition(B, p, r):
  x1, x2 = B[r].split()
  global i
  i = p-1
  for j in range(p, r):
    c1, c2 = B[j].split()
    if int(c2) <= int(x2):
      i += 1
      y = B[i]
      z = B[j]
      B[i] = z
      B[j] = y
  a = B[i+1]
  b = B[r]
  B[i+1] = b
  B[r] = a
  return i+1

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

def merge(A, left, mid, right):
  inf = float('inf')
  L = A[left:mid] + ["D inf"]
  R = A[mid:right] + ["D inf"]
  i = 0
  j = 0
  for k in range(left, right):
    l1 = L[i].split()
    r1 = R[j].split()
    l2 = float(l1[1])
    r2 = float(r1[1])
    if l2 <= r2:
      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)

Card2 = copy.deepcopy(Card1)

quicksort(Card1, 0, n-1)

mergesort(Card2, 0, n)

if Card1 == Card2:
  print("Stable")
else:
  print("Not stable")

for i in range(n):
  print(Card1[i])

Submission status: Accepted

Solution code:
inf = 10000000000

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

def quick_sort(a, left, right):
    if left < right:
        q = partition(a, left, right)
        quick_sort(a, left, q)
        quick_sort(a, q + 1, right)

def merge(a, left, mid, right):
    L = a[left : mid] + [('jorker', inf)]
    R = a[mid : right] + [('jorker', inf)]
    i = 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, 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)

    

if __name__ == "__main__":
    n = int(input())
    A = [None] * n
    B = [None] * n
    for i in range(n):
        picture, number = input().split()
        A[i] = (picture, int(number))
        B[i] = (picture, int(number))
    
    quick_sort(A, 0, n)
    merge_sort(B, 0, n)

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

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

Submission status: Accepted

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

    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):
    global count
    L = [0] * (mid - left + 1)
    R = [0] * (right - mid + 1)

    for i in range(len(L)):
        if i  == len(L) - 1:
            L[i] = ['A', float('inf')]
        else:
            L[i] = a[left+i]
    
    for i in range(len(R)):
        if i == len(R) - 1:
            R[i] = ['A', float('inf')]
        else:
            R[i] = a[mid+i]

    i = 0
    j = 0
    for k in range(left, right):
        if L[i][1] <= R[j][1]:
            a[k] = L[i]
            i += 1
        else:
            if i != len(L) - 1 and j != len(R) - 1:
                count += len(L) - i - 1
            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)

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

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

flag = 0
for i in range(n):
    if A[i] != A2[i]:
        flag = 1

if flag == 1:
    print('Not stable')
else:
    print('Stable')

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

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 int(A[j][2:]) <= int(x[2:]):
            i = i + 1
            y = A[i]
            A[i] = A[j]
            A[j] = y
    z = A[i+1]
    A[i+1] = A[r]
    A[r] = z
    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 i in range(n):
    A.append(str(input()))

B = copy.deepcopy(A)
B.sort(key = lambda x: int(x[2:]))

quickSort(A, 0, n-1)

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

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

Submission status: Accepted

Solution code:
class Card:

    def __init__(self, data):
        self.mark = data[0]
        self.number = int(data[2:])

    def __str__(self):
        return f"{self.mark} {self.number}"

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

    def __ne__(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 __ge__(self, other):
        return self.number >= other.number

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


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


def is_stable():
    count = 0
    for i, a in enumerate(A):
        if i == len(A) - 1:
            return True
        k = 0
        for o in Origin:
            if a.number == o.number:
                if count != k:
                    k += 1
                    continue
                if a.mark != o.mark:
                    return False
                else:
                    break
        if a.number != A[i + 1].number:
            count = 0
        else:
            count += 1

A = []
n = int(input())
for i in range(n):
    A.append(Card(input()))
Origin = A.copy()
quickSort(0, len(A) - 1)
print("Stable" if is_stable() else "Not stable")
print("\n".join(str(a) for a in A))

Submission status: Accepted

Solution code:
import 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[j], A[i] = A[i], A[j]
        else:
            pass 
    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):
    n1 = mid-left
    n2 = right-mid

    L = [[0, 0]]*(n1+1)
    for i in range(n1):
        L[i] = A[left+i]
    
    R = [[0, 0]]*(n2+1)
    for i in range(n2):
        R[i] = A[mid+i]
    
    L[n1][1] = 10000000000
    R[n2][1] = 10000000000

    i, j = 0, 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
    
def mergeSort(A, left, right):
    if left+1 < right:
        mid = (left+right)//2
        #sortする
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        #統合する
        merge(A, left, mid ,right)


#------------------------------------------------
n = int(input())
card = [input().split() for i in range(n)]

copy_card = copy.copy(card)
quickSort(copy_card, 0, n-1)
quick_list = copy_card

copy_card = copy.copy(card)
mergeSort(copy_card, 0, n)
merge_list = copy_card

if quick_list == merge_list:
    print('Stable')
else:
    print('Not stable')
for i in range(n):
    print(' '.join(quick_list[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
          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)

class checkstable:
    def __init__(self):
        self.d = {}
    def storecards(self,A):
        for i in range(len(A)):
            if A[i][1] in self.d:
                self.d[A[i][1]].append(A[i][0])
            else:
                 self.d[A[i][1]] = [(A[i][0])]

    def isstable(self,A):
        for i in range(len(A)):
            if self.d[A[i][1]].pop(0) != A[i][0]:
                      return "Not stable"
        return "Stable"

n = int(input())
A = []
for _ in range(n):
   mark,num = input().split()
   num = int(num)
   A.append([mark,num])
quick = checkstable()
quick.storecards(A)

quicksort(A,0,n - 1)
stable = quick.isstable(A)
print(stable)
for i in range(n):
   print(*A[i])

Submission status: Accepted

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

    for j in range(p, r):
        if key(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, key=lambda x: x):
    if p < r:
        q = partition(A, p, r, key=key)
        quick_sort(A, p, q - 1, key=key)
        quick_sort(A, q + 1, r, key=key)


if __name__ == '__main__':
    n = int(input())
    A = []
    for _ in range(n):
        egara, number = input().split()
        A.append((egara, int(number)))
    
    stable_sorted = sorted(A, key=lambda x: x[1])
    quick_sort(A, 0, n - 1, key=lambda x: x[1])

    if stable_sorted == A:
        print('Stable')
    else:
        print('Not stable')
    
    for egara, number in A:
        print(egara, number)

Submission status: Accepted

Solution code:
class Card():
    def __init__(self, num, mark):
        self.num = num
        self.mark = mark

    def __eq__(self, other):
        if other is None or not isinstance(other, Card):
            return False
        return self.__dict__ == other.__dict__

    def __ne__(self, other):
        return not self.__eq__(other)


def partition(array, start, end):
    end_val = array[end].num
    left_end = start - 1
    for search_idx in range(start, end):
        if array[search_idx].num <= end_val:
            left_end += 1
            array[left_end], array[search_idx] = array[search_idx], array[left_end]
    array[left_end + 1], array[end] = array[end], array[left_end + 1]
    return left_end + 1


def quicksort(array, start, end):
    if start < end:
        pivot_index = partition(array, start, end)
        quicksort(array, start, pivot_index - 1)
        quicksort(array, pivot_index + 1, end)


def mergesort(array, n):
    if n <= 1:
        return array
    left_end = n // 2
    left_sorted = mergesort(array[:left_end], left_end) + [Card(10**9, None)]
    right_sorted = mergesort(array[left_end:], n - left_end) + [Card(10**9, None)]
    left_idx, right_idx = 0, 0
    idx = 0
    sorted_list = [None] * n
    while idx < n:
        if left_sorted[left_idx].num <= right_sorted[right_idx].num:
            sorted_list[idx] = left_sorted[left_idx]
            left_idx += 1
        else:
            sorted_list[idx] = right_sorted[right_idx]
            right_idx += 1
        idx += 1
    return sorted_list


def main():
    n = int(input())
    cards = []
    for _ in range(n):
        mark, number = input().split(" ")
        cards.append(Card(int(number), mark))
    mergesorted_cards = mergesort(cards, n)
    quicksort(cards, 0, n - 1)
    message = "Stable"
    for i in range(n):
        if mergesorted_cards[i] != cards[i]:
            message = "Not stable"
    print(message)
    for i in range(n):
        print("{} {}".format(cards[i].mark, cards[i].num))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_C&lang=ja

def partition(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 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 = []
valset = set({})
for i in range(n):
    c, d = input().split()
    A.append((int(d), i, c))
    valset.add(int(d))

quicksort(A, 0, n - 1)

# flag
is_stable = True
for val in valset:
    tp = [A[j][1] for j in range(n) if A[j][0] == val]
    flag = False
    for j in range(len(tp) - 1):
        if tp[j] > tp[j + 1]:
            flag = True
            break
    # print(val, tp, flag)
    if flag:
        is_stable = False
        break
    
if is_stable:
    print("Stable")
else:
    print("Not stable")

for tp in A:
    print("{} {}".format(tp[2], tp[0]))

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for i in range(n):
	x,y=input().split()
	a.append([int(y),x])
from copy import copy
b=copy(a)

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

def Merge(A, left, mid, right):
	n1 = mid - left
	n2 = right - mid
	L=[[0,"ST"]for _ in range(n1+1)]
	R=[[0,"ST"]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][0] = 10**10
	R[n2][0] = 10**10
	i = 0
	j = 0
	for k in range(left,right):
		if L[i][0] <= R[j][0]:
			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)
MergeSort(a,0,n)
Quick(b,0,n-1)
print("Stable" if a==b else "Not stable")
for i in range(n):
	print(b[i][1],b[i][0])