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: Time Limit Exceeded

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

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

class card(object):
    def __init__(self, str):
        data = str.split()
        self.symbol,self.num = data[0],int(data[1])
    
    def __le__(self,obj):
        if(self.num <= obj.num):
            return True
        else:
            return False
    def __ge__(self,obj):
        if(self.num >= obj.num):
            return True
        else:
            return False

    def display_card(self):
        print("{0} {1}".format(self.symbol,self.num))

c = []        
n = int(input())
while(n>0):
    c.append(card(input()))
    n -= 1
c_org = c.copy()

qsort(c,0,len(c)-1)

notstable = False
for i in range(1,len(c)):
    if(c[i-1].num == c[i].num):
        firstCard = c[i-1]
        secondCard = c[i]
        is_found_1st = False
        is_found_2nd = False

        for org in c_org:
            if(org == firstCard):
                if is_found_2nd:
                    notstable = True
            if(org == secondCard):
                is_found_2nd = True
if(notstable == 1):
    print('Not stable')
else:
    print('Stable')
for x in c:
    x.display_card()

Submission status: Time Limit Exceeded

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

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

class card(object):
    def __init__(self, str):
        data = str.split()
        self.symbol,self.num = data[0],int(data[1])
    
    def __le__(self,obj):
        if(self.num <= obj.num):
            return True
        else:
            return False
    def __ge__(self,obj):
        if(self.num >= obj.num):
            return True
        else:
            return False

    def display_card(self):
        print("{0} {1}".format(self.symbol,self.num))

c = []        
n = int(input())
while(n>0):
    c.append(card(input()))
    n -= 1
c_org = c.copy()

qsort(c,0,len(c)-1)

notstable = False
for i in range(1,len(c)):
    if(c[i-1].num == c[i].num):
        firstCard = c[i-1]
        secondCard = c[i]
        is_found_1st = False
        is_found_2nd = False

        for org in c_org:
            if(org == firstCard):
                is_found_1st = True
                if is_found_2nd:
                    notstable = True
                    break
            if(org == secondCard):
                is_found_2nd = True
                if(is_found_1st == True):
                    break
                else:
                    notstable = True
                    break
if(notstable == 1):
    print('Not stable')
else:
    print('Stable')
for x in c:
    x.display_card()

Submission status: Time Limit Exceeded

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

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

class card(object):
    def __init__(self, str):
        data = str.split()
        self.symbol,self.num = data[0],int(data[1])
    
    def __le__(self,obj):
        if(self.num <= obj.num):
            return True
        else:
            return False
    def __ge__(self,obj):
        if(self.num >= obj.num):
            return True
        else:
            return False

    def display_card(self):
        print("{0} {1}".format(self.symbol,self.num))

c = []        
n = int(input())
while(n>0):
    c.append(card(input()))
    n -= 1
c_org = c.copy()

qsort(c,0,len(c)-1)

notStable = False
for i in range(1,len(c)):
    if(c[i-1].num == c[i].num):
        firstCard = c[i-1]
        secondCard = c[i]
        is_found_1st = False
        is_found_2nd = False

        for org in c_org:
            if(org == firstCard):
                is_found_1st = True
            if(org == secondCard):
                is_found_2nd = True
                if(is_found_1st == True):
                    break
                else:
                    notStable = True
                    break
if(notStable == 1):
    print('Not stable')
else:
    print('Stable')
for x in c:
    x.display_card()

Submission status: Time Limit Exceeded

