Problem:
Partition Quick sort is based on the Divide-and-conquer approach. In QuickSort(A, p, r), first, a procedure Partition(A, p, r) divides an array A[p..r] into two subarrays A[p..q-1] and A[q+1..r] such that each element of A[p..q-1] is less than or equal to A[q], which is, inturn, less than or equal to each element of A[q+1..r]. It also computes the index q. In the conquer processes, the two subarrays A[p..q-1] and A[q+1..r] are sorted by recursive calls of QuickSort(A, p, q-1) and QuickSort(A, q+1, r). Your task is to read a sequence A and perform the Partition 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 Input The first line of the input includes an integer n , the number of elements in the sequence A. In the second line, A i ( i = 1,2,..., n ), elements of the sequence are given separated by space characters. Output Print the sorted sequence. Two contiguous elements of the sequence should be separated by a space character. The element which is selected as the pivot of the partition should be indicated by [  ] . Constraints  1 ≤ n ≤ 100,000  0 ≤ A i ≤ 100,000  Sample Input 1 12
13 19 9 5 12 8 7 4 21 2 6 11 Sample Output 1 9 5 8 7 4 2 6 [11] 21 13 19 12

Solution (Python):
n = int(input())
A = [int(x) for x in input().split()]


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

    A[i], A[r] = A[r], A[i]

    return i


r = partition(A, 0, n - 1)

ans = [str(x) for x in A]
ans[r] = '[{}]'.format(ans[r])
print(' '.join(ans))

Solution (Python):
from sys import stdin

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

    A[i+1], A[r] = A[r], A[i+1]
    return i+1

n = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
res = partition(A, 0, len(A)-1)
A[res] = [A[res]]
print(*A)

Solution (Python):
def partition(lst,start,last):
    x = lst[last]
    i = start
    for j in range(start,last):
        if lst[j] <= x:
            lst[i],lst[j] = lst[j],lst[i]
            i += 1
    lst[i],lst[last] = lst[last],lst[i]
    return i

n = int(input())
n_lst = list(map(int,input().split()))
p = partition(n_lst,0,n-1)
str_lst = list(map(str,n_lst))
str_lst[p] = '['+str_lst[p]+']'
print(' '.join(str_lst))

Solution (Python):
from typing import List


def partition(A: List[int], p: int, r: int) -> int:
    """パーティション

    A[p, ..., r]を、A[p, ..., q-1]とA[q+1, ..., r]二分割する。
    A[p, ..., q-1]の各要素は A[q]以下とする。
    A[q+1, ..., r]の各要素は A[q]より大きくする。

    Args:
        A (List[int]): 分割対象のリスト
        p (int): 分割対象のリストの先頭のインデックス
        r (int): 分割対象のリストの最後のインデックス

    Returns:
        int: q
    """
    tmp = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= tmp:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1


n = int(input())
A = [int(i) for i in input().split()]
q = partition(A, 0, n - 1)
result = [str(A[i]) if i != q else '[' + str(A[i]) + ']' for i in range(len(A))]
print(' '.join(result))

Solution (Python):


"""
パーティション
"""

N = int(input())
aN = list(map(int, input().split()))

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

idx = partition(0, N-1)
aN[idx] = '[' + str(aN[idx]) + ']'
print(*aN)

Solution (Python):


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

if __name__ == "__main__":
    
    

    n = int(input())
    A = list(map(int, input().split()))
    
    q = partition(A, 0, len(A))
    A = list(map(str, A))
    A[q] = '[{}]'.format(A[q])
    print(' '.join(A))

Solution (Python):
import sys


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


n = int(sys.stdin.readline())
a = [int(v) for v in sys.stdin.readline().split()]
index = partition(a, 0, n - 1)
print(' '.join(f'[{v}]' if i == index else v
               for i, v in enumerate(map(str, a))))

Solution (Python):


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

	for j in range(p, r):
		
		if A[j] <= 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

if __name__ == '__main__':
	
	

	n = int(input())
	A = list(map(int, input().split()))

	q = partition(A, 0, n - 1)

	for i in range(n):
		if i:
			print(" ", end="")
		if i == q:
			print("[", end="")
		if i == n - 1:
			print(A[i])
		else:
			print(A[i], end="")
		if i == q:
			print("]", end="")

Solution (Python):
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


n = int(input())
A = list(map(int, input().split()))

p = partition(A, 0, n-1)
first = ' '.join(str(a) for a in A[0:p])
second = ' '.join(str(a) for a in A[p+1:n])
print(first + " [" + str(A[p]) + "] " + second)

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

    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
    
