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 printAns( A, index ):
    n = len(A)
    for i in range(0, index):
        print( str( A[i] ), end=" ")
    print( "[" + str(A[index]), end="] ")
    for i in range(index+1, n-1):
        print( str( A[i] ), end=" ")
    print( str( A[n-1] ) )

def partition(A, p, r):
    tmp = 0
    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] = A[r]
    A[r] = tmp
    printAns(A, i+1)
    return i+1

def main():
    n = int( input() )
    A = [int(x) for x in input().split()]
    index = partition(A, 0, n-1)

if __name__ == "__main__":
    main()

Solution (Python):
import sys


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

    for j in range(r):
        if A[j] <= x:
            i += 1
            tmpA = A[i]
            A[i] = A[j]
            A[j] = tmpA

    tmpB = A[i+1]
    A[i+1] = A[r]
    A[r] = tmpB
    for j in range(n):
        if j > 0:
            ans += " "
        if j == i+1:
            ans += "["+str(A[j])+"]"
        else:
            ans += str(A[j])
    print(ans)


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

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())
l = list(map(int, input().split()))
i = partition(l, 0, n - 1)
l[i] = "[%d]"%l[i]
print(*l)

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

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

n = int(input())
a = list(map(int, input().split()))
idx = partition(a, 0, len(a) - 1)
if idx == 0:
	print('[' + str(a[0]) + ']', end='')
else:
	print(a[0], end='')
for i in range(1, n):
	print(' ', end='')
	if idx == i:
		print('[' + str(a[i]) + ']', end='')
	else:
		print(a[i], 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
			swap(a, i, j)
	swap(a, i + 1, r)
	return i + 1

def swap(a, i, j):
	tmp = a[i]
	a[i] = a[j]
	a[j] = tmp
	
n = int(input())
a = list(map(int, input().split()))
idx = partition(a, 0, len(a) - 1)
if idx == 0:
	print('[' + str(a[0]) + ']', end='')
else:
	print(a[0], end='')
for i in range(1, n):
	print(' ', end='')
	if idx == i:
		print('[' + str(a[i]) + ']', end='')
	else:
		print(a[i], 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]
    for j,k in enumerate(A):A[j] = str(k)
    A[i+1] = "["+A[i+1]+"]"
    return i+1

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

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

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]
    return i+1
        
r = partition(0, N-1)
print(" ".join(map(str, A[:r]))+" ["+str(A[r])+"] "+" ".join(map(str, A[r+1:N])))

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


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

out = [str(a) for a in A]
out[q] = '[' + out[q] + ']'
print(' '.join(out))

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)
print(*A[:i], '[{}]'.format(A[i]), *A[i + 1:])

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


n = int(input())
A = [int(_) for _ in input().split()]
q = partition(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):
def swap(a,i,j):
	t=a[i]
	a[i]=a[j]
	a[j]=t

def partition(a,p,r):
	x=a[r]
	i=p-1
	for j in range(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()))
p=partition(a,0,n-1)
for i in range(n):
	if i==p:print('[',end='')
	print(a[i],end='')
	if i==p:print(']',end='')
	if i!=n-1:print(' ',end='')
print()

Solution (Python):
def partition(array, first, end):
    criteria = array[end]
    i_ins = first
    for i_cur in range(first, end):
        if array[i_cur] <= criteria:
            array[i_ins], array[i_cur] = array[i_cur], array[i_ins]
            i_ins += 1
    array[i_ins], array[end] = array[end], array[i_ins]
    return i_ins


def main():
    n = int(input())
    array = [int(x) for x in input().split()]
    i_ins = partition(array, 0, n-1)
    outputtxt = ""
    if i_ins != 0:
        outputtxt += " ".join([str(x) for x in array[:i_ins]]) + " "
    outputtxt += "[{}]".format(array[i_ins])
    if i_ins < n-1:
        outputtxt += " " + " ".join([str(x) for x in array[i_ins + 1:]])
    print(outputtxt)
    return


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 = 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+1):
        if A[j] <= x:
            i = i + 1
            A[i], A[j] = A[j], A[i]

    return i


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 = 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()))
mid = partition(A,0,n-1)
print(' '.join(map(str,A[:mid])),'['+str(A[mid])+']',' '.join(map(str,A[mid+1:])))

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

