Problem:
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] <= x 5        then i = i+1 6            exchange A[i] and A[j]  7 exchange A[i+1] and A[r] 8 return i+1   Quicksort(A, p, r) 1 if p < r 2    then q = Partition(A, p, r) 3        run Quicksort(A, p, q-1) 4        run Quicksort(A, q+1, r)   Here, A is an array which represents a deck of cards and comparison operations are performed based on the numbers.  Your program should also report the stability of the output for the given input (instance). Here, 'stability of the output' means that: cards with the same value appear in the output in the same order as they do in the input (instance).

Incorrect submission (verdict: Wrong Answer):
def main():
    cards = []
    for _ in range(int(input())):
        cards.append(Card(input()))

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

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

    print(check_stable(base_cards, cards))


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[-1]
    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):
    for i in range(0, len(card) - 1):
        if base.index(card[i]) > base.index(card[i + 1]):
            return 'Not stable'

    return 'Stable'


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


main()

Fixed, accepted submission:
"""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)