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:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
Input:
6
D 3
H 2
D 1
S 3
D 2
C 1

Output:
Not stable / Stable
D 1
C 1
D 2
H 2
D 3
S 3
"""
import sys
import copy


def partition(array, start, end):
    x = int(array[end][2:])
    i = start - 1
    assert start <= end
    for j in range(start, end):
        if int(array[j][2:]) <= x:
            i += 1
            array[i], array[j] = array[j], array[i]
    array[i + 1], array[end] = array[end], array[i + 1]
    return i + 1


def quick_sort(array, start, end):
    if start < end:
        cursor = partition(array, start, end)
        quick_sort(array, start, cursor - 1)
        quick_sort(array, cursor + 1, end)
    return array


def merge(A, left, mid, right):
    L = A[left:mid] + ['N ' + str(int(1e9 + 1))]
    R = A[mid:right] + ['N ' + str(int(1e9 + 1))]

    i, j = 0, 0

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

    return None


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


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(lambda x: x.strip('\n'), _input[1:]))
    assert len(array) == array_length

    merge_array = copy.deepcopy(array)

    # print('merge',merge_array)
    merge_result = merge_sort(A=merge_array, left=0, right=array_length)
    # print(*merge_result, sep='\n')

    # print('quick',array)
    quick_result = quick_sort(array=array, start=0, end=array_length - 1)
    if quick_result != merge_result:
        print('Not stable')
    else:
        print('Stable')
    print(*quick_result, sep='\n')

Submission status: Accepted

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

"""
Input:
6
D 3
H 2
D 1
S 3
D 2
C 1