Solution code:
class Quicksort:
    def quicksort(self, a, p, r):
        if p < r:
            q = self.partion(a, p, r)
            self.quicksort(a, p, q - 1)
            self.quicksort(a, q + 1, r)
        return(a)

    def partion(self, 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 bubbleSort(a, n):
    flag = 1
    while flag == 1:
        flag = 0
        for j in range(n-1, 0, -1):
            if a[j][1] < a[j - 1][1]:
                a[j], a[j-1] = a[j-1], a[j]
                flag = 1
    return(a)

if __name__ == '__main__':
    n = int(input().rstrip())
    cards = []
    for i in range(n):
        tmp = input().rstrip().split(" ")
        tmp[1] = int(tmp[1])
        cards.append(tmp)
    a = cards[:]
    b = cards[:]
    
    x = Quicksort()
    a = x.quicksort(a, 0, n-1)
        
    b = bubbleSort(b, n)

    if a == b:
        print("Stable")
    else:
        print("Not stable")
    
    for i in a:
        i[1] = str(i[1])
        print(" ".join(i))

Submission status: Time Limit Exceeded

Solution code:
def partition(A,p,r):
    x=A[r][1]
    i=p-1
    for j in xrange(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 bubblesort(a,n):
    flag=1
    while flag:
        flag=0
        if n==0:
            break
        else :
            for i in xrange(n-1,0,-1):
                if a[i][1]<a[i-1][1]:
                    a[i-1],a[i]=a[i],a[i-1]
                    flag=1

n=input()
card_1=[[0]*2 for i in xrange(n)]

for i in xrange(n):
    card_1[i][0],card_1[i][1]=map(str,raw_input().split())
    card_1[i][1]=int(card_1[i][1])

card_2=list(card_1)
quicksort(card_1,0,n-1)
bubblesort(card_2,n)

if card_1==card_2:
    print("Stable")
else :
    print("Not stable")

for i in xrange(n):
    card_1[i]=map(str,card_1[i])
    print(" ".join(card_1[i]))

Submission status: Time Limit Exceeded

Solution code:
from collections import namedtuple
Card = namedtuple('Card', 'suit value')

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

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

def checkStable(C0, C1):
    result = True
    num = {}
    for c in C0: num[c.value] = c.value
    for i in num.keys():
        f0 = [x.suit for x in list(filter(lambda c: c.value==i,C0))]
        f1 = [x.suit for x in list(filter(lambda c: c.value==i,C1))]
        if f0!=f1:
            result = False
    return result

if __name__=='__main__':
    n = int(input()) 
    Co = list(map(lambda X: Card(X[0],int(X[1])), [input().split() for _ in range(n)]))
    Cs = Co[:]
    quickSort(Cs,0,n-1)
    print("Stable" if checkStable(Co,Cs) else "Not stable")
    for c in Cs: print(c.suit,c.value)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy

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

    tmp = A[i+1]
    A[i+1] = A[r-1]
    A[r-1] = tmp
    return i+1

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

def babble_sort(A, n):
    for j in range(n):
        for i in range(n-1):
            if A[i+1][1] < A[i][1]:
                tmp = A[i+1]
                A[i+1] = A[i]
                A[i] = tmp
    return A

def stable(A, B):
    for i in range(0, len(A)):
        if A[i][0] != B[i][0]:
            return False
    return True


n = int(sys.stdin.readline())

A = [[x[0], int(x[1])] for x in [y.split() for y in sys.stdin.read().split("\n")[:-1]]]

B = babble_sort(copy.deepcopy(A), n)
C = quicksort(copy.deepcopy(A), 0, n)

if stable(C, B):
    print('Stable')
else:
    print("Not stable")

for i in C:
    print(*i)

Submission status: Time Limit Exceeded

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

def partition(target_list, l, r):
    x = int(target_list[r][1:])
    i = l - 1

    for j in range(l, r):
        if int(target_list[j][1:]) <= x:
            i = i + 1
            tmp = target_list[i]
            target_list[i] = target_list[j]
            target_list[j] = tmp
    tmp = target_list[r]
    target_list[r] = target_list[i + 1]
    target_list[i + 1] = tmp
    
    return  i + 1

def check_stable(origin_list, target_list):
    for i, origin_v in enumerate(origin_list):
        for origin_v2 in origin_list[i+1:]:
            if origin_v[2] == origin_v2[2]:
                for j, target_v in enumerate(target_list):
                    for target_v2 in target_list[j+1:]:
                        if origin_v == target_v2 and origin_v2 == target_v:
                            return "Not stable"
    return "Stable"

def quick_sort(target_list, l, r):
    if l < r:
        c = partition(target_list, l, r)
        quick_sort(target_list, l, c - 1)
        quick_sort(target_list, c + 1, r)
        
if __name__ == "__main__":
    n_list = int(input())

    target_list = []
    for i in range(n_list):
        target_list.append(input())
    origin_list = [a for a in target_list]
    quick_sort(target_list, 0, n_list - 1)
    print(check_stable(origin_list, target_list))
    print("\n".join(target_list))

Submission status: Time Limit Exceeded

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

def partition(target_list, l, r):
    x = int(target_list[r][1:])
    i = l - 1

    for j in range(l, r):
        if int(target_list[j][1:]) <= x:
            i = i + 1
            tmp = target_list[i]
            target_list[i] = target_list[j]
            target_list[j] = tmp
    tmp = target_list[r]
    target_list[r] = target_list[i + 1]
    target_list[i + 1] = tmp
    
    return  i + 1

def check_stable(origin_list, target_list):
    for i, origin_v in enumerate(origin_list):
        for origin_v2 in origin_list[i+1:]:
            if origin_v[1:] == origin_v2[1:]:
                for j, target_v in enumerate(target_list):
                    for target_v2 in target_list[j+1:]:
                        if origin_v == target_v2 and origin_v2 == target_v:
                            return "Not stable"
    return "Stable"

def quick_sort(target_list, l, r):
    if l < r:
        c = partition(target_list, l, r)
        quick_sort(target_list, l, c - 1)
        quick_sort(target_list, c + 1, r)
        
if __name__ == "__main__":
    n_list = int(input())

    target_list = []
    for i in range(n_list):
        target_list.append(input())
    origin_list = [a for a in target_list]
    quick_sort(target_list, 0, n_list - 1)
    print(check_stable(origin_list, target_list))
    print("\n".join(target_list))

Submission status: Time Limit Exceeded

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

def partition(target_list, l, r):
    x = int(target_list[r][1:])
    i = l - 1

    for j in range(l, r):
        if int(target_list[j][1:]) <= x:
            i = i + 1
            tmp = target_list[i]
            target_list[i] = target_list[j]
            target_list[j] = tmp
    tmp = target_list[r]
    target_list[r] = target_list[i + 1]
    target_list[i + 1] = tmp
    
    return  i + 1

def check_stable(origin_list, target_list):
    for i, origin_v in enumerate(origin_list):
        for origin_v2 in origin_list[i+1:]:
            if origin_v.split()[1] == origin_v2.split()[1]:
                for j, target_v in enumerate(target_list):
                    for target_v2 in target_list[j+1:]:
                        if origin_v == target_v2 and origin_v2 == target_v:
                            return "Not stable"
    return "Stable"

def quick_sort(target_list, l, r):
    if l < r:
        c = partition(target_list, l, r)
        quick_sort(target_list, l, c - 1)
        quick_sort(target_list, c + 1, r)
        
if __name__ == "__main__":
    n_list = int(input())

    target_list = []
    for i in range(n_list):
        target_list.append(input())
    origin_list = [a for a in target_list]
    quick_sort(target_list, 0, n_list - 1)
    print(check_stable(origin_list, target_list))
    print("\n".join(target_list))

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
n = int(input())
C = []

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

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, p + 1, r)

s = sorted(C, key=itemgetter(1) )

quicksort(C, 0, n - 1)

if s == C:
    print('Stable')
else:
    print('Not stable')
for c in C:
    print(' '.join(map(str, c)))

Submission status: Time Limit Exceeded

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, b):
    length = int(len(a))
    for i in range(length):
        for j in range(i+1,length-1) :
            for x in range(length):
                for y in range(x+1,length-1) :
                    if a[i][1]==a[j][1] and a[i] == b[y] and a[j] == b[x]:
                        return False
                        break
    return True

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    cards = []
    for _ in range(int(input())):
        cards.append(Card(input()))

    base_cards = cards.copy()
    quickSort(cards, 0, len(cards) - 1)

    print(check_stable(base_cards, cards))
    for c in cards:
        print(c.cha, c.num)


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


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

    for j in range(p, r):
        if A[j].num <= x.num:
            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 check_stable(base, card):
    nums = []
    for c in card:
        if c.num not in nums:
            nums.append(c.num)

    for n in nums:
        if list(filter(lambda x: x.num == n, base)) != list(filter(lambda x: x.num == n, card)):
            return 'Not stable'

    return 'Stable'