s = 0
last = a[-1]

for i in range(n-1):
    if a[i] <= last:
        tmp = a[i]
        a[i] = a[s]
        a[s] = tmp
        s += 1
tmp = a[-1]
a[-1] = a[s]
a[s] = tmp

for i in range(0, s):
    print(a[i], end=' ')
print('[' + str(a[s]) + '] ', end='')
for i in range(s+1, n-1):
    print(a[i], end=' ')
print(a[n-1])

Solution (Python):
def InputData():
    
    sequence_len = int(input())
    sequence = list(map(int, input().split(" ")))

    return sequence_len, sequence

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

def PrintOut(sequence):
    print(' '.join( map(str, sequence)))

def main():
    [sequence_len, sequence] = InputData()
    q = partition(sequence, 0, sequence_len-1)
    sequence[q] = "[" + str(sequence[q]) + "]"
    PrintOut(sequence)

if __name__=="__main__":
    main()

Solution (Python):
n = int(input())
lst_n = list(map(int,input().split()))
x = lst_n[n-1]
left  = []
right = []
i = -1
for j in range(0,n-1):
    if lst_n[j] <= x:
        i += 1
        lst_n[i],lst_n[j] = lst_n[j],lst_n[i]
i += 1
lst_n[i],lst_n[n-1] = lst_n[n-1],lst_n[i]

ans = ['['+str(lst_n[k])+']' if k == i else str(lst_n[k])
        for k in range(len(lst_n))]
print(' '.join(ans))

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


def partition(a, left, right):
    standard = a[right]
    cnt = left
    for i in range(left, right+1):
        if i == right:
            if a[i] <= standard:
                a[i],a[cnt] = a[cnt], [a[i]] 
        elif a[i] <= standard:
            a[cnt],a[i] = a[i], a[cnt]
            cnt += 1
    print(*a)
    return cnt

