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):
def partition(A, p, r):
    key = A[r]
    i = p
    for j in range(p, r):
        
        if A[j] <= key:
            A[i], A[j] = A[j], A[i]
            i += 1
    
    A[r], A[i] = A[i], A[r]
    return i


if __name__ == '__main__':
    n = int(input())
    numlist = [int(num) for num in input().split(' ')]
    index = partition(numlist, 0, len(numlist) - 1)
    out = str(numlist[0:index]).replace(',', '').replace('[', '').replace(']', '') \
        + ' [' + str(numlist[index]) + '] '\
        + str(numlist[index + 1:]).replace(',', '').replace('[', '').replace(']', '')
    print(out)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

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

def main():
    n=int(input())
    aa=list(map(int, input().split()))
    idx=Partition(aa,0,n-1)
    aa[idx]="["+str(aa[idx])+"]"
    print(*aa)
main()

Solution (Python):
def partition(A, left, right):
    pivot = A[right]
    i = -1
    for j in range(left, right):
        if A[j] <= pivot:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[right] = A[right], A[i+1]
    return i + 1


if __name__ == "__main__":
    n = int(input())
    *A, = map(int, input().split())
    
    k = partition(A, 0, len(A)-1)

    A[k] = '[' + str(A[k]) + ']'
    print(*A)

Solution (Python):

def partition(p, r):
    global A

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

q = partition(0, N-1)

A_str = list(map(str, A))
A_str[q] = '[' + A_str[q] + ']'

print(' '.join(A_str))

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)
A[P]="["+str(A[P])+"]"
print(*A)

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

x = A[-1]
i=0
for j in range(n-1):
    if A[j]<=x:
        A_j=A[j]
        A[j]=A[i]
        A[i]=A_j
        i+=1
A[-1]=A[i]
A[i]=[x]

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
            w = A[i]
            A[i] = A[j]
            A[j] = w
    v = A[i+1]
    A[i+1] = A[r]
    A[r] = v
    return i + 1

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



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



for i in range(n):
    if i:
        print(" ", end = "")
    if i == p:
        print("[", end="")
    print(A[i], end="")
    if i == p:
        print("]", end="")
print()

Solution (Python):
n = int(input())
s = list(map(int, input().split()))
def partition(s, l, r):
    pivot = s[r]
    minVI = -1
    i = l
    while i < r:
        if s[i] <= pivot:
            minVI+=1
            s[minVI], s[i] = s[i], s[minVI]
        i+=1
    s[minVI+1], s[r] = s[r], s[minVI+1]
    return minVI+1
pivotI = partition(s, 0, len(s)-1)
answer = ''
for i in range(len(s)):
    if i!= 0:
        answer+=' '
    if i == pivotI:
        answer+='['+str(s[i])+']'
    else:
        answer+=str(s[i])
print(answer)

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


if __name__ == '__main__':
    n = int(input())
    arr = list(map(int, input().split()))
    index = partition(arr, 0, n - 1)
    for i in range(n):
        if i != 0:
            print(' ', end='')
        if i == index:
            print('[', end='')
        print(arr[i], end='')
        if i == index:
            print(']', end='')
    print()

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
            m=A[i]
            A[i]=A[j]
            A[j]=m
    m=A[i+1]
    A[i+1]="["+str(x)+"]"
    A[r]=m
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-1]
    i = p-1
    for j in range(p,r):
        if A[j] <= x:
            i = i+1
            A[i], A[j] = A[j], A[i]
    return i+1

n = int(input())
A = list(map(int,input().split()))
num = partition(A, 0, n)
A[num-1] = f"[{A[num-1]}]"
print(*A)

Solution (Python):
n = int(input())
A = list(map(int, input().split(" ")))

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

q = partition(A, 0, n)
A[q] = "[" + str(A[q]) + "]"
print(*A)

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

N = int(input())
A = list(map(int, input().split()))
q = partition(A, 0, N)
print(*['['+str(A[i])+']' if i == q else A[i] for i in range(N)])