n = int(input())
A = list(map(int, input().split()))

i = partition(A, 0, n-1)

str_A = list(map(str,A))

str_A[i+1] = "[" + str_A[i+1] + "]"

print(" ".join(str_A))

Solution (Python):
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


n=int(input())
data=list(map(int, input().split()))
q=partition(data,0,n-1)
data[q]="["+str(data[q])+"]"
print(*data)

Solution (Python):
def partition(li, m, length):
    ini_i = 0
    target = li[length - 1]
    for i, n in enumerate(li[:length - 1]):
        if n <= target:
            li[ini_i], li[i] = li[i], li[ini_i]
            ini_i += 1
    li[ini_i], li[-1] = [li[-1]], li[ini_i]
    print(*li)
length = int(input())
li = [int(n) for n in input().split(" ")]
partition(li, 0, len(li))

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


n=int(input())
data=list(map(int,input().split()))

partition_ind=partition(data,0,n)


data=list(map(str,data))
data[partition_ind]="["+data[partition_ind]+"]"
print(" ".join(data))

Solution (Python):
N = int(input())
*A, = map(int, input().split())

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

j = partition(A, 0, N-1)
print(*(str(x) if i != j else "[%d]" % x for i, x in enumerate(A)))

Solution (Python):
def partition(n_list, p, r):
    x = n_list[r-1]
    i = p - 1
    for j in range(p, r-1):
        if n_list[j] <= x:
            i += 1
            y = n_list[i]
            n_list[i] = n_list[j]
            n_list[j] = y
    y = n_list[i]
    n_list[r-1] = n_list[i+1]
    n_list[i+1] = f'[{x}]'

    
n = int(input())
n_list = list(map(int, input().split()))
partition(n_list, 0, n)
print(' '.join(list(map(str, n_list))))

Solution (Python):
import sys

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, A

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))

i, b=Partition(a, 0, n-1)
print(' '.join(map(str, b[0:i])),'['+str(b[i])+']',' '.join(map(str, b[i+1:])))

Solution (Python):
n = int(input())
list_a = list(map(int, input().split()))
def partition(list_a, p, r):
    x = list_a[r]
    i = p-1
    for j in range(p,r):
        if list_a[j] <= x:
            i = i+1
            list_a[j], list_a[i] = list_a[i], list_a[j]
    list_a[i+1], list_a[r] = list_a[r], list_a[i+1]
    return i+1, list_a

ind,list_a = partition(list_a, 0, n-1)
for i in range(n):
    list_a[i] = str(list_a[i])
    if i == ind:
        list_a[i] = "[" + list_a[i] + "]"
print(" ".join(list_a))

Solution (Python):
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

n = int(input())
a = list(map(int, input().split()))
i = partition(a, 0, n-1)
a[i] = "[" + str(a[i]) + "]"
print(" ".join(map(str, a)))

Solution (Python):
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

n = int(input())
A = list(map(int, input().split()))
i = partition(A, 0, n-1)
for k in range(n):
    if (k == (n-1)):
        if (k == i):
            print('[{}]'.format(A[i]), end = '')
        else:
            print('{0}'.format(A[k]), end = '')
        
    elif(k == i):
        print('[{}]'.format(A[i]), end = ' ')
    else:
        print('{}'.format(A[k]), end =' ')
print()

Solution (Python):



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

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

def bracketify(A, i, q):
    return "[" + str(A[i]) + "]" if i == q else str(A[i])

def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    q = partition(A, 0, n - 1)
    print(*[bracketify(A, i, q) for i in range(n)])

main()

Solution (Python):
def swap(a, b):
    return b, a

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

n = int(input())
A = [int(i) for i in input().split()]

B, i = partition(A, 0, n-1)
print(*B[0:i], sep=" ", end=" ")
print("[{0}]".format(B[i]), end=" ")
print(*B[i+1:], sep=" ")

Solution (Python):
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]
    A[i+1] = "[{}]".format(A[i+1])


n = int(input())
A = list(map(int, input().split()))
partition(A, 0, n-1)
print(*A)

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


n = int(input())
a = [int(i) for i in input().split()]

q = partition(a, 0, n-1)

a = [str(i) for i in a]
a[q] = '[%s]' % a[q]
print(' '.join(a))

Solution (Python):

def partition(A,p,r):
    x = A[r]
    i = p - 1
    for j in range(p,r,1):
        if A[j] <= 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
n = int(input())
A = list(map(int,input().split()))
q = partition(A,0,len(A)-1)
print(*['['+str(a)+']' if i==q else a for i,a in enumerate(A)])