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 sys import stdin

def partition(cards, start, end):
    p = cards[end]
    p_idx = start
    for i in range(start, end):
        c = cards[i]
        if c[1] <= p[1]:
            cards[i], cards[p_idx] = cards[p_idx], cards[i]
            p_idx = p_idx + 1
    cards[p_idx], cards[end] = cards[end], cards[p_idx]
    return p_idx


# in-place quicksort
def quicksort(cards, start, end):
    if start < end:
        p_idx = partition(cards, start, end)
        quicksort(cards, start, p_idx - 1)
        quicksort(cards, p_idx + 1, end)


def merge(nums, left, mid, right):
    l = nums[left:mid] + [('_', 9999999999)]
    r = nums[mid:right] + [('_', 9999999999 )]
    l_cur = 0
    r_cur = 0
    for i in range(right - left):
        if l[l_cur][1] > r[r_cur][1]:
            nums[left + i] = r[r_cur]
            r_cur = r_cur + 1
        else:
            nums[left + i] = l[l_cur]
            l_cur = l_cur + 1


def mergesort(nums, left, right):
    if right - left <= 1:
        return nums
    else:
        mid = (left + right) // 2
        mergesort(nums, left, mid)
        mergesort(nums, mid, right)
        merge(nums, left, mid, right)


def is_stable_result(orig, result):
    stable_result = orig[:]
    mergesort(stable_result, 0, len(stable_result))
    is_stable = True
    for c1, c2 in zip(stable_result, result):
        if c1 != c2:
            is_stable = False
    return is_stable


def parseLine(l):
    kind, num = l.strip().split(' ')
    return (kind, int(num))


def main():
    _, *lines = stdin.readlines()
    nums = [parseLine(l) for l in lines]

    # sort
    result = nums[:]
    quicksort(result, 0, len(result) - 1)

    # check is stable
    is_stable = is_stable_result(nums, result)
    print('Stable' if is_stable else 'Not stable')
    print('\n'.join([kind + ' ' + str(num) for (kind, num) in result]))

if __name__ == '__main__':
    main()

Submission status: Accepted

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


if __name__ == "__main__":
    import sys
    from operator import itemgetter
    n = int(input())
    cards1, cards2 = [], []
    for i, card in enumerate((l.strip()) for l in sys.stdin):
        cards1.append(card)
        cards2.append((int(card[2:]), i))

    quicksort(cards2, 0, n-1)
    print("Stable" if all(i1 < i2 for (n1, i1), (n2, i2) in zip(cards2, cards2[1:]) if n1 == n2)
          else "Not stable")
    print(*(cards1[i] for i in map(itemgetter(1), cards2)), sep="\n")

Submission status: Accepted

Solution code:
class Card(object):
    def __init__(self, *data):
        self.chr, self.num = data
        self.num = int(self.num)
        self.chr = str(self.chr)


def partition(A, p, r):
    x = A[r]
    i = p-1
    for j in range(p, r):
        if A[j].num <= x.num:
            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] + [Card('A', 10**10)]
    R = A[mid:right] + [Card('A', 10**10)]
    i = 0
    j = 0
    # 右と左比べて小さい方をとってくる
    for k in range(left, right):
        if L[i].num <= R[j].num:
            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 = [Card(*(input().split())) for _ in range(n)]
B = A[:]
C = A[:]

quicksort(B, 0, n-1)
mergeSort(C, 0, n)
flag = True
for b, c in zip(B, C):
    if b is not c:
        flag = False
        break
if flag:
    print('Stable')
else:
    print('Not stable')

for i in range(n):
    print(B[i].chr, B[i].num)

Submission status: Accepted

