QuickSort.py

# 04-4 퀵정렬
# 기준 값(피봇)을 선정해 해당 데이터보다 작은 데이터와 큰 데이터로 분류하는 것을 반복하여 정렬한다.
# 기준 값에 따라서 시간 복잡도가 상이하다.
# 평균적으로 O(nlogn)이지만, 최악의 경우 O(n^2)이다.

# 과정) 피봇을 중심으로 데이터를 2개 집합으로 나누어 정렬해야 한다!
# 1) 데이터를 분할하는 피봇 설정
# 2) 피봇을 기준으로 다음 과정을 2개 집합으로 나눈다.
#   a) start가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start 인덱스를 오른쪽으로 1칸 이동
#   b) end가 가리키는 데이터가 pivot이 가리키는 데이터보다 크면 end 인덱스를 왼쪽으로 1칸 이동

#   c) start가 가리키는 데이터가 pivot보다 크고, end가 가리키는 데이터가 pivot보다 작으면,
#      start와 end가 가리키는 데이터를 서로 교환한다.(swap 연산)
#      이후 a, b 과정을 다시 수행한다.

#   d) start와 end가 가리키는 데이터가 서로 만날 때까지 a~c 과정을 반복한다.
#   e) 만나면, 그 데이터와 피봇이 가리키는 데이터를 비교한다.
#      피봇이 가리키는 데이터가 크면, 만난 지점의 오른쪽에 작으면 왼쪽에 피봇이 가리키는 데이터를 삽입한다.

# 3) 분리 집합에서 다시 pivot을 설정학고, 분리 집합이 1개 이하일 때까지 1~3 과정을 반복한다.


# ex. List = [42, 32, 24, 60, 15, 5, 90, 45], List[pivot] = 45, List[start] = 42, List[end] = 90
# step1. List[0] = 42 < 45 이고, List[7] = 90 > 45 이므로, start++, end-- 수행
# step2. List[1] = 32 < 45 이고, List[6] = 5 < 45 이므로, start++ 만 수행
# step3. List[2] = 24 < 45 이므로 start++ 만 수행
# step4. Listp[3] = 60 > 45이고, List[6] = 5 이므로 List[3] = 5, List[6] = 60
# step5. Listp[3] = 5 < 45이고, List[6] = 60 > 45 이므로 start++, end-- 수행
#        => List[4] = 15에서 만나므로, List[4] = 15와 List[pivot] = 45를 비교함
#        => 15 < 45이므로 List[5] = 45를 삽입
# step6. 정렬된 요소 List[5] = 45를 제외하고 pivot을 다시 설정
#        이때, List[5]를 기준으로 분리 집합이 2개로 나뉘는데 (왼쪽, 오른쪽 집합)
#        분리 집합이 1개 이하일 때까지 위 과정을 반복함