class Card:
    def __init__(self, imp):
        cha, num = imp.split(' ')
        self.cha = cha
        self.num = int(num)


main()

Submission status: Time Limit Exceeded

Solution code:
# Quick Sort #
def partition(A, p, r):
    x = A[r][1]
    i = p-1
    for k in range(p, r):
        if A[k][1] <= x:
            i += 1
            A[i], A[k] = A[k], 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(_in, out):
    n = len(_in)
    for i in range(n):
        for k in range(i+1, n):
            for a in range(n):
                for b in range(a+1, n):
                    if _in[i][1] == _in[k][1] and _in[i] == out[b] and _in[k] == out[a]:
                        return False
    return True

n = int(input())
a = []
for i in range(n):
    mrk, num = input().split()
    num = int(num)
    a.append((mrk, num))
b = a[:]
quick_sort(b, 0, n-1)
if is_stable(a, b):
    print("Stable")
else:
    print("Not stable")
for i in b:
    print(*i)

Submission status: Time Limit Exceeded

Solution code:
# Quick Sort #
def partition(A, p, r):
    x = A[r][1]
    i = p-1
    for k in range(p, r):
        if A[k][1] <= x:
            i += 1
            A[i], A[k] = A[k], 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 bubble_sort(c, n):
    x = c[:]
    for i in range(n):
        for k in range(n-1, i, -1):
            if x[k][1] < x[k-1][1]:
                x[k], x[k-1] = x[k-1], x[k]
    return x