Solution code:
def partition(arr, p, r):
    x = int(arr[r][1])
    i = p - 1
    for j in range(p, r):
        if int(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 quickSort(arr, p, r):
    if p < r:
        q = partition(arr, p, r)
        quickSort(arr, p, q - 1)
        quickSort(arr, q + 1, r)
def merge(arr, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = [i for i in range(n1 + 1)]
    R = [i for i in range(n2 + 1)]
    for i in range(n1):
        L[i] = arr[left + i]
    for i in range(n2):
        R[i] = arr[mid + i]
    L[n1] = ['last', 10**9 + 1]
    R[n2] = ['last', 10**9 + 1]
    i = 0
    j = 0
    for k in range(left, right):
        if int(L[i][1]) <= int(R[j][1]):
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
def mergeSort(arr, left, right):
    if left + 1 < right:
        mid = (left + right)//2
        mergeSort(arr, left, mid)
        mergeSort(arr, mid, right)
        merge(arr, left, mid, right)
n = int(input())
a = [list(input().split()) for i in range(n)]
b = [i for i in a]
mergeSort(b, 0, n)
quickSort(a, 0, n - 1)
print('Stable' if a == b else 'Not stable')
for i in a:
    print(' '.join(i))

Submission status: Accepted

Solution code:
# 関数定義
def partition(A, p, r):
    x = A[r]["number"]
    i = p - 1
    
    for j in range(p, r):
        if A[j]["number"] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    
    A[i + 1], A[r] = A[r], A[i + 1]
    
    return i + 1

def quickSort(A, p, r):
    if p < r:
        q = partition(A, p ,r)
        quickSort(A, p, q-1)
        quickSort(A, q+1, r)
        
def is_stable(A):
    for i in range(0, len(A) - 1):
        j = i + 1
        #print(A[i]["number"], A[j]["number"], ":", A[i]["order"], A[j]["order"])
        if (A[i]["number"] == A[j]["number"] and A[i]["order"] > A[j]["order"]):
            return False
    return True

# 入力
N = int(input())
A = []
for i in range(N):
    card = input().split()
    A.append({'mark': card[0], 'number': int(card[1]), 'order': i})
    
# ソート
quickSort(A,0,N-1)

# is_stable()
if(is_stable(A)):
    print("Stable")
else:
    print("Not stable")
    
# 中身
for a in A :
    print(a["mark"], a["number"])

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)


n = int(input())
s = []
for i in range(n):
    s.append(input().split())

l = copy.deepcopy(s)
l.sort(key=lambda x: x[1])

quickSort(s, 0, n - 1)

print("Stable" if s == l else "Not stable")
for v in s:
    print(" ".join(v))

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[r], a[i + 1] = a[i + 1], a[r]
    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)


#
# l = [int(i) for i in input().split()]
# quick_sort(l, 0, len(l) - 1)
# print(l)

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

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

l1 = l.copy()
quick_sort(l1, 0, len(l) - 1)
# print(l1)

l2 = l.copy()
l2_sorted = sorted(l2, key=lambda x: x[1])
# print(l2_sorted)

if l1 == l2_sorted:
    print("Stable")
else:
    print("Not stable")

for x, y in l1:
    print(x, y)

Submission status: Accepted

Solution code:
# coding: utf-8

class Card:
    def __init__(self, card, initial):
        self.mark = card[0]
        self.number = int(card[1])
        self.initial = initial

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

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, n):
    flag = True
    for i in range(n-1):
        if A[i+1].number == A[i].number and A[i+1].initial < A[i].initial:
            flag = False
    return flag

def printCards(A, n):
    for i in range(n):
        print(A[i].mark, end=" ")
        print(A[i].number)

n = int(input().rstrip())
cards = []
for i in range(n):
    cards.append(Card(input().rstrip().split(), i))
quickSort(cards, 0, n-1)
if isStable(cards, n):
    print("Stable")
else:
    print("Not stable")

printCards(cards, n)

Submission status: Accepted

Solution code:
from sys import stdin
from copy import deepcopy

INF = 1000000007

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

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

# l <= m < rの範囲をマージ
def merge(A, l, m, r):
    L = A[l:m] + [("?", INF)]
    R = A[m:r] + [("?", INF)]
    li = 0
    ri = 0
    for j in range(l, r):
        if L[li][1] <= R[ri][1]:
            A[j] = L[li]
            li += 1
        else:
            A[j] = R[ri]
            ri += 1

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