Solution (Python):
import sys
input = sys.stdin.readline

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


def main():
    
    partition(A, 1, len(A) - 1)


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

        
    tmp = A[i]
    A[i] = A[r]
    A[r] = tmp

    for k in range(len(A)):
        if k > 0:
            print(' ', end="")
        if k == i:
            strNum = "[" + str(A[k]) + "]"
        else:
            strNum = str(A[k])
        print(strNum, end="")
    print()
    


if __name__ == '__main__':
    main()

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

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

j = partition(A, 0, n - 1)
A = [str(i) for i in A]
A[j] = '[{}]'.format(A[j])
print(' '.join(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


if __name__ == "__main__":
	n = int(input())
	A = list(map(int, input().split()))
	q = partition(A, 0, n-1)
	A[q] = '[' + str(A[q]) + ']'
	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 = i+1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1


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

idx = partition(A, 0, len(A) - 1)
A[idx] = f'[{A[idx]}]'
print(*A)

Solution (Python):
"""
パーティション
ある基準の値を元に分類わけするアルゴリズム
12
13 19 9 5 12 8 7 4 21 2 6 11
"""

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



if __name__=="__main__":
    n = int(input())
    A = list(map(int, input().split()))
    reference_index  = partition(A, n)
    A_str = []
    for x, a in enumerate(A):
        if x == reference_index:
            A_str.append("["+str(a)+"]")
        else:
            A_str.append(str(a))
    print(" ".join(A_str))

Solution (Python):
n = int(input())
S = list(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

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

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

Solution (Python):
def Partition(NUM_LIST, left, right):
    NUM_LIST = NUM_LIST[left:right]
    v = NUM_LIST[-1]
    border = 0
    for i in range(len(NUM_LIST)-1):
        if v >= NUM_LIST[i]:
            NUM_LIST[border], NUM_LIST[i] = NUM_LIST[i], NUM_LIST[border]
            border+=1
    NUM_LIST[border], NUM_LIST[-1] = NUM_LIST[-1], NUM_LIST[border]
    return border, NUM_LIST

n = int(input())
NUM_LIST = list(map(int, input().split()))
border, NUM_LIST = Partition(NUM_LIST, 0, len(NUM_LIST))

print(" ".join(list(map(str, NUM_LIST[:border]))) + " ["+str(NUM_LIST[border])+"] "
+" ".join(list(map(str, NUM_LIST[border+1:]))))

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
            A[i], A[j] = A[j], A[i]
    return i

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

index = partition(A, 0, N - 1)

for i in range(N):
    if i == index:
        print('[{0}]'.format(A[i]), end='')
    else:
        print(A[i], end='')
    if i < N - 1:
        print(' ', end='')

print()

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

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

p = Partition(A,0,N-1)

for i in range(N):
    if i != 0:
        print(" ",end="")
    if i == p:
        print("[",end="")
    print(A[i],end="")
    if i == p:
        print("]",end="")
print()

Solution (Python):

import sys


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

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


n = int(input())
A = [int(i) for i in sys.stdin.readline().strip().split()]

q = partition(A, 0, n - 1)
print(' '.join(map(str, A[0: q])), end='')
print(' [{}] '.format(str(A[q])), end='')
print(' '.join(map(str, A[q + 1: n])))

Solution (Python):
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] = 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()))
    b = partition(A, 0, len(A)-1)
    a = list(map(str, A))
    a[b] = "[" + a[b] + "]"
    print(' '.join(a))

Solution (Python):
import sys
input = sys.stdin.readline

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 main():
    n = int(input())
    A = list(map(int, input().split()))
    i = partition(A, 0, n-1)
    for j in range(n):
        if j:
            print(' ', end='')
        if j == i:
            print('[', end='')
        print(A[j], end='')
        if j == i:
            print(']', end='')
    print()
if __name__ == '__main__': main()

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
            temp=a[i]
            a[i]=a[j]
            a[j]=temp
    temp=a[i+1]
    a[i+1]=a[r]
    a[r]=temp
    return i+1