def is_stable(_in, out):
    n = len(_in)
    for i in range(n):
        for k in range(i+1, n):
            for a in range(n):
                for b in range(a+1, n):
                    if _in[i][1] == _in[k][1] and _in[i] == out[b] and _in[k] == out[a]:
                        return False
    return True
n = int(input())
a = []
for i in range(n):
    mrk, num = input().split()
    num = int(num)
    a.append((mrk, num))
b = a[:]
quick_sort(b, 0, n-1)
c = bubble_sort(a[:], n)
if b == c:
    print("Stable")
else:
    print("Not stable")
for i in b:
    print(*i)

Submission status: Time Limit Exceeded

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 is_stable(A, sorted_A, N):
    A_nums = [int(x[2:]) for x in A]
    same_num = [x for x in set(A_nums) if A_nums.count(x) > 1]
    A_symbols, sorted_A_symbols = [], []
    flag = 'Stable'
    for num in same_num:
        if [card[0] for card in A if int(card[2:]) == num] != [card[0] for card in sorted_A if int(card[2:]) == num]:
            flag = 'Not stable'
            break
    return flag

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

quick_sort(cards, 0, n-1)
print(is_stable(init_cards, cards, n))
for c in cards:
    print(c)

Submission status: Time Limit Exceeded

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

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

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

if x1 == x2:
    print 'Stable'
else:
    print 'Not stable'
for e in x1:
    print 'SHDC'[e % 10], e/10

Submission status: Memory Limit Exceeded

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 suitlist(cards):
    suits = [[]]*10**9
    for card in cards:
        suits[int(card[1])-1].append(card[0])
    return suits


def is_stable(before, after):
    suits_b = suitlist(before)
    suits_a = suitlist(after)
    for a, b in zip(suits_b, suits_a):
        if a != b:
            return False
    return True


n = int(input())
cards = []
origin = cards.copy()
for _ in range(n):
    cards.append(input().split())
origin = cards.copy()
quicksort(cards, 0, n - 1)
print("Stable" if is_stable(origin, cards) else "Not stable")
for card in cards:
    print(*card)

Submission status: Accepted

