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 num_from_card(card):
    return int(card[2:])

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

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

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

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

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

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

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

for c in cards:
    print(c)

Submission status: Accepted

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

# Aizu Online Judge. Quick Sort
import sys

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

def partition(A, p, r):
    x = A[r].val
    i = p-1
    for n in range (p,r):
        if A[n].val <= x:
            i += 1
            A[i], A[n] = A[n], 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 check_stable(A):
    prev_val = None
    for card in A:
        if card.val == prev_val:
            if card.pos < prev_pos:
                print('Not stable')
                return
        prev_val = card.val
        prev_pos = card.pos

    print('Stable')
    return


n = int(sys.stdin.readline())
A = list()
for pos in range(n):
    suit, val_s = sys.stdin.readline().split()
    A.append(Card(suit, int(val_s), pos))

quicksort(A, 0, n-1)
check_stable(A)
for card in A:
    print(card.suit, card.val)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n = int(input())
trump = []
for i in range(n):
    str, num = input().split()
    num = int(num)
    trump.append((str, num, i))

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

def 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 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 False
    return True


quick_sort(trump,0,n)
if(isStable(trump)):
    print('Stable')
else:
    print('Not stable')
for i in trump:
    print('{} {}'.format(i[0], i[1]))

Submission status: Accepted

Solution code:
INF = 10**10


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

    ary[i + 1], ary[r] = ary[r], ary[i + 1]

    return i + 1


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


def merge(ary, left, mid, right):
    lry = ary[left:mid]
    rry = ary[mid:right]
    lry.append(('INF', INF))
    rry.append(('INF', INF))

    i = 0
    j = 0
    for k in range(left, right):
        if lry[i][1] <= rry[j][1]:
            ary[k] = lry[i]
            i += 1
        else:
            ary[k] = rry[j]
            j += 1

    return right - left


def merge_sort(ary, left, right):
    cnt = 0
    if left + 1 < right:
        mid = (left + right) // 2
        cnt += merge_sort(ary, left, mid)
        cnt += merge_sort(ary, mid, right)
        cnt += merge(ary, left, mid, right)

    return cnt


# if __name__ == '__main__':
import sys
from copy import deepcopy

n = int(input())
# ary = [(lambda x: (x[0], int(x[1])))(input().split()) for i in range(n)]

ary = [(lambda x: (x[0], int(x[1])))(line.strip().split()) for line in sys.stdin]

qary = deepcopy(ary)
mary = deepcopy(ary)
quick_sort(qary, 0, n - 1)
merge_sort(mary, 0, n)

if qary == mary:
    print('Stable')
else:
    print('Not stable')
[print(*_) for _ in qary]

Submission status: Accepted

Solution code:
INF = 10**10


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

    ary[i + 1], ary[r] = ary[r], ary[i + 1]

    return i + 1


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


def merge(ary, left, mid, right):
    lry = ary[left:mid]
    rry = ary[mid:right]
    lry.append(('INF', INF))
    rry.append(('INF', INF))

    i = 0
    j = 0
    for k in range(left, right):
        if lry[i][1] <= rry[j][1]:
            ary[k] = lry[i]
            i += 1
        else:
            ary[k] = rry[j]
            j += 1

    return right - left


def merge_sort(ary, left, right):
    cnt = 0
    if left + 1 < right:
        mid = (left + right) // 2
        cnt += merge_sort(ary, left, mid)
        cnt += merge_sort(ary, mid, right)
        cnt += merge(ary, left, mid, right)

    return cnt


if __name__ == '__main__':
    import sys
    from copy import deepcopy

    n = int(input())
    ary = [(lambda x: (x[0], int(x[1])))(line.strip().split()) for line in sys.stdin]

    qary = deepcopy(ary)
    mary = deepcopy(ary)
    quick_sort(qary, 0, n - 1)
    merge_sort(mary, 0, n)

    if qary == mary:
        print('Stable')
    else:
        print('Not stable')
    [print(*_) for _ in qary]

Submission status: Accepted

Solution code:
INF = 10**10


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

    ary[i + 1], ary[r] = ary[r], ary[i + 1]

    return i + 1


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


def merge(ary, left, mid, right):
    lry = ary[left:mid]
    rry = ary[mid:right]
    lry.append(('INF', INF))
    rry.append(('INF', INF))

    i = 0
    j = 0
    for k in range(left, right):
        if lry[i][1] <= rry[j][1]:
            ary[k] = lry[i]
            i += 1
        else:
            ary[k] = rry[j]
            j += 1

    return right - left


def merge_sort(ary, left, right):
    cnt = 0
    if left + 1 < right:
        mid = (left + right) // 2
        cnt += merge_sort(ary, left, mid)
        cnt += merge_sort(ary, mid, right)
        cnt += merge(ary, left, mid, right)

    return cnt


