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

def marge(A,left,mid,right):
    n1 = mid -left
    n2 = right -mid
    L = []
    R = []
    for i in range(left,n1+left):
        L.append(A[i])
    for i in range(mid,n2+mid):
        R.append(A[i])
 
    L.append(card('S 10000000000'))
    R.append(card('S 10000000000'))
 
    r_id,l_id = 0,0
    for k in range(left,right):
        if(L[l_id] <= R[r_id]):
            A[k] = L[l_id]
            l_id += 1
        else:
            A[k] = R[r_id]
            r_id += 1
 
def margeSort(A,left,right):
    if left+1 < right:
        mid = int((left+right)/2)
        margeSort(A,left,mid)
        margeSort(A,mid,right)
        marge(A,left,mid,right)


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_marge = c.copy()
margeSort(c_marge,0,len(c))

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

is_stable = True
for i in range(0,len(c)):
    if(c[i] != c_marge[i]):
        is_stable = False
        break
if(is_stable == True):
    print('Stable')
else:
    print('Not stable')
for i in c:
    i.display_card()

Submission status: Accepted

Solution code:
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 merge(A, left, mid, right):

    n1 = mid -left
    n2 = right - mid
    L = []
    R = []
    x = "  10000000000"
    for i in range(0, n1):
        L.append(A[left + i])
    for i in range(0, n2):
        R.append(A[mid + i])
    L.append(x)
    R.append(x)
    i = 0
    j = 0
    for k in range(left, right):
        if int(L[i][2:]) <= int(R[j][2:]):
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
            
            
def partition(A, p, r):
    x = int(A[r-1][2:])
    i = p - 1
    for j in range(p, r-1):
        if int(A[j][2:]) <= 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 quicksort(A, p, r):
    if p < r-1:
        q = partition(A, p, r)
         
        quicksort(A, p, q)
        quicksort(A, q+1, r)
 
 
 
 
if __name__ == "__main__":
    num = int(raw_input())
    num_list = []
    num_list1 = []
    for i in range(num):
        num_list.append(raw_input())
    num_list1 = list(num_list)
    quicksort(num_list, 0, len(num_list))
  
    mergesort(num_list1, 0, len(num_list1))
     
    if num_list == num_list1:
        print ("Stable")
    else:
        print ("Not stable")
    print "\n".join(num_list)

Submission status: Accepted

Solution code:
import copy

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

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

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

def merge_sort(S):
    if len(S) <= 1:
        return S
    S1,S2 = split(S)
    return merge(merge_sort(S1),merge_sort(S2))

def split(S):
    mid = len(S)/2
    return S[:mid],S[mid:]

def merge(S1,S2):
    S = []
    S1.append(('SENTINEL',100000000000))
    S2.append(('SENTINEL',100000000000))
    i = 0
    j = 0
    for k in range(len(S1)+len(S2)-2):
        if S1[i][1] <= S2[j][1]:
            S.append(S1[i])
            i += 1
        else:
            S.append(S2[j])
            j += 1
    return S



cards2 = copy.copy(cards)
quick_sort(cards,0,len(cards)-1)
cards2 = merge_sort(cards2)
flag = True
for i in range(len(cards)):
    if cards[i] != cards2[i]:
        print "Not stable"
        flag = False
        break
if flag: print "Stable"
for suit,num in cards:
    print suit,num

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:
#coding:utf-8
#1_6_C
def partition(A, p, r):
    x = int(A[r][1])
    i = p - 1
    for j in range(p, r):
        if int(A[j][1]) <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1

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

class CheckStable:
    def __init__(self):
        self.d = dict() # Key is number. Value is array of suit.

    def store_cards(self, cards):
        for i in range(n):
            if cards[i][1] in self.d:
                self.d[cards[i][1]].append(cards[i][0])
            else:
                self.d[cards[i][1]] = [cards[i][0]]

    def is_stable(self, cards):
        for item in reversed(cards):
            if self.d[item[1]].pop() != item[0]:
                return "Not stable"
        return "Stable"

