리스트 안의 자료를 작은 수부터 큰 수 순서로 배열하는 정렬 알고리즘을 만들어 보세요.

 

앞서 병합 정렬로 줄 세우기는 학생들을 일단 두 그룹으로 나눠 각각 병합 정렬을 한 후, 정렬된 두 그룹에 있는 학생들의 키를 다시 비교하여 한 줄로 합치는(병합) 과정이었습니다.

이번에 배울 퀵 정렬(Quicksort)은 ‘그룹을 둘로 나눠 재귀 호출’하는 방식은 병합 정렬과 같지만, 그룹을 나눌 때 미리 기준과 비교해서 나눈다는 점이 다릅니다. 즉, 먼저 기준과 비교해서 그룹을 나눈 다음 각각 재귀 호출하여 합치는 방식입니다.