# 쉽게 설명한 퀵 정렬
# 입력: 리스트 a
# 출력: 정렬된 새 리스트
def quick_sort(a):
n = len(a)
# 종료 조건: 정렬할 리스트의 자료 개수가 한 개 이하이면 정렬할 필요가 없음
if n <= 1:
return a
# 기준 값을 정하고 기준에 맞춰 그룹을 나누는 과정
pivot = a[-1] # 리스트의 마지막 값을 기준 값으로 정함
g1 = [] # 그룹1: 기준 값보다 작은 값을 담을 리스트
g2 = [] # 그룹2: 기준 값보다 큰 값을 담을 리스트
for i in range(0, n - 1): # 마지막 값은 기준 값이므로 제외
if a[i] < pivot: # 기준 값과 비교
g1.append(a[i]) # 작으면 g1에 추가
else:
g2.append(a[i]) # 크면 g2에 추가
# 각 그룹에 대해 재귀 호출로 퀵 정렬을 한 후
# 기준 값과 합쳐 하나의 리스트로 결과값 반환
return quick_sort(g1) + [pivot] + quick_sort(g2)
l = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
print(quick_sort(l))