n = int(input())
cards = [tuple(input().split()) for i in range(n)]
d = CheckStable()
d.store_cards(cards)

quick_sort(cards, 0, n - 1)

print(d.is_stable(cards))
for i in range(n):
    print(' '.join(cards[i]))

Submission status: Accepted

Solution code:
"""Quick Sort."""

def partition(A, p, r):
    """Divide list A into A[p:q] whose elements aren't greater than A[q] and
    A[q+1:r] whose elements are greater than A[q].

    Each element of A is a list [x, y].
    x is a character of S, H, C or D (trump suits).
    y is a natural number.
    
    Default value of p is 0.
    The number as a refernce of the division is A[r].
    
    Return the index q.
    """

    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):
    """Sort list A in ascending order with quick sort algorithm.

    Default value of p is 0 (the start index).
    r is 1 less than the length of A (the last index of A).
    """

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


def is_stable(A, B):
    """Check the stability of sorted list A.

    A is a sorted list.
    B is a original list.

    Return True or False.
    """

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



import sys

r = int(sys.stdin.readline()) - 1

A = [x.split() for x in sys.stdin.readlines()]

for i, x in enumerate(A):
    A[i][1] = int(x[1])

B = list (A)

quickSort(A, 0, r)

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

for x in A:
    print(*x)

Submission status: Accepted

Solution code:
"""Quick Sort."""

def partition(A, p, r):
    """Divide list A into A[p:q] whose elements aren't greater than A[q] and
    A[q+1:r] whose elements are greater than A[q].

    Each element of A is a list [x, y].
    x is a character of S, H, C or D (trump suits).
    y is a natural number.
    Sorting is done based on y numbers.
    
    Default value of p is 0.
    The number as a refernce of the division is A[r].
    
    Return the index q.
    """

    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):
    """Sort list A in ascending order with quick sort algorithm.

    Default value of p is 0 (the start index).
    r is 1 less than the length of A (the last index of A).
    """

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


def is_stable(A, B):
    """Check the stability of sorted list A.

    A is a sorted list.
    B is a original list.

    Return True or False.
    """

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



import sys

r = int(sys.stdin.readline()) - 1

A = []

for x in sys.stdin.readlines():
    suit, num = x.split()
    num = int(num)
    A.append([suit, num])

B = list (A)

quickSort(A, 0, r)

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

for x in A:
    print(*x)

Submission status: Accepted

Solution code:
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 = sorted(b, key=lambda i: i[1])
    
    if a == b:
        print("Stable")
    else:
        print("Not stable")
    
    for i in a:
        i[1] = str(i[1])
        print(" ".join(i))

Submission status: Accepted

Solution code:
n = int(raw_input())
stable = 1

class Card():
    __slots__ = ('suit', 'value')

#mergeSort
A = [Card() for _ in xrange(n)]
#quickSort
B = [Card() for _ in xrange(n)]

for i in xrange(n):
    a = raw_input().split()
    A[i].suit = a[0]
    B[i].suit = a[0]
    A[i].value = int(a[1])
    B[i].value = int(a[1])

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = [0] * (n1+1) 
    R = [0] * (n2+1)
    L[:n1] = A[left:mid]
    R[:n2] = A[mid:right]
    #for i in xrange(n1):
    #    L[i] = A[left + i]
    #for i in xrange(n2):
    #    R[i] = A[mid + i]
    L[n1] = Card()
    R[n2] = Card()
    L[n1].value = float('inf')
    R[n2].value = float('inf')
    i = 0
    j = 0
    for k in xrange(left,right):
        if L[i].value <= R[j].value:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    return 0

def mergeSort(A, left, right):
    if right - left > 1:
        mid = int((left + right) / 2)
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
    return 0