Output:
Not stable / Stable
D 1
C 1
D 2
H 2
D 3
S 3
"""
import sys
import copy


def partition(_array, start, end):
    x = int(_array[end][2:])
    i = start - 1
    assert start <= end
    for j in range(start, end):
        if int(_array[j][2:]) <= x:
            i += 1
            _array[i], _array[j] = _array[j], _array[i]
    _array[i + 1], _array[end] = _array[end], _array[i + 1]
    return i + 1


def quick_sort(_array, start, end):
    if start < end:
        cursor = partition(_array, start, end)
        quick_sort(_array, start, cursor - 1)
        quick_sort(_array, cursor + 1, end)
    return _array


def merge(_array, left, mid, right):
    array_left = _array[left:mid] + ['N ' + str(int(1e9 + 1))]
    array_right = _array[mid:right] + ['N ' + str(int(1e9 + 1))]

    i, j = 0, 0

    for k in range(left, right):
        if int(array_left[i][2:]) <= int(array_right[j][2:]):
            _array[k] = array_left[i]
            i += 1
        else:
            _array[k] = array_right[j]
            j += 1

    return None


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


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(lambda x: x.strip(), _input[1:]))
    # assert len(array) == array_length

    merge_array = copy.deepcopy(array)
    merge_result = merge_sort(_array=merge_array, left=0, right=array_length)
    # print(*merge_result, sep='\n')
    quick_result = quick_sort(_array=array, start=0, end=array_length - 1)

    if quick_result != merge_result:
        print('Not stable')
    else:
        print('Stable')
    print(*quick_result, sep='\n')

Submission status: Accepted

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

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

def checker(A,start,end):
    for i in range(start,end-1):
        if A[i][1]==A[i+1][1]:
            if A[i][2]>A[i+1][2]:
                return "Not stable"
    return "Stable"

n = int(input())
l = []
for i in range(n):
    card = input().split()
    l.append((card[0],int(card[1]),i))
quickSort(l,0,n-1)
print(checker(l,0,n))
for s,n,c in l:
    print("{} {}".format(s,n))

Submission status: Accepted

Solution code:
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 merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]
    R = A[mid:right]
    L.append(('J', 1000000001))
    R.append(('J', 1000000001))
    i = 0  # L[]??¨?????????????????????
    j = 0  # R[]??¨?????????????????????
    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 partition(A, p, r):
    """
    ???????????????????????????????????????A[r]?????°?????????????????????????????????????????????A[r-1]??¨?´??????????????????§??¨???
    """
    x = A[r][1]
    i = p - 1
    for j in range(p, r):
        if A[j][1] <= x:
            i += 1
            temp = A[i]
            A[i] = A[j]
            A[j] = temp
    temp = A[i+1]
    A[i+1] = A[r]
    A[r] = temp
    return i+1


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


if __name__ == '__main__':
    # ??????????????\???
    #cards = [('D', 3), ('H', 2), ('D', 1), ('S', 3), ('D', 2), ('C', 1)]
    #comp_cards = cards[:]
    num_of_cards = int(input())
    cards = []
    for i in range(num_of_cards):
        suit, rank = input().split(' ')
        cards.append((suit, int(rank)))
    comp_cards = cards[:]


    # ??????????????????
    data_length = len(cards)
    quick_sort(cards, 0, data_length-1)
    merge_sort(comp_cards, 0, data_length)  # ?????????????????????????????????????????¨

    # ???????????????
    stable = True  # ?????????????????????????????????????????????
    for x, y in zip(cards, comp_cards):
        if x != y:
            stable = False
            print('Not stable')
            break
    if stable is True:
        print('Stable')

    for c in cards:  # ??????????????¨???
        print('{0} {1}'.format(c[0], c[1]))

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
# AIZU ONLINE JUDGE
# Introduction to Algorithms and Data Structures
# ALDS1_6_C
# Sort II - Quick Sort

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

def quick_sort(A,B, p, r):
    # q??????????????????p??¨r????????????????????°??????????????§???
    # ?????????p?????????q-1???????????§???????????????????????????q+1???r????¶???????
    # ?????§??????????????§????????????????????¨?????????
    if p < r:
        # ???????????£?????§?????????????°??????°?????????
        q = partition(A,B,p,r)
        quick_sort(A,B,p,q-1)
        quick_sort(A,B,q+1,r)

# alds1_2_c??????
def stable_check(sorted_values,sorted_suits,default_values,default_suits,n):
    for i in set(sorted_values):
        check_ss = []
        check_ds = []
        if i in sorted_values:
            for x in xrange(n):
                if i == sorted_values[x]:
                    check_ss.append(sorted_suits[x])
                if i == default_values[x]:
                    check_ds.append(default_suits[x])
            for x in xrange(len(check_ss)):
                if check_ss[x]!=check_ds[x]:
                    return "Not stable"
    return "Stable"

def main():
    n = input()
    A = []
    B = []
    for i in xrange(n):
        b,a = raw_input().split()
        A.append(int(a))
        B.append(b)
    cpA=list(A)
    setA = set(A)
    cpB=list(B)
    quick_sort(A,B,0,n-1)

    # Stable Check
    print stable_check(A,B,cpA,cpB,n)
    for i in xrange(n):
        line = "%s %s"%(B[i],A[i])
        print line

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

class Card:
    def __init__(self, s, n, i):
        self.suit = s
        self.num = n
        self.ini_ord = i

def is_stable(A, n):
    for i in range(n - 1):
        if A[i].num == A[i + 1].num:
            if A[i].ini_ord > A[i + 1].ini_ord:
                return False

    return True

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

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

    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(sys.stdin.readline().rstrip())
cards = []

for i in range(n):
    line = sys.stdin.readline().split()
    cards.append(Card(line[0], int(line[1]), i))

quickSort(cards, 0, n - 1)

if is_stable(cards, n):
    print("Stable")
else:
    print("Not stable")

for i in range(n):
    print(cards[i].suit,str(cards[i].num))

Submission status: Accepted

Solution code:
def is_stable(before_sort, after_sort):
    current_num = 0
    same_number_card = list()
    for num in after_sort:
        if current_num == int(num[1]):
            for same_card in same_number_card:
                if before_sort.index(same_card) > before_sort.index(num):
                    return False
            same_number_card.append(num)
        else:
            current_num = int(num[1])
            same_number_card = [num,]
    return True

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)

if __name__ == '__main__':
    n = int(input())
    cards = list()
    for i in range(n):
        card = input().split()
        card[1] = int(card[1])
        cards.append(card)
    before_cards = list(cards)
    quicksort(cards, 0, n-1)
    print('Stable') if is_stable(before_cards, cards) else print('Not stable')
    for card in cards:
        print(*card)

Submission status: Accepted

Solution code:
def mergesort(A, s, e):
    if s + 1 < e:
        m = (e + s) // 2
        mergesort(A, s, m)
        mergesort(A, m, e)
        merge(A, s, m, e)


def merge(A, s, m, e):
    L = A[s:m] + [('*', 1E10)]
    R = A[m:e] + [('*', 1E10)]
    ix_l = ix_r = 0
    for ix in range(s, e):
        if L[ix_l][1] <= R[ix_r][1]:
            A[ix] = L[ix_l]
            ix_l += 1
        else:
            A[ix] = R[ix_r]
            ix_r += 1


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


if __name__ == '__main__':
    N = int(input().strip())
    AA = [0] * N
    for i in range(N):
        key, val = input().strip().split()
        val = int(val)
        AA[i] = (key, val)
    AA2 = AA[:]
    quicksort(AA, 0, len(AA) - 1)
    mergesort(AA2, 0, len(AA2))
    if all([a == a2 for a, a2 in zip(AA, AA2)]):
        print('Stable')
    else:
        print('Not stable')
    for key, val in AA:
        print('{} {}'.format(key, val))

Submission status: Accepted

Solution code:

def partition(a,b,c,p,r):
  x = a[r]
  i = p - 1
  
  for j in range(p,r):
    if x >= a[j]:
      i += 1
      a[i],a[j] = a[j],a[i]
      b[i],b[j] = b[j],b[i]
      c[i],c[j] = c[j],c[i]
      
  a[i+1],a[r] = a[r],a[i+1]
  b[i+1],b[r] = b[r],b[i+1]  
  c[i+1],c[r] = c[r],c[i+1]
  return i+1
  
def quickSort(a,b,c,p,r):
  if p < r:
    q = partition(a,b,c,p,r)
    quickSort(a,b,c,p,q-1)
    quickSort(a,b,c,q+1,r)
  
def checkStable(a,b):
  for i in range(1,len(a)):
    if a[i-1] == a[i]:
      if b[i-1] > b[i]:
        return "Not stable"
  return "Stable"
  
n = int(input())
mark = [""]*n
num = [0]*n
count = [i for i in range(n)]
for i in range(n):
  mark[i],num[i] = input().split()
num = list(map(int,num))

quickSort(num,mark,count,0,n-1)
print(checkStable(num,count))
for i in range(n):
  print(mark[i],num[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 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 is_stable(A, B):
  ma = {}
  for suit, num in A:
    if num not in ma: ma[num] = []
    ma[num].append(suit)

  mb = {}
  for suit, num in B:
    if num not in mb: mb[num] = []
    mb[num].append(suit)

  for num in ma:
    if ma[num] != mb[num]: return False

  return True

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

B = A[:]
quick_sort(A, 0, len(A) - 1)
print("Stable" if is_stable(A, B) else "Not stable")
for suit, num in A: print("{} {}".format(suit, num))

Submission status: Accepted

Solution code:
from collections import namedtuple

Card = namedtuple('Card', ['suit', 'value', 'init'])

def QuickSort(A, begin, end):
    if end - begin <= 1:
        return

    piv = A[end - 1].value
    left, right = begin, begin

    for i in range(begin, end - 1):
        if A[i].value <= piv:
            if i - left > 0:
                A[left], A[i] = A[i], A[left]
            left += 1

    A[left], A[end - 1] = A[end - 1], A[left]

    QuickSort(A, begin, left)
    QuickSort(A, left + 1, end)

n = int(input())

A = []

for i in range(n):
    suit, value = input().split()
    value = int(value)
    A.append(Card(suit, value, i))

QuickSort(A, 0, n)

for i in range(n - 1):
    if A[i].value == A[i + 1].value and A[i].init > A[i + 1].init:
        print('Not stable')
        break
else:
    print('Stable')

for a in A:
    print(a.suit, a.value)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import namedtuple

Card = namedtuple('Card', ['suit', 'value', 'init'])

def QuickSort(A, begin, end):
    if end - begin <= 1:
        return

    piv = A[end - 1].value
    left, right = begin, begin

    for i in range(begin, end - 1):
        if A[i].value <= piv:
            if i - left > 0:
                A[left], A[i] = A[i], A[left]
            left += 1

    A[left], A[end - 1] = A[end - 1], A[left]

    QuickSort(A, begin, left)
    QuickSort(A, left + 1, end)

n = int(stdin.readline())
A = [None] * n

for i in range(n):
    suit, value = stdin.readline().split()
    A[i] = Card(suit, int(value), i)

QuickSort(A, 0, n)

for i in range(n - 1):
    if A[i].value == A[i + 1].value and A[i].init > A[i + 1].init:
        print('Not stable')
        break
else:
    print('Stable')

for a in A:
    print(a.suit, a.value)

Submission status: Accepted

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

def merge(A, left, mid, right):
    L = A[left:mid] + [[0,1000000001]]
    R = A[mid:right] + [[0,1000000001]]
    i = j = 0
    for k in range(left, right):
        if int(L[i][1]) <= int(R[j][1]):
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
 
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 = [input().split() for i in range(n)]
B = A[:]
quicksort(A, 0, n-1)
mergeSort(B, 0, n)

juge = 1
for i in range(n):
 if A[i] != B[i]:
  juge = 0
  break
if juge == 1:
 print("Stable")
else:
 print("Not stable")

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

Submission status: Accepted

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

r = int(input())
a = []
for i in range(r):
   c = input().split()
   a.append((c[0],int(c[1]),i))
quickSort(a, 0, r-1)
print(check(a,0,r))
for s,r,d in a:
   print("{} {}".format(s,r))

Submission status: Accepted

Solution code:
# coding=utf-8

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


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

quick_sort(cards, 0, n-1)

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

for i in range(n):
    print(cards[i][0], cards[i][1])

Submission status: Accepted

Solution code:
def main():
    n = input()
    A = []
    for i in range(n):
        A.append(raw_input())
    B = A[:]
    
    quickSort(A,0,n-1)
    mergeSort(B,0,n)

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

    for item in A:
        print item


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 = int(A[r][2:])
    i = p - 1
    for j in range(p,r):
        if int(A[j][2:]) <= x:
            i += 1
            a = A[i]
            A[i] = A[j]
            A[j] = a
    b = A[i+1]
    A[i+1] = A[r]
    A[r] = b
    return i+1


def merge(A,left,mid,right):
    n1 = mid - left
    n2 = right - mid
    L = [A[left+i] for i in range(n1)]
    L += ["L inf"]
    R = [A[mid+i] for i in range(n2)]
    R += ["R inf"]
    i = 0
    j = 0
    for k in range(left,right):
        if float(L[i][2:]) <= float(R[j][2:]):
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

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


if __name__ == "__main__":
    main()

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 = i + 1
            temp = A[i]
            A[i] = A[j]
            A[j] = temp
    temp = A[i+1]
    A[i+1] = A[r]
    A[r] = temp
    return i+1


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


def isStable(A):
    for i in range(0, len(A)-1):
        if A[i][1] == A[i+1][1]:
            if A[i][2] > A[i+1][2]:
                return False
    return True

if __name__ == "__main__":
    n = int(sys.stdin.readline())
    B = []
    for i in range(n):
        c = sys.stdin.readline().split()
        B.append([c[0], int(c[1]), i])
    quickSort(B, 0, n-1)
    if isStable(B):
        print("Stable")
    else:
        print("Not stable")
    for b in B:
        print(b[0], b[1])

Submission status: Accepted

Solution code:
import sys

def swap(A, i, j):
    x = A[i]
    A[i] = A[j]
    A[j] = x

def partition(A, p, r, idx):
    x = A[r][idx]                # 1 x = A[r]
    i = p - 1                    # 2 i = p-1
    for j in range(p, r):        # 3 for j = p to r-1
        if A[j][idx] <= x:       # 4     if A[j] <= x
            i += 1               # 5        then i = i+1
            if(i != j):
                swap(A, i, j)    # 6        exchange A[i] and A[j] 
    i += 1 
    swap(A, i, r)                # 7 exchange A[i+1] and A[r]
    return i                     # 8 return i+1

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

def main():
    """ ????????? """
    num = int(input().strip())
    istr = sys.stdin.read()
    cards = list(istr.splitlines())
    
    A = [[0,0] for i in range(num)]
    B = [[0,0] for i in range(num)]
    
    for i in range(num):
        A[i][0] = cards[i][0]
        A[i][1] = int(cards[i][2:])
        B[i][0] = cards[i][0]
        B[i][1] = int(cards[i][2:])

    quickSort(A, 0, num-1,1)
    B.sort(key = lambda d:d[1])
    res = "Stable"
    for i in range(num):
        if A[i][0] != B[i][0] or A[i][1] != B[i][1]:
            res = "Not stable"
            break

    print(res)
    for x in A:
        print(" ".join(map(str, x)))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy

n = int(raw_input())
a = [] 
        
for i in range(n):
    char, num = raw_input().split()
    num = int(num)
    a.append([char, num])

a_original = copy.copy(a)
    
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)
        
quickSort(a, 0, n-1)
for i in range(n-1):
    if a[i][1] == a[i+1][1]:
        if a_original.index(a[i]) > a_original.index(a[i+1]):
            print 'Not stable'
            break
else:
     print 'Stable'       

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

Submission status: Accepted

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


def partition(a, p, r):
    pivot = a[r]
    i = p-1
    for j in range(p, r):
        if compare(pivot, a[j]) >= 0:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[r], a[i+1] = a[i+1], a[r]
    return i+1

def compare(a,b):
    if a[0] > b[0]:
        return 1
    elif a[0] < b[0]:
        return -1
    else:
        return 0

n = int(raw_input())
a = []
suits = {}
for _ in range(n):
    suit, number = raw_input().split(' ')
    number = int(number)
    a.append((number, suit))
    if number not in suits:
        suits[number] = []
    suits[number].append(suit)

sort(a, 0, len(a)-1)

flag = True
for number, suit in a:
    correct_suit = suits[number].pop(0)
    if suit != correct_suit:
        flag = False
        break

if flag:
    print "Stable"
else:
    print "Not stable"

for number, suit in a:
    print suit, number

Submission status: Accepted

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

    for j in range(p,r-1):
        if int(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 qsort(A,p,r):
    if p < r:
        q = partition(A,p,r)
        qsort(A,p,q)
        qsort(A,q+1,r)
    return A

def isStable(a):
    length = int(len(a))
    for i in range(length):
        for j in range(i+1,length-1) :
            if a[i][1] == a[j][1] and a[i][2] > a[j][2]:
                return False
                break
    return True

if __name__ == '__main__':
    cnt = int(input())
    A = []
    for i in range(cnt):
        N = input().split()
        N.append(i)
        A.append(N)
    p = 0
    r = len(A)
    B = qsort(A,p,r)
    if isStable(B):
        print("Stable")
    else:
        print("Not stable")
    for i in B:
        print ("{0} {1}".format(i[0],i[1]))

Submission status: Accepted

Solution code:
def num(card):
    return int(card[2:])

def partition(A, p, r):
    x = num(A[r])
    i = p - 1
    for j in range(p, r):
        if num(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(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() for _ in range(n)]
B = sorted(A, key=num)
quicksort(A, 0, n - 1)

msg = "Stable"
for i in range(n):
    if A[i] != B[i]:
        msg = "Not stable"
        break

print(msg)
for card in A:
    print(card)

Submission status: Accepted

Solution code:
def num(card):
    return int(card[2:])

def partition(A, p, r):
    x = num(A[r])
    i = p - 1
    for j in range(p, r):
        if num(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(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, B):
    C = B[:]
    for card in A:
        i = C.index(card)
        if i == 0:
            pass
        elif num(C[i - 1]) == num(card):
            return False
        del C[i]
    return True

n = int(input())
A = [input() for _ in range(n)]
B = A[:]
quicksort(B, 0, n - 1)

print("Stable" if is_stable(A, B) else "Not stable")
for card in B:
    print(card)

Submission status: Accepted

Solution code:
def num(card):
    return int(card[0][2:])

def partition(A, p, r):
    x = num(A[r])
    i = p - 1
    for j in range(p, r):
        if num(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(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(n - 1):
        if num(A[i]) == num(A[i + 1]) and A[i][1] > A[i + 1][1]:
            return False
    return True

n = int(input())
A = [(input(), i) for i in range(n)]
quicksort(A, 0, n - 1)

print("Stable" if is_stable(A) else "Not stable")
for card in A:
    print(card[0])

Submission status: Accepted

Solution code:
def swap(A,i,j):
    A[i],A[j] = A[j],A[i]
    return A

def isStable(A):
    for i in range(1, len(A)):
        if A[i][1] == A[i-1][1]:
            if A[i][2] < A[i-1][2]:
                return False
    return True

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

def quick(A,p=0,r=None):
    if r is None:
        r = len(A)-1
    if p < r:
        q = partition(A,p,r)
        quick(A,p,q-1)
        quick(A,q+1,r)

import sys
if __name__ == "__main__":
    n = int(sys.stdin.readline())
    A = []
    for i in range(n):
        card = sys.stdin.readline().split()
        A.append([card[0], int(card[1]), i])
    quick(A,0,n-1)
    if isStable(A):
        print("Stable")
    else:
        print("Not stable")
    for card in A:
        print(card[0], card[1])

Submission status: Accepted

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

b = a[:]

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 checkStable(a):
    for i in range(len(a) - 1):
        if a[i][1] == a[i + 1][1] and a[i][2] > a[i + 1][2]:
            return "Not stable"
    return "Stable"

quickSort(a, 0, n - 1)

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