def isStable(A, sorted_A):
    stable_A = deepcopy(A)
    mergeSort(stable_A, 0, len(stable_A))
    for i in range(len(A)):
        if stable_A[i] != sorted_A[i]:
            return False

    return True

n = int(stdin.readline().rstrip())
cards = []
for _ in range(n):
    s, num = stdin.readline().rstrip().split()
    cards.append((s, int(num)))

sorted_cards = deepcopy(cards)
quicksort(sorted_cards, 0, n-1)
if isStable(cards, sorted_cards):
    print("Stable")
else:
    print("Not stable")

for card in sorted_cards:
    print(*card)

Submission status: Accepted

Solution code:
class card:
    def __init__(self, suit, value, no):
        self.suit = suit
        self.value = value
        self.no = no
def partition(A, p, r):
    piv = A[r].value
    i = p - 1
    for j in range(p, r):
        if A[j].value <= piv:
            i += 1
            temp = A[j]
            A[j] = A[i]
            A[i] = 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, r)

def isstable(A, n):
    for i in range(n-1):
        if A[i].value == A[i+1].value and A[i].no > A[i+1].no:
            print("Not stable")
            return
    print("Stable")


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

for i in range(n):
    temp = list(input().split())
    ob = card(temp[0], int(temp[1]), i)
    cards.append(ob)
quicksort(cards, 0, n-1)
isstable(cards, n)
for i in range(n):
    print(cards[i].suit + " " + str(cards[i].value))

Submission status: Accepted

Solution code:
class Card:
    def __init__(self,m, v):
        self.m = m
        self.v = v
    
    def __repr__(self):
        return str(self.m) + ' ' + str(self.v)


def quicksort(A, p, r):
    #print("init",p,r)
    if p < r:
        #print("calcq")
        q = partition(A, p, r)
        #print("q=",q)
        #print("sortleft")
        quicksort(A, p,q-1)
        #print("sortright")
        quicksort(A,q+1,r)

def partition(A, p, r):
  x = A[r]
  i = p-1
  #print("s",A,p,r,i)
  for j in range(p,r):
    #print("compr",A[j],x)
    if A[j].v <= x.v:
      i = i+1
      #print("change! idx", i ,j)
      A[i], A[j] = A[j], A[i]
    #print(A)
  A[i+1],A[r] = A[r], A[i+1]
  #print("e",A,p,r,i+1)
  return i+1

cnt = 0
def merge(A, left, mid, right):
  global cnt
  n1 = mid - left
  n2 = right - mid
  #L = [0] * (n1+1)
  #R = [0] * (n2+1)
  #print("init ",left,mid,right,A[left:mid],A[mid:right],n1,n2)
  L = [Card(None,None) for i in range(n1+2)]
  R = [Card(None,None) for i in range(n2+2)]
  #print("check ", L, R)
  for i in range(n1):
    L[i] = A[left + i]
  for i in range(n2):
    R[i] = A[mid + i]
  L[n1].v = 9999999999999
  R[n2].v = 9999999999999
  #print("split ",n1,n2, L, R)
  i = 0
  j = 0
  for k in range(left,right):
    cnt+=1
    if L[i].v <= R[j].v:
      A[k] = L[i]
      i = i + 1
    else:
      A[k] = R[j]
      j = j + 1
  #print("reslt ",A)

def mergeSort(A, left, right):
  #print("margeSort ",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)

A1 = []
A2 = []
n = int(input())

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

quicksort(A1,0,n-1)

mergeSort(A2,0,n)

flag = True
for i in range(n):
    if A1[i].m != A2[i].m:
        flag = False
        print("Not stable")
        break    
if flag:
    print("Stable")

for i in range(0,n):
    print(A1[i])
    #print(A2[i])

Submission status: Accepted

Solution code:
"""マージソートを用いて安定かどうかを確認する。"""

from typing import List, Tuple
import math
import sys


