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: Wrong Answer

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 = [" "," ", 999999999]
    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][-1]) <= int(R[j][-1]):
            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: Wrong Answer

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 = [" "," ", 999999999]
    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 float(L[i][-1]) <= float(R[j][-1]):
            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: Wrong Answer

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 = [" "," ", float("inf")]
    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 float(L[i][-1]) <= float(R[j][-1]):
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
            
            
def partition(A, p, r):
    x = float(A[r][2])
    i = p - 1
    for j in range(p, r):
        if float(A[j][2]) <= 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)
 
 
 
 
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)-1)
  
    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: Wrong Answer

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 = [" "," ", 10**9]
    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 float(L[i][-1]) <= float(R[j][-1]):
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
            
            
def partition(A, p, r):
    x = float(A[r][2])
    i = p - 1
    for j in range(p, r):
        if float(A[j][2]) <= 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)
 
 
 
 
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)-1)
  
    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: Wrong Answer

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: Wrong Answer

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: Wrong Answer

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: Wrong Answer

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)
    x = Quicksort()
    a = x.quicksort(cards, 0, n-1)
    num = set([i[1] for i in cards])
    
    if len(num) == 1:
        print("Stable")
    else:
        print("Not stable")
    
    for i in a:
        i[1] = str(i[1])
        print(" ".join(i))

Submission status: Wrong Answer

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 for d in A if d.value == i] != [d 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: Wrong Answer

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


def is_stable(before, after):
    suits_b = suitlist(before)
    suits_a = suitlist(after)
    if suits_b == suits_a:
        return True
    else:
        return False


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

Submission status: Wrong Answer

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)

Submission status: Wrong Answer

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

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: Wrong Answer

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
    for i in range(1,10):
        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: Wrong Answer

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 - 1)
        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: Wrong Answer

Solution code:
#coding:UTF-8

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

def QS(A,p,r):
    if p<r:
        q=Partition(A,p,r)
        QS(A,p,q-1)
        QS(A,q+1,r)
 
    
if __name__=="__main__":
    n=int(input())
    A=[]
    for i in range(n):
        A.append(input().split(" "))
    for i in range(n):
        print(A[i])
        A[i][1]=int(A[i][1])    
    QS(A,0,n)
    if n>2:
        print("Not stable")
    else:
        print("Stable")
    for i in range(n):
        print(A[i][0]+" "+str(A[i][1]))

Submission status: Wrong Answer

Solution code:
#coding:UTF-8

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

def QS(A,p,r):
    if p<r:
        q=Partition(A,p,r)
        QS(A,p,q-1)
        QS(A,q+1,r)
 
    
if __name__=="__main__":
    n=int(input())
    A=[]
    for i in range(n):
        A.append(input().split(" "))
    for i in range(n):
        A[i][1]=int(A[i][1])    
    QS(A,0,n)
    if n>2:
        print("Not stable")
    else:
        print("Stable")
    for i in range(n):
        print(A[i][0]+" "+str(A[i][1]))

Submission status: Wrong Answer

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][2])
    i = l - 1

    for j in range(l, r):
        if int(target_list[j][2]) <= 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: Wrong Answer

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][2])
    i = l - 1

    for j in range(l, r):
        if int(target_list[j][2]) <= 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: Wrong Answer

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):
    global count
    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)
    
    r = merge_sort(target_list[mid:])
    l = 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: Wrong Answer

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


import sys


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


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
    result = quick_sort(array=array, start=0, end=array_length - 1)
    print('Not stable')
    print(*result, sep='\n')

Submission status: Wrong Answer

Solution code:
s = True

def checher(A,start,end):
    global s
    for i in range(start+1,end+1):
        if A[start][1]==A[i][1]:
            if A[start][0]!=A[i][0]:
                s = False
                return
    return

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
            if s:
                checher(A,i,j)
            (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())
l = []
for i in range(n):
    card = input().split()
    l.append((card[0],int(card[1])))
quickSort(l,0,n-1)
if s:
    print("Stable")
else:
    print("Not Stable")
for s,n in l:
    print("{} {}".format(s,n))

Submission status: Wrong Answer

Solution code:
s = True

def checher(A,start,end):
    global s
    for i in range(start+1,end+1):
        if A[start][1]==A[i][1]:
            if A[start][0]!=A[i][0]:
                s = False
                return
    return

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
            if s:
                checher(A,i,j)
            (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())
l = []
for i in range(n):
    card = input().split()
    l.append((card[0],int(card[1])))
quickSort(l,0,n-1)
if s:
    print("Stable")
else:
    print("Not stable")
for s,n in l:
    print("{} {}".format(s,n))

Submission status: Wrong Answer

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


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