Solution code:
class Card:
	def __init__(self, mark, num, order):
		self.mark = mark
		self.num = num
		self.order = order
	def __str__(self):
		return self.mark + ' ' + str(self.num)

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

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

def swap(cards, i, j):
	tmp = cards[i]
	cards[i] = cards[j]
	cards[j] = tmp

def check_stability(cards):
	for i in range(1, len(cards)):
		c1 = cards[i-1]
		c2 = cards[i]
		if c1.num == c2.num and c1.order > c2.order:
			return False
	return True

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

quick_sort(cards, 0, n - 1)
stable = check_stability(cards)
if stable == True:
	print('Stable')
else:
	print('Not stable')
for i in range(n):
	print(cards[i])

Submission status: Accepted

Solution code:

class Card:
	def __init__(self, m, n, o):
		self.m = m
		self.n = n
		self.o = o
	def __str__(self):
		return str(self.m + ' ' + str(self.n))
	
def swap(a, i, j):
	tmp = a[i]
	a[i] = a[j]
	a[j] = tmp

def partition(a, f, c):
	x = a[c].n
	i = f - 1
	for j in range(f, c):
		if a[j].n <= x:
			i += 1
			swap(a, i, j)
	swap(a, i + 1, c)
	return i + 1

def quick_sort(a, f, c):
	if (f < c):
		q = partition(a, f, c)
		quick_sort(a, f, q - 1)
		quick_sort(a, q + 1, c)

def check_stability(a):
	for i in range(1, len(a)):
		c1 = a[i-1]
		c2 = a[i]
		if (c1.n == c2.n and c1.o > c2.o):
			return False
	return True
		
n = int(input())
cards = []
for i in range(n):
	m, num = map(str, input().split())
	cards.append(Card(m, int(num), i))

quick_sort(cards, 0, n - 1)
if (check_stability(cards) == True):
	print('Stable')
else:
	print('Not stable')