def partition(A, p, r):
    x = A[r].value
    i = p-1
    for j in xrange(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 quickSort(A,p,r):
    if p < r:
        q = partition(A, p, r)
        quickSort(A, p, q-1)
        quickSort(A, q, r)
    return 0

mergeSort(A, 0, n)
quickSort(B, 0, n-1)

for i in xrange(n):
    if A[i].suit != B[i].suit:
        stable = 0

if stable == 1:
    print 'Stable'
else:
    print 'Not stable'

for i in xrange(n):
    print B[i].suit, B[i].value

Submission status: Accepted

Solution code:
n = int(raw_input())
#stable = 1

class Card():
    __slots__ = ('suit', 'value')

#mergeSort
A = [Card() for _ in xrange(n)]
#quickSort
B = [Card() for _ in xrange(n)]

s = set()
for i in xrange(n):
    a = raw_input().split()
    A[i].suit = a[0]
    B[i].suit = a[0]
    A[i].value = int(a[1])
    B[i].value = int(a[1])
    s.add(int(a[1]))
'''
def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = [0] * (n1+1) 
    R = [0] * (n2+1)
    L[:n1] = A[left:mid]
    R[:n2] = A[mid:right]
    #for i in xrange(n1):
    #    L[i] = A[left + i]
    #for i in xrange(n2):
    #    R[i] = A[mid + i]
    L[n1] = Card()
    R[n2] = Card()
    L[n1].value = float('inf')
    R[n2].value = float('inf')
    i = 0
    j = 0
    for k in xrange(left,right):
        if L[i].value <= R[j].value:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    return 0

def mergeSort(A, left, right):
    if right - left > 1:
        mid = int((left + right) / 2)
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
    return 0
'''
def partition(A, p, r):
    x = A[r].value
    i = p-1
    for j in xrange(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 quickSort(A,p,r):
    if p < r:
        q = partition(A, p, r)
        quickSort(A, p, q-1)
        quickSort(A, q, r)
    return 0

#mergeSort(A, 0, n)
quickSort(B, 0, n-1)

for i in s:
    if [d.suit for d in A if d.value == i] != [d.suit for d in B if d.value == i]:
        print('Not stable')
        break
else:
    print('Stable')

#for i in xrange(n):
#    if A[i].suit != B[i].suit:
#        stable = 0
for i in xrange(n):
    print B[i].suit, B[i].value

Submission status: Accepted

Solution code:
n = int(raw_input())
#stable = 1

class Card():
    __slots__ = ('suit', 'value')

#mergeSort
A = [Card() for _ in xrange(n)]
#quickSort
B = [Card() for _ in xrange(n)]

s = set()
for i in xrange(n):
    a = raw_input().split()
    A[i].suit = a[0]
    B[i].suit = a[0]
    A[i].value = int(a[1])
    B[i].value = int(a[1])
    s.add(int(a[1]))

def partition(A, p, r):
    x = A[r].value
    i = p-1
    for j in xrange(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 quickSort(A,p,r):
    if p < r:
        q = partition(A, p, r)
        quickSort(A, p, q-1)
        quickSort(A, q, r)
    return 0

quickSort(B, 0, n-1)

for i in s:
    if [d.suit for d in A if d.value == i] != [d.suit for d in B if d.value == i]:
        print('Not stable')
        break
else:
    print('Stable')

for i in xrange(n):
    print B[i].suit, B[i].value

Submission status: Accepted

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


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


def is_stable(cards):
    for i in range(1, len(cards)):
        if cards[i-1][1] == cards[i][1]:
            if cards[i-1][2] > cards[i][2]:
                return False
    return True


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

Submission status: Accepted

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 merge(A,left,mid,right):
    n1=mid-left
    n2=right-mid
    l=[A[left+i] for i in xrange(n1)]
    r=[A[mid+i] for i in xrange(n2)]
    l.append([0,float('inf')])
    r.append([0,float('inf')])
    i=0
    j=0
    for k in xrange(left,right):
        if l[i][1]<=r[j][1]:
            A[k]=l[i]
            i=i+1
        else:
            A[k]=r[j]
            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=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)
mergesort(card_2,0,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: Accepted

Solution code:
import sys

class card:
    def __init__(self, types, value):
        self.types = types
        self.value = value

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].value
    i = p - 1
    for j in range(p, r):
        if A[j].value <= x:
            i += 1
            swap(A, i, j)
    swap(A, i + 1, r)

    return i + 1

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

def checkStable(origin, sorted, N):
    for i in range(0, N - 1):
        if sorted[i].value == sorted[i + 1].value:
            if origin.index(sorted[i]) > origin.index(sorted[i + 1]):
                return False
    return True

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    del lines[0]
    A = [card(c[0], int(c[2:])) for c in lines]
    origin = A[:]
    quickSort(A, 0, len(A) - 1)
    if checkStable(origin, A, len(A)):
        print "Stable"
    else:
        print "Not stable"
    for a in A:
        print a.types + " " + str(a.value)

Submission status: Accepted

Solution code:
import sys

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

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].num
    i = p - 1
    for j in range(p, r):
        if A[j].num <= 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 checkStable(origin, sorted):
    for i in range(0, len(origin) - 1):
        if sorted[i].num == sorted[i + 1].num:
            if origin.index(sorted[i]) > origin.index(sorted[i + 1]):
                return False
    return True

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    del lines[0]
    A = [card(c[0], int(c[2:])) for c in lines]
    origin = A[:]
    quickSort(A, 0, len(A) - 1)

    if checkStable(origin, A):
        print "Stable"
    else:
        print "Not stable"

    for a in A:
        print a.suit, str(a.num)

Submission status: Accepted

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

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

def quick_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(raw_input())
data = []
s = set()
for i in range(n):
    c, num = map(str, raw_input().split())
    data.append((int(num), c))
    s.add(int(num))
out = data[:]
quick_sort(out, 0, n-1)
for i in s:
    if [d for d in data if d[0] == i] != [d for d in out if d[0] == i]:
        print "Not stable"
        break
else:
    print "Stable"
for num, c in out:
    print "%s %s" %(c, num)

Submission status: Accepted

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 merge(L,R):
    global cnt
    n = len(L)+len(R)
    A = []
    i = j = 0
    L.append(Card('X',-1))
    R.append(Card('X',-1))
    for _ in range(n):
        if L[i].value > R[j].value:
            A.append(L[i])
            i += 1
        else:
            A.append(R[j])
            j += 1
    return A

def mergeSort(A):
    if len(A)==1: return A
    m = len(A)//2
    return merge(mergeSort(A[:m]),mergeSort(A[m:])) 

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

Submission status: Accepted

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 isStable(Co,Cs):
    C = Cs[:]
    for ci in Co:
        j = C.index(ci)
        if j > 0:
            if Cs[j-1].value == ci.value:
                return False
        del C[j]
    return True

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 isStable(Co,Cs) else "Not stable")
    for c in Cs: print(c.suit,c.value)

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 isstable(a):
    for i in range(n-1):
        if a[i][1] == a[i+1][1]:
            if a[i][2] > a[i+1][2]:
                return False
    return True


