def insertion_sort(A, r = False):
	for i in range(1,len(A)):
		k = A[i]
		j = i - 1
		while j>=0 and ( (A[j] > k and r) or (A[j] < k and not r ) ):
			A[j + 1] = A[j]
			j = j - 1
		A[j + 1] = k
	return A
	
def bubble_sort(A, r = False):
	for i in range(len(A)):
		print(A)
		for j in range(len(A) - i - 1):
			if A[j] > A[j+1]:
				t = A[j]
				A[j] = A[j+1]
				A[j+1] = t
	return A
	
	
def quick_sort(A, p, r):
	def partition(p, r):
		x = A[p]
		while True:
			while A[p] < x:
				p = p + 1
			while A[r] > x:
				r = r - 1
			if p < r:
				t = A[r]
				A[r] = A[p]
				A[p] = t
				p = p + 1
				r = r - 1
			else:
				return r
	if p < r:
		q = partition(p, r)
		quick_sort(A, p, q)
		quick_sort(A, q+1, r)
		
A = [4,2,1,6,7]
quick_sort(A, 0, len(A) - 1)
print(A)
#print(insertion_sort(A, False))

#print(bubble_sort(A))