n=int(input())
*a,=map(int,input().split())

ans=partition(a,0,n-1)
a=list(a)
a[ans]="["+str(a[ans])+"]"
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[i+1]
    A[i+1] = A[r]
    A[r] = tmp
    return i+1
    
n = int(input())
A = list(map(int, input().split()))

p = partition(A, 0, n-1)
A = ["[" + str(A[i]) + "]" if i == p else str(A[i]) for i in range(n)]
print(*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

def test():

	n = int(sys.stdin.readline())
	A = list(map(int,sys.stdin.readline().split()))
	Ptt = Partition(A,0,n-1)

	for i in range(n):

		if i == Ptt:
			print(f"[{A[i]}]",end='')
		else:
			print(f"{A[i]}",end='')

		if i != n-1:
			print(" ",end='')
		else:
			print()


if __name__ == "__main__":
	test()

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

i = -1

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

A[i+1], A[n-1] = A[n-1], A[i+1]

A[i+1] = '[' + str(A[i+1]) + ']'

print(*A)

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

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

num = int(input())
num_list = [int(s) for s in input().split()]

idx = partition(num_list, 0, len(num_list) - 1)

print(*num_list[:idx], end="")
print(" [" + str(num_list[idx]) + "] ", end="")
print(*num_list[idx+1:])

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

def main():
    n = int(input())
    A = [int(x) for x in input().split()]

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

    left = A[:q+1]
    p = A[q+1]
    right = A[q+2:]
    print('{0} [{1}] {2}'.format(' '.join(map(str, left)), p, ' '.join(map(str, right))))
             
if __name__ == "__main__":
    main()

Solution (Python):
n=int(input())
A=list(map(int,input().split()))
x=A[-1]
i=-1
for j in range(n-1):
	if A[j]<=x:
		i=i+1
		A[i],A[j]=A[j],A[i]
A[i+1],A[-1]=A[-1],A[i+1]
print(*A[:i+1], end=' ')
print(f'[{A[i+1]}]', end=' ')
print(*A[i+2:])

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()))
q = partition(A, 0, n - 1)
for i in range(n):
    if i != 0:
        print(" ", end="")
    if i == q:
        print("[", end="")
    print(A[i], end="")
    if i == q:
        print("]", end="")
print("")

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

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

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