n = int(input())
deck = [None]*n
for num in range(n):
    card = input().split()
    deck[num] = [card[0], int(card[1]), num]

quicksort(deck, 0, n-1)
if isstable(deck):
    print("Stable")
else:
    print("Not stable")
[print(deck[i][0], deck[i][1]) for i in range(n)]

Submission status: Accepted

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 = sorted(copy.deepcopy(A), key=lambda x: x[1])
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: Accepted

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 merge(l,r):
    
    l_index = 0
    r_index = 0
    merge_list = []
    l.append("X " + str(pow(10,9) + 1))
    r.append("X " + str(pow(10,9) + 1))
   
    for k in range(len(l) + len(r) - 2):
        if int(l[l_index][1:]) <= int(r[r_index][1:]):
            merge_list.append(l[l_index])
            l_index += 1
        else:
            merge_list.append(r[r_index])
            r_index += 1
    
    return merge_list
    
def merge_sort(target_list):
    if len(target_list) == 1:
        return target_list
    
    mid = int(len(target_list) / 2)
    l = merge_sort(target_list[:mid])
    r = merge_sort(target_list[mid:])
    
    return merge(l, r)

def check_stable(origin_list, target_list):
    sorted_list = merge_sort(origin_list)
    if sorted_list == target_list:
        return "Stable"
    return "Not 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: Accepted

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


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