Quick Sort in Python (퀵 정렬)

# 1구역: 피벗(기준 원소)보다 작은 영역
# 2구역: 피벗(기준 원소)보다 큰 영역
# 3구역: 아직 보지 않은 영역


def partition(lst, s, e):
	i = s-1  # 1구역의 끝
	# 2구역은 i+1 ~ j-1
	pivot = A[e]  # 기준원소

	for j in range(s, e-1):  # 3구역의 범위
		if A[j] <= pivot:
			i += 1
			A[i], A[j] = A[j], A[i]  # 1구역을 하나 늘리고, 3구역과 swap
	A[i+1], A[e] = A[e], A[i+1]  # pivot과 2구역 첫번째 원소를 swap
	return i+1  # 2구역의 첫번째 원소를 return (그냥 중앙에 넣어주는 것)


def quick(A, s, e):
	if s < e:
		q = partition(A, s, e)
		quick(A, s, q-1)
		quick(A, q+1, e)


A = [31, 8, 48, 73, 11, 3, 20, 29, 65, 15]
quick(A, 0, len(A)-1)
print(A)