Solution (Python):
def partition(A,p,r):
    x=int(A[r])
    i=p-1
    for j in range(p,r):
        if int(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=[str(i) for i in input().split()]
q=partition(A,0,n-1)
print(' '.join(A[:q]) , '['+A[q]+']',' '.join(A[q+1:]))

Solution (Python):
def main():
    n = int(input())
    a_s = list(map(int, input().split(' ')))
    q = partition(a_s, 0, n-1)

    def display(index, a):
        if index == q:
            return '[{}]'.format(a)
        else:
            return str(a)

    print(' '.join([display(i, a) for i, a in enumerate(a_s)]))


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


if __name__ == "__main__":
    main()

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[i],A[j] = A[j],A[i]
  A[i+1],A[r-1] = A[r-1],A[i+1]
  return i+1
n = int(input())
A = [int(i) for i in input().split()]
idx = partition(A,0,n)
A[idx] = "["+str(A[idx])+"]"
print(" ".join(map(str,A)))

Solution (Python):
def s():
 n=int(input())-1
 A=list(map(int,input().split()))
 i=0
 for j in range(n):
  if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
 A[i],A[n]=A[n],A[i]
 print(" ".join(map(str,A[:i]))+" ["+str(A[i])+"] "+" ".join(map(str,A[i+1:])))
if'__main__'==__name__:s()

Solution (Python):
from typing import List


def partition(elements: List[int], start_idx: int, pivot_idx: int) -> int:
    pivot = elements[pivot_idx]
    i = start_idx - 1

    for j in range(start_idx, pivot_idx):
        if elements[j] <= pivot:
            i += 1
            elements[i], elements[j] = elements[j], elements[i]
    elements[i + 1], elements[pivot_idx] = elements[pivot_idx], elements[i + 1]

    return i + 1


if __name__ == "__main__":
    n = int(input())
    elements = list(map(lambda x: int(x), input().split()))

    

    pivot_idx = partition(elements, 0, n - 1)

    print(" ".join([f"{elem}" if pivot_idx != idx else f"{[elem]}"
                    for idx, elem in enumerate(elements)]))

Solution (Python):

def partition(arr, left, right):
    x = arr[right]
    i = left - 1
    for j in range(left, right):
        if arr[j] <= x:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[right] = arr[right], arr[i + 1]
    return i + 1

if __name__ == '__main__':
    n = int(input())
    A = list(map(int, input().split()))

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

    for i in range(n):
        if i:
            print(' ', end='')
        if i == pos:
            print('[%d]'%(A[i]), end='')
        else:
            print(A[i], end='')

    print()

Solution (Python):
from enum import Enum
from queue import Queue
import collections

import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

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

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

Solution (Python):
def partition(A, p, r):
    
    x = A[r]
    i = p - 1
    j = p
    
    
    while j < r:
        if A[j] > x:
            j += 1
        else:
            i += 1
            A[i], A[j] = A[j], A[i]
            j += 1
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1


if __name__ == '__main__':
    n = int(raw_input())
    A = map(int, raw_input().split())
    q = partition(A, 0, n - 1)
    for i in range(n):
        if i == q:
            print "[%d]" % (A[i]),
        else:
            print A[i],
    print

Solution (Python):
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]=A[j],A[i]
    A[i+1],A[r]=A[r],A[i+1]
    return i+1

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

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

print(*A[0:c],end=" ")
print(f"[{A[c]}]",end=" ")
print(*A[c+1:n])

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

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

idx = partition(A, 0, len(A) - 1)

B = []
for i in range(n):
    if i == idx:
        B.append('[' + str(x) + ']')
    else:
        B.append(str(A[i]))

print(' '.join(B))

Solution (Python):
def partition(arr, p, r):
    x = arr[r]
    i = p - 1
    for j in range(p, r):
        if arr[j] <= x:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[r] = arr[r], arr[i + 1]
    print(" ".join(str(ele) if j != i + 1 else "[{}]".format(ele) for j, ele in enumerate(arr)))


n = int(input())
arr = list(map(int, input().split()))
partition(arr, 0, n - 1)

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


def main():
    n = int(input())
    A = list(map(int, input().split()))
    q = partition(A, 0, len(A)-1)
    for i in range(q):
        print(A[i], end=" ")
    print("[{}]".format(A[q]), end=" ")
    for i in range(q+1, n):
        if i == n-1:
            print(A[i])
        else:
            print(A[i], end=" ")


if __name__ == '__main__':
    main()

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

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


pat = partition(A,0,len(A)-1)

for i in range(len(A)):
  if i == pat:
    print("[%d]" %(A[i]),end="")
  else:
    print(A[i],end = "")
  if i != len(A)-1:
    print(" ",end="")

print()

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]
    q = i + 1

    return q


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

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

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  A, i+1

def main():
    n = int(input())
    A = list(map(int, input().split()))
    A, i = partition(A, 0, len(A))
    for j, a in enumerate(A):
        if j == i:
            print(f"[{a}] ", end="")
        elif j == (len(A)-1):
            print(f"{a}")
        else:
            print(f"{a} ", end="")
        




if __name__ == "__main__":
    main()

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

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

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

result = list(map(str, A))
result[q] = '[' + result[q] + ']'

print(' '.join(result))

Solution (Python):
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    def swap(a, i, j):
        
        k = a[j]
        a[j] = a[i]
        a[i] = k

    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


    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="")
        print(A[i], end="")
        if i==q:
            print("]", end="")
    print()

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

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

