실행 결과
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
알아 보기
퀵 정렬 함수 quick_sort()는 재귀 호출 함수이므로 병합 정렬과 마찬가지로 첫 부분에 종료 조건이 명시되어 있습니다.
먼저 입력으로 주어진 리스트 a의 크기가 1 이하이면, 즉 자료가 한 개뿐이거나 아예 비어 있다면 정렬할 필요가 없으므로 입력 리스트를 그대로 돌려주면서 재귀 호출을 끝냅니다.
n = len(a)
if n <= 1:
return a
또한, 퀵 정렬에서는 그룹을 나누기 위한 기준 값( pivot)이 필요합니다. 프로그램 11-1에서는 편의상 주어진 리스트의 맨 마지막 값을 기준 값으로 사용하였습니다.
pivot = a[-1]
다음 문장은 g1을 퀵 정렬한 결과에 기준 값과 g2를 퀵 정렬한 결과를 이어 붙여 새로운 리스트를 만들어 돌려주는 문장입니다.
return quick_sort(g1) + [pivot] + quick_sort(g2)
TIP
두 개 이상의 리스트를 더하기로 연결하면 각 리스트 안의 자료를 순서대로 포함하는 새 리스트를 만들 수 있습니다. 다음 예제를 참고하세요.
>>> [1,2] + [3] + [4,5]
[1,2,3,4,5]