partition(a, 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[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, a in enumerate(A):
    if i == q:
        print('[', end='')
    print(a, end='')
    if i == q:
        print(']', 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]

	return i+1

if __name__ == '__main__':

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

	end = len(A)
	p = 0
	r = end - 1
	cnt = partition(A,p,r)

	ans = []
	for i,j in enumerate(A):
		if i == cnt:
			ans.append("["+str(j)+"]")
		else:
			ans.append(str(j))

	print(" ".join(ans))

Solution (Python):
input()
a=raw_input().split()
b=a.pop()
i=0
for j in range(len(a)):
    if int(a[j])<=int(b):
        a[i],a[j]=a[j],a[i]
        i+=1
a[i],b="["+b+"]",a[i]
print " ".join(a+[b])

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

n = input()
a = list(map(int, input().split()))
q = partition(a, 0, len(a) - 1)
a[q] = '[{}]'.format(a[q])
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]
    return i + 1

n = int(input())
a = list(map(int, input().split()))
q = partition(a, 0, len(a) - 1)
a[q] = '[{}]'.format(a[q])
print(*a)

Solution (Python):
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in xrange(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(raw_input())
A = map(int, raw_input().split())
q = partition(A, 0, n-1)
s = ""
for i, x in enumerate(A):
    if i == q:
        s += "[" + str(x) + "]"
    else:
        s += str(x)
    s += " "
print s[:len(s)-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 = input()
a = map(int, raw_input().split())
r = partition(a,0,n-1)
print " ".join(map(str,a[:r])) + " [" + str(a[r]) + "] " + " ".join(map(str,a[r+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
      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 = sys.stdin.readline()
  for line in sys.stdin:
    items = line.strip().split()
    items = [ int(item) for item in items ]
    target = partition(items, 0, len(items) - 1)
    items[target] = "[%s]" % (items[target])
    print " ".join([ str(item) for item in items ])

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

n = sys.stdin.readline()
n = int(n)

data = sys.stdin.readline()
data_list = data.split(" ")

data_list = map(int, data_list)

co = partition(data_list, 0, n-1)

data_list = map(str, data_list)

data_list[co] = "[{0}]". format(data_list[co])

print " ".join(data_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



if __name__ == "__main__":
    lines = sys.stdin.readlines()
    N = int(lines[0])
    nums = map(int, lines[1].split(" "))
    (i, A) = partition(nums, 0, N-1)
    A = map(str, A)
    A[i] = "[{0}]".format(A[i])
    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())
s=input()
a=list(map(int,s.split()))
m=partition(a,0,n-1)
a=list(map(str,a))
a[m]="[%s]"%(a[m])
print(" ".join(a))

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

def main():
    num = raw_input()
    num_list = raw_input().split()
    num_list = map(int, num_list)

    index = partition(num_list, 0, len(num_list)-1)
    num_list = map(str, num_list)
    num_list[index] = "[" + num_list[index] + "]"
    print " ".join(num_list)

if __name__ == "__main__":
    main()

Solution (Python):
N = int(raw_input())

A_str = raw_input().split()
A = map(int, A_str)

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

print "%s [%d] %s" % (' '.join(map(str, A[:i-1])), A[i-1], ' '.join(map(str, A[i:])))

Solution (Python):
n = int(raw_input())
A_str = raw_input().split(" ")
A = map(int, A_str)

i = 0

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

print "%s [%d] %s" % (" ".join(map(str, A[:i-1])), A[i-1], " ".join(map(str, A[i:])))

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

    
    
if __name__ == "__main__":
    num = int(raw_input())
    num_list = raw_input().strip().split()
    num_list = map(int, num_list)
    i = partition(num_list, 0, len(num_list))
    num_list = map(str, num_list)
    data = ""
    for j in range(len(num_list)):
        if j == i:
            data += "[" + num_list[j] + "] "
        else:
            data += num_list[j] + " "
    print data[:-1]

Solution (Python):
def pertition(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(raw_input())
a = raw_input()
l = []
l = a.split(" ")
for i in range(len(l)):
	l[i] = int(l[i])
i = pertition(l, 0, n - 1)
l[i] = "[" + str(l[i]) + "]"
print " ".join(map(str, l))

Solution (Python):




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

    return i + 1, array


def main():
    n = raw_input()
    num = raw_input()
    array = num.strip().split(" ")
    array = map(int, array)
    index, new_array = partition(array, 0, len(array) - 1)
    new_array = map(str, new_array)
    new_array[index] = "[" + new_array[index] + "]"
    print " ".join(new_array)

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

mid = Partition(data,0,len(data)-1)
for i in range(0,mid):
    print(data[i],end=" ")
print("[{0}] ".format(data[mid]),end="")
for i in range(mid+1,len(data)-1):
    print(data[i],end=" ")
print(data[len(data)-1])

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

    
    
if __name__ == "__main__":
    num = int(raw_input())
    num_list = raw_input().strip().split()
    num_list = map(int, num_list)
    i = partition(num_list, 0, len(num_list))
    num_list = map(str, num_list)
    data = ""
    for j in range(len(num_list)):
        if j == i:
            data += "[" + num_list[j] + "] "
        else:
            data += num_list[j] + " "
    print data[:-1]

Solution (Python):
n = int(raw_input())
S = map(int,raw_input().strip().split(' '))

def partition(S,p,r):
    x = S[r]
    i = p-1
    for j in range(p,r):
        if S[j] <= x:
            i += 1
            S[j],S[i]=S[i],S[j]
    S[i+1],S[r]=S[r],S[i+1]
    for j in range(len(S)):
        if j == i+1: print "["+str(S[j])+"]",
        else: print S[j],

partition(S,0,len(S)-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
            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()))
m = partition(a, 0, n-1)
a = list(map(str, a))
a[m] = "[%s]"%(a[m])
print(" ".join(a))

Solution (Python):
"""Partition."""

def partition(A, p, r):
    """Divide list A into A[p:q-1] whose elements aren't greater than A[q] and
    A[q+1:r] whose elements are greater than A[q].

    Default value of p is 0.
    The number as a refernce of the division is A[r].
    
    Return the index q.
    """

    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 = int(input()) - 1

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

q = partition(A, 0, r)

print(*A[0:q], end = ' ')
print('[{0}]'.format(A[q]), end = ' ')
print(*A[q + 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())
numbers = list(map(int, input().split()))
x = partition(numbers, 0, n - 1)
numbers[x] = "[{}]".format(numbers[x])
print(*numbers)

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

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

a[i] = '[' + str(a[i]) + ']'
print(*a)

Solution (Python):
class Partition:
    def partion(self, a, p, r): 
        x = a[-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((a, i))

if __name__ == '__main__':
    n = int(input().rstrip())
    a = [int(x) for x in input().rstrip().split(" ")]
    x = Partition()
    a, i = x.partion(a, 0, n)
    res = []
    for j in range(len(a)):
        if j == i:
            res.append("[{}]".format(a[j]))
        else:
            res.append(str(a[j]))
    print(" ".join(res))

Solution (Python):
class Partition:
    def partion(self, 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().rstrip())
    a = [int(x) for x in input().rstrip().split(" ")]
    x = Partition()
    i = x.partion(a, 0, n-1)
    a = [str(i) for i in a]
    a[i] = "[{}]".format(a[i])
    print(" ".join(a))

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

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

def main():
    i = partition(A, 0, n-1)
    print ' '.join(map(str, A[:i])), '[{}]'.format(A[i]), ' '.join(map(str,A[i+1:]))
    return 0

main()

Solution (Python):
N = input()
A = map(int,raw_input().split())
temp = 0
q = 0
r = N-1

for i in range(N-1):
    if A[i] <= A[r] and q < i:
        A[q],A[i] = A[i],A[q]
        q += 1
    elif A[i] <= A[r]:
        q += 1


A[r],A[q] = A[q],A[r]
i = 0
for elem in A:
    if i == q:
        print("["+str(elem)+"]"),
    else:
        print(elem),
    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

input()
A = list(map(int, input().split()))
index = partition(A, 0, len(A) - 1)
for i in range(len(A)):
    if i == index:
        A[i] = '[{}]'.format(A[i])
    else:
        A[i] = str(A[i])
print(' '.join(A))

Solution (Python):
def partition(A,p,r):
    x=A[r]
    i=p-1
    for j in xrange(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=input()
A=map(int,raw_input().split())
base_i=partition(A,0,n-1)
base="["+str(A[base_i])+"]"
A[base_i]=base
A=map(str,A)
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
            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

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    A = map(int, lines[1].split())
    q = partition(A, 0, len(A) - 1)

    pre = ""
    suf = ""
    for i in range(len(A) - 1):
        if i == q:
            pre = "["
            suf = "]"
        print pre + str(A[i]) + suf,
        pre = ""
        suf = ""
    print A[i + 1]

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

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    A = map(int, lines[1].split())
    q = partition(A, 0, len(A) - 1)
    A = map(str, A)
    A[q] = "[" + A[q] + "]"
    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()))

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

print(*A[:q], end = ' ')
print('[{0}]'.format(A[q]), end = ' ')
print(*A[q + 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(raw_input())
A = map(int, raw_input().split())
q = partition(A, 0, n-1)
print " ".join(map(str, A[:q])) + " [%d] " %(A[q]) + " ".join(map(str, A[q+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
			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
    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

if __name__=='__main__':
    n=int(input())
    A = list(map(int,input().split()))
    ref = partition(A,0,n-1)
    print(*A[:ref],end='')
    print(' ['+str(A[ref])+'] ',end='')
    print(*A[ref+1:])

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


n = int(input())
a = list(map(int, input().split()))
idx = partition(0, n-1)
a[idx] = [a[idx]]
print(*a)

Solution (Python):
import sys

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
            tmp = A[j]
            A[j] = A[i]
            A[i] = tmp
    tmp = x
    A[r - 1] = A[i + 1]
    A[i + 1] = '[{}]'.format(tmp)

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

partition(A, 0, n)

print(*A)

Solution (Python):


def Partition(A,n):
    x=A[n-1]
    i=0
    ans=""
    for j in range(n-1):
        if A[j]<=x:
            swap=A[j]
            A[j]=A[i]
            A[i]=swap
            i+=1
    swap=A[n-1]
    A[n-1]=A[i]
    A[i]=swap
    for j in range(n):
        if j>0:
            ans+=" "
        if j==i:
            ans+="["+str(A[j])+"]"
        else:
            ans+=str(A[j])
    print(ans)
            
 
    
if __name__=="__main__":
    n=int(input())
    A=input().split(" ")
    for i in range(n):
        A[i]=int(A[i])
    Partition(A,n)

Solution (Python):



def partition(target_list):
    x = target_list[-1]
    i = -1

    for j in range(len(target_list))[:-1]:
        if target_list[j] <= x:
            i = i+1
            tmp = target_list[i]
            target_list[i] = target_list[j]
            target_list[j] = tmp
    tmp = target_list[-1]
    target_list[-1] = target_list[i + 1]
    target_list[i + 1] = tmp
    
    return  i + 1

def convert(l):
    return " ".join([str(n) for n in l])

if __name__ == "__main__":
    n_list = int(input())
    target_list = [int(n) for n in input().split()]

    center_index = partition(target_list)
    print(convert(target_list[:center_index]) + " ["+ str(target_list[center_index]) + "] " + convert(target_list[center_index + 1:]))

Solution (Python):




import sys


def partition(A, p, r):
    x = A[r]
    i = p - 1
    assert p <= 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 dict(array=A, cursor=i + 1)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    assert len(array) == array_length
    raw_result = partition(A=array, p=0, r=array_length - 1)
    array_result = raw_result['array']
    cursor = raw_result['cursor']
    array_result[cursor] = '[' + str(array_result[cursor]) + ']'
    print(*array_result)

Solution (Python):




import sys


def partition(A, p, r):
    x = A[r]
    i = p - 1
    assert p <= 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 dict(array=A, cursor=i + 1)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    assert len(array) == array_length
    raw_result = partition(A=array, p=0, r=array_length - 1)
    array_result, cursor = raw_result['array'], raw_result['cursor']
    array_result[cursor] = '[' + str(array_result[cursor]) + ']'
    print(*array_result)

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




if __name__ == '__main__':
    
    
    num_of_data = int(input())
    A = [int(x) for x in input().split(' ')]

    
    p = partition(A, 0, len(A))

    
    left = A[:p+1]
    partition = A[p+1]
    right = A[p+2:]
    print('{0} [{1}] {2}'.format(' '.join(map(str, left)), partition, ' '.join(map(str, right))))

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




if __name__ == '__main__':
    
    
    num_of_data = int(input())
    A = [int(x) for x in input().split(' ')]

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

    
    left = A[:p+1]
    partition = A[p+1]
    right = A[p+2:]
    print('{0} [{1}] {2}'.format(' '.join(map(str, left)), partition, ' '.join(map(str, right))))

Solution (Python):
def partition(A, p, r):
    """
    ???????????????????????????????????????A[r]?????°?????????????????????????????????????????????A[r-1]??¨?´??????????????????§??¨???
    """
    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__':
    
    
    num_of_data = int(input())
    A = [int(x) for x in input().split(' ')]

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

    
    left = A[:p]
    partition = A[p]
    right = A[p+1:]
    print('{0} [{1}] {2}'.format(' '.join(map(str, left)), partition, ' '.join(map(str, right))))