if __name__ == '__main__':
    import sys
    from copy import deepcopy

    n = int(input())
    # ary = [(lambda x: (x[0], int(x[1])))(line.strip().split()) for line in sys.stdin]
    ary = [(lambda x: (x[0], int(x[1])))(input().split()) for i in range(n)]

    qary = deepcopy(ary)
    mary = deepcopy(ary)
    quick_sort(qary, 0, n - 1)
    merge_sort(mary, 0, n)

    if qary == mary:
        print('Stable')
    else:
        print('Not stable')
    [print(*_) for _ in qary]

Submission status: Accepted

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

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

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


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


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

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

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


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


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

mergeSort(merge_cards, 0, n)

quick_sort(cards, 0, n - 1)

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

for card in cards:
    print(*card)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

B = deepcopy(A)



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

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

    

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


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




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

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

Submission status: Accepted

Solution code:
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
            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 print_a(a):
    for x in a:
        print(x["design"], x["value"])


n = int(input())
a = []
for _ in range(n):
    s = input().split()
    a.append({"design": s[0], "value": int(s[1])})
b = a.copy()

quick_sort(a, 0, n - 1)

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

print_a(a)

Submission status: Accepted

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

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

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

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

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

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, p, r):
    if p < r:
        q = partition(a, p, r)
        quicksort(a, p, q-1)
        quicksort(a, q+1, r)
   
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'
       
import sys
n = int(sys.stdin.readline())
a = []
for i in range(n):
    suit, num = sys.stdin.readline().split()
    a += [[suit, int(num), i]]
   
quicksort(a, 0, len(a) - 1)
print(check_stable(a))
   
for line in a:
    print(line[0],line[1])

Submission status: Accepted

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

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

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

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

    return 'Stable'

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

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


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


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


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

Submission status: Accepted

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


def merge(A, left, mid, right):
    L = A[left:mid] + [[10000000000, 'S']]
    R = A[mid:right] + [[10000000000, 'S']]

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

n = int(input())
lstA = []
for i in range(n):
    C, N = input().split()
    k = [int(N), C]
    lstA.append(k)

lstB = copy.copy(lstA)
mergeSort(lstA, 0, n)
quicksort(lstB, 0, n-1)

if lstA == lstB:
    print('Stable')

else:
    print('Not stable')

for i in lstB:
    print(i[1], i[0])

Submission status: Accepted

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

def Merge(As, Ms, l, m, r):
    global cnt
    cnt += r - l
    L = As[l:m] + [float('inf')]
    R = As[m:r] + [float('inf')]
    Lm = Ms[l:m]
    Rm = Ms[m:r]
    i, j = 0, 0
    for k in range(l, r):
        if L[i] <= R[j]:
            As[k] = L[i]
            Ms[k] = Lm[i]
            i += 1
        else:
            As[k] = R[j]
            Ms[k] = Rm[j]
            j += 1
    return

def MergeSort(As, Ms, l, r):
    if r - l > 1:
        m = (l + r) // 2
        MergeSort(As, Ms, l, m)
        MergeSort(As, Ms, m, r)
        Merge(As, Ms, l, m, r)
    return

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

def QuickSort(A, p, r):
    if p < r:
        m = Partition(A, p, r)
        QuickSort(A, p, m-1)
        QuickSort(A, m+1, r)

n = int(input())
M, A = [], []
for i in range(n):
    a, b = input().split()
    M.append(a)
    A.append(int(b))
As = A[:]
Ms = M[:]
QuickSort(A, 0, n-1)
MergeSort(As, Ms, 0, n)
if M == Ms:
    print('Stable')
else:
    print('Not stable')
for i in range(n):
    print('{} {}'.format(M[i], A[i]))

Submission status: Accepted

Solution code:
def make_card(i, card):
    suit, value = card.split()
    return (int(value), i, card)


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


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


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


n = int(input())
a = list(make_card(i, input()) for i in range(n))
b = a[:]

quick_sort(a, 0, n - 1, partition_not_stable)
quick_sort(b, 0, n - 1, partition_stable)
print(('S' if a == b else 'Not s') + 'table')
print('\n'.join(card[2] for card in a))

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 stable(A,Q):
    for i in range(1,len(Q)):
        if int(Q[i-1][1]) == int(Q[i][1]):
            x = A.index(Q[i-1])
            y = A.index(Q[i])
            if y<x:
                return 'Not stable'
    return 'Stable'

n = int(input())
A = []
for i in range(n):
    a = input().split()
    a[1]=int(a[1])
    A.append(a)
Q = A.copy()
quicksort(Q, 0, n-1)
print(stable(A,Q))
for i in range(len(Q)):
    print(Q[i][0], Q[i][1])

Submission status: Accepted