class sort_object:
    """ソート対象のオブジェクト。必要に応じてプロパティやメソッドを増やす。"""

    def __init__(self, value: int, inf1='', inf2=''):
        self.value = value
        self.inf1 = inf1

    def set_value(self, value: int):
        self.set_value = value

    def get_value(self):
        return self.value

    def set_inf1(self, inf1):
        self.inf1 = inf1

    def get_inf1(self):
        return self.inf1

    def set_inf2(self, inf2):
        self.inf2 = inf2

    def get_inf2(self):
        return self.inf2


def merge(A: List[sort_object], left: int, mid: int, right: int) -> None:

    left_list = A[left:mid]
    right_list = A[mid:right]
    left_list.append(sort_object(sys.maxsize))
    right_list.append(sort_object(sys.maxsize))

    i = 0  # left_listのインデックス
    j = 0  # right_listのインデックス
    for k in range(left, right):
        if left_list[i].get_value() <= right_list[j].get_value():
            A[k] = left_list[i]
            i += 1
        else:
            A[k] = right_list[j]
            j += 1


def merge_sort(A: List[sort_object], left: int, right: int) -> int:
    if left + 1 < right:
        mid = math.floor((left + right) / 2)
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)


def partition(A: List[sort_object], p: int, r: int) -> int:
    """パーティション

    A[p, ..., r]を、A[p, ..., q-1]とA[q+1, ..., r]二分割する。
    A[p, ..., q-1]の各要素は A[q]以下とする。
    A[q+1, ..., r]の各要素は A[q]より大きくする。

    Args:
        A (List[int]): 分割対象のリスト
        p (int): 分割対象のリストの先頭のインデックス
        r (int): 分割対象のリストの最後のインデックス

    Returns:
        int: q
    """
    tmp = A[r].get_value()
    i = p - 1
    for j in range(p, r):
        if A[j].get_value() <= tmp:
            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: List[sort_object], p: int, r: int) -> None:
    if p < r:
        q = partition(A, p, r)
        quick_sort(A, p, q - 1)
        quick_sort(A, q + 1, r)
    return


n = int(input())
cards_1 = []
for _i in range(n):
    pic, num = map(str, input().split())
    num = int(num)
    cards_1.append(sort_object(num, pic))
cards_2 = [i for i in cards_1]

quick_sort(cards_1, 0, n - 1)
merge_sort(cards_2, 0, n)

if cards_1 == cards_2:
    print('Stable')
else:
    print('Not stable')
for c in cards_1:
    print(c.get_inf1(), c.get_value())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
