# 퀵 정렬
# 병합 정렬과 같지만, 그룹을 나눌 때 미리 기준과 비교해서 나눈점이 다름
# 먼저 기준과 비교해서 그룹을 나눈 다음 가각 재귀 호출하여 합치는 방식

# 퀵 정렬로 줄 세우기
# 열 명 중에 기준이 될 사람을 한 명 뽑는다.
# 기준으로 뽑은 태호를 줄 가운데 세운 다음 
# 태호 보다 키가 작은 학생은 태호 앞에, 큰 학생은 뒤에 서게 한다
# 기준인 태호는 가민히 있고, 태호보다 키가 작은 학생은 작은 학생끼리
# 큰 학생은 큰 학생들끼리 다시 키 순서대로 줄을 서면 끝난다.

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)

d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
print(quick_sort(d))

# 리스트 a의 크기가 1이하면 재귀 호출 종료
# 그룹을 나누기 위한 기준 값(pivot)이 필요하다.
# 편의상 리스트 맨 마지막 값을 기준 값으로 사용한다.
# 그룹 1에 퀵 정렬한 결과에 기준 값과 그룹 2를 이어 붙여 새로운 리스트 생성

# 편의상 맨 마지막값을 기준 값으로 정한다
# [6 8 3 9 10 1 2 4 7 5]의 기준 값: 5

# 기준 값보다 작은 값을 저장할 g1, 큰 값을 저장할 g2 생성

# 리스트 자료들을 기준 값 5와 비교 
# 5보다 작은 값은 g1, 5보다 큰 값은 g2에 넣는다.
# 기준 값: 5
# g1: [3 1 2 4]
# g2: [6 8 9 10 7]

# 재귀 호출을 이용하여 g1, g2 정렬

# g1 + 기준값 + g2 순서대로 이어 붙인다
# [1 2 3 4] + [5] + [6 7 8 9 10] → [1 2 3 4 5 6 7 8 9 10]