Solution code:
def partition(a, p, r):
    """パーティション分割"""
    x = int(a[r].split()[1])
    i = p - 1
    for j in range(p, r):
        if int(a[j].split()[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 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())
li = [input().splitlines()[0] for x in range(n)]
stable = sorted(li, key=lambda x: int(x.split()[1]))
# print(f"{li=}")
# print(f"{stable=}")

quick_sort(li, 0, n - 1)
# print(f"{li=}")
print("S" if stable == li else "Not s", end="")
print("table")
for i in li:
    print(i)

Submission status: Accepted

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

def isStable(inData, outData, N):
    for i in range(N):
        if inData[i][0] != outData[i][0]:
            return False
    return True

def merge(A, left, mid, right):

    n1 = mid - left
    n2 = right - mid
    
    L = list(range(n1+1))
    R = list(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] = ['ban', 100000000000]
    R[n2] = ['ban', 100000000000]
    
    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
            
    return
            
def mergeSort(A, left, right):
    count = 0
    if left+1 < right:
        mid = int((left + right) / 2)
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)

    return


import sys
import copy

n = int(sys.stdin.readline())
a = []
for _ in range(n):
    tin = list(sys.stdin.readline().split())
    a.append([tin[0], int(tin[1])])
b = copy.deepcopy(a)

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

if isStable(a, b, n):
    print('Stable')
else:
    print('Not stable')

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

Submission status: Accepted

Solution code:
n = int(input())
cards = []
for i in range(n):
    sign, num = input().split(' ')
    cards.append((int(num), sign))

#in: A list of (num, sign) p:start r:end
#out: return i+1
def partition(A, p, r):
    pivot = A[r][0]
    i = p-1
    for j in range(p, r):
        if A[j][0]<= pivot:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

#in: list of (num, sign)
#out: none  overwrite list
def quick_sort(cards, p, r):
    if p >= r:
        return
    pivot = partition(cards, p, r)
    quick_sort(cards, p, pivot-1)
    quick_sort(cards, pivot+1, r)

def merge(list1, list2):
    output = []
    p1 = 0
    p2 = 0
    l1 = len(list1)
    l2 = len(list2)
    while p1 < l1 and p2 < l2:
        if list1[p1][0] <= list2[p2][0]:
            output.append(list1[p1])
            p1 += 1
        else:
            output.append(list2[p2])
            p2 += 1
    return output + list1[p1:] + list2[p2:]

#in: A list of (num, sign)
#out: none overwrite
def merge_sort(cards):
    if len(cards) <= 1:
        return cards
    else:
        pivot = len(cards)//2
        return merge(merge_sort(cards[:pivot]), merge_sort(cards[pivot:]))
        
quick = cards.copy()
quick_sort(quick, 0, len(quick)-1)
merge = merge_sort(cards)

for i in range(n):
    if quick[i][1] != merge[i][1]:
        print("Not stable")
        break
else:
    print("Stable")

for num, sign in quick:
    print( sign + ' ' + str(num))

Submission status: Accepted

Solution code:
def partition(A,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 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 i in range(n)]
a_before=a[:]
quickSort(a,0,n-1)
isStable=True
for i in range(1,n):
    if a[i][1]==a[i-1][1] and a_before.index(a[i])<a_before.index(a[i-1]):
        isStable=False
        break
if isStable:
    print("Stable")
else:
    print("Not stable")
for i in a:
    print(" ".join(i))

Submission status: Accepted

Solution code:
from copy import copy

def merge(arr, left, middle, right):
    L = arr[left:middle]
    L.append([None, float('inf')])
    R = arr[middle:right]
    R.append([None, float('inf')])

    iterL, iterR = iter(L), iter(R)
    l,r = next(iterL), next(iterR)

    for index in range(left, right):
        if l[1] <= r[1]:
            arr[index] = l
            l = next(iterL)
        else:
            arr[index] = r
            r = next(iterR)


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


def partition(arr, start, end):
    criteria = arr[end][1]
    idx1 = start
    for idx2 in range(start, end):
        if arr[idx2][1] <= criteria:
            arr[idx1],arr[idx2] = arr[idx2],arr[idx1]
            idx1 += 1
    arr[idx1],arr[end] = arr[end],arr[idx1]
    return idx1

def quick_sort(arr, start, end):
    if start < end:
        pivot = partition(arr, start, end)
        quick_sort(arr, start, pivot - 1)
        quick_sort(arr, pivot +1, end)


num = int(input())
arr = []
for index in range(num):
    sign, number = input().split()
    arr.append([sign, int(number)])

arr1 = copy(arr)
arr2 = copy(arr)

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

print("Stable" if arr1 == arr2 else "Not stable")
for sign, number in arr2:
    print(sign + " " + str(number))

Submission status: Accepted

Solution code:

def partition(A,p,r):
    x = A[r]
    i = p-1
    for j in range(p,r):
        if A[j][1] <= x[1]:
            i+=1
            A[i],A[j] = A[j],A[i]
    A[i+1],A[r] = A[r],A[i+1]
    return i+1
    
def quickSort(A,p,r):
    if p<r:
        q = partition(A,p,r)
        quickSort(A,p,q-1)
        quickSort(A,q+1,r)
        
n = int(input())
data = []
for i in range(n):
    m,num = map(str,input().split())
    data.append([m, int(num)])
data1 = 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 i in data:
    print(' '.join(str(d) for d in i))