q, A = Partition(A, 0, n-1)
for ni in range(n-1):
    if ni == q:
        print("[" + str(A[ni]) + "]",end = " ")
    else:
        print(A[ni], end = " ")
print(A[n-1])

Solution (Python):
from sys import stdin

def partition(A):
    
    p = A[-1]

    
    p_idx = 0
    for i, num in enumerate(A[:-1]):
        if num <= p:
            A[p_idx], A[i] = A[i], A[p_idx]
            p_idx = p_idx + 1
    A[p_idx], A[len(A) - 1] = A[len(A) - 1], A[p_idx]
    return p_idx

def main():
    lines = stdin.readlines()
    nums = [int(n) for n in lines[1].split(' ')]
    p_idx = partition(nums)
    res = [str(n) if i != p_idx else '['+str(n)+']' for i, n in enumerate(nums)];
    print(' '.join(res))

if __name__ == '__main__':
    main()

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


if __name__ == "__main__":
    n = int(input())
    A = list(map(int, input().split()))
    i = partition(A, 0, n-1)
    A[i] = f"[{A[i]}]"
    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
      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()))
idx = partition(A, 0, n-1)

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

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()))
index = partition(A, 0, n-1)
A[index] = '[' + str(A[index]) + ']'
print(*A)

Solution (Python):
n =  int(input())
nums = list(map(int,input().split(" ")))
ref = nums[-1]

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

partition(nums,0,ref)
indexes = [i for i, x in enumerate(nums) if x == ref]

ans = ""
for i in range(n):
    if i == indexes[-1]:
        ans += "[" + str(nums[i]) + "] "
    else:
        ans += str(nums[i]) + " "

print(ans[0:-1])

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

Solution (Python):



def partition(array, p, len_array):
    X = array[len_array]
    i = 0 - 1
    for j in range(p, len_array):
        if array[j] <= X:
            i += 1
            tmp = array[i]
            array[i] = array[j]
            array[j] = tmp
    tmp = array[i + 1]
    array[i + 1] = array[len_array]
    array[len_array] = tmp
    
    return i + 1, array
    
len_array = int(input()) - 1
array = [int(i) for i in input().split()]
p = 0 

index, array = partition(array, p, len_array)


str_array = list(map(str, array))

str_array[index] = '[{}]'.format(str_array[index])
print(' '.join(str_array))

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())
*s, = map(int, input().split())

c = partition(s, 0, n - 1)
for i in range(n):
    s[i] = f"[{s[i]}]" if i == c else s[i]
print(" ".join([str(v) for v in s]))

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[r], a[i + 1] = a[i + 1], a[r]
    return i + 1






n = int(input())
l = [int(i) for i in input().split()]
x = partition(l, 0, n - 1)

for i in range(n - 1):
    if i == x:
        char = "[" + str(l[i]) + "]"
    else:
        char = str(l[i])
    print(char, end=" ")
print(l[-1])

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
_ = input()
A = [int(num) for num in input().split()]
p = 0
r = len(A)-1
q = partition(A, p, r)
A_str = [str(a) for a in A]
A_str[q] = "[" + A_str[q] + "]"
print(" ".join(A_str))

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

def printA(A, pos):
    for i in range(len(A)):
        if i == pos:
            print("["+str(A[i])+"]",end="")
        else:
            print(str(A[i]),end="")
        if i == len(A)-1:
            print()
        else:
            print(" ",end="")

n = int(input().rstrip())
A = list(map(int,input().rstrip().split()))
ret = partition(A, 0, len(A)-1)
printA(A, ret)

Solution (Python):
import sys
input = sys.stdin.readline

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

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

r = partition(S, 0, N-1)

S = [str(x) for x in S]

print('{} [{}] {}'.format(' '.join(S[:r]), S[r], ' '.join(S[r+1:])))

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

n = int(input())
A = list(map(int,input().split()))
pos = partition(A, 0, n - 1)
val = A[pos]
A.pop(pos)
A.insert(pos, [val])
print(*A)