for i in range(n):
	print(cards[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)
    return None
        
n = int(input())
A = [(i,int(j)) for i,j in [input().split() for i in range(n)]]
B = A.copy()
quickSort(A,0,n-1)
num = A[0][1]
pos = B.index(A[0])
ans = "Stable"
for i in A[1:]:
    if i[1] != num:
        num = i[1]
        pos = B.index(i)
    else:
        if pos > B.index(i):
            ans = "Not stable"
            break
        else:
            pos = B.index(i)
print(ans)
for i,j in A:
    print(i,j)

Submission status: Accepted

Solution code:
import copy

def partition(p, r):
    i = p
    for j in range(p, r):
        if A[r][1] >= A[j][1]:
            A[i], A[j] = A[j], A[i]
            i += 1
    A[r], A[i] = A[i], A[r]
    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():
    for i in range(N-1):
        if A[i][1] == A[i+1][1]:
            small_idx, large_idx = 0, 0
            for j in range(N):
                if A[i] == orig_list[j]:
                    small_idx = j
                elif A[i+1] == orig_list[j]:
                    large_idx = j
            if small_idx > large_idx:
                return False
    return True


N = int(input())
A = []
for _ in range(N):
    suit, num = input().split()
    num = int(num)
    A.append([suit, num])
orig_list = copy.deepcopy(A)

quick_sort(0, N-1)

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

for card in A:
    print("%s %d" % (card[0], card[1]))

Submission status: Accepted

Solution code:
import copy

def partition(p, r):
    i = p
    for j in range(p, r):
        if A[r][1] >= A[j][1]:
            A[i], A[j] = A[j], A[i]
            i += 1
    A[r], A[i] = A[i], A[r]
    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 correct_same_num_suits(l, num):
    suits = []
    for card in l:
        if num == card[1]:
            suits.append(card[0])
    return suits

def is_stable():
    idx = 0
    while idx < N-1:
        idx_incr_flg = True
        if A[idx][1] == A[idx+1][1]:
            num = A[idx][1]
            sorted_suits = correct_same_num_suits(A, num)
            orig_suits = correct_same_num_suits(orig_list, num)
            if sorted_suits != orig_suits:
                return False
            idx += len(sorted_suits)
            idx_incr_flg = False
        if idx_incr_flg:
            idx += 1
    return True


N = int(input())
A = []
for _ in range(N):
    suit, num = input().split()
    num = int(num)
    A.append([suit, num])
orig_list = copy.deepcopy(A)

quick_sort(0, N-1)

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

for card in A:
    print("%s %d" % (card[0], card[1]))

Submission status: Accepted

Solution code:
import copy

def partition(p, r):
    i = p
    for j in range(p, r):
        if A[r][1] >= A[j][1]:
            A[i], A[j] = A[j], A[i]
            i += 1
    A[r], A[i] = A[i], A[r]
    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():
    for i in range(N-1):
        if A[i][1] == A[i+1][1]:
            small_idx, large_idx = 0, 0
            cnt = 0
            for j in range(N):
                if A[i] == orig_list[j]:
                    small_idx = j
                    cnt += 1
                elif A[i+1] == orig_list[j]:
                    large_idx = j
                    cnt += 1
                if cnt == 2:
                    break
            if small_idx > large_idx:
                return False
    return True


N = int(input())
A = []
for _ in range(N):
    suit, num = input().split()
    num = int(num)
    A.append([suit, num])
orig_list = copy.deepcopy(A)

quick_sort(0, N-1)

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

for card in A:
    print("%s %d" % (card[0], card[1]))

Submission status: Accepted

Solution code:
import copy

def partition(p, r):
    i = p
    for j in range(p, r):
        if A[r][1] >= A[j][1]:
            A[i], A[j] = A[j], A[i]
            i += 1
    A[r], A[i] = A[i], A[r]
    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 correct_same_num_suits(l, num, first):
    suits = []
    for i in range(first, N):
        if num == l[i][1]:
            suits.append(l[i][0])
    return suits

def is_stable():
    idx = 0
    while idx < N-1:
        idx_incr_flg = True
        if A[idx][1] == A[idx+1][1]:
            num = A[idx][1]
            sorted_suits = correct_same_num_suits(A, num, idx)
            orig_suits = correct_same_num_suits(orig_list, num, 0)
            if sorted_suits != orig_suits:
                return False
            idx += len(sorted_suits)
            idx_incr_flg = False
        if idx_incr_flg:
            idx += 1
    return True


N = int(input())
A = []
for _ in range(N):
    suit, num = input().split()
    num = int(num)
    A.append([suit, num])
orig_list = copy.deepcopy(A)

quick_sort(0, N-1)

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

for card in A:
    print("%s %d" % (card[0], card[1]))

Submission status: Accepted

Solution code:
import copy

def partition(p, r):
    i = p
    for j in range(p, r):
        if A[r][1] >= A[j][1]:
            A[i], A[j] = A[j], A[i]
            i += 1
    A[r], A[i] = A[i], A[r]
    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 correct_same_num_suits(l, num, first, ele_cnt):
    suits = []
    for i in range(first, N):
        if num == l[i][1]:
            suits.append(l[i][0])
        if ele_cnt == len(suits):
            break
    return suits

def is_stable():
    idx = 0
    while idx < N-1:
        idx_incr_flg = True
        if A[idx][1] == A[idx+1][1]:
            num = A[idx][1]
            j = idx
            ele_cnt = 0
            while j < N and num == A[j][1]:
                ele_cnt += 1
                j += 1
            sorted_suits = correct_same_num_suits(A, num, idx, ele_cnt)
            orig_suits = correct_same_num_suits(orig_list, num, 0, ele_cnt)
            if sorted_suits != orig_suits:
                return False
            idx += len(sorted_suits)
            idx_incr_flg = False
        if idx_incr_flg:
            idx += 1
    return True


N = int(input())
A = []
for _ in range(N):
    suit, num = input().split()
    num = int(num)
    A.append([suit, num])
orig_list = copy.deepcopy(A)

quick_sort(0, N-1)

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

for card in A:
    print("%s %d" % (card[0], card[1]))