퀵 정렬시 재귀함수 동작방식 질문

[dgnee]

퀵 정렬 예시 6-4.py (168p) 중 아래의 quicksort(array, right+1, end)는 언제 불리는 건가요? 계속 바로 윗줄만 반복해서 불리는 거 아닌가요? 재귀함수의 동작방식이 이해가 잘 가지 않습니다..ㅠㅠ 도움 부탁드려요

quicksort(array, start, right - 1) quicksort(array, right + 1, end)

[ghost]

https://github.com/ndb796/python-for-coding-test/blob/master/6/4.py 여기 예시로 설명 드리겠습니다.

[1] quick_sort([5, 7, 9, 0, 3, 1, 6, 2, 4, 8], 0, 9) 함수 호출 array 변화 과정 array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8] # 초기 값 array = [5, 4, 9, 0, 3, 1, 6, 2, 7, 8] # 11-15번째 줄에 의해 left = 1, right = 8이고 / left <= right이므로 left<->right 위치 변경 array = [5, 4, 2, 0, 3, 1, 6, 9, 7, 8] # 11-15번째 줄에 의해 left = 2, right = 7이고 / left <= right이므로 left<->right 위치 변경 array = [1, 7, 9, 0, 3, 5, 6, 2, 4, 8] # 11-15번째 줄에 의해 left = 6, right = 5이고 / left > right이므로 right <-> pivot 위치 변경 left > right 이므로 9번째 줄의while문을 빠져 나오게 됩니다.

start 는 항상 0이고, right와 left의 값은 while문이 종료되었을 때의 값인 right = 5, left = 6입니다. 인덱스 5의 값 기준 array[5] 기준으로 왼쪽은 array5미만의 수 / 오른쪽은 array5 초과의 수가 있게 되는 것을 알 수 있죠..? 이제 재귀 함수를 호출하여 범위를 줄여나갑니다. 인덱스 0이상 4이하 기준으로 재귀함수 호출 인덱스 6이상 9이하 기준으로 재귀함수 호출

[2] 위에서 얘기 했듯이 재귀 함수를 호출합니다.. 21번째 줄에서 quick_sort([1, 7, 9, 0, 3, 5, 6, 2, 4, 8], 0, 4)를 호출
22번째 줄에서 quick_sort([1, 7, 9, 0, 3, 5, 6, 2, 4, 8], 6, 9)를 호출