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

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

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

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

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

b = partition_l(A,0,len(A)-1)
for i,a in enumerate(A):
    if i == b:
        print('[{}] '.format(a),end='')
    elif i < len(A)-1:
        print('{} '.format(a),end='')
    else:
        print('{}'.format(a),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]
    return i+1


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

index = partition(A, 0, n - 1)
A[index] = "[" + str(A[index]) + "]"
A = map(str, A)
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 = i+1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return A, i+1

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

A_out, pos = partition(A, 0, n-1)
*A_out, = map(str,A_out)


print(" ".join(A_out[:pos]) + " [" + str(A_out[pos]) + "] " + " ".join(A_out[pos+1:]))

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

p = partition(A, 0, n-1)
for i in range(n):
    if i != 0:
        print(" ", end="")
    if i == p:
        print(f"[{A[i]}]", end="")
    else:
        print(A[i], end="")
print()

Solution (Python):
N=int(input())
num_list=list(map(int,input().split()))
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
x=partition(num_list,0,N)
for i in range(N):
    if i==x:
        print([num_list[i]],end=" ")
    elif i==N-1:
        print(num_list[i],end="\n")
    else:print(num_list[i],end=" ")

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

def partition(A):
    x=A[-1]
    i=-1
    for j in range(n-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[-1]
    A[-1]=tmp
    return i+1


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

Solution (Python):
def partition(A, l, r):
    i = l - 1
    for j in range(l, 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
n = int(input())
arr = list(map(int, input().split()))
idx = partition(arr, 0, n - 1)
print(*(arr[0:idx] + ['[' + str(arr[idx]) + ']'] + arr[idx + 1:]))

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

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

for j, a in enumerate(A):
    if j == 0:
        print(a, end='')
    elif j == i:
        print(' [{}]'.format(a), end='')
    else:
        print(' {}'.format(a), end='')
print()

Solution (Python):



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

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

idx = partiton(A, 0, n - 1)

for i in range(n):
	if i == idx:
		A[i] = '[' + str(A[idx]) + ']'

print(*A)

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


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


i = partition(0, n - 1)
S[i] = '[' + str(S[i]) + ']'

print(*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
            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(_) for _ in input().split()]
idx = partition(A, 0, n-1)

print(" ".join(map(str, A[:idx])) + ' [' + str(A[idx]) + '] ' + " ".join(map(str, A[idx+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


if __name__ == "__main__":
    import sys
    input = sys.stdin.readline 

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

    q = partition(A, 0, n-1)
    A[q] = '[{}]'.format(A[q])

    print(' '.join(map(str, A)))

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

    return i+1


y = partition(A,0,n-1)
A = list(map(str,A))
A[y] = "["+A[y]+"]"

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

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

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

for i in range(n):
    if i == r and i == n-1:
        print("["+str(A[i])+"]",end="")
    elif i == r:
        print("["+str(A[i])+"]",end=" ")
    elif i == n-1:
        print(A[i],end="")
    else:
        print(A[i],end=" ")
print()

Solution (Python):
def partition(a,p,r)->int:
    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()))
    index = partition(a,0,n-1)
    print (' '.join(map(str,a[:index])),end=' ')
    print ('[%d]'%a[index],end=' ')
    print (' '.join(map(str,a[index+1:])))


if __name__ == '__main__':
    main()

Solution (Python):
N=input()
L=input()

L=list(map(int,L.split()))

i=0
j=0

x=L[-1]

while j < len(L):
    if L[j] > x:
        j += 1
        
    else:
        L_i = L[i]
        L_j = L[j]
        if j == len(L)-1:
            L_j='['+str(L_j)+']'
        L[i] = L_j
        L[j] = L_i
        i += 1
        j += 1
         
print(' '.join(map(str,L)))

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


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  
  
idx = partition(A, 0, n-1)

def tostr(x,i):
  if i == idx :
    return "[{}]".format(x)
  return str(x)

print(" ".join([tostr(x,i) 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 + 1

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

idx = partition(A, 0, n - 1)
S = " ".join(map(str, A[:idx]))
S += " [" + str(A[idx]) + "] "
S += " ".join(map(str, A[idx + 1:]))
print(S)

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


n = int(input())
A = [int(i) for i in input().split()]
par = partition(A, 0, n - 1)
for i in range(0, par):
    print(A[i], end=" ")
print("[", A[par], "]", sep="", end=" ")
for i in range(par + 1, n - 1):
    print(A[i], end=" ")
print(A[n - 1])

Solution (Python):
def partition(arr, p: int, r: int):
    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()))
index = partition(a, 0, n - 1)
ans = []
for i in range(n):
    ans.append('[' + str(a[i]) + ']' if i == index else str(a[i]))
print(*ans)

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())
A = [int(x) for x in 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())
A = list(map(int, input().split()))

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

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

print(*A)

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


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


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

Solution (Python):

import sys,collections
n = int(sys.stdin.readline())
A = list(map(int,sys.stdin.readline().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
q = partition(A,0,len(A)-1)
print(" ".join([str(e) if i != q else "["+str(e)+"]" for i,e 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 + 1

def Main():
    n = int(input())
    A = [int(a) for a in input().split()]

    idx = Partition(A, 0, n - 1)
    s_A = [str(a) for a in A]
    
    res = " ".join(s_A[:idx]) + " [" + s_A[idx] + "] " + " ".join(s_A[idx + 1:])
    print(res)

Main()

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

    (A[i+1], A[-1]) = (A[-1], A[i+1])

    return " ".join(map(str, A[:i+1])) + " [" + str(A[i+1]) + "] " + " ".join(map(str, A[i+2:]))
    
n = int(input())
X = list(map(int, input().split()))

print(partition(X, n))

Solution (Python):
def partition(A, l, r):
    x = A[r - 1]
    i = l - 1
    for j in range(l, 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, = map(int, input().split())
r = str(A[-1])
partition(A, 0, n)
A = list(map(str, A))
B = []
flg = True
for a in A[::-1]:
    if a == r and flg:
        b = '[{}]'.format(a)
        flg = False
    else:
        b = a
    B.append(b)
print(*B[::-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 = [int(x) for x in 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):
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 = [i for i in map(int,input().split())]

x = partition(A,0,n-1)
ans = []

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

Solution (Python):
def partition(A: list, p: int = 0, r: int = None):
    if r is None:
        r = len(A) - 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


N = int(input())
A = list(map(int, input().split()))
r = partition(A)
A = ["[{}]".format(a) if i == r else str(a) for i, a in enumerate(A)]
print(*A)

Solution (Python):



def pertision(A, l, r):
    pivot = A[r]
    i = 0
    for j in range(l, r):
        if A[j] <= pivot:
            A[l+i], A[j] = A[j], A[l+i]
            i += 1
    A[l+i], A[r] = A[r], A[l+i]      
    
    return l+i

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

pivot_i = pertision(A, 0, N-1)

s = []
for i in range(N):
    if i == pivot_i:
        s.append('[{}]'.format(A[i]))
    else:
        s.append(str(A[i]))

print(*s)

Solution (Python):
N = int(input())
num_list = [int(item) for item 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 A, i+1


res, index = partition(num_list, 0, len(num_list)-1)

res_out = ''
for i, v in enumerate(res):
    if i == index:
        res_out += '['+ str(v) + '] '
    else:
        res_out += str(v) + ' ' 
    
print(res_out[:-1])

Solution (Python):

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

_ = int(raw_input())
nums = map(int, raw_input().split(" "))
p = partition(nums, 0, len(nums)-1)
nums[p] = "[{}]".format(nums[p])
sys.stdout.write(str(nums[0]))
for n in nums[1:]:
    sys.stdout.write(" {}".format(n))
sys.stdout.write("\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
            tmp = A[j]
            A[j] = A[i]
            A[i] = tmp
        else:
            continue
    A[r] = A[i+1]
    A[i+1] = x
    return i+1

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    x = partition(a, 0, n-1) 
    A = [str(a[i]) for i in range(n)]
    A[x] = '[' + A[x] + ']'
    for i in range(n):
        if i == n-1:
            print(A[i])
        else:
            print(A[i], end=' ')
main()

Solution (Python):
import bisect

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

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

print(*a[:p_ind], '['+str(a[p_ind])+']', *a[p_ind+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, len(A) - 1)
A[index] = "[{}]".format(A[index])
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 = 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])
    return i + 1


if __name__ == "__main__":
    input()
    A = [int(x) for x in input().split()]
    target = A[-1]

    partition(A, 0, len(A) - 1)
    output_str = [str(a) for a in A]
    print(' '.join(output_str))

Solution (Python):
def partition(A, l, r):
    """ partition A[l:r] using q(A[r]) and return q's index
    """
    q = A[r]
    sep_i = l 
    for j in range(l, r):
        if A[j] <= q:
            
            
            
            A[sep_i], A[j] = A[j],  A[sep_i]
            sep_i += 1 
        else:
            
            pass

    A[sep_i], A[r] = A[r], A[sep_i]
    
    return sep_i

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

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

print(*A[:q_i],  '[' + str(A[q_i]) + ']', *A[q_i+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()))

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):
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())
A = [int(x) for x in 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):
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())
B = list(map(int,input().split()))
b = partition(B,0,N-1)

B_str = list(map(str,B))
B_str[b] = '[' + B_str[b] +']'
print(' '.join(B_str))

Solution (Python):

input_n = int(input())
input_a = list(map(int, input().split()))
position = -1


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


position = partition(input_a, input_n)
print(" ".join(map(str, input_a[0:position])), end="")
print(f" [{input_a[position]}] ", end="")
print(" ".join(map(str, input_a[position+1:])))

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 = [int(s) for s in input().split()]
t = partition(a,0,n-1)
print(*(str(x) if i != t 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+1

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

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

Solution (Python):
def partition(p, r):
    x = A[r]
    i = - 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]
    print(' '.join(list(map(str, A))))

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

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

qi=part(a,0,len(a)-1)
list_qi=[a[qi]]
a[qi]=list_qi
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 A, i+1
n = int(input())
A = list(map(int, input().split(' ')))
parted_A, idx = partition(A, 0, n-1)
str_parted_A = list(map(str, parted_A))
str_parted_A[idx] = "[{}]".format(str_parted_A[idx])
print(" ".join(str_parted_A))

Solution (Python):
n = int(input())

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

def partition(B, p, r):
  x = B[r]
  global i
  i = p-1
  for j in range(p, r):
    if B[j] <= x:
      i += 1
      y = B[i]
      z = B[j]
      B[i] = z
      B[j] = y
  a = B[i+1]
  b = B[r]
  B[i+1] = b
  B[r] = a

partition(A, 0, n-1)

print(" ".join(map(str, A[:i+1])), end='')
print(" [" + str(A[i+1]) + "] ", end='')
print(" ".join(map(str, A[i+2:])))

Solution (Python):
"""
配列の一番左の値Xを基準に
それより小さい値と大きい値を分けて再配置するコード
Xより小さい値はiより左に、大きい値は右側に配置する。
jは現在探索している添字
"""


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



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

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

















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

Solution (Python):





def exchangeData(A, it1, it2):
    tmp = A[it1]
    A[it1] = A[it2]
    A[it2] = tmp


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

    exchangeData(A, i+1, r)
    return i+1


def print_partitionData(A, part_index):
    for i, s in enumerate(A):
        if i !=0:
            print(" ", end= "")

        if i==part_index :
            print ("[{}]".format( s), end="")
        else:
            print (s, end="")
    print("")

        
def inputData():
    data = map(int, input().split())
    return list(data)

if __name__ == "__main__" :
    input()
    A = inputData()
    part_index = partition(A, 0, len(A)-1)
    print_partitionData(A, part_index)

Solution (Python):


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

    return i+1

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

result = ''
for i in range(len(A)):
    if i == p:
        result += '['+str(A[i])+'] '
    else:
        result += str(A[i]) + ' '

print(result[:-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 = i + 1
            y = A[i]
            A[i] = A[j]
            A[j] = y
    z = A[i+1]
    A[i+1] = '['+str(A[r])+']'
    A[r] = z
    return i + 1

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

partition(A, 0, n-1)

print(*A)

Solution (Python):
def partition(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] = f"[{A[i + 1]}]"
    print(" ".join(map(str, A)))
    return i + 1


input()
A = list(map(int, input().split()))
partition(0, len(A) - 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[j], A[i] = A[i], A[j]
        else:
            pass 
    A[i+1], A[r] = A[r], A[i+1]
    return i+1, A 


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

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

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

num = partition(A,0,n)
A[num] = "[" + str(A[num]) +"]"
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


if __name__ == '__main__':
    import sys

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

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

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

x = A[-1]
i = -1
for j in range(0, len(A) - 1):
    if x >= A[j]:
        i += 1
        A[i], A[j] = A[j], A[i]
A[i+1], A[-1] = A[-1], A[i+1]
q = i + 1

return_str = str(A[0])
for i, k in enumerate(A):
    if i != 0:
        if i == q:
            return_str += " [" + str(k) + "]"
        else:
            return_str += ' ' + str(k)

print(return_str)

Solution (Python):
def partition(array, start, end):
    end_val = array[end]
    left_end = start - 1
    for search_idx in range(start, end):
        if array[search_idx] <= end_val:
            left_end += 1
            array[left_end], array[search_idx] = array[search_idx], array[left_end]
    array[left_end + 1], array[end] = array[end], array[left_end + 1]
    return left_end + 1


def main():
    n = int(input())
    array = list(map(int, input().split(" ")))
    partition_idx = partition(array, 0, n - 1)
    array = list(map(str, array))
    print(" ".join(array[:partition_idx]) +
          " [{}] ".format(array[partition_idx]) +
          " ".join(array[partition_idx + 1:]))


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

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

for j in range(n - 1):
    if j == q:
        print("[{}]".format(A[q]), end=' ')
    else:
        print(str(A[j]), end=' ')
print(A[-1])

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

buf = i = j = 0
x = A[n-1]
for j in range(n-1):
    if A[j] <= x:
        buf = A[i]
        A[i] = A[j]
        A[j] = buf
        i += 1
A[n-1] = A[i]
A[i] = x
k = 0
[print(A[k],"",end="") if k != i else print("[",A[k],"]",sep="",end=" ") for k in range(n-1)]
print(A[n-1])

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

tmp = partition(A, 0, n)
for i in range(n - 1):
    if i == tmp:
        print("[" + str(A[tmp]) + "]", end = " ")
    else:
        print(A[i], end = " ")
print(A[-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, *A = map(int, open(0).read().split())
f = partition(A, 0, n-1)
ans = ''
for i in range(n):
    if i == f:
        ans += f'[{A[i]}] '
    else:
        ans += f'{A[i]} '
print(ans[:len(ans) - 1])

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
r=""
q=partition(a,0,n-1)
for i in range(n):
	if i:
		r+=(" ")
	if i==q:
		r+=("[")
	r+=str(a[i])
	if i==q:
		r+=("]")
print(r)