1. 학습
    2. /
  2. 강의
    3. /
  3. Python으로 배우는 자료구조와 알고리즘
Connected

연습 문제

퀵 정렬 알고리즘 구현하기

이 연습에서는 퀵 정렬(Quicksort) 알고리즘을 구현해 숫자 리스트를 정렬해 보겠습니다.

첫 번째 단계에서는 partition() 함수를 구현합니다. 이 함수는 피벗을 기준으로 리스트를 재배치한 뒤, 피벗의 최종 인덱스를 반환합니다. 즉, 피벗의 왼쪽에는 피벗보다 작은 값들이, 오른쪽에는 피벗보다 큰 값들이 오도록 만듭니다.

두 번째 단계에서는 quicksort() 함수를 구현하며, 이 함수는 내부에서 partition() 함수를 호출합니다.

지침 1/2

undefined XP
    1
    2
  • left_pointer가 가리키는 값이 pivot보다 크거나 left_pointer가 last_index보다 커질 때까지 반복하세요.
  • left_pointer와 right_pointer 위치의 요소 값을 서로 교환하세요.