クイックソート
"""

N = int(input())
aN = [[None] * 2 for i in range(N)]
for i in range(N):
    suit, num = input().split()
    aN[i][0] = suit
    aN[i][1] = int(num)

def partition(p, r):
    # 今回は基準xの選び方が最後尾固定だけど、
    # これをうまく選ぶ方がクイックソートは高速になる
    x = aN[r][1]
    i = p-1
    for j in range(p, r):
        if aN[j][1] <= x:
            i = i+1
            aN[i], aN[j] = aN[j], aN[i]
    aN[i+1], aN[r] = aN[r], aN[i+1]
    # 基準となった末尾要素のindex
    return i+1

def quick_sort(p, r):
    if p < r:
        # 再帰処理の中でパーティションを使う
        q = partition(p, r)
        quick_sort(p, q-1)
        quick_sort(q+1, r)

# 安定比較用にライブラリで安定ソートする
aN2 = sorted(aN, key=lambda x: x[1])
quick_sort(0, N-1)

# クイックソートは安定ではないが、
# マージソートに対して、メモリ領域を使わない利点がある
if all([aN[i][0] == aN2[i][0] for i in range(N)]):
    print('Stable')
else:
    print('Not stable')

for i in range(N):
    print(*aN[i])

Submission status: Accepted

Solution code:
# coding: utf-8
import copy

def partition(A, p, r):
    r -= 1
    i = p - 1
    x = A[r][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)
        quick_sort(A, q+1, r)

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

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

if __name__ == "__main__":
    # n = 6
    # A = [('D', 3), ('H', 2), ('D', 1), ('S', 3), ('D', 2), ('C', 1)]
    n = int(input())
    A = []
    for _ in range(n):
        mark, num = input().split()
        num = int(num)
        A.append((mark, num))
    B = copy.deepcopy(A)

    quick_sort(A, 0, len(A))
    merge_sort(B, 0, len(B))

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

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

Submission status: Accepted

Solution code:
import sys
import operator
import collections


Card = collections.namedtuple('Card', ('suit', 'value'))


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(sys.stdin.readline())
a = []
for _ in range(n):
    suit, value = sys.stdin.readline().split()
    a.append(Card(suit, int(value)))

stable = sorted(a, key=operator.itemgetter(1))
quick_sort(a, 0, n - 1)

print('Stable' if a == stable else 'Not stable')
for suit, value in a:
    print(f'{suit} {value}')

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 _ in range(n):
    mark, num = map(str, input().split())
    data.append([mark, int(num)])
data1 = copy.deepcopy(data)

quicksort(data, 0, n-1)

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

for d in data:
    print(' '.join(str(dd) for dd in d))

Submission status: Accepted

Solution code:
import copy

def quicksort(li, ini_i, length):
    # print(li, ini_i, length)
    if ini_i < length:
        next_len = partition(li, ini_i, length)
        # print(next_len)
        quicksort(li, ini_i, next_len - 1)
        quicksort(li, next_len + 1, length)

def partition(li, ini_i, length):
    target = li[length][1]
    # print(target, li, ini_i, length)
    for i in range(ini_i, length):
        if li[i][1] <= target:
            li[ini_i], li[i] = li[i], li[ini_i]
            ini_i += 1
    # print(f"its {ini_i}")
    li[ini_i], li[length] = li[length], li[ini_i]
    return ini_i

length = int(input())
li = []
base_li = []
for i in range(length):
    t = input().split(" ")
    t[1] = int(t[1])
    base_li.append(t)
li = copy.deepcopy(base_li)

quicksort(li, 0, length - 1)

for i in range(length - 1):
    if li[i + 1][1] == li[i][1]:
        if base_li.index(li[i + 1]) < base_li.index(li[i]):
            print("Not stable")
            break
else:
    print("Stable")
for i, n in enumerate(li):
    print(*n)

Submission status: Accepted

Solution code:
def partition(A,p,r):#A[p]〜A[r-1]までのリストをpartitionする
    x=A[r-1][1]
    i=p-1
    for j in range(p,r-1):
        if(A[j][1] <= x):
            i+=1
            A[j],A[i]=A[i],A[j]
    A[i+1],A[r-1]=A[r-1],A[i+1]
    return i+1
    

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

        


def stability_judge(sorted,original):
    n=len(sorted)
    j=-1
    x=sorted[0][1]
    for i in range(n):
        if(x!=sorted[i][1]):
            x=sorted[i][1]
            j=-1
        
        while(1):
            j+=1
            if(x==original[j][1]):
                if(sorted[i][0]!=original[j][0]):
                    return 0
                else:
                    break
    return 1





n=int(input())
original_cards=[]
for loop in range(n):
    original_cards.append(list(input().split()))
for card in original_cards:
    card[1]=int(card[1])

sorted_cards=[card for card in original_cards]
quick_sort(sorted_cards,0,n)

if(stability_judge(sorted_cards,original_cards)):
    print("Stable")
else:
    print("Not stable")



for card in sorted_cards:
    card[1]=str(card[1])
    print(" ".join(card))

Submission status: Accepted

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

n = int(input())
a = [list(input().split()) for i in range(n)]

for i in range(n):
    a[i][1] = int(a[i][1])
b = copy.deepcopy(a)
quicksort(a, 0, n-1)


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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
writelines = sys.stdout.writelines
N = int(input())
A = []
D = {}
for i in range(N):
    v, d = readline().split()
    A.append((v, int(d)))
    D.setdefault(int(d), []).append(v)

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

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

D = {k: iter(v).__next__ for k, v in D.items()}

quicksort(A, 0, N-1)
ok = 1
for v, d in A:
    if D[d]() != v:
        ok = 0
ans = ['Stable\n' if ok else 'Not stable\n']
for v, d in A:
    ans.append("%s %d\n" % (v, d))
writelines(ans)

Submission status: Accepted

Solution code:
import sys

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, A


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

n = int(sys.stdin.readline())
cards = []
for _ in range(n):
    s,t = sys.stdin.readline().split()
    cards.append([s, int(t)])

orig = cards[:]
Quicksort(cards, 0, n-1)
mm=[c[0] for c in cards]
nn=[c[1] for c in cards]
cc=[]
for k in nn:
    if k in cc: continue
    cc.append(k)
    if nn.count(k)<=1: continue
    a=[]
    b=[]
    for o in orig:
        if o[1]==k:  a.append(o[0])
    for p in cards:
        if p[1]==k:  b.append(p[0])
    if a!=b:
        print('Not stable')
        break
else:
    print('Stable')

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

Submission status: Accepted

Solution code:
def Partition(A,p,r): ## r = n-1 (A의 p~r번째(0 base)요소를 partition!)
    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[r], A[i+1] = A[i+1], A[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 = []
color = [[]for i in range(4)] #S H C D
for i in range(n):
    a,v = input().split()
    v = int(v)
    A.append((a,v))
copya = A[:]
Quicksort(A, 0, n-1)
Avdic = dict()
for a,v in A:
    if (v not in Avdic.keys()):
        Avdic[v] = [a]
    else:
        Avdic[v] += [a]
cvdic = dict()
for a,v in copya:
    if (v not in cvdic.keys()):
        cvdic[v] = [a]
    else:
        cvdic[v] += [a]
if (Avdic == cvdic):
    print('Stable')
else:
    print('Not stable')
for a in A:
    print(*a)

Submission status: Accepted

Solution code:
#! /usr/local/bin/python3
# coding: utf-8

from sys import stdin
from math import inf

def merge(A, left, mid, right):
    L = A[left:mid]; L.append(("", inf))
    R = A[mid:right]; R.append(("", inf))
    i = iter(L); l = next(i)
    j = iter(R); r = next(j)
    for k in range(left, right):
        if l[1] <= r[1]:
            A[k] = l
            l = next(i)
        else:
            A[k] = r
            r = next(j)

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 swap(A, i, j):
    tmp = A[i]
    A[i] = A[j]
    A[j] = tmp

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
            swap(A, i, j)
    swap(A, i + 1, r)
    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():
    n = int(stdin.readline())
    A = []
    for l in stdin:
        suit, num = l.split()
        A.append((suit, int(num)))
    B = A[:]
    quick_sort(A, 0, n - 1)
    merge_sort(B, 0, n)
    print("Stable" if A == B else "Not stable")
    [print(*a) for a in A]

main()

Submission status: Accepted

Solution code:
import copy

def swap(a, b):
    return b, a

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

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

def merge_sort(A, left, right):
    if left+1 < right:
        mid = (left + right) >> 1
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        return merge(A, left, mid, right)

def read_n_lows_input(n):
    Alist=[[j for j in input().split()] for i in range(n)]
    return Alist

n = int(input())
A = read_n_lows_input(n)
B = copy.deepcopy(A)
quick_sort(A, 0, n-1)
merge_sort(B, 0, n)
if A == B:
    print("Stable")
else:
    print("Not stable")
for i in A:
    print(*i, sep=" ")

Submission status: Accepted

Solution code:
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 = a[left:left+n1]
    r = a[mid:mid+n2]
    l.append(Card('X', float('inf')))
    r.append(Card('X', float('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)


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
            tmp = a[i]
            a[i] = a[j]
            a[j] = tmp
    tmp = a[r]
    a[r] = a[i+1]
    a[i+1] = tmp
    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 = []
b = []
for i in range(n):
    tmp = input().split()
    a.append(Card(tmp[0], int(tmp[1])))
    b.append(Card(tmp[0], int(tmp[1])))

mergeSort(a, 0, n)
quickSort(b, 0, n-1)

is_stable = True
for i in range(n):
    if a[i].suit != b[i].suit:
        is_stable = False
        break

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

for v in b:
    print('%s %d' % (v.suit, v.value))