퀵 정렬 알고리즘 구현하기
이 연습에서는 퀵 정렬(Quicksort) 알고리즘을 구현해 숫자 리스트를 정렬해 보겠습니다.
첫 번째 단계에서는 partition() 함수를 구현합니다. 이 함수는 피벗을 기준으로 리스트를 재배치한 뒤, 피벗의 최종 인덱스를 반환합니다. 즉, 피벗의 왼쪽에는 피벗보다 작은 값들이, 오른쪽에는 피벗보다 큰 값들이 오도록 만듭니다.
두 번째 단계에서는 quicksort() 함수를 구현하며, 이 함수는 내부에서 partition() 함수를 호출합니다.
이 연습은 강의의 일부입니다
Python으로 배우는 자료구조와 알고리즘
실습형 인터랙티브 연습
이 예제를 이 샘플 코드를 완성하여 풀어보세요.
def partition(my_list, first_index, last_index):
pivot = my_list[first_index]
left_pointer = first_index + 1
right_pointer = last_index
while True:
# Iterate until the value pointed by left_pointer is greater than pivot or left_pointer is greater than last_index
while ____ < ____ and ____ < ____:
left_pointer += 1
while my_list[right_pointer] > pivot and right_pointer >= first_index:
right_pointer -= 1
if left_pointer >= right_pointer:
break
# Swap the values for the elements located at the left_pointer and right_pointer
my_list[left_pointer], my_list[right_pointer] = ____, ____
my_list[first_index], my_list[right_pointer] = my_list[right_pointer], my_list[first_index]
return right_pointer